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

Start Free Trial

No credit card required