Scribd
Upload
36 views2 pages

Salesman Program

The document contains a Python implementation of the Traveling Salesman Problem using Dynamic Programming, specifically the Held-Karp Algorithm. It defines a function that calculates the minimum tour cost and optimal path based on a given adjacency matrix representing distances between cities. An example graph is provided, and the results are printed, showing the minimum cost and optimal tour path.

Uploaded by

nagalallig
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
36 views2 pages

Salesman Program

The document contains a Python implementation of the Traveling Salesman Problem using Dynamic Programming, specifically the Held-Karp Algorithm. It defines a function that calculates the minimum tour cost and optimal path based on a given adjacency matrix representing distances between cities. An example graph is provided, and the results are printed, showing the minimum cost and optimal tour path.

Uploaded by

nagalallig
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

import sys

def tsp_dp(graph):
"""
Solves the Traveling Salesman Problem using Dynamic Programming (Held-Karp Algorithm).
:param graph: 2D list (adjacency matrix) representing distances between cities.
:return: Tuple (minimum tour cost, optimal tour path).
"""
n = len(graph)
memo = {}
parent = {} # Dictionary to store the best path choices

def tsp(mask, pos):


"""
Recursive function with memoization.
:param mask: Binary mask representing visited cities.
:param pos: Current city index.
:return: Minimum tour cost starting from pos and visiting all unvisited cities.
"""
if mask == (1 << n) - 1: # All cities visited
return graph[pos][0] # Return to starting city

if (mask, pos) in memo: # Memoization check


return memo[(mask, pos)]

min_cost = sys.maxsize
best_city = -1

for city in range(n):


if mask & (1 << city) == 0: # If city is not visited
new_mask = mask | (1 << city)
new_cost = graph[pos][city] + tsp(new_mask, city)

if new_cost < min_cost:


min_cost = new_cost
best_city = city

memo[(mask, pos)] = min_cost


parent[(mask, pos)] = best_city # Store the best next city choice
return min_cost

# Solve the problem


min_cost = tsp(1, 0)

# Retrieve the optimal path


path = [0] # Start at city 0
mask = 1
pos = 0

while len(path) < n:


next_city = parent[(mask, pos)]
path.append(next_city)
mask |= (1 << next_city)
pos = next_city

path.append(0) # Return to the starting city

return min_cost, path

# Example Graph (Adjacency Matrix)


graph = [
[0, 10, 15, 20],
[10, 0, 35, 25],
[15, 35, 0, 30],
[20, 25, 30, 0]
]

# Solve TSP
min_cost, optimal_path = tsp_dp(graph)

# Output results

print("Minimum cost of traveling salesman tour:", min_cost)


print("Optimal tour path:", " -> ".join(map(str, optimal_path)))
# Output results
print("Minimum cost of traveling salesman tour:", min_cost)
print("Optimal tour path:", " -> ".join(map(str, optimal_path)))

You might also like