The Traveling Salesman Problem
The Traveling Salesman Problem (TSP) is a classic optimization problem in computer science and mathematics. It is a problem that has been studied for over a century and has numerous real-world applications.
The Traveling Salesman Problem (TSP) problem is defined as follows: Given a set of cities and the distances between each city, find the shortest possible route that visits each city exactly once and returns to the starting city.
The Traveling Salesman Problem (TSP) originated in the early 1900s when mathematicians and computer scientists first began to study the problem of finding the shortest route for a salesman to visit a set of cities. Over the years, the TSP has been formalized and refined and has become one of computer science’s most well-known optimization problems.
The above image solves the travelling salesman problem, where the map shows two options to travel from Point one to Point B. Route 1 is 5.5 know long and takes 16 minutes, while Route 2 is 7.5 km long and takes 21 minutes. This helps the travelling person in decision-making, and by default, the person would choose Route 1, marked in blue. To understand how this process works, let us understand this solution is detail.
You can also explore: Space Complexity in Data Structures
The Formal Definition of the Traveling Salesman Problem
The Traveling Salesman Problem (TSP) can be formally defined as follows: Given a set of cities and the distances between each city, find the shortest possible route that visits each city exactly once and returns to the starting city.
The input to the TSP consists of a set of n cities, where n is an integer greater than 2. Each city is represented by a unique identifier, and the distances between each city are given in a distance matrix, where the ij-th element of the matrix represents the distance between city i and city j.
The output of the TSP is a permutation of the cities, representing the order in which the cities should be visited. The length of the route is calculated as the sum of the distances between each consecutive pair of cities in the permutation. The goal is to find the permutation that minimizes the length of the route.
For the purposes of this article, we will use a simple example with four cities, A, B, C, and D. The distance matrix for this example is given below:
| A | B | C | D | |
| A | 0 | 4 | 8 | 7 |
| B | 4 | 0 | 2 | 3 |
| C | 8 | 2 | 0 | 6 |
| D | 7 | 3 | 6 | 0 |
In this example, the TSP requires finding the shortest route to visit each city exactly once and return to the starting city. One possible route could be A -> D -> B -> C -> A with a total distance of 7 + 3 + 2 + 8 = 20. This means that starting from city A, we visit city D, then city B, then city C, and finally return to city A.
This example demonstrates the basic form of the TSP and will be used throughout the article to illustrate various solution methods and algorithms.
Best-suited Data Structures and Algorithms courses for you
Learn Data Structures and Algorithms with these high-rated online courses
Brute force solution
The brute force solution to the Traveling Salesman Problem (TSP) is to generate all possible city permutations and calculate each route’s length. The shortest route is then returned as the solution to the TSP.
The time complexity of this solution is O(n!), where n is the number of cities. This is because there are n! possible permutations of the cities, and calculating the length of each route takes O(n) time. Thus, the total time complexity of the brute force solution is O(n!n).
The space complexity of the brute force solution is O(n), since it only requires storage for the permutations and the distances between the cities.
Here is an example implementation of the brute force solution in Python:
from itertools import permutations
def brute_force(cities, distances): min_distance = float('inf') best_route = None for route in permutations(cities): route = list(route) + [route[0]] distance = 0 for i in range(len(route) - 1): distance += distances[route[i]][route[i + 1]] if distance < min_distance: min_distance = distance best_route = route return best_route, min_distance
cities = ['A', 'B', 'C', 'D']distances = { 'A': {'B': 4, 'C': 8, 'D': 7}, 'B': {'A': 4, 'C': 2, 'D': 3}, 'C': {'A': 8, 'B': 2, 'D': 6}, 'D': {'A': 7, 'B': 3, 'C': 6}}
route, distance = brute_force(cities, distances)print("Route using brute force:", route[:-1])print("Total distance using brute force:", distance)
The code first defines a brute_force function that takes as input the list of cities and the distances between them. The function then uses the permutations function from the itertools module to generate all possible permutations of the cities and calculates the total distance of each permutation by summing up the distances between consecutive cities. The function keeps track of the permutation with the minimum total distance and returns the best route and the minimum distance.
The code then defines the list of cities and the distances between them and calls the brute_force function to get the solution. Finally, the code prints the best route and the minimum distance obtained by the brute force method.
Note that the brute force method is an exact method that guarantees to find the optimal solution, but it’s also very computationally expensive, especially for large problems with many cities. For this reason, it’s usually only feasible to use the brute force method for small problems or for testing and comparison purposes.
Dynamic programming solution
The dynamic programming solution to the Traveling Salesman Problem (TSP) is a more efficient alternative to the brute force solution. In this approach, we break down the problem into smaller subproblems and store the results of these subproblems to avoid redundant calculations.
The following code uses the dynamic programming approach to solve the TSP problem using a top-down recursion method with memoization.
n = 4dist = [ [0, 4, 8, 7], [4, 0, 2, 3], [8, 2, 0, 6], [7, 3, 6, 0]]
memo = [[-1]*(1 << (n)) for _ in range(n)]
def fun(i, mask): if mask == ((1 << i) | 3): return dist[1][i] # memoization if memo[i][mask] != -1: return memo[i][mask] res = 10**9 for j in range(1, n): if (mask & (1 << j)) != 0 and j != i and j != 1: res = min(res, fun(j, mask & (~(1 << i))) + dist[j][i]) memo[i][mask] = res return res
ans = 10**9for i in range(1, n): ans = min(ans, fun(i, (1 << (n))-1) + dist[i][1]) print("Total distance using DP algorithm = " + str(ans))
The inputs to the function are the current node ‘i’ and the visited nodes ‘mask’. The function uses the memo array to store the results of subproblems so that they can be reused. The base case is when the only ith bit and the 1st bit is set in the mask. This implies that all other nodes have been visited. In this case, the function returns the distance between node 1 and node i.
In the main part of the function, we loop through all nodes j in the mask and end the path at node i. For every node j, we recursively calculate the cost of traveling all nodes in the mask except node i, and then travel back from node j to node i taking the shortest path. We take the minimum of all possible j nodes and store it in the memo array.
In the main part of the code, we loop through all nodes from 1 to n and calculate the minimum cost of starting from node i and visiting all other nodes once. Finally, we print the minimum distance.
The time complexity of the dynamic programming solution is O(2^n*n^2), where n is the number of cities. This is because there are 2^n possible subsets of the cities, and each subset can be filled in with a time complexity of O(n^2).
This code provides a solution for the TSP problem using the dynamic programming approach with memoization, which is an efficient way to solve the TSP problem.
Approximate solutions
While the dynamic programming solution provides an exact solution to the Traveling Salesman Problem (TSP), it is often too slow for large instances of the problem. For this reason, a number of approximate solutions have been developed that provide good solutions to the TSP in a fraction of the time required by the dynamic programming solution.
Must explore: What is Rabin Karp Algorithm?
One of the simplest approximate solutions to the TSP is the nearest neighbor algorithm. The idea behind the nearest neighbor algorithm is to start at a random city and visit the closest city that has not yet been visited. This process is repeated until all cities have been visited. The nearest neighbor algorithm is simple to implement and has a time complexity of O(n^2), where n is the number of cities.
You must explore: Sparse Matrix Representation and Operations
Here is an example implementation of the nearest neighbor algorithm in Python:
def nearest_neighbor(cities, distances): route = [cities[0]] remaining_cities = cities[1:] while remaining_cities: closest_city = min(remaining_cities, key=lambda x: distances[route[-1]][x]) route.append(closest_city) remaining_cities.remove(closest_city) route.append(route[0]) distance = sum(distances[route[i]][route[i+1]] for i in range(len(route)-1)) return route, distance
cities = ['A', 'B', 'C', 'D']distances = { 'A': {'B': 4, 'C': 8, 'D': 7}, 'B': {'A': 4, 'C': 2, 'D': 3}, 'C': {'A': 8, 'B': 2, 'D': 6}, 'D': {'A': 7, 'B': 3, 'C': 6}}
route, distance = nearest_neighbor(cities, distances)print("Route using nearest neighbor algorithm:", route[:-1])print("Total distance using nearest neighbor algorithm:", distance)
Another popular approximate solution to the TSP is the 2-opt algorithm. The idea behind the 2-opt algorithm is to start with a solution to the TSP and then improve it by making small changes to the order in which the cities are visited. The 2-opt algorithm makes these changes by swapping pairs of cities in the solution, and it repeats this process until no further improvement can be made. The 2-opt algorithm is more sophisticated than the nearest neighbor algorithm and can provide better solutions, but it is also more complex to implement.
Here is an example implementation of the 2-opt algorithm in Python:
def two_opt(cities, distances): route = nearest_neighbor(cities, distances)[0][:-1] best_route = route[:] best_distance = sum(distances[route[i]][route[i+1]] for i in range(len(route)-1)) + distances[route[-1]][route[0]] improved = True while improved: improved = False for i in range(1, len(route)-2): for j in range(i+1, len(route)): if j-i == 1: continue new_route = route[:i] + route[i:j][::-1] + route[j:] new_distance = sum(distances[new_route[k]][new_route[k+1]] for k in range(len(new_route)-1)) + distances[new_route[-1]][new_route[0]] if new_distance < best_distance: best_route = new_route[:] best_distance = new_distance route = new_route[:] improved = True return best_route, best_distance
cities = ['A', 'B', 'C', 'D']distances = { 'A': {'B': 4, 'C': 8, 'D': 7}, 'B': {'A': 4, 'C': 2, 'D': 3}, 'C': {'A': 8, 'B': 2, 'D': 6}, 'D': {'A': 7, 'B': 3, 'C': 6}}
route, distance = two_opt(cities, distances)print("Route using 2-opt algorithm:", route)print("Total distance using 2-opt algorithm:", distance)
Real-world applications of the Traveling Salesman Problem
The Traveling Salesman Problem (TSP) is a well-known optimization problem that has numerous real-world applications in various fields. Here are some of the most notable applications of the TSP:
- Vehicle Routing: The TSP is widely used in the optimization of delivery and transportation routes. In this application, the salesman is represented by a delivery vehicle, and the cities correspond to delivery locations. The goal is to find the shortest possible route that visits each location exactly once and returns to the starting point. This problem is critical in the context of delivery companies, as it helps to minimize fuel consumption, reduce the number of vehicles required, and ensure the timely delivery of goods.
- Circuit Design: In the field of electronics, the TSP is used to design efficient circuits. In this application, the cities represent the components of a circuit, and the salesman is the electrical signal that must travel through each component exactly once. The goal is to find the shortest possible path that minimizes the total resistance and capacitance of the circuit.
- Protein Folding: The TSP is also used in the field of biology, specifically in the study of protein folding. In this application, the cities represent different amino acids in a protein, and the salesman is the path that the protein takes to fold into its final three-dimensional shape. The goal is to find the shortest possible path that minimizes the energy required for the protein to fold into its final shape.
Each of these real-world applications demonstrates the versatility of the TSP and how it has been applied to solve a wide range of problems. Whether it’s optimizing delivery routes, designing efficient circuits, or understanding protein folding, the TSP provides a valuable tool for solving complex optimization problems.
Must explore: Introduction To Asymptotic Analysis
Conclusion
In conclusion, the Traveling Salesman Problem is a well-studied optimization problem with a wide range of real-world applications. The problem is defined as finding the shortest route that visits a set of cities exactly once and returns to the starting point. There are various algorithms to solve the TSP, each with its own advantages and disadvantages.
Must explore: Master’s Theorem and Its Use in Calculating Time Complexity
Brute force is an exact method to find the solution, but its time complexity grows exponentially with the number of cities, making it impractical for large instances of the problem. The nearest neighbor algorithm and 2-opt algorithm are heuristics that provide quick solutions but with suboptimal results. Dynamic programming provides a more optimized solution to the problem, but its time complexity is still quite high.
In vehicle routing, the TSP is used to optimize the delivery routes of vehicles to minimize the total distance covered and reduce costs. And, in circuit design, the TSP is used to minimize the total length of wire required in the circuit board. In protein folding, the TSP is used to minimize the energy required to fold a protein into its native structure.
In summary, the TSP is a classic example of an optimization problem that has numerous real-world applications. The development of more efficient algorithms for solving the TSP remains an active area of research, and further improvements in this field are likely to have a significant impact in various applications.
Author: Somya Dipayan
This is a collection of insightful articles from domain experts in the fields of Cloud Computing, DevOps, AWS, Data Science, Machine Learning, AI, and Natural Language Processing. The range of topics caters to upski... Read Full Bio
Top Picks & New Arrivals
