Outer Limits of Reason (23 page)

Since we have been learning about graphs, we might represent the same information with the graph in
figure 5.9
.

The number on each edge represents the distance between the cities. Such a graph is called a
weighted
graph because the edges are given weights. Since there is an edge between every two vertices, we also call this graph
complete
.

The question is which route through all the cities is the shortest? One method of going about this is to pick one possible route through all six cities, add up all the distances between the cities (don't forget to come back to the starting place), and see what that total is. Once that is done, try another possible route, sum up all of its distances, and see if it is shorter. To ensure that you have the shortest route, one would have to make a brute-force search through
all
possible routes.

How many possible routes are there to check? We have to search through all the possible orders or permutations of six cities. Let us count how many permutations there are. There are six possible cities where you can start. Once you are in the first city, since you do not want to return to that city, there are five possibilities for a second city. There are four possible cities for the next destination on your trip. Continuing this way, we find that the number of possible routes that you must search through is

6 × 5 × 4 × 3 × 2 × 1 = 720.

That's a lot of work,
⁴
but with modern computers, going through all 720 possible routes can be done in microseconds.

Let us examine this problem from a somewhat more general perspective. Imagine that our traveler wanted to visit
n
cities. We can visualize this problem as a graph with
n
vertices. Between any two vertices there will be a weighted edge representing the distance between the two cities. So we are given a complete, weighted graph with
n
vertices and we are interested in the shortest route that hits every city (vertex) exactly once and returns to the starting city. Using the same reasoning as above: there are
n
possible first cities,
n
– 1 possible second cites, . . . . In conclusion, the number of possible routes that must be checked is

n
× (
n
– 1) × (
n
– 2) ×···× 2 × 1

We write this number as
n
! and call this function “
n
factorial.” The amazing fact about this function is that as
n
gets larger,
n
! grows unbelievably larger.

Let us roll up our sleeves and do a little calculating. For
n
= 100, how many routes are there and how long would it take for a reasonable computer to search through all of those possible routes? We would need to calculate 100!. We can do this by sitting down and multiplying 100 times 99 times 98 times . . . times 3 times 2 times 1. Or, we can just cheat and type it into the fancy scientific calculator that comes with every computer. We obtain the following result:

100! = 93,326,215,443,944,152,681,699,238,856,266,700,490,715,968,264,381,621,468,592,963,895,217,599,993,229,915,608,941,463,976,156,518,286,253,697,920,827,223,758,251,185,210,916,864,000,000,000,000,000,000,000,000.

Before your head starts spinning, let's look at this number for a minute. It consists of a 9 followed by 157 digits. A very large number called a
googol
is a 1 followed by 100 zeros.
⁵
Our number is much larger than a googol. It is an unimaginably large number.

For each of these potential routes, we would have to add up the distances between the 100 cities and compare the sum to the shortest distance that was already found. Imagine that we have a computer that can check a million routes in a second. Then dividing 100! by a million gives us

93,326,215,443,944,152,681,699,238,856,266,700,490,715,968,264,381,621,468,592,963,895,217,599,993,229,915,608,941,463,976,156,518,286,253,697,920,827,223,758,251,185,210,916,864,000,000,000,000,000,000 seconds.

To find out how many minutes this would take, we must further divide by 60 to get

1,555,436,924,065,735,878,028,320,647,604,445,008,178,599,471,073,027,024,476,549,398,253,626,666,553,831,926,815,691,066,269,275,304,770,894,965,347,120,395,970,853,086,848,614,400,000,000,000,000,000 minutes.

Dividing again by 60 will give us

25,923,948,734,428,931,300,472,010,793,407,416,802,976,657,851,217,117,074,609,156,637,560,444,442,563,865,446,928,184,437,821,255,079,514,916,089,118,673,266,180,884,780,810,240,000,000,000,000,000 hours.

A simple division by 24 gives us

1,080,164,530,601,205,470,853,000,449,725,309,033,457,360,743,800,713,211,442,048,193,231,685,185,106,827,726,955,341,018,242,552,294,979,788,170,379,944,719,424,203,532,533,760,000,000,000,000, 000 days.

Shall we continue? Dividing by 365 gives us

2,959,354,878,359,467,043,432,877,944,452,901,461,527,015,736,440,310,168,334,378,611,593,658,041,388,569,114,946,139,776,006,992,588,985,721,014,739,574,573,764,941,185,024,000,000,000,000,000 years.

Dividing by 100, we get

29,593,548,783,594,670,434,328,779,444,529,014,615,270,157,364,403,101,683,343,786,115,936,580,413,885,691,149,461,397,760,069,925,889,857,210,147,395,745,737,649,411,850,240,000,000,000,000 centuries.

That is 2.9 × 10
¹⁴²
centuries. That is a very long time. That is a
shockingly
long time!

A moment of meditation is in order. The Traveling Salesman Problem is a seemingly simple problem that can be explained to any elementary school student and for small inputs can be performed by everyone in seconds. But when the inputs get larger, the number of operations required is immense. Yes, a solution to the problem is possible, but there is no way we can say that a computer can “solve” this problem in a reasonable amount of time.

A problem in which we are given an input and asked to find the shortest or longest or best solution, is called an
optimization problem
. Many problems that computers solve are optimization problems. The Traveling Salesman Problem, like all the other problems that I will mention in the rest of this chapter, also comes in another form called a
decision problem
. A decision problem is one in which the computer is only required to give a yes or no answer. Such problems are not concerned with the shortest, longest, or best solutions. Rather, they are only concerned if a solution of a certain type exists. For example, an optimization problem would be concerned with determining the speed of the fastest runner in the United States. The related decision problem might be, “Can any runner in the United States run a mile in under 3.5 minutes?” Such a question demands a yes or no answer.

The traveling salesman problem in its decision-problem form is as follows: given a complete weighted graph and an integer
K
, tell whether or not there is a path through every vertex whose sum total of all the distances of the trip is less than or equal to
K
. If there is a route that is less than or equal to
K
, answer yes. If not, answer no. Notice that we are not required to find the route. It is worth mentioning that a decision problem has the potential to end sooner than an optimization problem. In a decision problem, if we find what we are looking for, we stop there and answer yes. By contrast, an optimization problem would have to examine all possible routes in its search for the best. Nevertheless, our major concern in this section and the next will be decision problems.

The traveling salesman problem must be seen as a limitation of the human ability to know. There is no way that one can possibly know the shortest route to take in a reasonably sized problem.

Hamiltonian Cycle Problem

This problem is also concerned with finding paths through a given graph. For a graph (we do not require that it be weighted or complete), we are to find a continuous path in the graph that hits every vertex exactly once and returns to the starting place. Such a cycle is called a
Hamiltonian cycle
. The decision version of the Hamiltonian Cycle Problem is to determine whether a Hamiltonian cycle exists for a given graph. There are many real-world applications of this problem. For example, a bus driver can be given a map of a city and told to pick up students at the given vertices. Can the driver make this trip without crossing any vertex twice? Consider the two graphs in
figure 5.10
.

In the graph on the left, one can simply start at any vertex and go either clockwise or counterclockwise to obtain a Hamiltonian cycle. In contrast, try to find such a cycle in the graph on the right. (There is none.)

One way of solving this decision problem is to attempt a brute-force search through all possible permutations in a given graph. For every permutation, check to see whether it makes a connected path in the graph. For a graph of size
n,
there are
n
! possible permutations. As we saw with the traveling salesman problem, this is far from satisfactory. There is simply not enough time to solve this problem for any moderately large input. Can we do any better than an
n
! algorithm?

There is a certain similarity between the Hamiltonian cycle problem and the Euler Cycle Problem. In each case we are given a graph and are looking for a cycle. In the Hamiltonian Cycle Problem we are looking for a cycle that hits every vertex exactly once, whereas in the Euler Cycle Problem we are looking for one that hits every edge exactly once. In the last section, we saw that Euler taught us a cool trick to determine if an Euler cycle exists on a given graph: simply make sure the number of edges that touch every vertex is even. Is there a similar trick that tells whether a Hamiltonian cycle exists for a given graph? Unfortunately, your humble author does not know any such trick, and neither does anyone else. At this time, the only way to be absolutely certain of the existence of a Hamiltonian cycle in a given graph of
n
vertices is to perform a brute-force search through all
n
! possible cycles. So although the two problems are similar, one is easily solvable and the other seems to be very hard. Each problem presented to us must be examined carefully.

Just because we do not know of any better algorithm than a brute-force search does not mean that no such algorithm exists. Someone might come up with one at some point. However, in the next section, I show why most researchers believe that no such algorithm exists at all.

Set Partition Problem

Say we have a class of students whose ages are {18, 23, 27, 65, 22, 25, 19, 21}. We want to split them into two groups with equal years of “life experience.” A little tinkering shows that the groups {18, 27, 65} and {23, 22, 25, 19, 21} will do; both groups have a sum of 110. The Set Partition Problem generalizes this example. Given a set of positive whole numbers, determine if they can be partitioned, or split, into two sets such that the sum of all numbers in one set is the same as the sum of all numbers in the other set.

Let us look at some other instances of this problem. How about the set {18, 23, 28, 65, 22, 25, 19, 21}? The numbers are almost exactly alike except that instead of a twenty-seven-year-old, we now have a twenty-eight-year-old. Some thought shows that this set cannot be split into two equal parts. In the last example, the sum of all the numbers was 220, and we were able to split them into two sets, each containing 110. In this example, the sum of all the numbers is 221. There is no way to divide the odd number 221 into two equal whole-number parts. So one way to determine that there is no solution is to add up all of the numbers and see if the result is odd. If odd, we are certain that no possible solution exists. But what if the sum is even?

Consider the set {30, 4, 32}. The sum of these three numbers is 66, which is even. However, it is obvious that there is no way to partition this set into two equal parts. So our trick of seeing if the sum of all the numbers is odd or even does not always work. The sum can be even but the numbers still cannot be partitioned into two equal parts.