مسئله یافتن کوتاهترین مسیر
در نظریه گرافها مسئلهٔ یافتن کوتاهترین مسیر در واقع مسئلهٔ یافتن مسیری بین دو رأس (یا گره) است به گونه‌ای که مجموع وزن یال‌های تشکیل دهندهٔ آن کمینه شود. برای مثال می‌توان مسئلهٔ یافتن سریع‌ترین راه برای رفتن از یک مکان به مکان دیگر روی نقشه را، در نظر گرفت؛ در این حالت رأس‌ها نشان دهندهٔ مکان‌ها و یال‌ها نشان دهندهٔ بخش‌های مسیر هستند که برحسب زمانِ لازم برای طی کردن آن‌ها وزن گذاری شده‌اند.
اگر یک گراف وزن دار (که شامل مجموعهٔ V از رئوس، مجموعهٔ E از یال‌ها و تابع وزن f : E → R است) و یک عنصر مانند v از مجموعهٔ V داشته باشیم، هدف ما یافتن مسیری مانند P از v به 'v است به گونه‌ای که:
کوتاهترین مسیر بین تمام مسیرهای موجود از v به 'v باشد.
این مسئله گاهی تحت عنوان مسئلهٔ یافتن کوتاهترین مسیر بین دو راس نام گذاری می‌شود تا از سایر حالت‌های کلی که به شرح زیر هستند، متمایز شود:
- مسئلهٔ یافتن کوتاهترین مسیر از مبدا واحد که در آن هدف یافتن کوتاهترین مسیر از رأس مبدا v تا تمامی رئوس دیگر در گراف است.
- مسئلهٔ یافتن کوتاهترین مسیر به مقصد واحد که در آن هدف یافتن کوتاهترین مسیر از تمامی رئوس گراف تا رأس مقصد v است.
- مسئلهٔ یافتن کوتاهترین مسیر بین هر دو رأس که در آن هدف یافتن کوتاهترین مسیر بین هر جفت رأسِ v و 'v در گراف است.
این حالت‌های عمومی به صورت معناداری از الگوریتم‌های کارآمدتری نسبت به مسئلهٔ مورد نظر ما برخوردارند.
الگوریتم‌ها
مهم‌ترین الگوریتم‌ها برای حل این مسئله عبارتند از:
- الگوریتم دیکسترا: مسئلهٔ یافتن کوتاهترین مسیر بین دو رأس، از مبدأ واحد و به مقصد واحد را حل می‌کند.
- الگوریتم بلمن-فورد: مسئلهٔ یافتن کوتاهترین مسیر از مبدأ واحد را در حالتی حل می‌کند که وزن یال‌ها منفی نیز می‌تواند باشد.
- الگوریتم جستجوی آ*: با کمک روش‌های ابتکاریِ جستجو، مسئلهٔ یافتن کوتاهترین مسیر بین دو رأس را تسریع می‌بخشد.
- الگوریتم فلوید-وارشال: مسئلهٔ یافتن کوتاهترین مسیر بین هر دو رأس را حل می‌کند.
- الگوریتم جانسون: که مسئلهٔ یافتن کوتاهترین مسیر بین هر دو رأس را حل می‌کند و در گراف‌های پراکنده ممکن است سریع تر از فلوید-وارشال عمل کند.
- نظریهٔ بی نظمی‌ها: (در بدترین حالت) کوتاهترین مسیر محلی را می‌یابد.
کاربردها
مسئلهٔ یافتن کوتاهترین مسیر برای یافتن مسیرهای میان مکان‌های واقعی از قبیل راه‌های عبور و مرور در نقشه‌های اینترنتی مانند نقشه گوگل استفاده می‌شود.
اگر یک ماشین مجازی غیرواقعی را به صورت گرافی در نظر بگیریم که در آن رأس‌ها بیان کنندهٔ حالت‌ها و یال‌ها بیان کنندهٔ گذار از حالتی به حالتی دیگر باشند، می‌توان از الگوریتم یافتن کوتاهترین مسیر به عنوان ابزاری برای یافتن دنباله‌ای بهینه از انتخاب‌ها به منظور رسیدن به یک حالت ویژه استفاده کرد. هم چنین می‌توان این الگوریتم را به منظور دست یابی به یک کران پایین از زمان مورد نیاز برای رسیدن به یک حالت مشخص به کار برد. برای مثال اگر رأس‌ها بیانگر حالت‌های یک پازل مانند مکعب رابیک و هر یک از یال‌های جهت دار بیانگر یک حرکت یا چرخش باشند، می‌توان از الگوریتم‌های کوتاهترین مسیر بهره برد به گونه‌ای که این الگوریتم‌ها به راه حلی با کمترین تعداد حرکت منجر شوند.
گاهی در ساختار شبکه‌های ارتباطی یا شبکه‌های مخابراتی از این مسئله با عنوان مسئله یافتن کم تاخیرترین مسیر یاد می‌کنند که اغلب ارتباط تنگاتنگی با مسئله یافتن عریض‌ترین مسیر دارد.
این مسئله در رباتیک، حمل و نقل و طراحی مدارهای VLSI نیز کاربرد دارد.
مسائل مرتبط
برای مشاهدهٔ مسئلهٔ یافتن کوتاهترین مسیر در هندسه محاسباتی به کوتاهترین مسیر اقلیدسی مراجعه نمایید.
مسئله فروشنده دوره گرد برای یافتن کوتاهترین مسیری است که از هر یک از رئوس دقیقاً یک بار بگذرد و به مبدأ بازگردد. برخلاف مسئلهٔی یافتن کوتاهترین مسیر که برای گراف‌های فاقد دور منفی در زمان چند جمله‌ای قابل است، این مسئله از دسته مسائل ان پی-کامل است. مسئلهٔ یافتن طولانی‌ترین مسیر در یک گراف نیز از جمله مسائل ان پی-کامل است.
مسئله مسافر کانادایی و مسئلهٔ یافتن کوتاهترین مسیر اتفاقی حالت‌های عمومی هستند که در آن‌ها یا گراف به‌طور کامل برای مسافر مشخص نیست یا گراف با زمان تغییر می‌کند یا پیمایش‌ها احتمالی هستند.
اگر در گراف تغییر شکلی (از قبیل کاهش تعداد گره‌ها) رخ دهد، نیازمند محاسبهٔ مجدد کوتاهترین مسیر خواهیم بود.
جستارهای وابسته
منابع
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, ۲۰۰۱. ISBN 0-262-03293-7.
- ویکی‌پدیای انگلیسی