مسئله طولانی‌ترین مسیر

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

مساله طولانی‌ترین مسیر (به انگلیسی: longest path problem) در تئوری گراف، مساله یافتن یک مسیر ساده با با حداکثر طول در یک گراف خاص است.

مقدمه[ویرایش]

یک مسیر زمانی ساده نامیده می‌شود که دارای رئوس تکراری نباشد. بر خلاف مساله کوتاه ترین مسیر که کوتاهترین مسیر بین دو راس را به ما می‌دهد و در زمان چند جمله‌ای حل می‌شود، برای مساله یافتن طولانی ترین مسیر زمان چند جمله‌ای وجود ندارد و جزء مسائل ان‌پی کامل(NP-complete)است. و به این معنی است که در زمان چند جمله‌ای نمی توان برای آن جواب پیدا کرد مگر اینکه P=NP باشد.

NP-completeness[ویرایش]

واضح است که اگر یک مسیر عمومی معین دارای مسیر Hamiltonian باشد، این مسیر Hamiltonian، بلندترین مسیر احتمالی است، زیرا همه رئوس احتمالی را طی می‌کند. برای حل مساله Hamiltonian از یک الگوریتم طولانی ترین مسیر استفاده می‌کنیم، از این الگوریتم برای حل بلندترین مسیر در یک گراف با ورودی‌های یکسان و مجموئه k=|V|-۱ استفاده می‌کنیم که |V| تعداد رئوس در گراف است.

اگر یک مسیر Hamiltonian در گراف وجود داشته باشد پس الگوریتم yes را برمی گرداند، زیرا مسیر Hamiltonian دارای طول معادل با1-|V| است. بر عکس اگر الگوریتم دارای خروجی yes باشد، یک مسیر ساده با طول 1-|V| در گراف وجود دارد. و چون طول آن |V|-1 است می‌توان نتیجه گرفت که از همه رئوس گراف بدون تکرارگذشته‌است که همان مسیر Hamiltonian است. چون مساله مسیر Hamiltonian یک مساله ان پی کامل NP-complete است، این ساده سازی اثبات می‌کند که ان‌پی سخت (NP-hard) نیز است. برای اینکه تشان دهیم NP-complete است باید نشان دهیم NP است.

ارتباط با مسئله یافتن کوتاهترین مسیر[ویرایش]

مساله یافتن طولانی ترین مسیر را می توان به مسئله یافتن کوتاهترین مسیر کاهش (reduction) داد.(گرچه ممکن است این گراف دارای دور با وزن منفی باشد) اگر گراف ورودی برای مساله بلندترین مسیر G باشد، کوتاهترین مسیر ساده بر روی گراف Hamiltonian خواهد بود که دقیقاً مشابه G است، اما وزن‌های لبه منفی می‌شود، و بلندترین مسیر بر روی G است. هر چند هر یک از دورها با وزن مثبت در گراف اصلی G منتهی به دورهایی با وزن منفی در گراف Hamiltonian خواهد شد. بنابراین یافتن کوتاه ترین مسیر ساده بر روی یک گراف با دورهایی با وزن منفی، نیز ان پی کاملاست. اگر G حاوی هیچ دوری نباشد، پس Hamiltonian هیچ دوری با وزن منفی نخواهد داشت و هر یک از الگوریتم‌های یافتن کوتاه ترین مسیر اکنون می‌تواند بر روی Hamiltonian اجرا شوند تا مساله اصلی در زمان چند جمله‌ای حل شود. بنابراین مساله بلندترین مسیر بر روی گراف‌های بدون دور ساده‌است.

الگوریتم برای گراف‌های بدون دور[ویرایش]

همانطور که در بالا اشاره شد، مساله یافتن طولانی ترین مسیر بر روی گراف‌های بدون دور را می توان در زمان چند جمله‌ای و از طریق منفی کردن وزن یال‌ها و اجرای یک الگوریتم یافتن کوتاه ترین مسیر حل کرد.

راه حل برنامه نویسی پویا برای گراف‌های بدون دور[ویرایش]

همانطور که در بالا گفته شد طولانی ترین مسیر در گراف‌های بدون دور از طریق معکوس کردن وزن یال‌ها و اجرای الگوریتم‌های پیدا کردن کوتاه ترین مسیر در زمان چند جمله‌ای حل کرد. الگوریتمی که در ادامه امده از روش تبدیل قبلی استفاده نمی‌کند و پیچیدگی زمانی بهتری هم دارد.

گراف‌های وزن دار جهتدار بی دور[ویرایش]

اگر G گراف جهت‌دار غیرمدور باشد، مسئلهٔ یافتن بلندترین مسیر را می توان در زمان خطی با استفاده از روشبرنامه نویسی پویا حل کرد. فرض کنید که (toporder(g دارای خروجی یک رشته از راس‌ها در به صورت توپولوژیکی (که می‌تواند به وسیله یمرتب سازی توپولوژیکی انجام شود و این مرحله باید گراف جهتدار بدون دور باشد) باشد. بعلاوه، (V(G مجموعه راس‌های گراف و (E(G مجموعه یال‌های گراف باشد، اگر گراف وزن دار بود وزن خود یال را به کار می‌بریم در غیر این صورت به هر یال یک وزن دلخواه به جز صفر اختصاص می‌دهیم. سپس الگوریتم زیر طول بلند ترین مسیر را پیدا می‌کند.

افزودن عنوان در اینجا

algorithm dag-longest-path is

   input:
        Directed acyclic graph G
   output:
        Length of the longest path
length_to = array with |V(G)| elements of type int with default value 0
 for each vertex v in topOrder(G) do
       for each edge (v, w) in E(G) do
           if length_to[w] <= length_to[v] + weight(G,(v,w)) then
               length_to[w] = length_to[v] + weight(G, (v,w))
   return max(length_to[v] for v in V(G))

مسئله‌های مشابه[ویرایش]

مسئلهٔ فروشندهٔ مسافر

مطالعهٔ بیشتر[ویرایش]

سورس الگوریتم

NP-completenes

منابع[ویرایش]

  • مشارکت‌کنندگان ویکی‌پدیا، «Longest path problem»، ویکی‌پدیای انگلیسی، دانشنامهٔ آزاد (بازیابی در ۱۴ ژوئیه ۲۰۱۲).