الگوریتم تقریبی برای پیدا کردن کوتاه ترین مسیر با محدودیت راسی در گراف های بزرگ

جستجوی کوتاه ترین مسیر یکی از مسائل مهم در نظریه گراف است که به خوبی مورد توجه و مطالعه قرار گرفته است. این مقاله، حالت خاصی از مسئله کوتاه ترین مسیر است، پیدا کردن کوتاه ترین مسیر با محدودیت راسی که توسط کاربر تعیین شده اند را مورد مطالعه قرار می دهد، که این مسئله، یک مسئله NP- سخت است. برای حل کوتاه ترین مسیر الگوریتم های زیادی موجود هستند که اکثر آ نها تمام جایگشت های رئوس داده را محاسبه می کنند سپس کوتاه ترین آ نها را از میان این جایگشت ها می یابند. زمانی که اندازه گراف یا مجموعه رئوس داده شده بزرگ باشند، هزینه انجام محاسبات به شدت زیاد خواهد بود. در این مقاله ابتدا یک الگوریتم ابتکاری برای جستجوی بهترین- اولین را مطرح شده و سپس یک الگوریتم تقریبی ابتکاری در زمان چند جمله ای برای این مسئله روی گراف های بزرگ ارائه شده است. نتایج تجربی معتبری وجود دارند که نشان می دهند حتی اگر اندازه گراف یا مجموعه رئوس بزرگ باشند الگوریتم های ارائه شده، از روش های موجود بهتر هستند.

Keywords:

کوتاه ترین مسیر , الگوریتم تقریبی , پیچیدگی محاسباتی