TRAVELING SALESMAN PROBLEM
Tour Construction Algorithms
Nearest Neighbor Algorithm
(Rosenkrantz, Stearns, Lewis, 1974)
- Step 1. Start with any node as the beginning node
- Step 2. Find the unvisited node closest to the last node added to the
path. Add this node to the path.
- Step 3. Repeat Step 2 until all nodes are contained in the
path. Then join the first and last nodes.
Worst Case Behavior:
where 
denotes the greatest integer smaller
than or equal to x.
Number of Computations:
The nearest neighbor algorithm is 
("order
n square"), that is, the number of computations that it requires
will not gorw faster than 
.
Note:
A modified application of Nearest Neighbor Algorithm is starting
from each of the nodes in order, and seeing which starting node
gives the best result. However, this modified algorithm is
.
