تجزیه و تحلیل فضای برازندگی جواب های مسئله طولانی ترین مسیر ساده در گرافها

مسئل طولانیترین مسیر روی گراف ها یکی از مهمترین مسائل در تئوری گراف بوده و عبارت است از یافتن مسیری ساده با بیشترین تعداد رئوس بین دو راس معین یا ماکزیمم مجموع طو ل های یال ها بین بین دو راس معین در گراف. این مسئله کاربردهای مختلفی در حوزه ای گوناگون دارد، که از مهمترین آنها می توان به یافتن مسیر بحرانی در سیستم VLSI و بدست آوردن طولانیترین مسیر در شبکه صف اشاره کرد. از آنجایی که تعداد بسیار معدودی الگوریتم حل در زمان چند جمله ای برای کلاس ها (انواع) خاصی از گراف ها برای این مسئله توسعه داده شده است، در مقاله حاضربرای نخستین بار، تجزیه و تحلیل فضای برازندگی جواب های مسئله بر اساس شاخصهای آماری مستخرج از اجرای ١٠٠٠ مرتبه جستجوی محلی ساده انجام شده که در نتیجه آن تخمین زده شد بهینه های محلی این مسئله در چندین نقطه فضا تجمع یافته اند و لذا روشهای حل مبتنی بر جمعیت به جواب های بهتری برای مسئله مذکور در گرافهای مختلف دست خواهند یافت. این فرضیه با حل چند مسئله طولانیترین مسیر توسط الگوریتم های فراابتکاری مبتنی بر تک جواب (شبیه سازی تبرید) و مبتنی بر چند جواب (الگوریتم ژنتیک) مورد آزمون قرار گرفت، و با توجه به برتری جواب هایتولیدی الگوریتم ژنتیک، مورد پذیرش قرار گرفت. نتایج این تحلیل نشان میدهد که میانگین اختلاف نتایج الگوریتم ژنتیک پیشنهادی برای یک مسئله بهینه، ٠٫٠٢۴٣۶٣ است.کلمات کلیدی:مسئله طولانیترین مسیر؛

Keywords:

مسئله طولانی ترین مسیر , مسیر همیلتونی , الگوریتم فراابتکاری , تجزیه و تحلیل فضای برازندگی جواب