# Traveling Salesperson Problem

The travelling salesman problem can be solved in $O(2^{n}n^{2})$ time and $O(2^{n}n)$ space using Dynamic Programming, which is better than the $O(n!)$ 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 $C(v,v')$ 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, $M(S,v)$ find the minimum of $M(S-v,v')+C(v',v)$ for each v' in S. To enforce the particular choice of starting location, force $C(\{v\},v)=\infty$ for each non start vertex v.