Traveling Salesman Problem Using Dynamic Programming With Practical Example

Traveling Salesman Problem Using Dynamic Programming With Practical Example

https://www.gyanodhan.com/video/7B1.%20GATE%20CSEIT/Algorith%20Analysis%20and%20Design/616.%20AAD-%20Traveling%20Salesman%20Problem%20%20%20Using%20Dynamic%20Programming%20%20%20With%20Practical%20Example%2045%20HD.mp4

 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)?

Traveling Salesman Problem Using Dynamic Programming With Practical Example

travelsalesman problem using dynamic programming

Here’s a complete and student-friendly explanation of the Traveling Salesman Problem (TSP) using Dynamic Programming, with a practical example, ideal for B.Tech, GATE, BCA, or computer science interviews.

---

Traveling Salesman Problem (TSP) Using Dynamic Programming

---

What is TSP?

The Traveling Salesman Problem (TSP) asks:

“Given a set of cities and the distances between every pair, what is the shortest possible route that visits every city exactly once and returns to the starting city?”

It’s a combinatorial optimization problem
TSP is an NP-hard problem
Useful in logistics, circuit design, planning, etc.

---

Dynamic Programming Approach (Bitmasking + DP)

We use a bitmask to represent visited cities and memoization to store subproblem solutions.

---

Basic Idea:

Let’s say:

• n = number of cities
• dp[mask][i] = minimum cost to reach city i after visiting cities in mask

---

Recurrence Relation:

dp[mask][i]=min⁡j∉mask(dp[mask∣(1<<j)][j]+dist[i][j])dp[mask][i] = \min_{j \notin mask} \left( dp[mask | (1 << j)][j] + dist[i][j] \right)

• mask is a binary number representing visited cities
• Base case:

dp[1<<i][i]=dist[0][i](if we start from city 0)dp[1 << i][i] = dist[0][i] \quad \text{(if we start from city 0)}

---

Practical Example:

Let’s solve for 4 cities (0, 1, 2, 3) with the distance matrix:

     0   1   2   3
0 |  0   10  15  20
1 | 10   0   35  25
2 | 15  35   0   30
3 | 20  25  30   0

Goal: Start from city 0, visit all cities exactly once, and return to 0.

---

Using DP (Bitmasking Approach)

There are 2n×n2^n \times n states
For n=4 ⇒ 16 x 4 = 64 states

---

Code (C++ Style Pseudocode):

int tsp(int mask, int pos, vector<vector<int>> &dist, vector<vector<int>> &dp) {
    int n = dist.size();

    if (mask == (1 << n) - 1)
        return dist[pos][0]; // return to start

    if (dp[mask][pos] != -1)
        return dp[mask][pos];

    int ans = INT_MAX;

    for (int city = 0; city < n; city++) {
        if ((mask & (1 << city)) == 0) {
            int newAns = dist[pos][city] + tsp(mask | (1 << city), city, dist, dp);
            ans = min(ans, newAns);
        }
    }

    return dp[mask][pos] = ans;
}

---

Initial Call:

int n = 4;
vector<vector<int>> dp(1 << n, vector<int>(n, -1));
int result = tsp(1, 0, dist, dp);

---

Output for This Example:

The minimum cost path is:

0 → 1 → 3 → 2 → 0

With total cost = 80

---

Time Complexity:

O(n2⋅2n)O(n^2 \cdot 2^n)

Space: O(n⋅2n)O(n \cdot 2^n)

Efficient for n ≤ 16

---

TSP Recap:

Feature	Description
Technique	Bitmasking + Memoization (DP)
Complexity	O(n2⋅2n)O(n^2 \cdot 2^n)
Input	Distance matrix
Output	Shortest tour covering all cities

---

Want These?

• Python or Java implementation?
• Step-by-step animated explanation?
• PDF notes with trace table?
• Hindi explanation video?

Just say the word — I’ll deliver what you need for your exam or project!

Traveling Salesman Problem Using Dynamic Programming With Practical Example