122 CHAPTER 2 Discrete Mathematics
A B C D E
A * 20 23 19 17
B * 20 25 18
C * 24 19
D * 23
E *Use the Nearest-Neighbor algo-
rithm to find a Hamiltonian cycle
starting at vertex A. What is the
total weight of this Hamiltonian cy-
cle?- Use the Nearest-Neighbor algorithm to find a Hamiltonian cycle
starting at vertex A. What is the resulting total weight of this
cycle?
A B C D E F
A 4.7 5.1 3.6 1.1 0.8
B 0.6 8.2 5.7 5.2
C 8.1 5.9 5.6
D 3.2 3.1
E 1.5
F - There is a variation of the Nearest-Neighbor Algorithm which in-
creases the computation time by a factor of the number of ver-
tices of the weighted graph. This might seem stiff, but this added
time pales by comparison with the time required to carry out the
Brute-Force method. Namely, for each vertex of the weighted
graph compute the Hamiltonian cycle constructed by the Nearest-
Neighbor Algorithm, and then take the Hamiltonian cycle of least
total weight. This is called the Repetitive Nearest-Neighbor
algorithm. Do this for the above weighted graph consisting of
travel among the given five Midwestern cities.
TSP: The cheapest-link algorithm
There is a alternative algorithm—theCheapest-Linkalgorithm which
efficiently computes a relatively cheap Hamiltonian cycle in a weighted
graph. This is easy to describe, as follows.
In the weighted graph start by choosing the edge of minimal weight
(the “cheapest link”). Next choose the next cheapest link, and so on.