Traveling salesperson problem
The traveling salesperson problem can be described as follows:
A traveler has a list of cities they need to visit, the distance between the cities is known and all the cities are to be visited just once. We need to find the shortest route to visit each city and come back to their source point.
It is a classic algorithm problem used in the field of computer science and operations.
This problem statement has been one of the notorious computational problems, it can be solved using brute force, but that will take longer, so we instead of using a different approach.
The two approaches of solving them are:
1. The naive approach
In this approach, we consider city A as the source and the destination city. Then, we generate all (n-1)! Permutations for all the cities, while keeping track of the cost for each permutation. We return the permutation with the minimum cost.
The time complexity in this approach is Θ(n!).
2. Dynamic programming
Let us assume a graph (g, h), where g is the number of cities in the list and h is the set of weighted edges. We also take an edge (u, v), where u and v are vertices that are connected. The distance between vertices u and v is taken as d (u, v). The distance should be non-negative.
Assuming we have started our travel, and have already visited x number of cities so far. To find the best and most convenient route, we will need to know x is which city, and also what cities have we covered so far, so as to not revisit any of them again. This is a problem involving partial travel and can be referred to as a perfect sub- problem.
Basically, we start with a subset of size 2 and calculate C(g, h). C(g, h) represents the minimum cost of visiting each vertex in set S exactly once.
Algorithm:
If size of S is 2, then S must be {1, i}, C(g, h) = dist(1, i) Else if size of S is greater than 2. C(g, h) = min { C(S-{i}, j) + dis(j, i)} where j belongs to S, j != i and j != 1.
If there was a set of size n then we consider n-2 subsets and each of size n-1, such that all subsets don’t have nth in them.
Traveling salesperson problem or TSP is very similar to the Hamiltonian cycle problem, so it is important to keep the difference noted.
The Hamiltonian cycle problem asks us to find if there is a tour in which the tourist visits all the cities exactly once? If we can find such a tour, the problem is to find the minimum weight Hamiltonian cycle.
TSP is a common computational problem and is often used in theory, but it also has very practical applications too, it is used in the manufacture of microchips, planning, logistics, and many more. After some slight tweaking, it is also used in DNA sequencing.
Reference