Discrete Mathematics for Computer Science

422 CHAPTER 7 Counting and Combinatorics

basis. Between each pair of cities, air service is available. The problem is to schedule a

sequence of flights that visits each city exactly once before returning to the starting point

so that the total time spent flying is minimized.

A naive algorithm for the solution of the problem uses three steps.

STEP 1: Find all possible routes.

STEP 2: Find the travel time for each route found in Step 1.

STEP 3: Choose a route with travel time equal to the minimum

of the travel times calculated in Step 2.

Example 1 carries out the steps of this algorithm for a set of four cities.

Example 1. Find a best route for visiting the four cities with the travel times given. The

entry in row I and column J is the time to travel either from city I to city J or from city

J to city I. Edges indicate direct air service between cities. The number on an edge gives

the distance for a flight between the two cities that are the ends of the edge.

8 1 2 3 4

1 - 18 30 16

"16 30 31 2 3-- -^31 1917

19 ~4-

17

Solution.

Step 1: Find all possible routes.

1-2-3-4-1

1-2-4-3-1

1-3-2-4-1

1-4-3-2-1

1-3-4-2-1

1-4-2-3-1

Step 2: Calculate the travel time for each route.

1-2-3-4-1 :18 + 31 + 17 + 16 = 82

1-2-4-3-1 :18 + 19 + 17 + 30 = 84

1-3-2-4-1 :30 + 31 + 19 + 16 = 96

1-4-3-2-1 :16 + 17 + 31 + 18 = 82

1-3-4-2-1 : 30 + 17 + 19 + 18 = 84

1-4-2-3-1 :16 + 19 + 31 + 30 = 96

Step 3: Choose a minimum-distance route.

1-2-3-4-1 : 18 + 31 + 17 + 16 = 82

A more general description of a solution for n cities gives insight regarding the number

of operations required to find a solution. Assume that n cities need to be visited and that one