- List all possible Hamilton circuits (leaving out the exact reversals, if you wish)
- Find the weight of each
- Choose (the) one with the smallest weight.

*Pluses:* It always works (given enough time
& care).

*Minuses:* It can only be used for
relatively small graphs. For a computer doing 10,000 circuits/sec, it would take about 18
seconds to handle 10 vertices, 50 days to handle 15 vertices, 2 years for 16 vertices,
193,000 years for 20 vertices.

Bottom line: Unfortunately, the Brute Force Algorithm is the ONLY method known that is guaranteed to produce an optimal solution.

*Mathematicians have not been able to prove
that another such method exists nor have they been able to prove that one doesn’t
exist.*

*This is one of the most important and
famous unsolved problems in mathematics. If you can find an efficient solution to the TSP,
you will be rich and famous!!*

Although we do not have an efficient algorithm
for solving TSPs, we do have several algorithms that produce results that may not be
optimal; in this respect, we are willing to give up our requirement for an optimal
solution in the interest of time and settle for a "good" solution which may not
be optimal. We call this class of algorithms *approximate algorithms*. The remaining
algorithms are approximate algorithms.

**Cheapest
Link Algorithm (CLA)**

- Choose the edge with the smallest weight
*(the "cheapest" edge*), randomly breaking ties - Keep choosing the "cheapest" edge unless it (a) closes a smaller circuit OR (b) results in 3 selected edges coming out of a single vertex
- Continue until the Hamilton Circuit is complete

**The resulting path is a Hamilton Circuit.**

**Nearest
Neighbor Algorithm (NNA)**

- Start at a vertex
*(think of it as your Home city)* - Travel to the vertex
*(think of it as a city)*that you haven’t been to yet whose path has the smallest weight*(think of it as the closest city) (If there is a tie, pick randomly.)* - Continue until you travel to all vertices
*(cities)* - Travel back to your starting vertex
*(your Home)*

**The resulting path is a Hamilton Circuit.**

**Repetitive Nearest Neighbor Algorithm
(RNNA)**

- DO NNA for each vertex (city)
- Choose the best solution (smallest weight)
- If necessary, rewrite this solution with a particular starting vertex (Home)

**The resulting path is a Hamilton Circuit.**