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.
- Program to Create Snake Game in Python
- Write a Program to Create Hangman Game in Python
- Program to Create Tic Tac Toe Game in Python
- Program to Create BlackJack Game 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.
