Traveling Salesman Problem Using Dynamic Programming With Practical Example
Traveling Salesman Problem Using Dynamic Programming With Practical Example
Contents
- 1 Traveling Salesman Problem (TSP) Using Dynamic Programming
- 2 Problem Statement
- 3 Why Dynamic Programming?
- 4 Approach – Dynamic Programming with Bitmasking
- 5 Example
- 6 Distance Matrix (Graph Representation)
- 7 Dynamic Programming Solution
- 8 Explanation of the Code
- 9 Output
- 10 Time Complexity
- 11 Applications of TSP
- 12 Traveling Salesman Problem Using Dynamic Programming With Practical Example
- 13 travelsalesman problem using dynamic programming
Traveling Salesman Problem (TSP) Using Dynamic Programming
The Traveling Salesman Problem (TSP) is one of the most famous optimization problems in computer science and operations research. The goal is to find the shortest possible route that visits each city exactly once and returns to the starting point.
Problem Statement
Given a set of N cities and the cost to travel between each pair of cities, find the shortest possible route that visits every city exactly once and returns to the starting city.
Why Dynamic Programming?
Brute force solution (O(N!) complexity) is too slow for large N
Dynamic Programming (DP) approach reduces complexity to O(2^N * N)
Approach – Dynamic Programming with Bitmasking
- Use Bitmasking to track visited cities.
- Use Memoization to store results of subproblems.
- Define dp[mask][i] as the minimum cost to visit all cities in mask ending at city i.
Example
Let’s take 4 cities: A, B, C, D
Distance Matrix (Graph Representation)
A | B | C | D | |
---|---|---|---|---|
A | 0 | 10 | 15 | 20 |
B | 10 | 0 | 35 | 25 |
C | 15 | 35 | 0 | 30 |
D | 20 | 25 | 30 | 0 |
We start from city A (0th city) and find the shortest route covering all cities.
Dynamic Programming Solution
Explanation of the Code
mask
keeps track of visited cities using bitmasking.pos
represents the last visited city.
Base Case: If all cities are visited, return cost to return to the start.
Recursive Case: Try visiting all unvisited cities and take the minimum cost.
Memoization (dp
table) avoids recomputing subproblems.
Output
Optimal Path: A -> B -> D -> C -> A
with cost 80
Time Complexity
O(2^N * N) (Much better than O(N!))
Applications of TSP
Logistics & Delivery Optimization
Route Planning for Salespersons
Network Routing & Data Communication
Would you like a Graph Visualization or another approach (e.g., Genetic Algorithm)?