Scribd
Upload
30 views2 pages

TSP Problem

The document presents a solution to the Traveling Salesman Problem (TSP) using Python. It defines a distance matrix for four cities and calculates all possible paths starting from city 0 to determine the minimum cost path and its associated cost. The result is printed as the minimum cost path and its cost.

Uploaded by

rharsh995520
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
30 views2 pages

TSP Problem

The document presents a solution to the Traveling Salesman Problem (TSP) using Python. It defines a distance matrix for four cities and calculates all possible paths starting from city 0 to determine the minimum cost path and its associated cost. The result is printed as the minimum cost path and its cost.

Uploaded by

rharsh995520
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

TSP Problem

import itertools

# Distance matrix between cities

dist_matrix = [

[0, 29, 20, 21],

[29, 0, 15, 17],

[20, 15, 0, 28],

[21, 17, 28, 0]

# Number of cities

n = len(dist_matrix)

# Generate all possible paths starting from city 0

cities = list(range(1, n))

min_path = None

min_cost = float('inf')

for perm in itertools.permutations(cities):

path = [0] + list(perm) + [0] # start and end at city 0

cost = sum(dist_matrix[path[i]][path[i + 1]] for i in range(n))

if cost < min_cost:

min_cost = cost

min_path = path

print("Minimum cost path:", min_path)

print("Minimum cost:", min_cost)

You might also like