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

مسئله طولانی‌ترین مسیر (به انگلیسی: 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»، ویکی‌پدیای انگلیسی، دانشنامهٔ آزاد (بازیابی در ۱۴ ژوئیه ۲۰۱۲).