动态规划.txt

动态规划介绍及其应用！

i f ( i = = j - 1 ) { / /两个矩阵的情形

kay[i][i+1]=i;

c [ i ] [ j ] = r [ i ] * r [ i + 1 ] * r [ i + 2 ] ;

return c[i][j];}

/ /多于两个矩阵的情形

/ /设u为k = i 时的最小值

int u=C(i,i)+C(i+1,j)+r[i]*r[i+1]*r[j+1];

k a y [ i ] [ j ] = i ;

/ /计算其余的最小值并更新u

for (int k==i+1; k<j;k++){

int t=C(i,k)+C(k+1,j)+r[i]*r[k+1]*r[j+1];

if (t<u) {// 比最小值还小

u = t ;

k a y [ i ] [ j ] = k ; }

}

c [ i ] [ j ] = u ;

return u;

}

为分析改进后函数C 的复杂性，再次使用分期计算方法。注意到调用C(1, q) 时每个c (i, j)（1≤i≤j≤q）仅被计算一次。要计算尚未计算过的c(a,b)，需附加的工作量s =j-i＞1。将s 计入第一次计算c (a, b) 时的工作量中。在依次计算c(a, b) 时，这个s 会转计到每个c (a, b) 的第一次计算时间c 中，因此每个c (i, i) 均被计入s。对于每个s，有q-s+ 1个c(i, j) 需要计算，因此总的工作消耗为q-1 ?s=1(q-s+ 1) = (q3 )。

3. 迭代方法

c 的动态规划递归式可用迭代的方法来求解。若按s = 2，3，.，q-1 的顺序计算c (i, i+s)，每个c 和kay 仅需计算一次。

例3-14 考察例3 - 1 3中五个矩阵的情况。先初始化c (i, i) (0≤i≤5) 为0，然后对于i=1, ., 4分别计算c (i, i+ 1 )。c (1, 2)= r1 r2 r3 = 5 0，c (2, 3)= 5 0，c ( 3,4)=20 和c (4, 5) = 2 0 0。相应的k ay 值分别为1，2，3和4。

当s= 2时，可得：

c( 1 , 3 ) = m i n {c( 1 , 1 ) +c(2,3)+ r1 r2 r4 , c( 1 , 2 ) +c( 3 ,3 )+r1r3r4 }=min{0+50+500,50+0+100}

=150

且k a y( 1 , 3 ) = 2。用相同方法可求得c( 2 , 4 )和c( 3 , 5 )分别为3 0和4 0，相应k a y值分别为2和3。

当s= 3时，需计算c(1,4) 和c( 2 , 5 )。计算c(2,5) 所需要的所有中间值均已知(见( 1 5 - 5 )式)，代入计算公式后可得c( 2 , 5 ) = 9 0，k a y( 2 , 5 ) = 2。c( 1 , 4 )可用同样的公式计算。最后，当s= 4时，可直接用（1 5 - 4）式来计算c( 1 , 5 )，因为该式右边所有项都已知。 

计算c 和kay 的迭代程序见函数M a t r i x C h a i n（见程序1 5 - 8），该函数的复杂性为(q3 )。计算出kay 后同样可用程序1 5 - 6中的Traceback 函数推算出相应的最优乘法计算过程。

程序15-8 c 和kay 的迭代计算

void MatrixChain(int r[], int q, int **c, int **kay)

{// 为所有的Mij 计算耗费和k a y

// 初始化c[i][i], c[i][i+1]和k a y [ i ] [ i + 1 ]

for (int i = 1; i < q; i++) {

c[i][i] = 0;

c[i][i+1] = r[i]*r[i+1]*r[i+2];

kay[i][i+1] = i;

}

c[q][q] = 0;

/ /计算余下的c和k a y

for (int s = 2; s < q; s++)

for (int i = 1; i <= q - s; i++) {

// k = i时的最小项

c[i][i+s] = c[i][i] + c[i+1][i+s] + r[i]*r[i+1]*r[i+s+1];

kay[i][i+s] = i;

// 余下的最小项

for (int k = i+1; k < i + s; k++) {

int t = c[i][k] + c[k+1][i+s] + r[i]*r[k+1]*r[i+s+1];

if (t < c[i][i+s]) {// 更小的最小项

c[i][i+s] = t;

kay[i][i+s] = k;}

}

}

}

 

3.2.4 最短路径

假设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中包含边<i, j>，则c(i, j, 0) =边<i, j> 的长度；若i= j ，则c(i,j, 0)=0；如果G中不包含边<i, j>，则c (i, j, 0)= +∞。c(i, j, n) 则是从i 到j 的最短路径的长度。

例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 < = n )

for(int k=1;k<=n;k++)

for (int i=1;i<=n;i++)

for (int j= 1 ;j< = n ;j+ + )

if (c(i,k,k-1)+c(k,j, k - 1 ) < c ( i ,j, k - 1 ) )

c ( i ,j, k ) = c ( i , k , k - 1 ) + c ( k ,j, k - 1 ) ;

else c(i,j, k ) = c ( i ,j, k - 1 ) ;

图15-5 最短路径算法的伪代码

 

注意到对于任意i，c(i,k,k) =c(i,k,k- 1 )且c(k,i,k) =c(k,i,k- 1 )，因而，若用c(i,j)代替图1 5 - 5的c(i,j,k)，最后所得的c(i,j) 之值将等于c(i,j,n) 值。此时图1 5 - 5可改写成程序1 5 - 9的C + +代码。程序1 5 - 9中还利用了程序1 2 - 1中定义的AdjacencyWDigraph 类。函数AllPairs 在c 中返回最短路径的长度。若i 到j 无通路，则c [i] [j]被赋值为N o E d g e。函数AllPairs 同时计算了k a y [ i ] [ j ]，其中kay[i][j] 表示从i 到j 的最短路径中最大的k 值。在后面将看到如何根据kay 值来推断出从一个顶点到另一顶点的最短路径（见程序1 5 - 1 0中的函数O u t p u t P a t h）。

程序1 5 - 9的时间复杂性为(n3 )，其中输出一条最短路径的实际时间为O (n)。

程序15-9 c 和kay 的计算

template<class T>

void AdjacencyWDigraph<T>::Allpairs(T **c, int **kay)

{ / /所有点对的最短路径

/ /对于所有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 < t3)) {

c[i][j] = t1 + t2;

kay[i][j] = k;}

}

}

程序15-10 输出最短路径

void outputPath(int **kay, int i, int j)

{// 输出i 到j 的路径的实际代码

if (i == j) return;

if (kay[i][j] == 0) cout << j << ' ';

else {outputPath(kay, i, kay[i][j]);

o u t p u t P a t h ( k a y, kay[i][j], j);}

}

template<class T>