Traveling Salesperson Problem

From Algorithmist
Jump to navigation Jump to search
This is a stub or unfinished. Contribute by editing me.

Definition of TSP[edit]

The Traveling Salesman Problem is an NP-Complete optimization problem. Given a weighted digraph G, find a cycle that goes through every vertex in G exactly once while having minimum cost total cost. There are variants of the problem which ask for a path which visits every vertex but starts and ends at given points, but they are conceptually very similiar.

Dynamic Programming Solution[edit]

The travelling salesman problem can be solved in time and space using Dynamic Programming, which is better than the time bruteforce try all paths algorithm in time, but much worse in space.

The solution to the variant of the problem where a path rather than a cycle is required is described here, but this algorithm can be tweaked slightly to answer the cycle variation of the problem as well. To solve the problem, use memoization storing the minimum cost to visit for every subset of vertices with a given ending vertex. For example, one such entry would be the minimum cost of visiting the set of vertices {2, 4, 7} ending at vertex 4; another distinct entry is the set of vertices {2, 4, 7} ending at vertex 2. Then it is clear that the answer to the travelling salesman problem corresponds to entry that has visited every vertex in G, starting at the source vertex and ending at the destination vertex. Let be the cost taking the edge from v to v' in G. To find the minimum cost of a given set, S and vertex v, find the minimum of for each v' in S. To enforce the particular choice of starting location, force for each non start vertex v.

Essentially, just try to take each edge between the visited set and the ending vertex. The intuition on why memoization works on the problem is as follows. Consider taking some partial path through vertices starting at a, through b and c, and ending at d with the final destination being z. The order in which b and c were visited, either a,b,c,d or a,c,b,d does not matter to the subsequent portion of the path after d, since any path through only remaining vertices reaching z will not be affected by the order of visiting the first four. Thus, it's clear that only the minumum cost for the set a,b,c,d ending at d matters. Since the number of subsets of size n grows strictly slower than the number of permutations of size n, the memoization algorithm is asympotically faster than the bruteforce algorithm.