假设G为有向图，其中每条边都有一个长度（或耗费），图中每条有向路径的长度等于该路径中各边的长度之和。对于每对顶点(i, j)，在顶点i 与j 之间可能有多条路径，各路径的长度可能各不相同。我们定义从i 到j 的所有路径中，具有最小长度的路径为从i 到j 的最短路径。
例3-15 如图1 5 - 4所示。从顶点1到顶点3的路径有
1) 1,2,5,3
2) 1,4,3
3) 1,2,5,8,6,3
4) 1,4,6,3
由该图可知,各路径相应的长度为1 0、2 8、9、2 7，因而路径3) 是该图中顶点1到顶点3的最短路径。
在所有点对最短路径问题（ a l l - p a i r sshorest-paths problem）中，要寻找有向图G中每对顶点之间的最短路径。也就是说，对于每对顶点(i, j)，需要寻找从i到j 的最短路径及从j 到i 的最短路径。因此对于一个n 个顶点的图来说，需寻找p =n(n-1) 条最短路径。假定图G中不含有长度为负数的环路，只有在这种假设下才可保证G中每对顶点(i, j) 之间总有一条不含环路的最短路径。当有向图中存在长度小于0的环路时，可能得到长度为－∞的更短路径，因为包含该环路的最短路径往往可无限多次地加上此负长度的环路。
设图G中n 个顶点的编号为1到n。令c (i, j, k)表示从i 到j 的最短路径的长度，其中k 表示该路径中的最大顶点。因此，如果G中包含边
例3-16 考察图1 5 - 4。若k=0, 1, 2, 3，则c (1, 3, k)= ∞；c (1, 3, 4)= 2 8；若k = 5, 6, 7，则c (1, 3,k) = 1 0；若k=8, 9, 10，则c (1, 3, k) = 9。因此1到3的最短路径长度为9。对于任意k＞0，如何确定c (i, j, k) 呢？中间顶点不超过k 的i 到j 的最短路径有两种可能：该路径含或不含中间顶点k。若不含，则该路径长度应为c(i, j, k- 1 )，否则长度为c(i, k, k- 1) +c (k, j, k- 1 )。c(i, j, k) 可取两者中的最小值。因此可得到如下递归式：
c( i, j, k)= m i n {c(i, j, k-1), c (i, k, k- 1) +c (k, j, k- 1 ) }，k＞0
以上的递归公式将一个k 级运算转化为多个k-1 级运算，而多个k-1 级运算应比一个k 级运算简单。如果用递归方法求解上式，则计算最终结果的复杂性将无法估量。令t (k) 为递归求解c (i, j, k) 的时间。根据递归式可以看出t(k) = 2t(k- 1 ) +c。利用替代方法可得t(n) = ( 2n )。因此得到所有c (i, j, n) 的时间为(n2 2n )。
当注意到某些c (i, j, k-1) 值可能被使用多次时，可以更高效地求解c (i, j, n)。利用避免重复计算c(i, j, k) 的方法，可将计算c 值的时间减少到(n3 )。这可通过递归方式（见程序1 5 - 7矩阵链问题）或迭代方式来实现。出迭代算法的伪代码如图1 5 - 5所示。
/ /寻找最短路径的长度
/ /初始化c（i，j，1）
for （int i=1； i < = n ; i + +） for (int j=1; j<=n; j+ + ) c ( i ,j, 0 ) = a ( i ,j); // a 是长度邻接矩阵 / /计算c ( i ,j, k ) ( 0 < k="1;k<="n;k++)" i="1;i<="n;i++)" j=" 1" t="">
void AdjacencyWDigraph
{ / /所有点对的最短路径
/ /对于所有i和j，计算c [ i ] [ j ]和k a y [ i ] [ j ]
/ /初始化c [ i ] [ j ] = c（i，j，0）
for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) { c[i][j] = a[i][j]; kay[i][j] = 0; } for (i = 1; i <= n; i++) c[i][i] = 0; // 计算c[i][j] = c(i,j,k) for (int k = 1; k <= n; k++) for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) { T t1 = c[i][k]; T t2 = c[k][j]; T t3 = c[i][j]; if (t1 != NoEdge && t2 != NoEdge && (t3 == NoEdge || t1 + t2 < i ="="" t="">
void OutputPath(T **c, int **kay, T NoEdge, int i, int j)
{// 输出从i 到j的最短路径
if (c[i][j] == NoEdge) {
cout << "There is no path from " << i=" 1时，(" cu="" a="" x="" ci="" 20="" ns="" 6="" 8="" 3="" 7="" 9="" ze="" traceback="" 0="" n="" m="" n2="" 5="" 11="" void="" s="" i="2," z="" e="" 1="" for="" int="" j="">< j =" C[1];" i =" 2;" j =" 0;" j =" C[i];" j =" n;" m =" 0;" i =" n;"> 1; i--)
// i 号n e t在M N S中?
if (size[i][j] != size[i-1][j]){// 在M N S中
Net[m++] = i;
j = C[i] - 1;}
// 1号网组在M N S中?
if (j >= C[1])
Net[m++] = 1; // 在M N S中
}
3.2.6 元件折叠
在设计电路的过程中，工程师们会采取多种不同的设计风格。其中的两种为位－片设计（bit-slice design）和标准单元设计（standard-cell design）。在前一种方法中，电路首先被设计为一个元件栈（如图15-10a 所示）。每个元件Ci 宽为wi ，高为hi ，而元件宽度用片数来表示。图15-10a 给出了一个四片的设计。线路是按片来连接各元件的，即连线可能连接元件Ci 的第j片到元件Ci+1 的第j 片。如果某些元件的宽度不足j 片，则这些元件之间不存在片j 的连线。当图1 5 -10a 的位－片设计作为某一大系统的一部分时，则在V L SI ( Very Large Scale Integrated) 芯片上为它分配一定数量的空间单元。分配是按空间宽度或高度的限制来完成的。现在的问题便是如何将元件栈折叠到分配空间中去，以便尽量减小未受限制的尺度（如，若高度限制为H时，必须折叠栈以尽量减小宽度W）。由于其他尺度不变，因此缩小一个尺度（如W）等价于缩小面积。可用折线方式来折叠元件栈，在每一折叠点，元件旋转1 8 0°。在图15-10b 的例子中，一个1 2元件的栈折叠成四个垂直栈，折叠点为C6 , C9 和C1 0。折叠栈的宽度是宽度最大的元件所需的片数。在图15-10b 中，栈宽各为4，3，2和4。折叠栈的高度等于各栈所有元件高度之和的最大值。在图15-10b 中栈1的元件高度之和最大，该栈的高度决定了包围所有栈的矩形高度。
实际上，在元件折叠问题中，还需考虑连接两个栈的线路所需的附加空间。如，在图1 5 -10b 中C5 和C6 间的线路因C6 为折叠点而弯曲。这些线路要求在C5 和C6 之下留有垂直空间，以便能从栈1连到栈2。令ri 为Ci 是折叠点时所需的高度。栈1所需的高度为5 ?i =1hi +r6，栈2所需高度为8 ?i=6hi +r6+r9。
在标准单元设计中，电路首先被设计成为具有相同高度的符合线性顺序的元件排列。假设此线性顺序中的元件为 C1，.，Cn，下一步元件被折叠成如图1 5 - 11所示的相同宽度的行。在此图中， 1 2个标准单元折叠成四个等宽行。折叠点是C4，C6 和C11。在相邻标准单元行之间，使用布线通道来连接不同的行。折叠点决定了所需布线通道的高度。设li 表示当Ci 为折叠点时所需的通道高度。在图1 5 - 11的例子中，布线通道1的高度为l4，通道2的高度为l6，通道3的高度为l11。位－片栈折叠和标准单元折叠都会引出一系列的问题，这些问题可用动态规划方法来解决。
1. 等宽位－片元件折叠
定义r1 = rn+1 =0。由元件Ci 至Cj 构成的栈的高度要求为j ?k= ilk+ ri+ rj + 1。设一个位－片设计中所有元件有相同宽度W。首先考察在折叠矩形的高度H给定的情况下，如何缩小其宽度。设Wi
为将元件Ci 到Cn 折叠到高为H的矩形时的最小宽度。若折叠不能实现（如当ri +hi＞H时），取Wi =∞。注意到W1 可能是所有n 个元件的最佳折叠宽度。
当折叠Ci 到Cn 时，需要确定折叠点。现假定折叠点是按栈左到栈右的顺序来取定的。若第一点定为Ck+ 1，则Ci 到Ck 在第一个栈中。为了得到最小宽度，从Ck+1 到Cn 的折叠必须用最优化方法，因此又将用到最优原理，可用动态规划方法来解决此问题。当第一个折叠点k+ 1已知时，可得到以下公式：
Wi =w+ Wk + 1 （1 5 - 9）
由于不知道第一个折叠点，因此需要尝试所有可行的折叠点，并选择满足（ 1 5 - 9）式的折叠点。令h s u m(i,k)=k ?j = ihj。因k+ 1是一个可行的折叠点，因此h s u m(i, k) +ri +rk+1 一定不会超过H。
根据上述分析，可得到以下动态规划递归式：
这里Wn+1 =0，且在无最优折叠点k+ 1时Wi 为∞。利用递归式（1 5 - 1 0），可通过递归计算Wn , Wn- 1., W2 , W1 来计算Wi。Wi 的计算需要至多检查n-i+ 1个Wk+ 1，耗时为O (n-k)。因此计算所有Wi 的时间为O (n2 )。通过保留式（1 5 - 1 0）每次所得的k 值，可回溯地计算出各个最优的折叠点，其时间耗费为O (n)。
现在来考察另外一个有关等宽元件的折叠问题：折叠后矩形的宽度W已知，需要尽量减小其高度。因每个折叠矩形宽为w，因此折叠后栈的最大数量为s=W / w。令Hi, j 为Ci , ., Cn 折叠成一宽度为jw 的矩形后的最小高度， H1, s 则是所有元件折叠后的最小高度。当j= 1时，不允许任何折叠，因此：Hi,1 =h s u m(i,n) +ri , 1≤i≤n
另外，当i=n 时，仅有一个元件，也不可能折叠，因此：Hn ,j=hn+rn , 1≤j≤s
在其他情况下，都可以进行元件折叠。如果第一个折叠点为k+ 1，则第一个栈的高度为
h s u m(i,k) +ri +rk+ 1。其他元件必须以至多(j- 1 ) *w 的宽度折叠。为保证该折叠的最优性，其他元件也需以最小高度进行折叠.
因为第一个折叠点未知，因此必须尝试所有可能的折叠点，然后从中找出一个使式（1 5 - 11）的右侧取最小值的点，该点成为第一个折叠点。
可用迭代法来求解Hi, j ( 1≤i≤n, 1≤j≤s)，求解的顺序为：先计算j=2 时的H i, j，再算j= 3，.，以此类推。对应每个j 的Hi, j 的计算时间为O (n2 )，所以计算所有H i, j 的时间为O(s n2 )。通过保存由（ 1 5 - 1 2）式计算出的每个k 值，可以采用复杂性为O (n) 的回溯过程来确定各个最优的折叠点。
2. 变宽位－片元件的折叠
首先考察折叠矩形的高度H已定，欲求最小的折叠宽度的情况。令Wi 如式（1 5 - 1 0）所示，按照与（1 5 - 1 0）式相同的推导过程，可得：
Wi = m i n {w m i n(i, k) +Wk+1 | h s u m(i,k)+ ri +rk+ 1≤H, i≤k≤n} （1 5 - 1 3）
其中Wn+1=0且w m i n(i,k)= m ini≤j≤k{wj }。可用与（1 5 - 1 0）式一样的方法求解（1 5 - 1 3）式，所需时间为O(n2 )。
当折叠宽度W给定时，最小高度折叠可用折半搜索方法对超过O(n2 )个可能值进行搜索来实现，可能的高度值为h(i,j)+ri +rj + 1。在检测每个高度时，也可用（ 1 5 - 1 3）式来确定该折叠的宽度是否小于等于W。这种情况下总的时间消耗为O (n2 l o gn)。
3. 标准单元折叠
用wi 定义单元Ci 的宽度。每个单元的高度为h。当标准单元行的宽度W 固定不变时，通过减少折叠高度，可以相应地减少折叠面积。考察Ci 到Cn 的最小高度折叠。设第一个折叠点是Cs+ 1。从元件Cs+1 到Cn 的折叠必须使用最小高度，否则，可使用更小的高度来折叠Cs+1 到Cn，从而得到更小的折叠高度。所以这里仍可使用最优原理和动态规划方法。
令Hi , s 为Ci 到Cn 折叠成宽为W的矩形时的最小高度，其中第一个折叠点为Cs+ 1。令w s u m(i, s)=s ?j = iwj。可假定没有宽度超过W的元件，否则不可能进行折叠。对于Hn,n 因为只有一个元件，不存在连线问题，因此Hn, n =h。对于H i, s（1≤i＜s≤n）注意到如果w s u m(i, s )＞W，不可能实现折叠。若w s u m(i,s)≤W，元件Ci 和C j + 1 在相同的标准单元行中，该行下方布线通道的高度为ls+ 1（定义ln+1 = 0）。因而：Hi, s = Hi+1, k （1 5 - 1 4）
当i=s＜n 时，第一个标准单元行只包含Ci 。该行的高度为h 且该行下方布线通道的高度为li+ 1。因Ci+ 1 到Cn 单元的折叠是最优的.
为了寻找最小高度折叠，首先使用式（ 1 5 - 1 4）和（1 5 - 1 5）来确定Hi, s （1≤i≤s≤n）。最小高度折叠的高度为m in｛H1 , s｝。可以使用回溯过程来确定最小高度折叠中的折叠点。
没有评论:
发表评论