Travelling Salesperson Algorithm
The Travelling Salesperson Problem (TSP) seeks the minimum weight tour visiting every city node exactly once and returning to the origin city.
Travelling Salesperson Bitmask DP Trace
Start at Origin City 0
Initial state: visited mask = 0001 (City 0 visited), current position = 0.
Mask: 0001 | Current City: 0 | Cost: 0Explore Sub-Paths & Memoize
Recursively branch to unvisited cities (1, 2, 3), memoizing minimum costs for sub-states (mask, city).
Path: 0 -> 1 -> 3 -> 2 -> 0 vs 0 -> 2 -> 3 -> 1 -> 0Reconstruct Optimal Hamiltonian Cycle
Combine shortest sub-path costs to compute final minimum tour distance returning to City 0.
Optimal Tour Cost: 35 | Tour Path: 0 -> 1 -> 3 -> 2 -> 0Real-world analogy: Delivery Driver Route
A delivery truck must visit 5 neighborhood addresses and return to the warehouse using the shortest total driving distance.
- NP-Hard= Exhaustive search requires O(N!) factorial permutations.
Complexity analysis
500 steps (Linear)
O(N × W) Memoized Time
O(N × W) Cache Matrix
Memory growth rate as N expands.
Relative efficiency rating for large N.
| Operation | Time Complexity | Space Complexity |
|---|---|---|
| Bitmask Dynamic Programming | O(N² × 2ᴺ) | O(N × 2ᴺ) |
Code implementations
function tsp(dist) {
const n = dist.length;
const memo = Array.from({ length: 1 << n }, () => new Array(n).fill(-1));
// bitmask DP solver
}Real-world applications
Logistics Fleet Routing
Calculates optimal package delivery paths for FedEx/UPS.
Circuit Board Drilling
Minimizes robotic arm movement across PCB hole coordinates.
Interview questions
Topic Knowledge Test & Assessment
Tsp Knowledge & Skill Test
Validate your conceptual understanding, operation mechanics, and core concepts of Tsp.
Topic Metadata
Using Held-Karp Bitmask DP reduces TSP runtime from O(N!) factorial down to O(N² 2ⁿ) exponential!