TSP کمهزینهترین تور را پیدا میکند که همه نقاط را یک بار ببیند و به نقطه شروع برگردد. در این مقاله قرار نیست فقط چند خط کد ببینیم؛ ابتدا مسئله را شهودی میفهمیم، بعد مراحل، کاربردهای واقعی، هزینه اجرای الگوریتم و محدودیتهای آن را بررسی میکنیم.
این الگوریتم چه مسئلهای را حل میکند؟
Travelling Salesman Problem (TSP) زمانی ارزشمند است که ساختار مسئله را به صورت گراف ببینیم. قبل از کدنویسی باید بدانیم Vertexها چه چیزی هستند، Edgeها چه رابطهای را نشان میدهند و خروجی مورد انتظار دقیقاً چیست.
ایده اصلی به سادهترین شکل
این مسئله یک Hamiltonian Cycle وزندار و بهینه است؛ فقط وجود مسیر کافی نیست و کمترین هزینه مهم است.
مراحل اجرا
- در روش ساده همه ترتیبها ساخته میشوند.
- هزینه هر تور حساب میشود.
- کمترین هزینه نگه داشته میشود.
- برای ابعاد بزرگتر از DP یا Heuristic استفاده میشود.
نمونه کد JavaScript
// Brute-force TSP is suitable only for small n.
// Production systems usually need DP, branch-and-bound or heuristics.
function tourCost(tour, dist) {
return tour.slice(0,-1).reduce((sum, city, i) =>
sum + dist[city][tour[i+1]], 0);
}مثالهای واقعی و دنیای کار
- Delivery Route
- Technician Scheduling
- Warehouse Robot
- ترتیب بازدید مشتریان فروش
پیچیدگی زمانی و فضایی
Brute Force حدود O(V!)؛ Held-Karp حدود O(V²2^V)
چه زمانی استفاده کنیم؟
بهینهسازی تور بازدید همه نقاط
چه زمانی مناسب نیست؟
برای داده بزرگ exact solution بسیار گران است.
جمعبندی
Travelling Salesman Problem (TSP) را زمانی انتخاب کنید که نوع گراف و هدف مسئله با ویژگیهای آن همخوان باشد. مهمترین نکته این است که الگوریتم را به خاطر اسمش استفاده نکنیم؛ ابتدا مسئله را مدل کنیم و سپس ابزار مناسب را انتخاب کنیم.