TSP (Dynamic Programming)
Solve Travelling Salesman Problem using Held-Karp dynamic programming algorithm
Travelling Salesman Problem - Dynamic Programming Approach
The Held-Karp algorithm uses dynamic programming to solve TSP in O(n²2ⁿ) time, which is exponentially better than brute force O(n!) but still exponential.
Theory & Concepts
Definition:
Find the shortest possible route that visits each city exactly once and returns to the starting city using dynamic programming with bitmasks to represent visited sets.
Key Points:
- Uses bitmasks to represent subsets of visited cities
- Optimal substructure: optimal tour contains optimal sub-tours
- Memoization prevents recalculating same subproblems
- Still exponential but much better than brute force
Applications:
- Vehicle routing and logistics
- Circuit board drilling optimization
- DNA sequencing assembly
- Warehouse order picking optimization
University Guidelines
Exam Weightage
10-15 marks MarksSyllabus Coverage:
- Travelling Salesman Problem formulation
- Dynamic programming with bitmasks
- Held-Karp algorithm implementation
- State space representation
- Time and space complexity analysis
Common Questions:
- Solve TSP using dynamic programming
- Explain state representation with bitmasks
- Show DP table construction step by step
- Trace back optimal tour from DP table
Exam Tips:
DP[mask][i] = minimum cost to visit cities in mask ending at city i
Base case: DP[1][0] = 0 (start at city 0)
Recurrence: DP[mask][i] = min(DP[mask^(1<<i)][j] + dist[j][i])
Show bitmask representation clearly in solution
Algorithm Details
O(n²2ⁿ) where n is number of cities
Time Complexity
O(n2ⁿ) for DP table
Space Complexity
Algorithm Steps:
- 1Initialize DP table: DP[mask][i] = min cost to visit cities in mask, ending at i
- 2Base case: DP[1][0] = 0 (start at city 0 with only city 0 visited)
- 3For each subset mask and city i: compute DP[mask][i]
- 4For each previous city j: DP[mask][i] = min(DP[mask^(1<<i)][j] + cost[j][i])
- 5Final answer: min over all cities i of (DP[fullMask][i] + cost[i][0])
- 6Trace back path using parent pointers
Configure TSP
Distance Matrix:
Enter distances between cities (symmetric matrix)
| From\\To | A | B | C | D |
|---|---|---|---|---|
| A | - | |||
| B | - | |||
| C | - | |||
| D | - |
Graph Visualization:
Algorithm Results
🌐
Configure the distance matrix and click "Solve TSP (DP)" to find the optimal tour