Cheapest Link <- TSP Generator <- Research <- Sean Forman <- You Are Here
|
The cheapest link algorithm is a greedy algorithm for finding candidate solutions to the traveling salesman problem. The cheapest link algorithm begins by choosing the route that is the shortest distance between any two cities. It continues by choosing the next shortest link between any two cities. After the first two links, you must make certain that no link closes the loop until all of the cities are connected. This method can at times find the best overall solution, but it is not guaranteed to.
| 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
The shortest link is 255 between Boston and Philadelphia. The next shortest is between Philadelphia and Chicago (672). The next shortest is between Palo Alto and Seattle (708). The next shortest is 848 between Boston and Chicago, but this would lead to a loop between Philadelphia, Boston, and Chicago, so we can't choose that link. Going to the next longest we add the 871 link between Houston and Denver. We continue until we've added 8 total links.
ROUTE FOUND BY CHEAPEST LINK:
Chicago, IL -> Philadelphia, PA 672
Philadelphia, PA -> Boston, MA 255
Boston, MA -> Seattle, WA 2489
Seattle, WA -> Palo Alto, CA 708
Palo Alto, CA -> Miami, FL 2565
Miami, FL -> Houston, TX 967
Houston, TX -> Denver, CO 871
Denver, CO -> Chicago, IL 906
------
DISTANCE: 9433