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

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

Keywords:

الگوریم کرم شبتاب , الگوریتم فروشنده ی دوره گرد , جهش حریصانه , NP-hard