Example 1

EXAMPLE 1 Vacation Planning

Let’s imagine that you are a college student studying in Chicago. During spring break, you and a group of friends have decided to take a car trip to visit other friends in Minneapolis, Cleveland, and St. Louis. there are many choices as to the order of visiting the cities and returning to Chicago, but you want to design a route that minimizes the distance you have to travel. Presumably, you also want a route that cuts costs, and you know that minimizing distance will minimize the cost of gasoline for the trip. Similar problems with different complications would arise for bus, railroad, or airplane trips.

Imagine now that the internet has provided you with the intercity driving distances between Chicago, Minneapolis, Cleveland, and St. Louis. We can construct a graph model with this information, representing each city by a vertex and the legs of the journey between the cities by edges joining the vertices. TO construct the model, we add a number called a weight to each graph edge, as in Figure 2.3. In this example, the weights represent the distances between the cities, each of which corresponds to one of the endpoints of the edges in the graph. (in other examples the weight might represent a cost, time, satisfaction rating, or profit.) We want to find a minimum-cost tour that starts and ends in Chicago and visits each other city only once. Using our earlier terminology, what we wish to find is a minimum-cost Hamiltonian circuit—a Hamiltonian circuit with the lowest possible sum of the weights of its edges.

Steps 2 and 3 of the algorithm are straightforward. thus, we need worry only about Step 1, generating all the possible Hamiltonian circuits in a systematic way. TO find the Hamiltonian tours, we use the method of trees, as follows: Starting from Chicago, we can choose any of the three cities to visit after leaving Chicago. The first stage of the enumeration tree is shown in Figure 2.4. if Minneapolis is chosen as the first city to visit, then there are two possible cities to visit next, Cleveland and St. Louis. the possible branchings of the tree at this stage are shown in Figure 2.5. In this second stage, however, for each choice of first city to visit, there are two choices from this city to the second city to visit. This would lead to the diagram in Figure 2.6.

Figure 2.3: Figure 2.3 Road mileages between four cities.

Finding a Minimum-Cost Hamiltonian Circuit PROCEDURE

How can we determine which Hamiltonian circuit has minimum cost? There is a conceptually easy algorithm, or a step-by-step process like a recipe in cooking, for solving this problem:

Generate all possible Hamiltonian tours (starting from Chicago).
Add up the distances on the edges of each tour.
Choose a tour with total distance being a minimum, that is, as small as possible.

Figure 2.4: Figure 2.4 First stage in finding vacation-planning routes.

Figure 2.5: Figure 2.5 Part of the second stage in finding vacation-planning routes.

Figure 2.6: Figure 2.6 Complete second stage in finding vacation- planning routes.

Having chosen the order of the first two cities to visit, and knowing that no revisits (reuses) can occur in a Hamiltonian circuit, we have only one choice left for the next city. From this city, we return to Chicago. The complete tree diagram showing the third and fourth stages for these routes is given in Figure 2.7. Notice, however, that because we can traverse a circular tour in either of two directions, the paths shown in the tree diagram of Figure 2.7 do not correspond to different Hamiltonian circuits. For example, the leftmost path (C–M–S–CL–C) and the rightmost path (C–CL–S–M–C) represent the same Hamiltonian circuit. Thus, among what appear to be six different paths in the tree diagram, only three in fact correspond to different Hamiltonian circuits. These three distinct Hamiltonian circuits are shown in Figure 2.8.

Figure 2.7: Figure 2.7 Completed enumeration of routes using the method of trees for the vacation-planning problem.

Figure 2.8: Figure 2.8 The three Hamiltonian circuits for the vacation-planning problem of Figure 2.3.

Note that in generating the Hamiltonian circuits, we disregard the distances involved. We are concerned only with the different patterns of carrying out the visits. To find the optimal, or best, route, however, we must add up the distances on the edges to get each tour’s length and select a tour whose total length is smallest. Figure 2.8 shows that the optimal tour is Chicago, Minneapolis, St. Louis, Cleveland, Chicago. The length of this tour is 1877 miles, which saves 163 miles over the longest choice of tour.