موضوع مقاله: مسئله یافتن کوتاه‌ترین مسیر | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # مسئله یافتن کوتاه‌ترین مسیر | مقدمه: برای مثال می‌توان مسئلهٔ یافتن سریع‌ترین راه برای رفتن از یک مکان به مکان دیگر روی نقشه را، در نظر گرفت؛ در این حالت رأس‌ها نشان دهندهٔ مکان‌ها و یال‌ها نشان دهندهٔ بخش‌های مسیر هستند که برحسب زمانِ لازم برای طی کردن آن‌ها وزن گذاری شده‌اند. | ## بخش 1: مسئله یافتن کوتاه‌ترین مسیر | اگر یک گراف وزن دار (که شامل مجموعهٔ V از رئوس، مجموعهٔ E از یال‌ها و تابع وزن f: E → R است) و یک عنصر مانند v از مجموعهٔ V داشته باشیم، هدف ما یافتن مسیری مانند P از v به 'v است به گونه‌ای که: کوتاه‌ترین مسیر بین تمام مسیرهای موجود از v به 'v باشد. این مسئله گاهی تحت عنوان مسئلهٔ یافتن کوتاهترین مسیر بین دو راس نام گذاری می‌شود تا از سایر حالت‌های کلی که به شرح زیر هستند، متمایز شود: مسئلهٔ یافتن کوتاه‌ترین مسیر از مبدأ واحد که در آن هدف یافتن کوتاه‌ترین مسیر از رأس مبدأ v تا تمامی رئوس دیگر در گراف است. مسئلهٔ یافتن کوتاه‌ترین مسیر به مقصد واحد که در آن هدف یافتن کوتاه‌ترین مسیر از تمامی رئوس گراف تا رأس مقصد v است. مسئلهٔ یافتن کوتاه‌ترین مسیر بین هر دو رأس که در آن هدف یافتن کوتاه‌ترین مسیر بین هر جفت رأسِ v و 'v در گراف است. این حالت‌های عمومی به صورت معناداری از الگوریتم‌های کارآمدتری نسبت به مسئلهٔ مورد نظر ما برخوردارند. الگوریتم‌ها مهم‌ترین الگوریتم‌ها برای حل این مسئله عبارتند از: الگوریتم دیکسترا: مسئلهٔ یافتن کوتاه‌ترین مسیر بین دو رأس، از مبدأ واحد و به مقصد واحد را حل می‌کند. | ## بخش 2: مسئله یافتن کوتاه‌ترین مسیر | الگوریتم بلمن-فورد: مسئلهٔ یافتن کوتاه‌ترین مسیر از مبدأ واحد را در حالتی حل می‌کند که وزن یال‌ها منفی نیز می‌تواند باشد. الگوریتم جستجوی آ*: با کمک روش‌های ابتکاریِ جستجو، مسئلهٔ یافتن کوتاه‌ترین مسیر بین دو رأس را تسریع می‌بخشد. الگوریتم جانسون: که مسئلهٔ یافتن کوتاه‌ترین مسیر بین هر دو رأس را حل می‌کند و در گراف‌های پراکنده ممکن است سریع تر از فلوید-وارشال عمل کند. کاربردها مسئلهٔ یافتن کوتاه‌ترین مسیر برای یافتن مسیرهای میان مکان‌های واقعی از قبیل راه‌های عبور و مرور در نقشه‌های اینترنتی مانند نقشه گوگل استفاده می‌شود. اگر یک ماشین مجازی غیرواقعی را به صورت گرافی در نظر بگیریم که در آن رأس‌ها بیان کنندهٔ حالت‌ها و یال‌ها بیان کنندهٔ گذار از حالتی به حالتی دیگر باشند، می‌توان از الگوریتم یافتن کوتاه‌ترین مسیر به عنوان ابزاری برای یافتن دنباله‌ای بهینه از انتخاب‌ها به منظور رسیدن به یک حالت ویژه استفاده کرد. هم چنین می‌توان این الگوریتم را به منظور دست یابی به یک کران پایین از زمان مورد نیاز برای رسیدن به یک حالت مشخص به کار برد. | ## بخش 3: مسئله یافتن کوتاه‌ترین مسیر | برای مثال اگر رأس‌ها بیانگر حالت‌های یک پازل مانند مکعب رابیک و هر یک از یال‌های جهت دار بیانگر یک حرکت یا چرخش باشند، می‌توان از الگوریتم‌های کوتاه‌ترین مسیر بهره برد به گونه‌ای که این الگوریتم‌ها به راه حلی با کمترین تعداد حرکت منجر شوند. گاهی در ساختار شبکه‌های ارتباطی یا شبکه‌های مخابراتی از این مسئله با عنوان مسئله یافتن کم تاخیرترین مسیر یاد می‌کنند که اغلب ارتباط تنگاتنگی با مسئله یافتن عریض‌ترین مسیر دارد. مسائل مرتبط برای مشاهدهٔ مسئلهٔ یافتن کوتاه‌ترین مسیر در هندسه محاسباتی به کوتاه‌ترین مسیر اقلیدسی مراجعه نمایید. مسئله فروشنده دوره‌گرد برای یافتن کوتاه‌ترین مسیری است که از هر یک از رئوس دقیقاً یک بار بگذرد و به مبدأ بازگردد. برخلاف مسئلهٔی یافتن کوتاه‌ترین مسیر که برای گراف‌های فاقد دور منفی در زمان چند جمله‌ای قابل است، این مسئله از دسته مسائل ان پی-کامل است. مسئله مسافر کانادایی و مسئلهٔ یافتن کوتاه‌ترین مسیر اتفاقی حالت‌های عمومی هستند که در آن‌ها یا گراف به‌طور کامل برای مسافر مشخص نیست یا گراف با زمان تغییر می‌کند یا پیمایش‌ها احتمالی هستند. | ## جمع‌بندی | اگر در گراف تغییر شکلی (از قبیل کاهش تعداد گره‌ها) رخ دهد، نیازمند محاسبهٔ مجدد کوتاه‌ترین مسیر خواهیم بود.