---

---

The Salesperson's Journey

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 better routes.