Traveling Salesman Problem Using Dynamic Programming With Practical Example

March 11, 2025March 12, 2025 Ali Seron Jason 0 Comments

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

import sys
# Number of cities

N = 4

# Distance matrix

dist = [

    [0, 10, 15, 20],

    [10, 0, 35, 25],

    [15, 35, 0, 30],

    [20, 25, 30, 0]

]



# Memoization table (stores results of subproblems)

dp = [[-1] * (1 << N) for _ in range(N)]
# Function to find the shortest route using DP + Bitmasking

def tsp(mask, pos):

    # Base case: If all cities are visited, return cost to return to starting city

    if mask == (1 << N) - 1:

        return dist[pos][0]  # Return to start city



    # If already computed, return stored result

    if dp[pos][mask] != -1:

        return dp[pos][mask]
    # Try visiting the next unvisited city

    min_cost = sys.maxsize

    for city in range(N):

        if (mask & (1 << city)) == 0:  # If city not visited

            new_cost = dist[pos][city] + tsp(mask | (1 << city), city)

            min_cost = min(min_cost, new_cost)



    # Store result in DP table

    dp[pos][mask] = min_cost

    return min_cost

# Start from city 0 with only city 0 visited (mask = 1) min_route_cost = tsp(1, 0) print("Minimum Traveling Cost:", min_route_cost)

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

DIZNR INTERNATIONAL

Traveling Salesman Problem Using Dynamic Programming With Practical Example

Traveling Salesman Problem (TSP) Using Dynamic Programming

Problem Statement

Why Dynamic Programming?

Approach – Dynamic Programming with Bitmasking

Example

Distance Matrix (Graph Representation)

Dynamic Programming Solution

Explanation of the Code

Output

Time Complexity

Applications of TSP