We have added some cities to your interview trip. Instead of drawing a graph, we have list...

We have added some cities to your interview trip. Instead of drawing a graph, we have listed the cost between pairs of cities in a table. Again, you will start at Philadelphia, visit all the cities, and then return home. Recall that the original cities in this problem were (P)hiladelphia, (N)ew York, (A)tlanta, (M)emphis, and (C)leveland.

Finding the cheapest route. Redo Exercise; however, in addition to Raleigh and Boston, assume that we have also added (D)allas to the trip. The cost of travel between Dallas and each of the other cities is given in the following table.

Finding the cheapest route. Assume that (R)aleigh and (B)oston are to be added to the trip.

---

a. If you were to draw a graph as we did in Example 5 and then use the brute force algorithm, how many Hamilton circuits would you have to consider?

---

b. If you could examine one Hamilton circuit per minute, how many hours would it take you to solve this TSP using the brute force algorithm?

---

c. Use the nearest neighbor algorithm to find a Hamilton circuit beginning at Philadelphia.

---

d. Use the best edge algorithm to find a Hamilton circuit beginning at Philadelphia.

Solving a TSP Using Brute Force

Use Figure to find the sequence of cities for you to visit that will minimize your total travel cost.

Graph model of your possible trips. Weights on edges denote the cost of travel between cities.

SOLUTION:

Another way to state this problem is that we want to find the Hamilton circuit that has the smallest weight. For example, if you choose the circuit PMACNP, the cost of your trip will be

Our plan for a solution is simple but tedious. We will calculate the weight of each Hamilton circuit in the graph. The circuit with the smallest weight will be our solution. Because this graph has five vertices there will be 4! = 24 Hamilton circuits. However, in Table 4.3 we have listed only 12 of these circuits because clearly each circuit has the same weight as its reverse.

From Table, we see that the smallest weight is $1,200, which corresponds to the circuit PAMCNP. Thus, you should start at Philadelphia and then travel to Atlanta, Memphis, Cleveland, and New York City in that order and then return home.

Hamilton circuits and their weights.