216 NONDETERMINISTIC ALGORITHMS
these cities. The goal is to determine the order we should visit all of the cities
(once), returning to the starting city at the end, while minimizing the total
cost. This problem can be applied to the order streets should be visited to col-
lect garbage efficiently, deciding on the route a truck should take to make
deliveries in the shortest time possible, or choosing the routing of a packet so
that information is transmitted quickly between all nodes in a network. When
we have 8 cities, there are 40,320 possible orderings of the cities, and when
that number increases to 10 cities, there are now 3,628,800 possible orderings
of the cities. To find the most efficient route, we would have to examine all of
the possibilities. Let’s say that we have an algorithm that can calculate the cost
of traveling between a set of 15 cities in a given order. If this algorithm can do
100 of these calculations per second, it would still take over four centuries to look
at all of the possible orderings of those 15 cities to find the quickest possible
trip. Even if we had 400 computers work on this problem, it would still take
over a year, and there are only 15 cities. If we have 20 cities, it would take one
billion computers working in parallel about nine months to find the most effi-
cient route. Clearly, it is faster and cheaper to travel to all of them via any path
than to wait for the algorithm to find the shortest path.
Is it possible that we might be able to construct the shortest path without
looking at all of the possible paths? At this point, no one has been able to
devise a construction algorithm that doesn’t effectively just check all of the
potential paths. The situation where the number of cities is small could be
solved quickly, but one instance of the problem (with a restricted input) that
can be done quickly doesn’t mean that there is an algorithm that can do all
instances of the problem quickly. We are interested in the general solution to
this problem.
If you think about the traveling salesperson problem, you should see it’s
similarity to the graphs and graph algorithms that were discussed in Chapter- Each city can be represented by a node in the graph, the ability to travel
between two cities can be represented in the edges of the graph, and the cost
to travel between those cities can be the weight attached to the edge. From
this, you might be tempted to think that the shortest-path algorithm we dis-
cussed in Section 6.5 would also solve this problem, but it won’t. What are
the two requirements of the traveling salesperson problem that make it differ-
ent from the shortest-path problem? The first is that we must visit all of the
nodes and the shortest-path algorithm only tells us the quickest way to get
between two nodes. If you try to use multiple pieces that the shortest-path