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

چکیده مقاله

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

کلیدواژه‌ها

نویسندگان

محمدرضا قائمی

دانشگاه زنجان، دانشکده علوم، گروه ریاضی

نوید تقی پور

دانشگاه زنجان، دانشکده علوم، گروه ریاضی

قائمی، محمدرضا و تقی پور، نوید،1398،الگوریتم تقریبی برای پیدا کردن کوتاه ترین مسیر با محدودیت راسی در گراف های بزرگ،هفتمین کنفرانس ملی علوم و مهندسی کامپیوتر و فناوری اطلاعات،بابل

ارائه‌شده در

مجموعه مقالات هفتمین کنفرانس ملی علوم و مهندسی کامپیوتر و فناوری اطلاعات3 مرداد 1398 · بابل