发布时间 : 星期二 文章第6讲 - - 动态规划专题讲座更新完毕开始阅读
printf(\}
运行程序示例：
请输入序列x：hsbafdreghsbacdba 请输入序列y：acdbegshbdrabsa 最长公共子序列的长度为：9 最长公共子序列为：adeghbaba
6.3 最优路径搜索
本节应用动态规划探讨两类最优路径搜索问题，一类是点数值路径，即连接成路径的每一个点都带有一个数值；另一类是边数值路径，即连接成路径的每一条边都带有一个数值。
6.3.1 点数值三角形的最优路径搜索
点数值三角形是一个二维数阵：三角形由n行构成，第k行有k个点，每一个点都带有一个数值数。点数值三角形的数值可以随机产生，也可从键盘输入。
最优路径通常由路径所经各点的数值和来确定。 1. 案例提出
在一个n行的点数值三角形中，寻找从顶点开始每一步可沿左斜（L）或右斜（R）向下至底的一条路径，使该路径所经过的点的数值和最小。
图6.1 7行点数值三角形 例如，n=7时给出的点数值三角形如图6.1所示，如何寻找从项到底的数值和最小路径？该最优路径的数值和为多少？
2．动态规划算法设计
设点数值三角形的数值存储在二维数组a(n,n)。 （1）建立递推关系
设数组b(i,j)为点(i,j)到底的最小数值和，字符数组stm(i,j)指明点(i,j)向左或向右的路标。b(i,j)与stm(i,j)(i=n?1,?,2,1)的值由b数组的第i+1行的第j个元素与第j+1个元素值的大小比较决定，即有递推关系：
b(i,j)=a(i,j)+b(i+1,j+1); stm(i,j)=“R” （b(i+1,j+1) 其中i=n?1,?,2,1 边界条件：b(n,j)=a(n,j), j=1,2,?,n。 所求的最小路径数值和即问题的最优值为b(1,1)。 （2）逆推计算最优值 for(j=1;j<=n;j++) b[n][j]=a[n][j]; for(i=n?1;i>=1;i??) // 逆推得b[i][j] for(j=1;j<=i;j++) if (b[i+1][j+1] {b[i][j]=a[i][j]+b[i+1][j+1];stm[i][j]='R';} else {b[i][j]=a[i][j]+b[i+1][j];stm[i][j]='L';} Printf(\（3）构造最优解 为了确定与并输出最小路径，利用stm数组从上而下查找： 先打印a(1,1)，若stm(1,1)=“R”，则下一个打印a(2,2)，否则打印a(2,1)。 一般地，在输出i循环（i=2,3,?,n）中： 若stm(i?1,j)=“R”则打印“?R?”;a(i,j+1)；同时赋值j=j+1。 若stm(i?1,j)=“L”则打印“?L?”；a(i,j)； 依此打印出最小路径，即所求的最优解. （4）算法的复杂度分析 22 以上动态规划算法的时间复杂度为O(n)，空间复杂度也为O(n)。 2．最小路径寻求与测试程序设计 // 点数值三角形的最小路径 #include int a[50][50],b[50][50]; char stm[50][50]; printf(\请输入数字三角形的行数n:\ scanf(\ t=time(0)00; srand(t); //随机数发生器初始化 for(i=1;i {for(j=1;j<=36-2*i;j++) printf(\ for(j=1;j<=i;j++) {a[i][j]=rand()/1000+1; printf(\// 产生并打印n行数字三角形 } printf(\ } printf(\请在以上点数值三角形中从顶开始每步可左斜或右斜至底\ printf(\寻找一条数字和最小的路径.\\n \ for(j=1;j<=n;j++) b[n][j]=a[n][j]; for(i=n-1;i>=1;i--) // 逆推得b[i][j] for(j=1;j<=i;j++) if (b[i+1][j+1] {b[i][j]=a[i][j]+b[i+1][j+1];stm[i][j]='R';} else {b[i][j]=a[i][j]+b[i+1][j];stm[i][j]='L';} printf(\最小路径和为:%d\\n\// 输出最小数字和 printf(\最小路径为:%d\// 输出和最小的路径 for(i=2;i<=n;i++) if(stm[i-1][j]=='R') { printf(\ else printf(\ printf(\} 运行程序，对于数据如图所示的点数值三角形，输出如下： 最小路径和为:74 最小路径为:22-R-19-R-10-L-12-R-6-R-2-R-3 6.3.2 边数值矩形的最优路径搜索 边数值矩形也是一个二维数阵：矩形由n行m列构成，每一行有m?1条横边，每一列有n?1条竖边，每一条边都带有一个数值。最优路径通常由路径所经各边的数值和来确定。 1. 案例提出 已知n行m列的边数值矩阵，每一个点可向右或向下两个去向，试求左上角顶点到右下角顶点的所经边数值和最大的路径。 例如，给出一个4行5列的边数值矩形如图6.2所示，如何寻找从矩阵的左上角顶点到右下角顶点的数值和最大路径？该最优路径的数值和为多少？ 图6.2 一个4行5列的边数值矩形 2．动态规划算法设计 设矩阵的行数n，列数m，每点为(i, j)，i=1,2,?,n；j=1,2,?,m。显然，该边数值矩 阵每行有m?1条横向数值边，每列有n?1条纵向数值边。 从点(i,j)水平向右的边长记为r(i,j)(j 设a(i,j)为点（i,j）到右下角顶点的最大路程。st(i,j)为点(i,j)路标数组，其值取为{‘d’,’r’}。 a(i,j)的值由a(i+1,j)+d(i,j)与a(i,j+1)+r(i,j)比较，取其较大者得到，即有递推关系： a(i,j)=max(a(i+1,j)+d(i,j),a(i,j+1)+r(i,j)) st(i,j)={‘d’,‘r’} 其中i=1,2,?,n?1；j=1,2,?,m?1。 注意到右边纵列与下边横行只有惟一出口，因而有边界条件： a(i,m)=a(i+1,m)+d(i,m); i=n?1,n?2,?,1 a(n,j)=a(n,j+1)+r(n,j); j=m?1,m?2,?,1 （2）逆推计算最优值 for(i=n?1;i>=1;i??) {a[i][m]=a[i+1][m]+d[i][m];st[i][m]='d';} // 右边纵列初始化 for(j=m?1;j>=1;j??) {a[n][j]=a[n][j+1]+r[n][j];st[n][j]='r';} // 下边横行初始化 for(i=n?1;i>=1;i??) // 逆推求解a(i,j) for(j=m?1;j>=1;j??) if(a[i+1][j]+d[i][j]>a[i][j+1]+r[i][j]) {a[i][j]=a[i+1][j]+d[i][j];st[i][j]='d';} else {a[i][j]=a[i][j+1]+r[i][j];st[i][j]='r';} 所求左上角顶点到右下角顶点的最大路程即最优值为a(1,1)。 （3）构造最优解 利用路标数组输出最优解，从点（1,1）即i=1,j=1开始判断： if(st[i][j]=='d') {printf(\?%d?\else {printf(\?%d?\必要时可打印出点座标。 （4）算法的复杂度分析 2 以上动态规划算法的时间复杂度为O(n)。 3．求边数值矩阵图的最大路径程序设计 // 求边数值矩阵图的最大路径 #include