Information Technology Reference
In-Depth Information
Now suppose that a salesperson starts from Des Moines. Can she or he go to
each of these cities exactly once and then return back to Des Moines? In review
ing the figure, this can be done in several ways. For example, two routes are:
1.
Des Moines
⇒
Chicago
⇒
Grand Rapids
⇒
Detroit
⇒
St. Louis
⇒
Kansas
City
⇒
Minneapolis
⇒
Des Moines
2.
Des Moines
⇒
Minneapolis
⇒
Detroit
⇒
Grand Rapids
⇒
Chicago
⇒
St. Louis
⇒
Kansas City
⇒
Des Moines
Now that we know that a specific route is possible, which route incurs the least cost?
One way to find the solution to this problem is to search through all possible
routes, compute the price of each, and then search the list of routes and prices
to find the smallest price. Such an enumeration of all possibilities is called an
ex-
haustive listing
, and a search of all options is called an
exhaustive search
.
In this approach, each possible route (or permutation of cities) might be consid
ered. In some cases, there may not be direct flights between some cities, so
some routes might not be possible (one cannot go directly from Minneapolis to
Grand Rapids, for example, so any potential route requiring this trip must be
ruled out). If airlines had flights from each city to each other city, however, then
this approach would require computing the cost for every possible route.
How many routes are there if the salesperson must go through
n
cities? The sales
person could start at home (she or he must start somewhere, so home is as good
a place as any). After that, the salesperson might go to any of the other
n
1 cities (number of total cities minus the number of cities already visited).
After that trip, the salesperson could go to any of the
n
2 remaining cities, and
so forth. With this analysis, the total number of possible routes is
(
n
1) (
n
2) (
n
3) . . . 3 2 1
In mathematics, this number is called
n
1 factorial, and written (
n
1)!.
Now suppose a computer could check 1 million routes in a second and evaluate 1)
their cost and 2) the time they require. (This speed is probably unrealistically fast, but
let's be optimistic.) To find the amount of time required for a computer to process the
routes with various numbers of cities, look at the next to last column in Table 6.2.
Computing the best (most time efficient and least expensive) route when only a few
cities are involved is fast. For example, if the salesperson had to visit 11 cities, then
n
would be 11, and our analysis indicates there would be (11 1)! or 10! factorial
routes. Looking at Table 6.2 with 10 routes to check, the computer's review of all
routes would take about 3.6 seconds—a rather short time for checking. However,
increasing the number of cities to 21 would mean 20! routes to check, and Table 6.2
indicates this would take 78,218 years to examine. We just about doubled the num
ber of cities, but the processing time went from 3.6 seconds to 78 millennia.
Clearly, creating an exhaustive list would yield a solution, but the time involved
could be substantial. It seems reasonably safe to conclude that exhaustive
searches do not scale up very well.