مسئله فروشنده دوره‌گرد (TSP) مسئله‌ای معروف است که ابتدا در سده ۱۸ مسائل مربوط به آن توسط ویلیام همیلتون و توماس کرکمن مطرح شد، در نهایت در دهه ۱۹۳۰ شکل عمومی آن به وسیله ریاضیدان مانند منگر از آکادمیک هاروارد و هاسر از آکادمی پرینستون مورد مطالعه قرار گرفت. جهت جزئیات بیشتر و دانلود سورس کد الگوریتم فروشنده دوره گرد به ادامه مطلب مراجعه نمایید. 

توضیحات کلی در مورد الگوریتم :

شرح مسئله بدین صورت می باشد: تعدادی شهر داریم و هزینه های رفتن از یکی به دیگری را می‌دانیم. خوب است کم هزینه ترین مسیری که از یک شهر آغاز شود و از تمامی شهرها دقیقاً یکبار عبور کند و به شهر اول بازگردد.

مسئله  فروشنده  دوره‌گرد جزء مسائل NP مشکل است. راه‌های بیان شده برخورد با چنین مسائلی عبارتند از:

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

دانلود : Colporteur
حجم: 3KB
منبع : سایت/ پسورد: digiemc.com