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

چکیده

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

1-مقدمه

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