مسئله یافتن کوتاهترین مسیر

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

در نظریه گراف‌ها مسالهٔ یافتن کوتاه‌ترین مسیر در واقع مسالهٔ یافتن مسیری بین دو رأس (یا گره) است به گونه‌ای که مجموع وزن یال‌های تشکیل دهندهٔ آن کمینه شود. برای مثال می‌توان مسألهٔ یافتن سریع‌ترین راه برای رفتن از یک مکان به مکان دیگر روی نقشه را، در نظر گرفت؛ در این حالت رأس‌ها نشان دهندهٔ مکان‌ها و یال‌ها نشان دهندهٔ بخش‌های مسیر هستند که برحسب زمانِ لازم برای طی کردن آن‌ها وزن گذاری شده‌اند.

اگر یک گراف وزن دار (که شامل مجموعهٔ V از رئوس، مجموعهٔ E از یال‌ها و تابع وزن f : E → R است) و یک عنصر مانند v از مجموعهٔ V داشته باشیم، هدف ما یافتن مسیری مانند P از v به 'v است به گونه‌ای که:

\sum_{p\in P} f(p)

کوتاه‌ترین مسیر بین تمام مسیرهای موجود از v به 'v باشد.

این مسأله گاهی تحت عنوان مسالهٔ یافتن کوتاهترین مسیر بین دو راس نام گذاری می‌شود تا از سایر حالت‌های کلی که به شرح زیر هستند، متمایز شود:

  • مسالهٔ یافتن کوتاه‌ترین مسیر از مبدا واحد که در آن هدف یافتن کوتاه‌ترین مسیر از رأس مبدا v تا تمامی رئوس دیگر در گراف است.
  • مسالهٔ یافتن کوتاه‌ترین مسیر به مقصد واحد که در آن هدف یافتن کوتاه‌ترین مسیر از تمامی رئوس گراف تا رأس مقصد v است.
  • مسالهٔ یافتن کوتاه‌ترین مسیر بین هر دو رأس که در آن هدف یافتن کوتاه‌ترین مسیر بین هر جفت رأسِ v و 'v در گراف است.

این حالت‌های عمومی به صورت معناداری از الگوریتم‌های کارآمدتری نسبت به مسألهٔ مورد نظر ما برخوردارند.

الگوریتم‌ها[ویرایش]

مهم‌ترین الگوریتم‌ها برای حل این مسأله عبارتند از:

کاربردها[ویرایش]

مسألهٔ یافتن کوتاه‌ترین مسیر برای یافتن مسیرهای میان مکان‌های واقعی از قبیل راه‌های عبور و مرور در نقشه‌های اینترنتی مانند گوگل نقشه‌ها استفاده می‌شود.

اگر یک ماشین مجازی غیرواقعی را به صورت گرافی در نظر بگیریم که در آن رأس‌ها بیان کنندهٔ حالت‌ها و یال‌ها بیان کنندهٔ گذار از حالتی به حالتی دیگر باشند، می‌توان از الگوریتم یافتن کوتاه‌ترین مسیر به عنوان ابزاری برای یافتن دنباله‌ای بهینه از انتخاب‌ها به منظور رسیدن به یک حالت ویژه استفاده کرد. هم چنین می‌توان این الگوریتم را به منظور دست یابی به یک کران پایین از زمان مورد نیاز برای رسیدن به یک حالت مشخص به کار برد. برای مثال اگر رأس‌ها بیانگر حالت‌های یک پازل مانند مکعب رابیک و هر یک از یال‌های جهت دار بیانگر یک حرکت یا چرخش باشند، می‌توان از الگوریتم‌های کوتاه‌ترین مسیر بهره برد به گونه‌ای که این الگوریتم‌ها به راه حلی با کمترین تعداد حرکت منجر شوند.

گاهی در ساختار شبکه‌های ارتباطی یا شبکه‌های مخابراتی از این مساله با عنوان مساله یافتن کم تاخیرترین مسیر یاد می‌کنند که اغلب ارتباط تنگاتنگی با مساله یافتن عریض‌ترین مسیر دارد.

این مساله در رباتیک، حمل و نقل و طراحی مدارهای VLSI نیز کاربرد دارد.

مسائل مرتبط[ویرایش]

برای مشاهدهٔ مسالهٔ یافتن کوتاه‌ترین مسیر در هندسه محاسباتی به کوتاه‌ترین مسیر اقلیدسی مراجعه نمایید.

مسئله فروشنده دوره گرد برای یافتن کوتاه‌ترین مسیری است که از هر یک از رئوس دقیقاً یک بار بگذرد و به مبدأ بازگردد. برخلاف مسألهٔی یافتن کوتاه‌ترین مسیر که برای گراف‌های فاقد دور منفی در زمان چند جمله‌ای قابل است، این مسأله از دسته مسائل ان پی-کامل است. مسألهٔ یافتن طولانی‌ترین مسیر در یک گراف نیز از جمله مسائل ان پی-کامل است.

مسئله مسافر کانادایی و مسألهٔ یافتن کوتاه‌ترین مسیر اتفاقی حالت‌های عمومی هستند که در آن‌ها یا گراف به طور کامل برای مسافر مشخص نیست یا گراف با زمان تغییر می‌کند و یا پیمایش‌ها احتمالی هستند.

اگر در گراف تغییر شکلی (از قبیل کاهش تعداد گره‌ها) رخ دهد، نیازمند محاسبهٔ مجدد کوتاه‌ترین مسیر خواهیم بود.

جستارهای وابسته[ویرایش]

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