Nearest Neighbor <- TSP Generator <- Research <- Sean Forman <- You Are Here
|
The nearest neighbor algorithm and the closely related repetitive nearest neighbor algorithm is a greedy algorithm for finding candidate solutions to the traveling salesman problem. The nearest neighbor algorithm begins at the first city in your list of cities to visit. It then selects the closest city to visit next. From the remaining unvisited cities it selects the city closest to city two and so on.
| 1 2 3 4 5 | 6 7 8
-----------------------+--------------------------------+-------------------
1 Chicago IL | 672 848 1737 954 | 1195 1850 906
2 Philadelphia PA | 672 255 2383 1368 | 1047 2520 1572
3 Boston MA | 848 255 2489 1617 | 1270 2689 1753
4 Seattle WA | 1737 2383 2489 1891 | 2732 708 1033
5 Houston TX | 954 1368 1617 1891 | 967 1615 871
-----------------------+--------------------------------+-------------------
6 Miami FL | 1195 1047 1270 2732 967 | 2565 1710
7 Palo Alto CA | 1850 2520 2689 708 1615 | 2565 952
8 Denver CO | 906 1572 1753 1033 871 | 1710 952
Beginning in Chicago, we choose the closest city, Philadelphia (2) to visit next. Once in Philly, we can't return to Chicago, but Boston (3) is closer anyway, so we go there. In Boston, we now can't go to Chicago or Philly. Continuing this way we get the route.
ROUTE BY NEAREST NEIGHBOR:
Chicago, IL -> Philadelphia, PA 672
Philadelphia, PA -> Boston, MA 255
Boston, MA -> Miami, FL 1270
Miami, FL -> Houston, TX 967
Houston, TX -> Denver, CO 871
Denver, CO -> Palo Alto, CA 952
Palo Alto, CA -> Seattle, WA 708
Seattle, WA -> Chicago, IL 1737
------
DISTANCE: 7432
In repetitive nearest neighbor, we generate a route using the nearest neighbor algorithm for each city in our list, and then select the shortest route from our choices.
DISTANCES BY NEAREST NEIGHBOR BEGINNING AT: Chicago, IL 7432 Philadelphia, PA 9503 Boston, MA 9433 Seattle, WA 8414 Houston, TX 9138 Miami, FL 9433 Palo Alto, CA 8328 Denver, CO 8328 BEST ROUTE BY REPETITIVE NEAREST NEIGHBOR: Chicago, IL 7432