Java Reference
In-Depth Information
2
A
B
6
3
3
2
1
8
E
C
4
1
1
D
Figure17.4
An illustration of the TRAVELING SALESMAN problem. Five
vertices are shown, with edges between each pair of cities. The problem is to visit
all of the cities exactly once, returning to the start city, with the least total cost.
Figure 17.4 illustrates this problem. Five vertices are shown, with edges and
associated costs between each pair of edges. (For simplicity Figure 17.4 shows an
undirected graph, assuming that the cost is the same in both directions, though this
need not be the case.) If the salesman visits the cities in the order ABCDEA, he
will travel a total distance of 13. A better route would be ABDCEA, with cost 11.
The best route for this particular graph would be ABEDCA, with cost 9.
We cannot solve this problem in polynomial time with a guess-and-test non-
deterministic computer. The problem is that, given a candidate cycle, while we can
quickly check that the answer is indeed a cycle of the appropriate form, and while
we can quickly calculate the length of the cycle, we have no easy way of knowing
if it is in fact the shortest such cycle. However, we can solve a variant of this
problem cast in the form of a decision problem. A decision problem is simply one
whose answer is either YES or NO. The decision problem form of TRAVELING
SALESMAN is as follows:
TRAVELING SALESMAN (2)
Input: A complete, directed graph G with positive distances assigned to
each edge in the graph, and an integer k.
Output: YES if there is a simple cycle with total distance k containing
every vertex in G, and NO otherwise.
We can solve this version of the problem in polynomial time with a non-deter-
ministic computer. The non-deterministic algorithm simply checks all of the pos-
sible subsets of edges in the graph, in parallel. If any subset of the edges is an
appropriate cycle of total length less than or equal to k, the answer is YES; oth-
erwise the answer is NO. Note that it is only necessary that some subset meet the
requirement; it does not matter how many subsets fail. Checking a particular sub-
set is done in polynomial time by adding the distances of the edges and verifying
that the edges form a cycle that visits each vertex exactly once. Thus, the checking
algorithm runs in polynomial time. Unfortunately, there are 2
jEj
subsets to check,
