Program to Solve Traveling Salesman Problem in Python

Write a step by step code to Solve Traveling Salesman Problem in Python.

Here is a step by step tutorial on how to solve the Traveling Salesman Problem in Python.

In this tutorial I will assume that you have basic knowledge of Python programming and will guide you through the process of solving the TSP using the Brute Force method.

What is the Traveling Salesman Problem?

The Traveling Salesman Problem is a famous optimization problem in computer science. It involves finding the shortest possible route that visits a given set of cities and returns to the starting city. The problem is NP-hard which means that finding an exact solution for large instances is computationally expensive.

The Brute Force Approach

The Brute Force approach involve generating all possible permutations of the cities and calculating the distance traveled for each permutation. The shortest distance traveled is the optimal solution.

Step-by-Step Tutorial to solve the Traveling Salesman Problem in Python.

Define the Cities

We begin by defining the cities that salesman must visit. We can represent each city as tuple containing its name and its coordinates. For this example we’ll use a list of six cities:

cities = [
    ("A", (0, 0)),
    ("B", (1, 5)),
    ("C", (2, 3)),
    ("D", (5, 5)),
    ("E", (6, 3)),
    ("F", (8, 0))
]

Define the Distance Function

Next we need to define a distance function that calculates the distance between two cities. We can use the Pythagorean theorem to calculate the distance between two points in a two-dimensional plane:

import math

def distance(city1, city2):
    x1, y1 = city1[1]
    x2, y2 = city2[1]
    return math.sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2)

Generate Permutations

We can use permutations function from the itertools module to generate all possible permutations of the cities:

import itertools

perm = list(itertools.permutations(cities))

Calculate Distances

Next, we need to calculate distance traveled for each permutation. We can use for loop to iterate over each permutation and sum distances between adjacent cities:

shortest_distance = float('inf')

for p in perm:
    d = 0
    for i in range(len(p) - 1):
        d += distance(p[i], p[i + 1])
    d += distance(p[-1], p[0])
    if d < shortest_distance:
        shortest_distance = d
        shortest_path = p

Print the Result

Finally we can print the shortest distance and the corresponding path:

print(f"Shortest Distance: {shortest_distance:.2f}")
print("Shortest Path:", end=" ")
for city in shortest_path:
    print(city[0], end=" ")
print(shortest_path[0][0])

Complete Code to Solve Traveling Salesman Problem in Python

Here is complete code for solving the TSP using the Brute Force approach:

import math
import itertools

cities = [
    ("A", (0, 0)),
    ("B", (1, 5)),
    ("C", (2, 3)),
    ("D", (5, 5)),
    ("E", (6, 3)),
    ("F", (8, 0))
]

def distance(city1, city2):
    x1, y1 = city1[1]
    x2, y2 = city2[1]
    return math.sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2)

perm = list(itertools.permutations(cities))

shortest_distance = float('inf')

for p in perm:
    d = 0
    for i in range(len(p) - 1):
        d += distance(p[i], p[i + 1])
    d += distance(p[-1], p[0])
    if d < shortest_distance:
        shortest_distance = d
        shortest_path = p

print(f"Shortest Distance: {shortest_distance:.2f}")
print("Shortest Path:", end=" ")
for city in shortest_path:
    print(city[0], end=" ")
print(shortest_path[0][0])

This code define the list of cities a distance function that calculates distance between two cities using their coordinates generates all possible permutations of the cities calculates the distance traveled for each permutation and prints shortest distance and the corresponding path. The result of running this code will output shortest distance and the corresponding path for the given set of cities.