动态规划.txt

动态规划介绍及其应用！

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 << " to " << j << endl;

r e t u r n ; }

cout << "The path is" << endl;

cout << i << ' ';

o u t p u t P a t h ( k a y, i , j ) ;

cout << endl;

}

例3-17 图15-6a 给出某图的长度矩阵a，15-6b 给出由程序1 5 - 9所计算出的c 矩阵，15-6c 为对应的k a y值。根据15-6c 中的kay 值，可知从1到5的最短路径是从1到k a y [ 1 ] [ 5 ] = 4的最短路径再加上从4到5的最短路径，因为k a y [ 4 ] [ 5 ] = 0，所以从4到5的最短路径无中间顶点。从1到4的最短路径经过k a y [ 1 ] [ 4 ] = 3。重复以上过程，最后可得1到5的最短路径为：1，2，3，4，5。

3.2.5 网络的无交叉子集

在11 . 5 . 3节的交叉分布问题中，给定一个每边带n 个针脚的布线通道和一个排列C。顶部的针脚i 与底部的针脚Ci 相连，其中1≤i≤n，数对(i, Ci ) 称为网组。总共有n 个网组需连接或连通。假设有两个或更多的布线层，其中有一个为优先层，在优先层中可以使用更细的连线，其电阻也可能比其他层要小得多。布线时应尽可能在优先层中布设更多的网组。而剩下的其他网组将布设在其他层。当且仅当两个网组之间不交叉时，它们可布设在同一层。我们的任务是寻找一个最大无交叉子集（Maximum Noncrossing Su b s e t，M N S )。在该集中，任意两个网组都不交叉。因(i, Ci ) 完全由i 决定，因此可用i 来指定(i, Ci )。

例3-18 考察图1 5 - 7（对应于图1 0 - 1 7）。( 1 , 8 )和( 2 , 7 )（也即1号网组和2号网组）交叉，因而不能布设在同一层中。而( 1 , 8 )，(7,9) 和(9,10) 未交叉，因此可布设在同一层。但这3个网组并不能构成一个M N S，因为还有更大的不交叉子集。图1 0 - 1 7中给出的例子中，集合｛ ( 4 , 2 ) ,( 5 , 5 ) , ( 7 , 9 ) , ( 9 , 1 0 )｝是一个含4个网组的M N S。

设M N S(i, j) 代表一个M N S，其中所有的(u, Cu ) 满足u≤i，Cu≤j。令s i z e(i,j) 表示M N S(i,j)的大小(即网组的数目)。显然M N S(n,n)是对应于给定输入的M N S，而s i z e(n,n)是它的大小。

例3-19 对于图1 0 - 1 7中的例子，M N S( 1 0 , 1 0 )是我们要找的最终结果。如例3 - 1 8中所指出的，s i z e( 1 0 , 1 0 ) = 4，因为( 1 , 8 )，( 2 , 7 )，( 7 , 9 )，( 8 , 3 )，( 9 , 1 0 )和( 1 0 , 6 )中要么顶部针脚编号比7大，要么底部针脚编号比6大，因此它们都不属于M N S( 7 , 6 )。因此只需考察剩下的4个网组是否属于M N S( 7 , 6 )，如图1 5 - 8所示。子集｛( 3 , 4 ) , ( 5 , 5 )｝是大小为2的无交叉子集。没有大小为3的无交叉子集，因此s i z e( 7 , 6) = 2。

当i= 1时，( 1 ,C1) 是M N S( 1 ,j) 的唯一候选。仅当j≥C1 时，这个网组才会是M N S( 1 ,j) 的一个成员. 

下一步，考虑i＞1时的情况。若j＜Ci，则(i,Ci ) 不可能是M N S( i,j) 的成员，所有属于M N S(i,j) 的(u, Cu ) 都需满足u＜i且Cu＜j，因此：s i z e(i,j) =s i z e(i- 1 ,j), j<Ci （1 5 - 7）

若j≥Ci，则(i,Ci ) 可能在也可能不在M N S(i,j) 内。若(i,Ci ) 在M N S(i,j) 内，则在M N S(i,j)中不会有这样的(u,Cu )：u＜i且Cu＞Ci，因为这个网组必与(i, Ci ) 相交。因此M N S(i,j) 中的其他所有成员都必须满足条件u＜i且Cu＜Ci。在M N S(i,j) 中这样的网组共有Mi- 1 , Ci- 1 个。若(i,Ci ) 不在M N S(i,j)中，则M N S(i,j) 中的所有(u, Cu ) 必须满足u＜i；因此s i z e(i,j)=s i z e(i- 1 ,j)。虽然不能确定(i, Ci )是否在M N S(i,j) 中，但我们可以根据获取更大M N S的原则来作出选择。因此：s i z e(i,j) = m a x {s i z e(i-1 ,j), s i z e(i- 1 ,Ci-1)+1}, j≥Ci （1 5 - 8）

虽然从（1 5 - 6）式到（ 1 5 - 8）式可用递归法求解，但从前面的例子可以看出，即使避免了重复计算，动态规划递归算法的效率也不够高，因此只考虑迭代方法。在迭代过程中先用式（1 5 - 6）计算出s i ze ( 1 ,j)，然后再用式（1 5 - 7）和（1 5 - 8）按i=2, 3, ., n 的顺序计算s i ze (i,j)，最后再用Traceback 来得到M N S(n, n) 中的所有网组。

例3-20 图1 5 - 9给出了图1 5 - 7对应的s i z e(i,j) 值。因s i z e( 1 0 , 1 0) = 4，可知M N S含4个网组。为求得这4个网组，先从s i ze ( 1 0 , 1 0 )入手。可用（1 5 - 8）式算出s i z e( 1 0 , 1 0 )。根据式（1 5 - 8）时的产生原因可知s i ze ( 1 0 , 1 0)=s i z e( 9 , 1 0 )，因此现在要求M NS ( 9 , 1 0 )。由于M NS ( 1 0 , 1 0 )≠s i z e( 8 , 1 0 )，因此M NS (9,10) 中必包含9号网组。M N S(9,10) 中剩下的网组组成M NS ( 8 , C9- 1)=M N S( 8 , 9 )。由M N S( 8 , 9 ) =M NS (7,9) 知，8号网组可以被排除。接下来要求M N S( 7 , 9 )，因为s i z e( 7 , 9 )≠s i z e( 6 , 9 )，所以M N S中必含7号网组。M NS (7,9) 中余下的网组组成M NS ( 6 , C7- 1 ) =M N S( 6 , 8 )。根据s i z e( 6 , 8 ) =s i z e( 5 , 8 )可排除6号网组。按同样的方法， 5号网组，3号网组加入M N S中，而4号网组等其他网组被排除。因此回溯过程所得到的大小为4的M N S为{ 3 , 5 , 7 , 9 }。

注意到在回溯过程中未用到s i z e( 1 0 ,j) (j≠1 0 )，因此不必计算这些值。

程序1 5 - 11给出了计算s i z e ( i , j ) 的迭代代码和输出M N S的代码。函数M N S用来计算s i ze (i,j) 的值，计算结果用一个二维数组M N来存储。size[i][j] 表示s i z e(i,j)，其中i=j= n 或1≤i＜n，0≤j≤n，计算过程的时间复杂性为(n2 )。函数Traceback 在N et［0 : m - 1］中输出所得到的M N S，其时间复杂性为(n)。因此求解M M S问题的动态规划算法的总的时间复杂性

为(n2 )。

程序1 5 - 11 寻找最大无交叉子集

void MNS(int C[], int n, int **size)

{ / /对于所有的i 和j，计算s i z e [ i ] [ j ]

/ /初始化s i z e [ 1 ] [ * ]

for (int j = 0; j < C[1]; j++)

size[1][j] = 0;

for (j = C[1]; j <= n; j++)

size[1][j] = 1;

// 计算size[i][*], 1 < i < n

for (int i = 2; i < n; i++) {

for (int j = 0; j < C[i]; j++)

size[i][j] = size[i-1][j];

for (j = C[i]; j <= n; j++)

size[i][j] = max(size[i-1][j], size[i-1][C[i]-1]+1);

}

size[n][n] = max(size[n-1][n], size[n-1][C[n]-1]+1);

}

void Traceback(int C[], int **size, int n, int Net[], int& m)

{// 在N e t [ 0 : m - 1 ]中返回M M S

int j = n; // 所允许的底部最大针脚编号

m = 0; // 网组的游标

for (int i = n; i > 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｝。可以使用回溯过程来确定最小高度折叠中的折叠点。

练习

1. 修改程序1 5 - 1，使它同时计算出能导致最优装载的xi 值。

2. 修改程序1 5 - 1，使用一个表格来确定f (i,y) 是否已被计算过。在求f (i,y) 时,若表中已经存在该值，则直接取用；若不存在该值，则采用一个递归调用来计算该值。

3. 定义0 / 1 / 2背包问题为： m a x{n ?i =1pi xi }。限制条件为：n ?i =1wi xi≤c 且xi?{ 0 , 1 , 2 } , 1≤i≤n。设f的定义同0 / 1背包问题中的定义。

1) 从0 / 1 / 2背包问题中推出类似于（1 5 - 1）和（1 5 - 2）的公式。

2) 假设ws 为整数。编写一个类似于15-2的程序来计算二维数组f，然后确定最优分配的x 值。

3) 程序的复杂性是多少?

4. 二维0 / 1背包问题定义为：m a x{n ?i =1pi xi }。限制条件为：n ?i =1vi xi≤c，n ?i =1wi xi≤d 且xi?{ 0 , 1 } ,1≤i≤n。设f (i,y,z) 为二维背包问题最优解的值，其中物品为i 到n，c=y，d=z。

1) 推出类似于（1 5 - 1）和（1 5 - 2）式的关于f (n , y, z) 和f (i , y, z) 的公式。

2) 假设vs 和ws 为整数。编写一个类似于1 5 - 2的程序计算三维数组f ，然后确定最优分配的x 值。

3) 程序的复杂性是多少?

*5. 编写一个实现元组方法的C + +代码，要求提供一个确定最优装载的xi 值的回溯函数。

6. 当取消段长限制时(即在程序1 5 - 3中L=∞)，程序1 5 - 3的时间复杂性按如下方式递归定义：

t ( 0 ) =c（c为常数）；当n＞0时t (n)=n-1 ?i =0t( j ) +n 。

1) 根据t (n- 1 )=n-2 ?j =0t( j ) +n-1 证明：当n＞0时，t (n) = 2t (n- 1 ) + 1。

2) 证明t (n) = ( 2n )

7. 编写函数Traceback (见程序15-3) 的迭代版本。试说明两个版本各自的优缺点。

8. 编写变长图像压缩过程中1) 和2) 的实现代码。

9. 证明：q-1?s=0s( q - s+1)= (q3 )。

10. 在求解矩阵乘法递归式时仅用到数组c 和kay 的上三角。重写程序1 5 - 6，定义c 和k a y为U p p e r M a t r i x类（见4 . 3 . 4节）的成员。

11. 改写程序1 5 - 9，把它作为L i n k e d W D i g r a p h的类成员，其渐进复杂性应与程序1 5 - 9相同。

12. 设G为有n 个顶点的有向无环图，G中各顶点的编号为1到n，且当〈i,j〉为G中的一条边时有i＜j。设l (i, j) 为边〈i,j〉的长度：

1) 用动态规划方法计算图G中最长路径的长度，算法的时间耗费应为O (h+e)，其中e 为G中的边数。

2) 编写一个函数，利用1) 中所得到的结果来构造最长路径，其复杂性应为O (p)，其中p为该路径的顶点数。

13. 改写程序1 5 - 9，首先从一个有向图的邻接矩阵开始，然后计算其反身传递闭包矩阵RT C。若从顶点i 到顶点j 无通路，则RT C [ i ] [ j ] = 1，否则RT C [ i ] [ j ] = 0。要求代码的复杂性为(n3 )，其中n 为图中的顶点数。

14. 利用（1 5 - 1 0）式，编写一个复杂性为O (n2 ) 的C + +迭代程序，寻找等宽元件栈的最优折叠点。

15. 用递归式（1 5 - 1 2）代替式（1 5 - 1 0）完成练习1 4，时间复杂性要求为O(s n2 )。

16. 用式（1 5 - 1 3）得出一个变宽元件栈的最小宽度折叠法，时间复杂性要求为O(n2 )。

17. 利用1 5 . 2 . 6节的设计，给出一个寻找折叠矩形宽度为W的最小高度折叠算法，其复杂性应为O (n2 l o gn)。位－片元件宽度不等。

18. 利用式（1 5 - 1 4）和（1 5 - 1 5）来确定一个含n 个标准单元的最小高度折叠。算法的时间复杂性应为O(n2 )。能否使用这两个公式得到一个时间复杂性为(n)的算法?

*19. 在1 3 . 3 . 3节可知，一个工程可分解为多个任务且这些任务可按拓扑顺序来完成。设任务从1到n 编号，首先完成任务1，然后完成任务2，以此类推..。假设我们有两种方法来完成每个任务。Ci, 1 为使用第一种方法完成任务i 时的代价，Ci , 2 为使用第2种方法完成任务i 时的代价。令Ti, 1 为第一种方法中任务i 的时间耗费，Ti, 2 为第二种方法中任务i 的时间耗费。并设各个T为整数。设计一个动态规划算法，以得到在时间t 内完成所有任务的最小代价的方法。假定工程的代价为各任务的代价之和，工程所需的时间是各任务时间耗费之和。（提示：可设c o st (i, j) 为在j 时间内完成任务i 到n 的最小代价）。算法的复杂性是多少？

*20. 某一机器中有n 个零件。每个零件有三个供应商，来自供应商j的零件i的重量为Wi ,j，其价格为Ci , j（1≤j≤3）。机器的价格等于所有零件价格之和，其重量也为各零件重量之和。设计一个动态规划算法，以决定在总价格不超过C的条件下，从哪些供应商购买零件能组成最轻的机器。（提示：可设w (i, j) 为价格低于j 时由零件i 到n 组成的最轻机器）。算法的复杂性是多少？

*21. 定义w(i, j) 为价格低于j 时由零件1到i 组成的最轻机器，完成练习2 0。

*22. 串s 为串a 中去掉某些字符而得到的子串。如串“ o n i o n”为串“re c o g n i t i o n”的子串。当且仅当串s 既是a 的子串又是b 的子串时，串s 是串a 和串b 的公共子串。串s 的长度指其所含的字符数。试用动态规划算法得到串a 和串b 的最长公共子串。（提示：设a=a1a2.an，b=b1b2.bm。定义l (i, j) 为串ai.an 和bj.bm 最长公共子串的长度）。算法的复杂性是多少?

*23. 若l (i,j)定义为串a1a2.ai 和b1b2.bj 的最长公共子串的长度，重做练习2 2。

*24. 在串编辑问题中，给出两个串a=a1a2.an 和b=b1b2.bm 及三个耗费函数C，D和I。其中C (i, j) 为将ai 改为bj 的耗费，D(i) 为从a 中删除ai 的耗费，I (i)为将bi 插入a 中的耗费。通过修改、删除和插入操作可把串a 改为串b。如，可删除所有ai，然后插入所有bi ；或者当n≥m 时，可先把ai 变成bi（1≤i≤n），然后删除其余的ai。整个操作序列的耗费为各个操作的耗费之和。设计一个动态规划算法来确定一个具有最少耗费的编辑操作序列。（提示：定义c (i, j) 为将a1a2.ai 转变为b1b2.bj 的最少耗费）。算法的复杂性是多少?