حل مسئله فروشنده دوره گرد با استفاده از الگوریتم کلونی مورچگان با پایتونیکشنبه 31, مارس 2019

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

شرح مسئله بدین شکل است:

تعدادی شهر داریم و هزینه رفتن مستقیم از یکی به دیگری را می‌دانیم. مطلوب است کم‌هزینه‌ترین مسیری که از یک شهر شروع شود و از تمامی شهرها دقیقاً یکبار عبور کند و به شهر شروع بازگردد.

تعداد جواب‌های شدنی مسئله، برابر است با {\displaystyle {\frac {1}{2}}(n-1)!} برای n>۲ که n تعداد شهرها می‌باشد. در واقع این عدد برابر است با تعداددورهای همیلتونی در یک گراف کامل با n رأس.

الگوریتم کلونی مورچه ها (ACO):

بهینه‌سازی گروه مورچه‌ها یا ACO یک الگوریتم مناسب یافتن راه‌حل‌های تقریبی برای مسائل بهینه‌سازی ترکیبیاتی است. در این روش، مورچه‌های مصنوعی به‌وسیله‌ٔ حرکت بر روی نمودار مساله و با باقی گذاشتن نشانه‌هایی بر روی نمودار، همچون مورچه‌های واقعی که در مسیر حرکت خود نشانه‌های باقی می‌‌گذارند، باعث می‌شوند که مورچه‌های مصنوعی بعدی بتوانند راه‌حل‌های بهتری را برای مساله فراهم نمایند. همچنین در این روش می توان توسط مسائل محاسباتی-عددی بر مبنای علم احتمالات بهترین مسیر را در یک نمودار یافت.