chap37.htm

程序设计的艺术,此书是英文版的,经久不衰,非常的经典

<h2><a name="0a1c_1d3c">37.2.1 The traveling-salesman problem with triangle inequality<a name="0a1c_1d3c"></h2><P>
<a name="0a1c_1d37"><a name="0a1c_1d38">The following algorithm computes a near-optimal tour of an undirected graph <I>G</I>, using the minimum-spanning-tree algorithm MST-<FONT FACE="Courier New" SIZE=2>PRIM</FONT> from Section 24.2. We shall see that when the cost function satisfies the triangle inequality, the tour that this algorithm returns is no worse than twice as long as an optimal tour.<P>
<pre><a name="0a1c_1d39">APPROX-TSP-TOUR(<I>G, c</I>)</sub></sup></pre><P>
<pre>1 select a vertex <I>r</I> <img src="../images/memof12.gif"> <I>V</I>[<I>G</I>] to be a &quot;root&quot; vertex</sub></sup></pre><P>
<pre>2 grow a minimum spanning tree <I>T</I> for <I>G</I> from root <I>r</I></sub></sup></pre><P>
<pre>using MST-PRIM(<I>G, c, r</I>)</sub></sup></pre><P>
<pre>3 let <I>L</I> be the list of vertices visited in a preorder tree walk of <I>T</I></sub></sup></pre><P>
<pre>4 <B>return</B> the hamiltonian cycle <I>H</I> that visits the vertices in the order <I>L</I></sub></sup></pre><P>
Recall from Section 13.1 that a preorder tree walk recursively visits every vertex in the tree, listing a vertex when it is first encountered, before any of its children are visited.<P>
Figure 37.2 illustrates the operation of <FONT FACE="Courier New" SIZE=2>APPROX</FONT>-TSP-<FONT FACE="Courier New" SIZE=2>TOUR</FONT>. Part (a) of the figure shows the given set of vertices, and part (b) shows the minimum spanning tree <I>T</I> grown from root vertex <I>a</I> by MST-<FONT FACE="Courier New" SIZE=2>PRIM</FONT>. Part (c) shows how the vertices are visited by a preorder walk of <I>T</I>, and part (d) displays the corresponding tour, which is the tour returned by <FONT FACE="Courier New" SIZE=2>APPROX</FONT>-TSP-<FONT FACE="Courier New" SIZE=2>TOUR</FONT>. Part (e) displays an optimal tour, which is about 23% shorter.<P>
The running time of <FONT FACE="Courier New" SIZE=2>APPROX</FONT>-TSP-<FONT FACE="Courier New" SIZE=2>TOUR</FONT> is <img src="../images/bound.gif">(<I>E</I>) = <img src="../images/bound.gif">(<I>V</I><SUP>2</SUP>), since the input is a complete graph (see Exercise 24.2-2). We shall now show that if the cost function for an instance of the traveling-salesman problem satisfies the triangle inequality, then <FONT FACE="Courier New" SIZE=2>APPROX</FONT>-TSP-<FONT FACE="Courier New" SIZE=2>TOUR</FONT> returns a tour whose cost is not more than twice the cost of an optimal tour.<P>
<a name="0a1c_1d3d">Theorem 37.2<a name="0a1c_1d3d"><P>
<FONT FACE="Courier New" SIZE=2>APPROX</FONT>-TSP-<FONT FACE="Courier New" SIZE=2>TOUR</FONT> is an approximation algorithm with a ratio bound of 2 for the traveling-salesman problem with triangle inequality.<P>
<I><B>Proof     </I></B>Let <I>H</I>* denote an optimal tour for the given set of vertices. An equivalent statement of the theorem is that <I>c</I>(<I>H</I>) <img src="../images/lteq12.gif"> 2<I>c</I>(<I>H</I>*), where <I>H</I> is the tour returned by <FONT FACE="Courier New" SIZE=2>APPROX</FONT>-TSP-<FONT FACE="Courier New" SIZE=2>TOUR</FONT>. Since we obtain a spanning tree by deleting any edge from a tour, if <I>T</I> is a minimum spanning tree for the given set of vertices, then<P>
<pre><I>c</I>(<I>T</I>) <img src="../images/lteq12.gif"> <I>c</I>(<I>H</I>*) .</sub></sup></pre><P>
<h4><a name="0a1c_1d3e">(37.4)<a name="0a1c_1d3e"></sub></sup></h4><P>
<a name="0a1c_1d3a">A<I><B> full walk</I></B> of <I>T</I> lists the vertices when they are first visited and also whenever they are returned to after a visit to a subtree. Let us call this walk <I>W</I>. The full walk of our example gives the order<P>
<pre><I>a, b, c, b, h, b, a, d, e, f, e, g, e, d, a.</I></sub></sup></pre><P>
Since the full walk traverses every edge of <I>T</I> exactly twice, we have<P>
<pre><I>c</I>(<I>W</I>) = 2<I>c</I>(<I>T</I>) .</sub></sup></pre><P>
<h4><a name="0a1c_1d3f">(37.5)<a name="0a1c_1d3f"></sub></sup></h4><P>
Equations (37.4) and (37.5) imply that<P>
<pre><I>c</I>(<I>W</I>) <img src="../images/lteq12.gif"> 2<I>c</I>(<I>H</I>*),</sub></sup></pre><P>
<h4><a name="0a1c_1d40">(37.6)<a name="0a1c_1d40"></sub></sup></h4><P>
and so the cost of <I>W</I> is within a factor of 2 of the cost of an optimal tour.<P>
<img src="971_a.gif"><P>
<h4><a name="0a1c_1d41">Figure 37.2 The operation of <FONT FACE="Courier New" SIZE=2>APPROX-TSP-TOUR</FONT>. (a) The given set of points, which lie on vertices of an integer grid. For example, f is one unit to the right and two units up from h. The ordinary euclidean distance is used as the cost function between two points. (b) A minimum spanning tree T of these points, as computed by MST-<FONT FACE="Courier New" SIZE=2>PRIM</FONT>. Vertex a is the root vertex. The vertices happen to be labeled in such a way that they are added to the main tree by MST-<FONT FACE="Courier New" SIZE=2>PRIM</FONT> in alphabetical order. (c) A walk of T, starting at a. A full walk of the tree visits the vertices in the order a, b, c, b, h, b, a, d, e, f, e, g, e, d, a. A preorder walk of T lists a vertex just when it is first encountered, yielding the ordering a, b, c, h, d, e, f, g. (d) A tour of the vertices obtained by visiting the vertices in the order given by the preorder walk. This is the tour H returned by <FONT FACE="Courier New" SIZE=2>APPROX-TSP-TOUR</FONT>. Its total cost is approximately 19.074. (e) An optimal tour H* for the given set of vertices. Its total cost is approximately 14.715.<a name="0a1c_1d41"></sub></sup></h4><P>
<a name="0a1c_1d3b">Unfortunately, <I>W</I> is generally not a tour, since it visits some vertices more than once. By the triangle inequality, however, we can delete a visit to any vertex from <I>W</I> and the cost does not increase. (If a vertex <I>v</I> is deleted from <I>W</I> between visits to <I>u</I> and <I>w</I>, the resulting ordering specifies going directly from <I>u</I> to <I>w</I>.) By repeatedly applying this operation, we can remove from <I>W</I> all but the first visit to each vertex. In our example, this leaves the ordering<P>
<pre><I>a, b, c, h, d, e, f, g .</I></sub></sup></pre><P>
This ordering is the same as that obtained by a preorder walk of the tree <I>T</I>. Let <I>H</I> be the cycle corresponding to this preorder walk. It is a hamiltonian cycle, since every vertex is visited exactly once, and in fact it is the cycle computed by <FONT FACE="Courier New" SIZE=2>APPROX</FONT>-TSP-<FONT FACE="Courier New" SIZE=2>TOUR</FONT>. Since <I>H</I> is obtained by deleting vertices from the full walk <I>W</I>, we have<P>
<pre><I>c</I>(<I>H</I>) <img src="../images/lteq12.gif"> <I>c</I>(<I>W</I>).</sub></sup></pre><P>
<h4><a name="0a1c_1d42">(37.7)<a name="0a1c_1d42"></sub></sup></h4><P>
Combining inequalities (37.6) and (37.7) completes the proof.       <P>
In spite of the nice ratio bound provided by Theorem 37.2, <FONT FACE="Courier New" SIZE=2>APPROX</FONT>-TSP-<FONT FACE="Courier New" SIZE=2>TOUR</FONT> is usually not the best practical choice for this problem. There are other approximation algorithms that typically perform much better in practice (see the references at the end of this chapter).<P>
<P>







<h2><a name="0a1d_0001">37.2.2 The general traveling-salesman problem<a name="0a1d_0001"></h2><P>
If we drop the assumption that the cost function <I>c</I> satisfies the triangle inequality, good approximate tours cannot be found in polynomial time unless P = NP.<P>
<a name="0a1d_0002">Theorem 37.3<a name="0a1d_0002"><P>
If P <img src="../images/noteq.gif"> NP and <img src="../images/rho12.gif"> <img src="../images/gteq.gif"> 1, there is no polynomial-time approximation algorithm with ratio bound <img src="../images/rho12.gif"> for the general traveling-salesman problem.<P>
<I><B>Proof     </I></B>The proof is by contradiction. Suppose to the contrary that for some number <img src="../images/rho12.gif"> <img src="../images/gteq.gif"> 1, there is a polynomial-time approximation algorithm <I>A</I> with ratio bound <img src="../images/rho12.gif">. Without loss of generality, we assume that <img src="../images/rho12.gif"> is an integer, by rounding it up if necessary. We shall then show how to use <I>A</I> to solve instances of the hamiltonian-cycle problem (defined in Section 36.5.5) in polynomial time. Since the hamiltonian-cycle problem is NP-complete, by Theorem 36.14, solving it in polynomial time implies that P = NP, by Theorem 36.4.<P>
Let <I>G</I> = (<I>V, E</I>) be an instance of the hamiltonian-cycle problem. We wish to determine efficiently whether <I>G</I> contains a hamiltonian cycle by making use of the hypothesized approximation algorithm <I>A</I>. We turn <I>G</I> into an instance of the traveling-salesman problem as follows. Let <I>G</I>' = (<I>V, E</I>') be the complete graph on <I>V</I>; that is,<P>
<pre><I>E</I>' = {(<I>u, v</I>): <I>u, v </I><img src="../images/memof12.gif"> <I>V</I> and <I>u</I> <img src="../images/noteq.gif"> <I>v</I>}.</sub></sup></pre><P>
Assign an integer cost to each edge in <I>E</I>' as follows:<P>
<img src="973_a.gif"><P>
Representations of <I>G</I>' and <I>c</I> can be created from a representation of <I>G</I> in time polynomial in |<I>V</I>| and |<I>E</I>|.<P>
Now, consider the traveling-salesman problem (<I>G</I>',<I> c</I>). If the originalgraph <I>G</I> has a hamiltonian cycle <I>H</I>, then the cost function <I>c</I> assigns to each edge of <I>H</I> a cost of 1, and so (<I>G</I>',<I> c</I>) contains a tour of cost |<I>V</I>| On the other hand, if <I>G</I> does not contain a hamiltonian cycle, then any tour of <I>G</I>' must use some edge not in <I>E</I>. But any tour that uses an edge not in <I>E</I> has a cost of at least<P>
<pre>(<img src="../images/rho12.gif"> |<I>V</I>| + 1) + (|<I>V</I>| - 1) &gt; <img src="../images/rho12.gif"> |<I>V</I>| .</sub></sup></pre><P>
Because edges not in <I>G</I> are so costly, there is a large gap between the cost of a tour that is a hamiltonian cycle in <I>G</I> (cost |<I>V</I>|) and the cost of any other tour (cost greater than <img src="../images/rho12.gif">|<I>V</I>|).<P>
What happens if we apply the approximation algorithm <I>A</I> to the traveling-salesman problem (<I>G</I>',<I> c</I>)? Because <I>A</I> is guaranteed to return a tour of cost no more than <img src="../images/rho12.gif"> times the cost of an optimal tour, if <I>G</I> contains a hamiltonian cycle, then <I>A</I> must return it. If <I>G</I> has no hamiltonian cycle, then <I>A</I> returns a tour of cost more than <img src="../images/rho12.gif">|<I>V</I>|<I>.</I> Therefore, we can use <I>A</I> to solve the hamiltonian-cycle problem in polynomial time.      <P>
<P>







<h2><a name="0a1e_1d3f">Exercises<a name="0a1e_1d3f"></h2><P>
<a name="0a1e_1d40">37.2-1<a name="0a1e_1d40"><P>
Show how in polynomial time we can transform one instance of the traveling-salesman problem into another instance whose cost function satisfies the triangle inequality. The two instances must have the same set of optimal tours. Explain why such a polynomial-time transformation does not contradict Theorem 37.3, assuming that P <img src="../images/noteq.gif"> NP.<P>
<a name="0a1e_1d41">37.2-2<a name="0a1e_1d41"><P>
<a name="0a1e_1d3c">Consider the following <I><B>closest-point heuristic</I> </B>for building an approximate traveling-salesman tour. Begin with a trivial cycle consisting of a single arbitrarily chosen vertex. At each step, identify the vertex <I>u</I> that is not on the cycle but whose distance to any vertex on the cycle is minimum. Suppose that the vertex on the cycle that is nearest <I>u</I> is vertex <I>v</I>. Extend the cycle to include <I>u</I> by inserting <I>u</I> just after <I>v</I>. Repeat until all vertices are on the cycle. Prove that this heuristic returns a tour whose total cost is not more than twice the cost of an optimal tour.<P>
<a name="0a1e_1d42">37.2-3<a name="0a1e_1d42"><P>
<a name="0a1e_1d3d"><a name="0a1e_1d3e">The <I><B>bottleneck traveling-salesman problem</I> </B>is the problem of finding the hamiltonian cycle such that the length of the longest edge in the cycle is minimized. Assuming that the cost function satisfies the triangle inequality, show that there exists a polynomial-time approximation algorithm with ratio bound 3 for this problem. (<I>Hint:</I> Show recursively that we can visit all the nodes in a minimum spanning tree exactly once by taking a full walk of the tree and skipping nodes, but without skipping more than 2 consecutive intermediate nodes.)<P>
<a name="0a1e_1d43">37.2-4<a name="0a1e_1d43"><P>
Suppose that the vertices for an instance of the traveling-salesman problem are points in the plane and that the cost <I>c</I>(<I>u, v</I>) is the euclidean distance between points <I>u</I> and <I>v</I>. Show that an optimal tour never crosses itself.<P>
<P>


<P>