II: Hamilton Circuits Quick Summary
(This Hamilton is Sir William
Rowan Hamilton, the great Irish mathematician and astronomer who lived from 1805 to 1865.) Euler circuits/paths are not the appropriate tool for analyzing problems where it is only important to visit each vertex. For problems of this type, whether or not an edge is traveled is not important. (Euler circuits/paths deal with situations where it is important to travel every edge.) Hamilton Circuit Unfortunately, there are no counterparts to Euler’s theorems that tell us whether or not a graph has a Hamilton Circuit. Occasionally, there are situations where the following theorem will help us determine that a graph does have a Hamilton Circuit. Dirac’s Theorem Complete Graph
In problems involving Hamilton Circuits, there are often many seemingly equivalent routes. The most important class of problems solved via Hamilton Circuits is actually when the edges connecting vertices have different weights. (For instance, it might be less expensive to travel one edge rather than a different one or perhaps the distance traveled is less.) Weighted Graph The weight of a path (or circuit) is the sum of the weights of each edge in the path (or circuit). An optimal Hamilton Circuit is one with the smallest possible weight. There may be more than one! The Traveling Salesman Problem (TSP) We will discuss several methods of ‘solving" TSPs. The Traveling Salesman Problem (TSP): Solution
Methods (Algorithms) We will discuss several methods of ‘solving" TSPs. THE BRUTE FORCE ALGORITHM
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. Approximate Algorithms (for solving TSPs)
CHEAPEST LINK ALGORITHM (CLA)
The resulting path is a Hamilton Circuit. NEAREST NEIGHBOR ALGORITHM (NNA)
The resulting path is a Hamilton Circuit. REPETITIVE NEAREST NEIGHBOR ALGORITHM (RNNA)
The resulting path is a Hamilton Circuit. |