当前位置：首页 > news >正文

【算法导论】第15章动态规划

news 来源：原创 2024/5/11 0:52:26

1、问题引入

　　和分治法一样，动态规划是通过组合子问题的解而解决整个问题的。分治法是指将问题划分成一些独立的子问题，递归求各个子问题，然后合并子问题的解而得到原问题的解。而动态规划适用于子问题不独立的情况，也就是各个子问题包含公共的“子子问题”，在这种情况下，分治法将不便于求解，而动态规划算法将对每个“子子问题”只求一次解，将其结果保存在一张表中，从而避免每次遇到各个子问题时重新计算答案。

　　动态规划通常应用于最优化问题，此类问题可能有多种可行解，每个解有一个值，而我们希望找出一个具有最优值的解，称这样的解为该问题的“一个”最优解（而不是“确定的”最优解），因为可能存在多个取最优值的解。

　　动态规划的设计可以分成如下4个步骤：

　　（1）描述最优解的结构；

　　（2）递归定义最优解的值；

　　（3）按自底向上的方式计算最优解的值；

　　（4）由计算结果构造一个最优解。

接下来将利用动态规划方法求解几个问题：装配线调度问题、矩阵链乘法问题、求最长的公共子序列问题、构造最优二叉查找树问题。

2、装配线调度

2.1 问题描述

　　某汽车工厂有2个装配线，每个装配线有n 个装配站（按顺序编号1～n ）标记为Si,j，表示第i个装配线的第j个装配站，两个装配线的对应的装配站执行相同的功能，但所用的时间可能不同。经过第i条流水线（i=1，2）的第j 个装配站所花的时间为a[i][j]。从第i条流水线的第j 个装配站移到第j+1个装配站的时间可以忽略，而移到另外一个流水线的下一个装配站则需要一定的时间t[i][j]。汽车进入流水线需要花时间，进入装配线1需要时间e[1]，进入装配线2需要时间e[2]; 汽车出流水线时需要花时间，出装配线1需要时间x[1]，出装配线2需要时间x[2] 。汽车的装配需要按顺序经过所有装配站。
　　现在已知装配时间a[i][j] 、转移时间t[i][j]、进入装配线的时间e[i]、出装配线的时间x[i]，要求输出装配一辆汽车所需要的最短时间，以及经过的装配站。

2.2 求解过程

（1）最优子结构

　　对于装配线问题，推理如下：一条经过装配线S1,j的最快路径，必定是经过装配线1或2上的装配站j-1.因此通过S1,j的最快路径只能是以下二者之一：

　　　　（a）通过装配站S1,j-1的最快路径，然后通过装配站S1,j;

　　　　 (b）通过装配站S2,j-1的最快路径，从装配线2移动到装配线1，然后通过装配站S1,j。

　　对于装配线2，有类似结论。

（2）一个递归的解

　　最终目标是确定通过工厂所有的装配线的最快时间，记为f*。设f[i][j]为一个汽车从起点到装配站Si,j的最快可能时间。汽车必然是经过装配线1或2最终到达装配站n，然后到达工厂的出口。即：

　　　　　　　　f*=min（f[1][n]+x[1] , f[2][n]+x[2])

　　要对f1[n]和f2[n]进行推理可以运用步骤1。

　　初始化：f[1][1]=e[1]+a[1][1]

　　　　　　f[2][1]=e[2]+a[2][1]

　　计算f[i][j]，其中j=2,3...,n;i=1,2

　　　　　　f[1][j]=min( f[1][j-1]+a[1][j] , f[2][j-1]+t[2][j-1]+a[1][j])

　　　　　　f[2][j]=min( f[2][j-1]+a[2][j] , f[1][j-1]+t[1][j-1]+a[2][j])

　　为了便于跟踪最优解的构造过程，定义l[i][j]：i为装配线的编号，i=1,2 ，j表示装配站j-1被通过装配站Si,j的最快路线所使用，j=2,3,...,n；

（3）自底向上计算最优解的值

　　用算法描述如下：

 1 int fastestWay
 2     f[1][1]=e[1]+a[1][1];
 3     f[2][1]=e[2]+a[2][1];
 4     for(j=2;j<n;j++)
 5     {
 6         if(f[1][j-1]+a[1][j]<=f[2][j-1]+t[2][j-1]+a[1][j])
 7         {
 8             f[1][j]=f[1][j-1]+a[1][j];
 9             l[1][j]=1;
10         }
11         else
12         {
13             f[1][j]=f[2][j-1]+t[2][j-1]+a[1][j];
14             l[1][j]=2;
15         }
16 
17         if(f[2][j-1]+a[2][j]<=f[1][j-1]+t[1][j-1]+a[2][j])
18         {
19             f[2][j]=f[2][j-1]+a[2][j];
20             l[2][j]=2;
21         }
22         else
23         {
24             f[2][j]=f[1][j-1]+t[1][j-1]+a[2][j];
25             l[2][j]=1;
26         }
27     }

2.3、具体实现代码如下：

View Code

 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 const int n=7;
 4 int fastestWay(int l[][n],int f[][n],int a[][n],int t[][n-1],int e[],int x[],int n)
 5 {
 6     int i,j,ff,ll;
 7     f[1][1]=e[1]+a[1][1];
 8     f[2][1]=e[2]+a[2][1];
 9     for(j=2;j<n;j++)
10     {
11         if(f[1][j-1]+a[1][j]<=f[2][j-1]+t[2][j-1]+a[1][j])
12         {
13             f[1][j]=f[1][j-1]+a[1][j];
14             l[1][j]=1;
15         }
16         else
17         {
18             f[1][j]=f[2][j-1]+t[2][j-1]+a[1][j];
19             l[1][j]=2;
20         }
21 
22         if(f[2][j-1]+a[2][j]<=f[1][j-1]+t[1][j-1]+a[2][j])
23         {
24             f[2][j]=f[2][j-1]+a[2][j];
25             l[2][j]=2;
26         }
27         else
28         {
29             f[2][j]=f[1][j-1]+t[1][j-1]+a[2][j];
30             l[2][j]=1;
31         }
32     }
33     if(f[1][n-1]+x[1]<=f[2][n-1]+x[2])
34     {
35         ff=f[1][n-1]+x[1];
36         l[1][1]=1;//利用l[1][1]保存出站的最后一个装配站
37     }
38     else
39     {
40         ff=f[2][n-1]+x[2];
41         l[1][1]=2;
42     }
43     return (ff);
44 }
45 
46 void main()
47 {
48     int i,j,k;
49     int a[3][7],t[3][6];//a[i][j]记录经过装配线i的装配站j所用的时间,t[i][j]记录由装配线i的装配站Si,j移动到另一条装配线所需要的时间
50     int e[3]={0,2,4};
51     int x[3]={0,3,2};
52     int l[3][7],f[3][7];//l[i][j]用于记录通过装配站Si,j的最快路径中经过的前一站所在的装配线
53     int b[2][6]={{7,9,3,4,8,4},{8,5,6,4,5,7}};
54     int c[2][5]={{2,3,1,3,4},{2,1,2,2,1}};
55     for(i=0;i<2;i++)
56         for(j=0;j<6;j++)
57             a[i+1][j+1]=b[i][j];
58     for(i=0;i<2;i++)
59         for(j=0;j<5;j++)
60             t[i+1][j+1]=c[i][j];
61     k=fastestWay(l,f,a,t,e,x,n);
62     printf("汽车装配的最少时间为：%d\n",k);
63     int cc[n+1];//用于将l[i][j]中的结果正向输出
64     cc[n]=l[1][1];//将最后经过的装配站所在的装配线放入cc[n]
65     for(i=6;i>=2;i--)
66         cc[i]=l[cc[i+1]][i];
67     printf("汽车装配经过的装配线和装配站情况如下：\n");
68     for(i=2;i<=n;i++)
69         printf("line %d , station %d \n",cc[i],i-1);        
70 }

3、矩阵链乘法

3.1 问题描述

　　矩阵链乘法问题可以描述如下：给定n个矩阵构成一个链（A1,A2，A3，... ，An)，其中i=1,2，... ，n，矩阵Ai的维数为pi-1*pi，对乘积A1A2...An以一种最小化标量乘法次数的方式进行加全部括号。

3.2 求解步骤

　　（1）最优加全部括号的结构

　　动态规划的第一步是寻找最优子结构，假设AiAi+1...Aj的一个最优加全部括号把乘积在Ak与Ak+1之间分开，则对AiAi+1...Aj最优加全部括号的“前缀”子链AiAi+1...Ak的加全部括号必须是AiAi+1...Ak的一个最优加全部括号。

　　（2）一个递归解

　　根据子问题的最优解来递归定义一个最优解的代价。对于矩阵链乘法问题，子问题即确定AiAi+1...Aj的加全部括号的最小代价问题，此处1<=i<=j<=n。设m[i][j]为计算矩阵Ai...j所需的标量乘法运算次数的最小值；对整个问题，计算A1...n的最小代价就是m[1][n]。

　　　　m[i][j]=0。i=j时

　　　　m[i][j]=min{ m[i][k]+m[k+1][j]+pi-1pkpj} 在i!=j时。

　　　　定义s[i][j]为这样的一个k值：在该处分裂乘积AiAi+1...Aj后可得一个最优加全部括号。亦即s[i][j]等于使得m[i][j]取最优解的k值。

　　（3）计算最优代价

　　具体算法如下：

 1 for(i=1;i<n;i++)
 2         m[i][i]=0;
 3 
 4     for(l=2;l<=c;l++)//确定步长，即i与j之间的距离，l=2时表示j-i等于1
 5     {
 6         for(i=1;i<=c-l+1;i++)//确定起始点
 7         {
 8             j=i+l-1;//确定终止点
 9             m[i][j]=max;
10             for(k=i;k<j;k++)//选取k值，确定起始点和终止点之间的最好k值
11             {
12                 q=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
13                 if(q<m[i][j])
14                 {
15                     m[i][j]=q;
16                     s[i][j]=k;
17                 }
18             }
19         }
20     }
21     return(m[1][n-1]);//返回总的标量乘法数。

　　具体实现代码如下：

View Code

 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 #define n 7
 4 #define max 20000
 5 int matrixChainOrder(int p[],int s[][n]);
 6 void printOptimalParens(int s[][n],int i,int j);
 7 void main()
 8 {
 9     int k,s[n][n];
10     int p[7]={30,35,15,5,10,20,25};
11     k=matrixChainOrder(p,s);
12     printf("%d个矩阵相乘所需的标量乘法的最小值为：%d\n",n-1,k);
13     printf("最终的最优全括号形式为：\n");
14     printOptimalParens(s,1,6);
15 }
16 void printOptimalParens(int s[][n],int i,int j)
17 {
18     if(i==j)
19         printf("A%d",i);
20     else 
21     {
22         printf("(");
23         printOptimalParens(s,i,s[i][j]);
24         printOptimalParens(s,s[i][j]+1,j);
25         printf(")");
26     }
27 }
28 int matrixChainOrder(int p[],int s[][n])
29 {
30     int i,l,j,k,c=n-1;
31     int q,m[n][n];
32     for(i=0;i<n;i++)
33         for(j=0;j<n;j++)
34             m[i][j]=0;
35     for(i=1;i<n;i++)
36         m[i][i]=0;
37 
38     for(l=2;l<=c;l++)//确定步长，即i与j之间的距离，l=2时表示j-i等于1
39     {
40         for(i=1;i<=c-l+1;i++)//确定起始点
41         {
42             j=i+l-1;//确定终止点
43             m[i][j]=max;
44             for(k=i;k<j;k++)//选取k值，确定起始点和终止点之间的最好k值
45             {
46                 q=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
47                 if(q<m[i][j])
48                 {
49                     m[i][j]=q;
50                     s[i][j]=k;
51                 }
52             }
53         }
54     }
55     return(m[1][n-1]);//返回总的标量乘法数。
56 }

4、最长公共子序列

4.1 问题描述

　　给定两个序列x和y，称z是x和y的公共子序列，如果z既是x的子序列，又是y的子序列；最长的公共子序列称作最长公共子序列LCS（longest common subsequence）。

4.1 求解步骤

（1）LCS的最优子结构

　　设zk是xm和yn的一个LCS，则，如果x和y的最后一个元素相同，则z中去掉最后一个元素之后zk-1仍为xm-1和yn-1的LCS

　　如果xm！=yn，若zk！=xm，则z是xm-1和y的一个LCS，若zk！=yn，则z是xm和yn-1的LCS。

（2）一个递归解

　　设c[i][j]为序列xi和yj的一个LCS的长度，则有：

　　　　c[i][j]=0 i=0或j=0

　　　　c[i][j]=c[i-1][j-1]+1 xi=yj且i,j>0

　　　　c[i][j]=max(c[i][j-1] , c[i-1][j]) xi!=yj且i,j>0

(3)计算LCS的长度

　　具体算法：

 1 lcsLength(x,y)
 2     m=length(x);
 3     n=length(y);
 4     for i=1 to m
 5         c[i][0]=0;
 6     for j=0 to n
 7         c[0][j]=0;
 8     for i=1 to m
 9         for j=1 to n
10             if(x[i]==y[j])
11                 c[i][j]=c[i-1][j-1]+1;
12             else//求二者中的较大值
13                 c[i][j]=(c[i-1][j]>=c[i][j-1])?c[i-1][j]:c[i][j-1]
14     return c

4.2 具体实现

View Code

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<malloc.h>
 4 void lcsLength(int **p,char x[],char y[],int m,int n)
 5 {
 6     int i,j;
 7     //printf("%d  %d",m,n);
 8     for(i=1;i<=m;i++)
 9         *(*(p+i))=0;
10     for(j=0;j<=n;j++)
11         *(*p+j)=0;
12     for(i=1;i<=m;i++)
13         for(j=1;j<=n;j++)
14         {
15             if(x[i-1]==y[j-1])
16                 *(*(p+i)+j)=*(*(p+i-1)+j-1)+1;
17             else
18                 *(*(p+i)+j)=((*(*(p+i-1)+j)>=*(*(p+i)+j-1))? (*(*(p+i-1)+j)):(*(*(p+i)+j-1)));
19         }
20 }
21 void main()
22 {
23     int i,j,k=0;
24     char x[]={"ABCBDAB"};
25     char y[]={"BDCABA"};
26     int m=strlen(x);//x序列的长度
27     int n=strlen(y);//y序列的长度
28     int **c=(int **)malloc(sizeof(int)*(m+1));//建立动态数组
29     for(i=0;i<m+1;i++)
30         c[i]=(int*)malloc(sizeof(int)*(n+1));
31     lcsLength(c,x,y,m,n);
32     printf("最长公共子序列的长度为：\n%d\n",c[m][n]);
33     char *p=(char *)malloc(sizeof(char)*(c[m][n]));
34     printf("其中的一个最长公共子序列为：\n");
35     i=m;
36     j=n;
37     while(c[i][j]>0)//将公共子序列中的值放入数组p[k]中
38     {
39             if(x[i-1]==y[j-1])
40             {
41                 p[k++]=x[i-1];
42                 i--;
43                 j--;
44             }
45             else
46             {
47                 if(c[i][j]==c[i-1][j])
48                     i--;
49                 else 
50                     j--;
51             }
52     }
53     for(i=k-1;i>=0;i--)
54         printf("%c  ",p[i]);
55     printf("\n");            
56 }

5、最优二叉查找树

5.1 问题描述

　　假设正在设计一个程序，用于将文章从英文翻译为法语，对于出现在文章内的每一个英文单词，需要查看与它等价的法语。执行这些搜索操作的一种方式是建立一棵二叉查找树，，，因为要为文章中的每个单词搜索这棵树，古故希望搜索所花费的总时间尽可能的小，因此我们希望文章中出现频繁的单词呗放置在距离根部较近的地方，而且文章中可能会有些单词没有法语的翻译，这些单词可能根本就不会出现在二叉查找树中。

　　n个关键字，对于每个关键字ki，一次搜索ki的概率为pi，，，，树中还存在n+1个虚拟的关键字di，一尺搜索di的概率为qi，假设n=5个的关键字的集合上的二叉查找树的概率如下：

　　，现在要求根据上表构造一棵二叉查找树，使得二叉查找树的期望搜索代价最低。

5.2 求解步骤

　　（1）分析给出一棵最优二叉查找树的结构

　　（2）一个递归解

　　　　定义e[i,j]为搜索一棵包含关键字ki，，，kj的最优二叉查找树的期望代价，最终要计算e[1,n]。。。。

　　　　当j=i-1时，只有虚拟键di-1，期望的搜索代价是e[i,i-1]=qi-1。

　　　　当j>=i时，需要从ki,...,kj中选择一个根kr,然后用关键字ki,...,kr-1来构造一棵最优二叉查找树作为其左子树，并用关键字kr+1，...,kj来构造一棵最优二叉查找树作为其右子树。。。注意当一棵树成为一个节点的子树时，它的期望搜索代价增加量将为该子树中所有概率的总和。对于一棵有关键字ki,...,kj的子树，定义概率的总和为：

　　　　　　w[i,j]=pl(l=i到j)的总和+ql（l=i-1到j的总和）

　　因此，有

　　　　　　e[i,j]=qi-1 j=i-1

　　　　　　e[i,j]=min{e[i,r-1]+e[r+1,j]+w[i,j]} i<=j

　　另外定义root[i,j]为kr的下标r。

　　（3）计算一棵最优二叉查找树的期望搜索代价

　　具体算法

 1 optimalBst(p,q,n)
 2     for i=1 to n+1//初始化
 3         e[i,i-1]=q[i-1]
 4         w[i,i-1]=q[i-1]
 5     for l=1 to n //步长
 6         for i=1 to n-l+1
 7             j=i+l-1
 8             e[i,j]=max//无穷大
 9             w[i,j]=w[i,j-1]+p[j]+q[j]
10             for r=i to j//比较
11                 t=e[i,r-1]+e[r+1,j]+w[i,j]
12                 if t<e[i,j]
13                     e[i,j]=t
14                     root[i,j]=r
15     return e and root

(4)具体实现

View Code

 1 #include<stdio.h>
 2 #include<malloc.h>
 3 #define max 9999
 4 #define n 5
 5 
 6 double optimalBst(double p[],double q[],int root[][n+1])
 7 {
 8     int i,j,l,r;
 9     double t;
10     double w[n+2][n+1];
11     double e[n+2][n+1];
12     for(i=1;i<=n+1;i++)
13     {
14         e[i][i-1]=q[i-1];
15         w[i][i-1]=q[i-1];
16     }
17     for(l=1;l<=n;l++)
18     {
19         for(i=1;i<=n-l+1;i++)
20         {
21             j=i+l-1;
22             e[i][j]=max;
23             w[i][j]=w[i][j-1]+p[j]+q[j];
24             for(r=i;r<=j;r++)
25             {
26                 t=e[i][r-1]+e[r+1][j]+w[i][j];
27                 if(t<e[i][j])
28                 {
29                     e[i][j]=t;
30                     root[i][j]=r;
31                 }
32             }
33         }
34     }
35     return(e[1][n]);
36 }    
37 void printBst(int root[][n+1],int i,int j)
38 {
39     int k;
40     if(i<=j)
41     {
42         printf("%d  " ,root[i][j]);
43         k=root[i][j];
44         printBst(root,i,k-1);
45         printBst(root,k+1,j);
46     }
47 }
48 void main()
49 {
50     int i;
51     double k;
52     int root[n+1][n+1];
53     double p[n+1]={0,0.15,0.10,0.05,0.10,0.20};
54     double q[n+1]={0.05,0.10,0.05,0.05,0.05,0.10};
55     k=optimalBst(p,q,root);
56     printf("最小期望搜索代价为：%f\n",k);
57     printf("最优二叉查找树的中序遍历结果为：\n");
58     printBst(root,1,n);
59 }