ch15.7.htm

介绍asci设计的一本书

 </A>
<SPAN CLASS="EquationVariables">
z</SPAN>
 <SPAN CLASS="Symbol">
&#8712;</SPAN>
 <SPAN CLASS="EquationVariables">
A</SPAN>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=204642">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=204644">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnNumber">
<A NAME="pgfId=204646">
 </A>
(15.15)</P>
</TD>
</TR>
</TABLE>
<P CLASS="EquationNumbered">
<A NAME="pgfId=5354">
 </A>
<IMG SRC="CH15-13.gif" ALIGN="BASELINE">
.(15.2)</P>
<P CLASS="BodyAfterHead">
<A NAME="pgfId=5362">
 </A>
So, in <A HREF="CH15.7.htm#35581" CLASS="XRef">
Figure&nbsp;15.8</A>
(a), <SPAN CLASS="EquationVariables">
I</SPAN>
<SUB CLASS="Subscript">
1</SUB>
 = 0, and <SPAN CLASS="EquationVariables">
I</SPAN>
<SUB CLASS="Subscript">
3</SUB>
 = 2. We define the edge costs for partition <SPAN CLASS="EquationVariables">
B</SPAN>
 in a similar way (so <SPAN CLASS="EquationVariables">
E</SPAN>
<SUB CLASS="Subscript">
8</SUB>
 = 2, and <SPAN CLASS="EquationVariables">
I</SPAN>
<SUB CLASS="Subscript">
8</SUB>
 = 1). The cost difference is the difference between external edge costs and internal edge costs,  </P>
<TABLE>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=204708">
 </A>
D<SUB CLASS="SubscriptVariable">
x</SUB>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=204710">
 </A>
=</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=204712">
 </A>
<SPAN CLASS="EquationVariables">
E</SPAN>
<SUB CLASS="SubscriptVariable">
x</SUB>
 &#8211; <SPAN CLASS="EquationVariables">
I</SPAN>
<SUB CLASS="SubscriptVariable">
x</SUB>
 .</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=204714">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnNumber">
<A NAME="pgfId=204716">
 </A>
(15.16)</P>
</TD>
</TR>
</TABLE>
<P CLASS="BodyAfterHead">
<A NAME="pgfId=147786">
 </A>
Thus, in <A HREF="CH15.7.htm#35581" CLASS="XRef">
Figure&nbsp;15.8</A>
(a) <SPAN CLASS="EquationVariables">
D</SPAN>
<SUB CLASS="Subscript">
1</SUB>
 = 1, <SPAN CLASS="EquationVariables">
D</SPAN>
<SUB CLASS="Subscript">
3</SUB>
 = &#8211; 2, and <SPAN CLASS="EquationVariables">
D</SPAN>
<SUB CLASS="Subscript">
8</SUB>
 = 1. Now pick any node in <SPAN CLASS="EquationVariables">
A</SPAN>
, and any node in <SPAN CLASS="EquationVariables">
B</SPAN>
. If we swap these nodes, <SPAN CLASS="EquationVariables">
a</SPAN>
&nbsp;and&nbsp;<SPAN CLASS="EquationVariables">
b,</SPAN>
 we need to measure the reduction in cut weight, which we call the gain, <SPAN CLASS="EquationVariables">
g</SPAN>
. We can express <SPAN CLASS="EquationVariables">
g</SPAN>
 in terms of the edge costs as follows:  </P>
<TABLE>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=204720">
 </A>
g</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=204722">
 </A>
=</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=204724">
 </A>
<SPAN CLASS="EquationVariables">
D</SPAN>
<SUB CLASS="SubscriptVariable">
a</SUB>
 + <SPAN CLASS="EquationVariables">
D</SPAN>
<SUB CLASS="SubscriptVariable">
b</SUB>
 &#8211; 2 <SPAN CLASS="EquationVariables">
c</SPAN>
<SUB CLASS="SubscriptVariable">
ab</SUB>
 .</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=204726">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnNumber">
<A NAME="pgfId=204728">
 </A>
(15.17)</P>
</TD>
</TR>
</TABLE>
<P CLASS="BodyAfterHead">
<A NAME="pgfId=5366">
 </A>
The last term accounts for the fact that <SPAN CLASS="EquationVariables">
a</SPAN>
 and <SPAN CLASS="EquationVariables">
b</SPAN>
 may be connected. So, in <A HREF="CH15.7.htm#35581" CLASS="XRef">
Figure&nbsp;15.8</A>
(a), if we swap nodes 1 and 6, then <SPAN CLASS="EquationVariables">
g</SPAN>
 = <SPAN CLASS="EquationVariables">
D</SPAN>
<SUB CLASS="Subscript">
1</SUB>
 + <SPAN CLASS="EquationVariables">
D</SPAN>
<SUB CLASS="Subscript">
6</SUB>
 &#8211; 2<SPAN CLASS="EquationVariables">
c</SPAN>
<SUB CLASS="Subscript">
16</SUB>
 = 1 + 1. If we swap nodes 2 and 8, then <SPAN CLASS="EquationVariables">
g</SPAN>
 = <SPAN CLASS="EquationVariables">
D</SPAN>
<SUB CLASS="Subscript">
2</SUB>
 + <SPAN CLASS="EquationVariables">
D</SPAN>
<SUB CLASS="Subscript">
8</SUB>
 &#8211; 2<SPAN CLASS="EquationVariables">
c</SPAN>
<SUB CLASS="Subscript">
28</SUB>
 = 1 + 2 &#8211; 2.</P>
<P CLASS="Body">
<A NAME="pgfId=2179">
 </A>
The K&#8211;L algorithm finds a group of node pairs to swap that increases the gain even though swapping individual node pairs from that group might decrease the gain. First we pretend to swap all of the nodes a pair at a time. Pretend swaps are like studying chess games when you make a series of trial moves in your head. </P>
<P CLASS="Body">
<A NAME="pgfId=182518">
 </A>
This is the algorithm:</P>
<OL>
<LI CLASS="NumberFirst">
<A NAME="pgfId=4599">
 </A>
Find two nodes, <SPAN CLASS="EquationVariables">
a</SPAN>
<SUB CLASS="SubscriptVariable">
i</SUB>
 from <SPAN CLASS="EquationVariables">
A</SPAN>
, and <SPAN CLASS="EquationVariables">
b</SPAN>
<SUB CLASS="SubscriptVariable">
i</SUB>
 from <SPAN CLASS="EquationNumber">
B</SPAN>
, so that the gain from swapping them is a maximum. The gain is  </LI>
<TABLE>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=204767">
 </A>
g<SUB CLASS="SubscriptVariable">
i</SUB>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=204769">
 </A>
=</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=204771">
 </A>
<SPAN CLASS="EquationVariables">
D</SPAN>
<SUB CLASS="SubscriptVariable">
ai</SUB>
 + <SPAN CLASS="EquationVariables">
D</SPAN>
<SUB CLASS="SubscriptVariable">
bi</SUB>
 &#8211; 2 <SPAN CLASS="EquationVariables">
c</SPAN>
<SUB CLASS="SubscriptVariable">
aibi</SUB>
 .</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=204773">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnNumber">
<A NAME="pgfId=204775">
 </A>
(15.18)</P>
</TD>
</TR>
</TABLE>
<LI CLASS="NumberList">
<A NAME="pgfId=4611">
 </A>
Next pretend swap <SPAN CLASS="EquationVariables">
a</SPAN>
<SUB CLASS="SubscriptVariable">
i</SUB>
 and <SPAN CLASS="EquationVariables">
b</SPAN>
<SUB CLASS="SubscriptVariable">
i</SUB>
 even if the gain <SPAN CLASS="EquationNumber">
g</SPAN>
<SUB CLASS="SubscriptVariable">
i</SUB>
 is zero or negative, and do not consider <SPAN CLASS="EquationVariables">
a</SPAN>
<SUB CLASS="SubscriptVariable">
i</SUB>
 and <SPAN CLASS="EquationVariables">
b</SPAN>
<SUB CLASS="SubscriptVariable">
i</SUB>
 eligible for being swapped again.</LI>
<LI CLASS="NumberList">
<A NAME="pgfId=2207">
 </A>
Repeat steps 1 and 2 a total of <SPAN CLASS="EquationVariables">
m</SPAN>
 times until all the nodes of <SPAN CLASS="EquationVariables">
A</SPAN>
 and <SPAN CLASS="EquationVariables">
B</SPAN>
 have been pretend swapped. We are back where we started, but we have ordered pairs of nodes in <SPAN CLASS="EquationVariables">
A</SPAN>
 and <SPAN CLASS="EquationVariables">
B </SPAN>
according to the gain from interchanging those pairs.</LI>
<LI CLASS="NumberList">
<A NAME="pgfId=5369">
 </A>
Now we can choose which nodes we shall actually swap. Suppose we only swap the first <SPAN CLASS="EquationVariables">
n</SPAN>
 pairs of nodes that we found in the preceding process. In other words we swap nodes <SPAN CLASS="EquationVariables">
X</SPAN>
 = <SPAN CLASS="EquationVariables">
a</SPAN>
<SUB CLASS="Subscript">
1</SUB>
,&nbsp;<SPAN CLASS="EquationVariables">
a</SPAN>
<SUB CLASS="Subscript">
2</SUB>
,&#8230;,&nbsp;<SPAN CLASS="EquationVariables">
a</SPAN>
<SUB CLASS="SubscriptVariable">
n</SUB>
 from <SPAN CLASS="EquationVariables">
A</SPAN>
 with nodes <SPAN CLASS="EquationVariables">
Y</SPAN>
 = <SPAN CLASS="EquationVariables">
b</SPAN>
<SUB CLASS="Subscript">
1</SUB>
,&nbsp;<SPAN CLASS="EquationVariables">
b</SPAN>
<SUB CLASS="Subscript">
2</SUB>
,&#8230;,&nbsp;<SPAN CLASS="EquationVariables">
b</SPAN>
<SUB CLASS="SubscriptVariable">
n</SUB>
 from B. The total gain would be  </LI>
<TABLE>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=204796">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">