The following table presents the airplane fares (in dollars) among pairs of seven cities. A salesperson needs to visit each of the cities at least once. Find the minimum fare for the salesperson to visit each city at least once and return to the home city. In otherwords, assuming the salesperson lives in NYC, what travel route should be followed to visit each city at least once and return home?
| ATL | CHI | MIA | STL | DLS | SF | NYC | |
| ATL | 0 | 153 | 152 | 136 | 174 | 411 | 177 |
| CHI | 153 | 0 | 239 | 87 | 204 | 368 | 204 |
| MIA | 152 | 239 | 0 | 224 | 247 | 394 | 227 |
| STL | 136 | 87 | 224 | 0 | 148 | 336 | 216 |
| DLS | 174 | 204 | 247 | 148 | 0 |
283 | 264 |
| SF | 411 | 368 | 394 | 336 | 283 | 0 | 478 |
| NYC | 177 | 204 | 227 | 216 | 264 | 478 | 0 |
Does it matter which city is the home city? Does a map help to understand the problem? With seven cities we probably are not wanting to do an exhaustive calculation of all possible routes, but rather we need a heuristic search for an algorithm that gives the "best" route, or at least one of the better routes.
Taken from a problem presented in a TWA travel magazine many years ago.