SECTION 2.2 Elementary Graph Theory 121
TSP: The nearest-neighbor algorithm
As indicated above, the brute-force method will always find the optimal
solution, but the amount of computing time required may be astronom-
ical (which is hardly optimal!). In this and the following sections we
shall consider two very simple algorithms which don’t necessarily find
the optimal solution but they are known to quickly find “good” solu-
tions.
The Nearest-Neighbor algorithm starts with a vertex in the
weighted graph, and then proceeds to move to the “nearest neighbor”
without prematurely returning to a previous vertex.
Example.In attempting to construct the cheapest route starting from
and returning to Chicago, we proceed as follows
- Move from Chicago to Merriville; the cost of $119 is the cheapest
among all costs involving travel from Chicago. - Move from Merriville to Joliet $120; this is the cheapest cost (other
than $119, which puts us back in Chicago). - Move from Joliet to Highland at a cost of $199.
- Move from Highland to Gary at a cost of $150.
- Return to Chicago at a cost of $185.
The total cost of the above Hamiltonian route is $773, which while not
optimal was an easy route to obtain.
Exercises
- Consider the weighted graph with vertices A, B, C, D, and E,
having weights assigned as follows
all the edge labels 1. The Ramsey number of the complete graph with six vertices is 3. In fact, one
way the above problem is often described is as follows:
Show that among six people
there must be either three mutual
friends or three mutual strangers.