Nick is a traveling salesman. His territory consists of the 11 cities shown on the mileage chart in Fig. 6-54. Nick must find a tour that starts and ends in Dallas (that's his home) and visits each of the other 10 cities.
(a) Find a nearest-neighbor tour that starts at Dallas.
(b) Find the cheapest-link tour.
Mileage Chart
|
Atlanta |
Boston |
Buffalo |
Chicago |
Columbus |
Dallas |
Denny |
Houston |
Kansas City |
Lotusville |
Memphis |
| Atlanta |
* |
1037 |
859 |
674 |
533 |
795 |
1398 |
789 |
798 |
382 |
371 |
| Boston |
1037 |
* |
446 |
963 |
735 |
1748 |
1949 |
1804 |
1391 |
941 |
1293 |
| Buffalo |
859 |
446 |
* |
522 |
326 |
1346 |
1508 |
1460 |
966 |
532 |
899 |
| Chicago |
674 |
963 |
522 |
* |
308 |
9i7 |
996 |
1067 |
499 |
292 |
530 |
| Columbus |
533 |
735 |
326 |
308 |
* |
1028 |
1229 |
1137 |
656 |
209 |
576 |
| Dallas |
795 |
1748 |
1346 |
917 |
1028 |
* |
781 |
243 |
439 |
829 |
452 |
| Denny |
1398 |
1949 |
1508 |
996 |
1229 |
787 |
* |
1019 |
600 |
1.12 |
1040 |
| Houston |
789 |
1804 |
1460 |
1067 |
1137 |
243 |
1019 |
* |
710 |
923 |
561 |
| Kansas City |
798 |
1391 |
966 |
499 |
656 |
489 |
600 |
710 |
* |
520 |
451 |
| Lotusville |
382 |
941 |
532 |
292 |
209 |
819 |
1120 |
923 |
520 |
* |
367 |
| Memphis |
371 |
1293 |
899 |
530 |
576 |
452 |
1040 |
501 |
451 |
367 |
* |