🚚 مسئله فروشنده دوره‌گرد (TSP) چیست؟

فرض کنید یک فروشنده باید از چندین شهر بازدید کند. چطور می‌تواند کوتاه‌ترین مسیر را پیدا کند؟ 🤔

هدف TSP این است که از یک شهر شروع کنیم، دقیقاً یک‌بار از تمام شهرها بگذریم، به شهر اول برگردیم و مجموع مسافت را حداقل کنیم.

📍 مطابق ویدیو (مثال برای ۵ شهر A تا E):
1️⃣ مسیر اول: A ➔ B ➔ D ➔ E ➔ C ➔ A (مسافت: ۵۳)
2️⃣ مسیر دوم: A ➔ C ➔ D ➔ E ➔ B ➔ A (مسافت: ۳۴)
همان‌طور که در ویدیو می‌بینید، مسیر دوم بسیار بهینه‌تر است.

💡 چرا TSP مهم است؟

بررسی همه حالت‌ها با افزایش شهرها انفجاری رشد می‌کند؛ مثلاً برای ۲۰ شهر حدود ۶۰ کوادریلیون مسیر وجود دارد! 🤯

🧠 راهکار: الگوریتم‌های تقریبی

اینجاست که الگوریتم کریستوفیدس (Christofides) وارد می‌شود؛ روشی که با ترکیب درخت پوشای کمینه (MST) و تطبیق کمینه (Matching)، در زمانی کوتاه تور بهینه‌ای می‌سازد.


🎯 تضمین ریاضی:
جواب بدست آمده حداکثر 1.5 برابر جواب بهینه سرتاسری (مطلق) است.
یعنی مجموع مسافت بدست آمده در این مسیر ارائه شده توسط الگوریتم حداکثر 1.5 برابر مسافت بهترین مسیر ممکن است.