This guide explains Travelling Salesman Problem (TSP) from first principles. The goal is to understand the problem it solves, why the algorithm works, how to implement it, and where it appears in real software systems.
What problem does it solve?
Travelling Salesman Problem (TSP) belongs to the graph-algorithm toolbox. Before coding, define what the vertices represent, what an edge means, and what result the system actually needs.
The core idea in simple terms
این مسئله یک Hamiltonian Cycle وزندار و بهینه است؛ فقط وجود مسیر کافی نیست و کمترین هزینه مهم است.
Step-by-step process
- در روش ساده همه ترتیبها ساخته میشوند.
- هزینه هر تور حساب میشود.
- کمترین هزینه نگه داشته میشود.
- برای ابعاد بزرگتر از DP یا Heuristic استفاده میشود.
JavaScript example
// 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);
}Real-world and workplace examples
- Delivery Route
- Technician Scheduling
- Warehouse Robot
- ترتیب بازدید مشتریان فروش
Time and space complexity
Brute Force about O(V!)؛ Held-Karp about O(V²2^V)
When should you use it?
Use it when the problem matches this condition: بهینهسازی تور بازدید همه نقاط.
When is it not a good fit?
It is usually not the best choice when: برای داده بزرگ exact solution بسیار گران است..
Summary
Do not choose an algorithm by name alone. First identify whether the graph is directed or undirected, weighted or unweighted, and whether the goal is traversal, reachability, shortest path, connectivity, spanning structure, or combinatorial optimization.