Nearest Neighbor   <-   TSP Generator   <-   Research   <-   Sean Forman   <-   You Are Here

Explanation of the Nearest Neighbor Algorithm

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.

For example

                       |     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