chap26.htm

美国麻省理工的算法导论,英文版,看后程序员宏观的能力培养有好处

<pre>1 <I>n</I> <img src="../images/arrlt12.gif"> <I>rows</I>[<I>D</I>]</sub></sup></pre><P>
<pre>2 let <I>D</I>' = (<I>d</I>'<I><SUB>ij</I></SUB>) be an <I>n</I> <img src="../images/mult.gif"> <I>n</I> matrix</sub></sup></pre><P>
<pre>3 <B>for</B> <I>i</I> <img src="../images/arrlt12.gif"> 1 <B>to</B> <I>n</I></sub></sup></pre><P>
<pre>4      <B>do for</B> <I>j</I> <img src="../images/arrlt12.gif"> 1 to <I>n</I></sub></sup></pre><P>
<pre>5             <B>do</B> <I>d</I>'<I><SUB>ij</I></SUB> <img src="../images/arrlt12.gif"> <img src="../images/infin.gif"></sub></sup></pre><P>
<pre><I>6                </I><B>for</B><I> k</I> <img src="../images/arrlt12.gif"> 1 <B>to</B> <I>n</I></sub></sup></pre><P>
<pre>7                    <B>do</B> <I>d</I>'<I><SUB>ij</I></SUB> <img src="../images/arrlt12.gif"> min(<I>d</I>'<I><SUB>ij</I></SUB>, d<I><SUB>ik</I></SUB> + <I>w<SUB>kj</I></SUB>)</sub></sup></pre><P>
<pre>8 <B>return</B> <I>D</I>'</sub></sup></pre><P>
The procedure computes a matrix <I>D</I>' = (<I>d</I>'<I><SUB>ij</I></SUB>), which it returns at the end. It does so by computing equation (26.2) for all <I>i</I> and <I>j</I>, using <I>D</I> for <I>D</I><SUP>(<I>m</I>-1)</SUP>and <I>D</I>' for <I>D</I><SUP>(<I>m</I>)</SUP>. (It is written without the superscripts to make its input and output matrices independent of <I>m</I>.) Its running time is <img src="../images/bound.gif">(<I>n</I><SUP>3</SUP>) due to the three nested <B>for</B> loops.<P>
We can now see the relation to matrix multiplication. Suppose we wish to compute the matrix product <I>C</I> = <I>A </I><img src="../images/dot10.gif"><I> B</I> of two <I>n <img src="../images/mult.gif"> n</I> matrices <I>A</I> and <I>B</I>. Then, for <I>i</I>, <I>j</I> = 1, 2, . . . , <I>n</I>, we compute<P>
<img src="554_a.gif"><P>
<h4><a name="08de_1844">(26.4)<a name="08de_1844"></sub></sup></h4><P>
Observe that if we make the substitutions<P>
<pre><I>d</I><SUP>(<I>m</I>-1)</SUP>  <img src="../images/arrow12.gif">  <I>a </I>,</sub></sup></pre><P>
<pre><I>w  </I><img src="../images/arrow12.gif">  <I>b </I>,</sub></sup></pre><P>
<pre><I>d</I><SUP>(<I>m</I>)</SUP> <img src="../images/arrow12.gif">  <I>c ,</I></sub></sup></pre><P>
<pre>min  <img src="../images/arrow12.gif">  + ,</sub></sup></pre><P>
<pre>+  <img src="../images/arrow12.gif">  <img src="../images/dot10.gif"></sub></sup></pre><P>
in equation (26.2), we obtain equation (26.4). Thus, if we make these changes to <FONT FACE="Courier New" SIZE=2>EXTEND</FONT>-<FONT FACE="Courier New" SIZE=2>SHORTEST</FONT>-<FONT FACE="Courier New" SIZE=2>PATHS</FONT> and also replace <img src="../images/infin.gif"> (the identity for min) by 0 (the identity for +), we obtain the straightforward <img src="../images/bound.gif">(<I>n</I><SUP>3</SUP>)-time procedure for matrix multiplication.<P>
<pre><a name="08de_1842">MATRIX-MULTIPLY(<I>A</I>, <I>B</I>)</sub></sup></pre><P>
<pre>1 <I>n</I> <img src="../images/arrlt12.gif"> <I>rows</I>[<I>A</I>]</sub></sup></pre><P>
<pre>2 let <I>C</I> be an <I>n</I> <img src="../images/mult.gif"> <I>n</I> matrix</sub></sup></pre><P>
<pre>3 <B>for</B> <I>i</I> <img src="../images/arrlt12.gif"> 1 <B>to</B> <I>n</I></sub></sup></pre><P>
<pre>4      <B>do for</B> <I>j</I> <img src="../images/arrlt12.gif"> 1 <B>to</B> <I>n</I></sub></sup></pre><P>
<pre>5             <B>do</B> <I>c<SUB>ij</I></SUB> <img src="../images/arrlt12.gif"> 0</sub></sup></pre><P>
<pre>6                <B>for </B><I>k</I> <img src="../images/arrlt12.gif"> 1 <B>to</B> <I>n</I></sub></sup></pre><P>
<pre>7                    <B>do</B> <I>c<SUB>ij</I></SUB> <img src="../images/arrlt12.gif"> <I>c<SUB>ij</I></SUB> + <I>a<SUB>ik </SUB></I><img src="../images/dot10.gif"><I> b<SUB>kj</I></sub></sup></pre><P>
<pre>8 <B>return </B><I>C</I></sub></sup></pre><P>
Returning to the all-pairs shortest-paths problem, we compute the shortest-path weights by extending shortest paths edge by edge. Letting <I>A</I> <img src="../images/dot10.gif"> <I>B </I>denote the matrix &quot;product&quot; returned by <FONT FACE="Courier New" SIZE=2>EXTEND</FONT>-<FONT FACE="Courier New" SIZE=2>SHORTEST</FONT>-<FONT FACE="Courier New" SIZE=2>PATHS</FONT>(<I>A, B</I>), we compute the sequence of <I>n</I> - 1 matrices<P>
<pre><I>D</I><SUP>(1)  </SUP>=   <I>D</I><SUP>(0)</SUP> <img src="../images/dot10.gif"> <I>W  </I>=  <I>W</I>,</sub></sup></pre><P>
<pre><I>D</I><SUP>(2)  </SUP>=   <I>D</I><SUP>(1)</SUP> <img src="../images/dot10.gif"> <I>W  </I>=  <I>W</I><SUP>2</SUP>,</sub></sup></pre><P>
<pre><I>D</I><SUP>(3)  </SUP>=   <I>D</I><SUP>(2) </SUP><img src="../images/dot10.gif"> <I>W  </I>=  <I>W</I><SUP>3</SUP>,</sub></sup></pre><P>
<img src="555_a.gif"><P>
<pre><I>D</I><SUP>(<I>n</I>-1)  </SUP>=  <I>D</I><SUP>(<I>n</I>-2) </SUP><img src="../images/dot10.gif"><SUP> </SUP><I>W  </I>=  <I>W<SUP>n</I>-1 <B>.</B></sub></sup></pre><P>
As we argued above, the matrix <I>D</I><SUP>(<I>n-</I>1)</SUP> = <I>W<SUP>n-</I>1</SUP> contains the shortest-path weights. The following procedure computes this sequence in <img src="../images/bound.gif">(<I>n</I><SUP>4</SUP>) time.<P>
<pre><a name="08de_1843">SLOW-ALL-PAIRS-SHORTEST-PATHS(<I>W</I>)</sub></sup></pre><P>
<pre>1  <I>n</I> <img src="../images/arrlt12.gif"> <I>rows</I>[<I>W</I>]</sub></sup></pre><P>
<pre>2  <I>D</I><SUP>(1)</SUP> <img src="../images/arrlt12.gif"> <I>W</I></sub></sup></pre><P>
<pre>3  <B>for</B> <I>m</I> <img src="../images/arrlt12.gif"> 2 <B>to</B> <I>n </I>- 1</sub></sup></pre><P>
<pre>4       <B>do</B> <I>D</I><SUP>(<I>m</I>)</SUP> <img src="../images/arrlt12.gif"> EXTEND-SHORTEST-PATHS(<I>D</I><SUP>(<I>m</I></SUP>-<SUP>1)</SUP>,<I>W</I>)</sub></sup></pre><P>
<pre>5  <B>return</B> <I>D</I><SUP>(<I>n</I></SUP>-<SUP>1)</sub></sup></pre><P>
Figure 26.1 shows a graph and the matrices <I>D</I><SUP>(<I>m</I>)</SUP> computed by the procedure <FONT FACE="Courier New" SIZE=2>SLOW</FONT>-<FONT FACE="Courier New" SIZE=2>ALL</FONT>-<FONT FACE="Courier New" SIZE=2>PAIRS</FONT>-<FONT FACE="Courier New" SIZE=2>SHORTEST</FONT>-<FONT FACE="Courier New" SIZE=2>PATHS</FONT>.<P>
<P>







<h2>Improving the running time</h2><P>
Our goal, however, is not to compute <I>all</I> the <I>D</I><SUP>(<I>m</I>)</SUP> matrices: we are interested only in matrix <I>D</I><SUP>(<I>n-</I>1)</SUP>. Recall that in the absence of negative-weight cycles, equation (26.3) implies <I>D</I><SUP>(<I>m</I>)</SUP> = <I>D</I><SUP>(<I>n-</I>1)</SUP> for all integers <I>m</I> <img src="../images/gteq.gif"> <I>n</I> - 1. We can compute <I>D</I><SUP>(<I>n-</I>1)</SUP> with only <FONT FACE="Courier New" SIZE=2><img src="../images/hfbrul14.gif"></FONT>lg(<I>n</I> - 1)<FONT FACE="Courier New" SIZE=2><img src="../images/hfbrur14.gif"></FONT> matrix products by computing the sequence<P>
<pre><I>D</I><SUP>(1)  </SUP>=   <I>W </I>,</sub></sup></pre><P>
<pre><I>D</I><SUP>(2)  </SUP>=   <I>W</I><SUP>2</SUP>   =  <I>W</I> <img src="../images/dot10.gif"><I>W</I>,</sub></sup></pre><P>
<pre><I>D</I><SUP>(4)  </SUP>=   <I>W</I><SUP>4</SUP>   =  <I>W</I><SUP>2 </SUP><img src="../images/dot10.gif"><I>W</I><SUP>2</sub></sup></pre><P>
<pre><I>D</I><SUP>(8)  </SUP>=   <I>W</I><SUP>8</SUP>   =  <I>W</I><SUP>4 </SUP><img src="../images/dot10.gif"><I>W</I><SUP>4</SUP>,</sub></sup></pre><P>
<img src="555_b.gif"><P>
<pre><I>D</I><SUP>(2</SUP><img src="../images/hfbrul14.gif"><SUP>lg(<I>n</I>-1)</SUP><img src="../images/hfbrur14.gif"><SUP>)  </SUP>= <I>W</I><SUP>2</SUP><img src="../images/hfbrul14.gif"><SUP>lg(<I>n</I>-1)</SUP><img src="../images/hfbrur14.gif"><SUP>   </SUP>=  <I>W</I><SUP>2</SUP><img src="../images/hfbrul14.gif"><SUP>lg(<I>n</I>-1)</SUP><img src="../images/hfbrur14.gif"><SUP>-1</SUP> <img src="../images/dot10.gif"> <I>W</I><SUP>2</SUP><img src="../images/hfbrul14.gif"><SUP>lg(<I>n</I>-1)</SUP><img src="../images/hfbrur14.gif"><SUP>-1</SUP>.</sub></sup></pre><P>
Since 2<img src="../images/hfbrul14.gif"><SUP>lg(<I>n</I>-1)</SUP><img src="../images/hfbrur14.gif"> <img src="../images/gteq.gif"> <I>n </I>- 1, the final product <I>D</I><SUP>(2<FONT FACE="Times New Roman" SIZE=1></SUP><img src="../images/hfbrul14.gif"><SUP>1g(<I>n</I>-1)</SUP><img src="../images/hfbrur14.gif"><SUP>)</FONT></SUP> is equal to <I>D</I><SUP>(<I>n</I>-1)</SUP>.<P>
<a name="08df_1844"><a name="08df_1845"><a name="08df_1846"><a name="08df_1847">The following procedure computes the above sequence of matrices by using this technique of <I><B>repeated squaring</I></B>.<P>
<img src="556_a.gif"><P>
<h4><a name="08df_1849">Figure 26.1 A directed graph and the sequence of matrices D<SUP>(m)</SUP><FONT FACE="Times New Roman" SIZE=2> computed by <FONT FACE="Courier New" SIZE=2>SLOW<FONT FACE="Times New Roman" SIZE=2>-<FONT FACE="Courier New" SIZE=2>ALL<FONT FACE="Times New Roman" SIZE=2>-<FONT FACE="Courier New" SIZE=2>PAIRS<FONT FACE="Times New Roman" SIZE=2>-<FONT FACE="Courier New" SIZE=2>SHORTEST<FONT FACE="Times New Roman" SIZE=2>-P<FONT FACE="Courier New" SIZE=2>ATHS.<FONT FACE="Times New Roman" SIZE=2> The reader may verify that D<SUP>(5)</SUP><FONT FACE="Times New Roman" SIZE=2> = D<SUP>(4)</SUP><FONT FACE="Times New Roman" SIZE=2> . W is equal to D<SUP>(4)</SUP><FONT FACE="Times New Roman" SIZE=2>, and thus D<SUP>(m)</SUP><FONT FACE="Times New Roman" SIZE=2> = D<SUP>(4)</SUP><FONT FACE="Times New Roman" SIZE=2> for all m <img src="../images/gteq.gif"> 4.<a name="08df_1849"></FONT></FONT></FONT></FONT></FONT></FONT></FONT></FONT></FONT></FONT></FONT></FONT></FONT></FONT></FONT></FONT></sub></sup></h4><P>
<pre><a name="08df_1848">FASTER-ALL-PAIRS-SHORTEST-PATHS(<I>W</I>)</sub></sup></pre><P>
<pre>1  <I>n</I> <img src="../images/arrlt12.gif"> <I>rows</I>[<I>W</I>]</sub></sup></pre><P>
<pre>2  <I>D</I><SUP>(1)</SUP> <img src="../images/arrlt12.gif"> <I>W</I></sub></sup></pre><P>
<pre>3  <I>m </I><img src="../images/arrlt12.gif"> 1</sub></sup></pre><P>
<pre>4  <B>while</B> <I>n</I> - 1 &gt; <I>m</I></sub></sup></pre><P>
<pre>5      <B>do</B> <I>D</I><SUP>(2<I>m</I>)</SUP> <img src="../images/arrlt12.gif"> EXTEND-SHORTEST-PATHS(<I>D</I><SUP>(<I>m</I>)</SUP>,<I>D</I><SUP>(<I>m</I>)</SUP>)</sub></sup></pre><P>
<pre>6         <I>m</I> <img src="../images/arrlt12.gif"> 2<I>m</I></sub></sup></pre><P>
<pre>7  <B>return</B> <I>D</I><SUP>(<I>m</I>)</sub></sup></pre><P>
In each iteration of the <B>while</B> loop of lines 4-6, we compute <I>D</I><SUP>(2<I>m</I>)</SUP> = (<I>D</I><SUP>(<I>m</I>))2</SUP>, starting with <I>m</I> = 1. At the end of each iteration, we double the value of <I>m</I>. The final iteration computes <I>D</I><SUP>(<I>n</I>-1)</SUP> by actually computing <I>D</I><SUP>(2<I>m</I>)</SUP> for some <I>n</I> - 1 <img src="../images/lteq12.gif"> 2<I>m</I> &lt; 2<I>n</I> - 2. By equation (26.3), <I>D</I><SUP>(2<I>m</I>)</SUP> = <I>D</I><SUP>(<I>n</I>-1)</SUP>. The next time the test in line 4 is performed, <I>m</I> has been doubled, so now <I>n</I> - 1 <img src="../images/lteq12.gif"> <I>m</I>, the test fails, and the procedure returns the last matrix it computed.<P>
The running time of <FONT FACE="Courier New" SIZE=2>FASTER</FONT>-<FONT FACE="Courier New" SIZE=2>ALL</FONT>-<FONT FACE="Courier New" SIZE=2>PAIRS</FONT>-<FONT FACE="Courier New" SIZE=2>SHORTEST</FONT>-<FONT FACE="Courier New" SIZE=2>PATHS</FONT> is <img src="../images/bound.gif">(<I>n</I><SUP>3</SUP>lg <I>n</I>) since each of the <FONT FACE="Times New Roman" SIZE=2><img src="../images/hfbrul14.gif"></FONT>lg(<I>n </I>- 1)<FONT FACE="Times New Roman" SIZE=2><img src="../images/hfbrur14.gif"></FONT> matrix products takes <img src="../images/bound.gif">(<I>n</I><SUP>3</SUP>) time. Observe that the code is tight, containing no elaborate data structures, and the constant hidden in the <img src="../images/bound.gif">-notation is therefore small.<P>
<img src="557_a.gif"><P>
<h4><a name="08df_184a">Figure 26.2 A weighted, directed graph for use in Exercises 26.1-1, 26.2-1,  and  26.3-1.<a name="08df_184a"></sub></sup></h4><P>
<P>







<h2><a name="08e0_184c">Exercises<a name="08e0_184c"></h2><P>
<a name="08e0_184d">26.1-1<a name="08e0_184d"><P>
Run <FONT FACE="Courier New" SIZE=2>SLOW</FONT>-<FONT FACE="Courier New" SIZE=2>ALL</FONT>-<FONT FACE="Courier New" SIZE=2>PAIRS</FONT>-<FONT FACE="Courier New" SIZE=2>SHORTEST</FONT>-<FONT FACE="Courier New" SIZE=2>PATHS</FONT> on the weighted, directed graph of Figure 26.2, showing the matrices that result for each iteration of the respective loops. Then do the same for <FONT FACE="Courier New" SIZE=2>FASTER</FONT>-<FONT FACE="Courier New" SIZE=2>ALL</FONT>-<FONT FACE="Courier New" SIZE=2>PAIRS</FONT>-<FONT FACE="Courier New" SIZE=2>SHORTEST</FONT>-<FONT FACE="Courier New" SIZE=2>PATHS</FONT>.<P>
<a name="08e0_184e">26.1-2<a name="08e0_184e"><P>
Why do we require that <I>w<SUB>ii</I></SUB> = 0 for all 1 <img src="../images/lteq12.gif"> <I>i</I> <img src="../images/lteq12.gif"> <I>n</I>?<P>
<a name="08e0_184f">26.1-3<a name="08e0_184f"><P>
What does the matrix<P>
<img src="557_b.gif"><P>
used in the shortest-paths algorithms correspond to in regular matrix multiplication?<P>
<a name="08e0_1850">26.1-4<a name="08e0_1850"><P>