An exponential algorithm becomes intractable quickly.
CHAP. 2] ALGORITHMS 23
For instance, solving the problem for a matrix of 20 entries will require about a million units of time, but solving
the problem for a matrix of 50 entries will require about a million billion units of time. If a unit of time is a millionth
of a second, the problem of size 20 will require a second to compute, but the problem of size 50 will require
more than 25 years. The ALFRED database is of size 494 ??— 1600 = 790,400. Students hoping to graduate need
a better algorithm or a different problem!
Another example of an intractable problem is the famous traveling salesman problem. This problem is
so famous it has its own acronym, TSP. The salesman needs to visit each of several cities, and wants to do so
without visiting any city more than once. In the interest of efficiency, the salesman wants to minimize the length
of the trip.
The salesman must visit each city, but he can visit the cities in any order. Finding the shortest route requires
computing the total distance for each permutation of the cities the salesman must visit, and selecting the shortest
one. Actually, since a route in one direction is the same distance as the reverse route, only half of the permutations
of cities need to be calculated.
Pages:
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72