Mastering Algorithms with C

Description of the Traveling-Salesman Problem

Imagine a salesman who needs to visit a number of cities as part of the route he works. His goal is to travel the shortest possible distance while visiting every city exactly once before returning to the point at which he starts. This is the idea behind the traveling-salesman problem.

In a graph, a tour in which we visit every other vertex exactly once before returning to the vertex at which we started is called a hamiltonian cycle. To solve the traveling-salesman problem, we use a graph G = (V, E ) as a model and look for the hamiltonian cycle with the shortest length. G is a complete, undirected, weighted graph, wherein V is a set of vertices representing the points we wish to visit and E is a set of edges representing connections between the points. Each edge in E is weighted by the distance between the vertices that define it. Since G is complete and undirected, E contains V (V - 1)/2 edges.

One way to solve the traveling-salesman problem is by exploring all possible permutations of the vertices in G. Using this approach, since each permutation represents one possible tour, we simply determine which one results in the tour that is the shortest. Unfortunately, this approach is not at all practical because it does not run in polynomial time. A polynomial-time algorithm is one whose complexity is less than or equal to O (n^k ), where k is some constant. This approach does not run in polynomial time because for a set of V vertices, there ...