【算法设计与分析】动态规划 | 复习笔记

文章目录

• • • 动态规划的概念
    • • • • 算法总体思想
          • 动态规划算法与分治法的异同
          • 动态规划的基本步骤
          • 动态规划算法的基本要素
    • 实例
    • • • • 矩阵连乘问题
          • 最长公共子序列
          • 最大子段和
          • 凸多边形最优三角剖分
          • 多边形游戏
          • 电路布线
          • 流水作业调度
          • 背包问题
          • 最优二叉搜索树

动态规划的概念

算法总体思想

动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题
但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。
如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。

动态规划算法与分治法的异同

相似之处：

• 都是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。

不同之处

• 适合用动态规划算法的求解的问题，经分解后得到的子问题往往不是互相独立的，以至于最后解原问题需要耗费指数时间，但不同子问题的数目常常只有多项式量级。
• 在用分治法求解时，有些子问题被重复计算了许多次，如果能保存已解决的子问题答案，在需要时再找出已解决子问题的答案，就可以避免大量重复计算，进而得到多项式时间算法。动态规划法就是利用这一特点，用一个记录所有已解决子问题的答案，不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。

总结：

1. 递归自顶向下，把大问题分解成小问题解决；动态规划自底向上，通过解决小问题，集合为解决大问题
2. 递归： 缺点：会重复计算相同的问题，相当耗时。 优点：不会记录每个问题的结果，所以内存消耗相对小。
3. 动态规划：缺点：会记录每一个问题的结果，内存消耗较大。 优点：不会计算相同问题，时间消耗较小。
4. 用递归能解决的问题，一般都可以用动态规划来解决

动态规划的基本步骤

1. 找出最优解的性质，并刻划其结构特征
2. 递归地定义最优值
3. 以自底向上的方式计算出最优值
4. 根据计算最优值时得到的信息，构造最优解

动态规划算法的基本要素

最优子结构：

• 最优解包含着其子问题的最优解。这种性质称为最优子结构性质
• 在分析问题的最优子结构性质时，所用的方法具有普遍性：首先假设由问题的最优解导出的子问题的解不是最优的，然后再设法说明在这个假设下可构造出比原问题最优解更好的解
• 利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。最优子结构是问题能用动态规划算法求解的前提
• 同一个问题可以有多种方式刻划它的最优子结构，有些表示方法的求解速度更快（空间占用小，问题的维度低）

重叠子问题：

• 递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。这种性质称为子问题的重叠性质。
• 动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果。
• 通常不同的子问题个数随问题的大小呈多项式增长。因此用动态规划算法只需要多项式时间，从而获得较高的解题效率。

备忘录方法：

• 自顶向下的动态规划
• 备忘录方法的控制结构与直接递归方法的控制结构相同，区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看，避免了相同子问题的重复求解。

实例

矩阵连乘问题

给定n个矩阵｛A1,A2,…,An｝，其中Ai与Ai+1是可乘的，i=1，2…，n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少

完全加括号的矩阵连乘积

• 完全加括号的矩阵连乘积可递归地定义为：
  1. 单个矩阵是完全加括号的；
  2. 矩阵连乘积 是完全加括号的，则 可表示为2个完全加括号的矩阵连乘积 和的乘积并加括号，即 A= (BC)
• 设有四个矩阵 A, B, C, D，它们的维数分别是：A = 50 * 10 ；B = 10 * 40 ；C = 40 * 30； D = 30 * 5；总共有五中完全加括号的方式
  
  分析最优解的结构
• 特征：计算A[i:j]的最优次序所包含的计算矩阵子链 A[i:k]和A[k+1:j]的次序也是最优的。
• 矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。

建立递归关系

• 设计算A[i:j]，1≤i≤j≤n，所需要的最少数乘次数m[i,j]，则原问题的最优值为m[1,n]
• 当i=j时，A[i:j]=Ai，因此，m[i,i]=0，i=1,2,…,n
• 当i
• 可以递归地定义m[i,j]为：
  
  k 的位置只有 j −i种可能

void MatrixChain(int *p，int n，int **m，int **s){//p矩阵表示每个矩阵的行列数//n表示矩阵个数//m矩阵表示从i到j的最少的计算次数//s矩阵表示从i到j的计算最少的加括号位置for (int i = 1; i <= n; i++)m[i][i] = 0; //将矩阵初始化全为0for (int r = 2; r <= n; r++)for (int i = 1; i <= n - r + 1; i++){//第i行int j = i + r - 1;//第j列//首先暂定最简方法是直接在原有基础后面多乘一个矩阵m[i][j] = m[i + 1][j] +  p[i - 1] * p[i] * p[j];s[i][j] = i;for (int k = i + 1; k < j; k++) {//更新int t = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];//计算在i到j中是否有更好选择if (t < m[i][j]) { //若有，则更新m[i][j] = t; s[i][j] = k;}}}
}
public static void TraceBack (int [][]s，int i，int j){//记录从i到j最简方法相乘的路径if (i == j) return;TraceBack(s, i, s[i][j]);TarceBack(s,s[i][j] + 1,j);System.out.println(“Multiply A”+i+”,”+s[i][j]+”and A”+(s[i][j]+1)+”,”+j);
}

算法复杂度分析：
算法matrixChain的主要计算量取决于算法中对r，i 和k的3重循环。循环体内的计算量为O(1)，而3重循环的总次数为O(n³)。因此算法的计算时间上界为O(n³)。算法所占用的空间显然为O(n²)。

备忘录方法：

int LookupChain(int i，int j){if (m[i][j] > 0) return m[i][j];if (i == j) return 0;int u = LookupChain(i，i) + LookupChain(i+1，j) + p[i-1]*p[i]*p[j];s[i][j] = i;for (int k = i+1; k < j; k++) {int t = LookupChain(i，k) + LookupChain(k+1，j) + p[i-1]*p[k]*p[j];if (t < u) { u = t; s[i][j] = k;}}m[i][j] = u;return u;
}

最长公共子序列

若给定序列X = {x1,x2,…,xm}，则另一序列Z = {z1,z2,…,zk}，是X的子序列是指存在一个严格递增下标序列 { i1, i2, …, ik}使得对于所 j = 1, 2, …, k有：zj = xij。例如，序列Z={B，C，D，B}是序列X={A，B，C，B，D，A，B}的子序列，相应的递增下标序列为{2，3，5，7}。
给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列
给定2个序列 X = {x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最长公共子序列。

最长公共子序列的结构

• 设序列X = {x1, x2, …, xm}和Y = {y1, y2, …, yn}的最长公共子序列为Z = { z1, z2, …, zk} ，则

1. 若x_m = y_n，则z_k = x_m = y_n，且z_k-1是X_m-1和Y_n-1的最长公共子序列。
2. 若x_m ≠ y_n且 z_k≠x_m，则Z是X_m-1和Y的最长公共子序列。
3. 若x_m ≠ y_n且 z_k≠y_n，则Z是X和Y_n-1的最长公共子序列。

• 由此可见，2个序列的最长公共子序列包含了这2个序列的前缀的最长公共子序列。因此，最长公共子序列问题具有最优子结构性质。

子问题的递归结构

• 由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。用c[i][j]记录序列Xi和Yj的最长公共子序列的长度。其中， Xi={x1,x2,…,xi}；Yj={y1,y2,…,yj}。当i=0或j=0时，空序列是Xi和Yj的最长公共子序列。故此时C[i][j]=0。其它情况下，由最优子结构性质可建立递归关系如下：
  
  计算最优值
• 由于在所考虑的子问题空间中，总共有θ(mn)个不同的子问题，因此，用动态规划算法自底向上地计算最优值能提高算法的效率

void LCSLength(int m，int n，char *x，char *y，int **c，int **b){int i，j;for (i = 1; i <= m; i++) //当x的长度为0时，没有公共子序列c[i][0] = 0;for (i = 1; i <= n; i++) //当y的长度为0时，没有公共子序列c[0][i] = 0;for (i = 1; i <= m; i++)for (j = 1; j <= n; j++) {if (x[i]==y[j]) {//如果xi和yj的值相同，那么增加一个公共子序列c[i][j]=c[i-1][j-1]+1; b[i][j]=1;//矩阵b记录x和y的情况，构造最长子序列时使用}else if (c[i-1][j]>=c[i][j-1]){c[i][j]=c[i-1][j]; b[i][j]=2;}else { c[i][j]=c[i][j-1]; b[i][j]=3; }}
}
void LCS(int i，int j，char *x，int **b){if (i == 0 || j== 0) return;if (b[i][j] == 1){ //xi==yj的情况LCS( i - 1，j - 1，x，b); cout<<x[i]; }else if (b[i][j] == 2) //xi>yj的情况LCS( i - 1，j，x，b);else //xiLCS(i，j - 1，x，b);
}

算法的改进

• 在算法lcsLength和lcs中，可进一步将数组b省去。事实上，数组元素c[i][j]的值仅由c[i-1][j-1]，c[i-1][j]和c[i][j-1]这3个数组元素的值所确定。对于给定的数组元素c[i][j]，可以不借助于数组b而仅借助于c本身在O(1)时间内确定c[i][j]的值是由c[i-1][j-1]，c[i-1][j]和c[i][j-1]中哪一个值所确定的。
• 如果只需要计算最长公共子序列的长度，则算法的空间需求可大大减少。事实上，在计算c[i][j]时，只用到数组c的第i行和第i-1行。因此，用2行的数组空间就可以计算出最长公共子序列的长度。进一步的分析还可将空间需求减至O(min(m,n))。

最大子段和

给定n个整数（可能为负）组成的序列
a₁a₂…a_n，求形如$\Sigma$^j_k=i a_k 的字段和的最大值。
当所有整数为负时，最大子段和为0.因而最优值为：max{ 0, max_1<=i<=j<=n$\Sigma$^j_k=i a_k}
如序列（-2,11,-4,13,-5,-2)的最大子段和为20

最大子段和的简单算法

Int MaxSum(int n,int *a,int& besti, int&
bestj){ sum=0;for (int i = 1;i <= n ; i++)for (int j = 1; j <= n; j++){int thissum = 0;for (int k = i; k <= j; k++)thissum += a[k];if (thissum > sum) {sum = thissum;besti = i;bestj = j; }}return sum;
}

时间复杂度O(n³)

减少一个for循环后的改进算法

Int MaxSum(int n, int *a, int& besti, int& bestj){ sum = 0;for (int i = 1; i <= n ; i++) {int thissum = 0;for (int j = i; j <= n; j++){thissum += a[j];if (thissum > sum) {sum = thissum;besti = i;bestj = j;}}}return sum;
}

时间复杂度为O(n2)，这个改进主要表现在充分利用已得到的结果

最大子段和的分治算法
若将序列a[1:n]分为长度相等的两段 a[1:n/2]和a[n/2+1:n]，分别求出最大子段和，则a[1:n]的最大字段和分三种情形：

1. a[1:n]的最大子段和与a[1:n/2]相等；
2. a[1:n]的最大子段和与a[n/2+1:n] 相等；
3. a[1:n]的最大子段和为 且$\Sigma$^j_k=i a_k 中1<=i<=n/2, n/2 <=j<=n

1)、2)两种情形可递归求得，对第三种情形，可以看出a[n/2]和a[n/2+1]在最优序列中。因而可在a[1:n/2]中计算出 s₁=max_1<=i<=n/2$\Sigma$^n/2_k=i a_k，在a[n/2+1:n]中计算出s₂=max_n/2<=i<=n$\Sigma$ⁱ_k=n/2+1 a_k，s1+s2即为出现情形3时的最优值

Int MaxSubSum(int *a, int left, int right){ sum = 0;if (left == right) //只有一个元素sum = a[left] > 0 ? a[left] : 0;else{int center = (left + right) / 2;int leftsum = MaxSubSum(a, left, center);int rightsum = MaxSubSum(a, center + 1, right);int s1 = 0;//s1记录左侧子段最大子段和int lefts = 0;//lefts为当前子段和for (int i = center;i <= left ; i--) {lefts += a[i];if(lefts > s1) s1 = lefts;}int s2 = 0;//s2记录右侧子段最大子段和int rights = 0;//rights为当前子段和for (int i = center + 1; i <= right ; i++) {rights += a[i];if(rights > s2) s2 = rights;}sum = s1 + s2; //计算第3钟情况的最大子段和if (sum < leftsum) sum = leftsum;if (sum < rightsum) sum = rightsum;}return sum;
}

时间复杂度为T(n)=O(nlogn)，调用参数为(a,1,n)

最大子段和的动态规划算法

• 若记 ,1<=j<=n;则所求的最大子段和为：
  
• 由b[j]的定义可知，当b[j1]>0时，b[j]=b[j-1]+a[j],否则b[j]=a[j],因而可得b[j]的动态规划递归式：
  
• 可令j从小到大，一次计算b[j]，记下和更大的，于是得到相应的算法。

Int MaxSum(int n,int *a){ int sum = 0;int b = 0;for (int i = 1; i <= n ; i++) {if(b > 0) b += a[i];else b = a[i];if(b > sum) sum = b;}return sum;
}

时间复杂度为O(n) 。
可推广到二维情形：最大子矩阵和问题

凸多边形最优三角剖分

本题和矩阵连乘非常类似，可以对比起来看，得以窥见天光

凸多边形：若多边形边界上或其内部任意两点连线所得的直线段上所有点都在多边形内部或边界上，则称为凸多边形。
凸多边形表示：用多边形顶点的逆时针序列表示凸多边形，即P={v₀,v₁,…,v_n-1}表示具有n条边的凸多边形。
若v_i与v_j是多边形上不相邻的2个顶点，则线段v_iv_j称为多边形的一条弦。弦将多边形分割成2个多边形{v_i,v_i+1,…,v_j}和{v_j,v_j+1,…v_i}。
多边形的三角剖分是将多边形分割成互不相交的三角形的弦的集合T。在有n个顶点的凸多边形的三角剖分中，恰有n-3条弦和n-2个三角形。
最优三角剖分问题：给定凸多边形P，以及定义在由多边形的边和弦组成的三角形上的权函数w。要求确定该凸多边形的三角剖分，使得即该三角剖分中诸三角形上权之和为最小。 如取权函数w(v_iv_jv_k ) = |v_iv_j|+|v_jv_k|+|v_kv_i|

三角剖分的结构及其相关问题

• 凸多边形的三角剖分与表达式的完全加括号有紧密联系。它们的相关性可从它们对应的完全二叉树的同构性看出。

• 一个表达式的完全加括号方式相应于一棵完全二叉树，称为表达式的语法树。例如，完全加括号的矩阵连乘积((A₁(A₂A₃))(A₄(A₅A₆)))所相应的语法树如图 (a)所示。

• 凸多边形{v₀,v₁,…v_n-1}的三角剖分也可以用语法树表示。例如，图 (b)中凸多边形的三角剖分可用图 (a)所示的语法树表示。

• 凸n+1多边形的三角剖分与n个矩阵的完全加括号乘积一一对应：矩阵连乘积中的每个矩阵Ai对应于凸(n+1)边形中的一条边v_i-1v_i。三角剖分中的一条弦v_iv_j，i

• 

• 矩阵连乘积的最优计算次序问题是凸多边形最优三角剖分的特殊情形：对给定矩阵链A₁A₂ …A_n，定义凸(n+1)边形P = (v₀v₁ …v_n) ，使得矩阵A_i与凸(n+1)边形中的一条边v_i-1v_i一一对应。若A_i 的维数为p_i-1*p_j，则定义三角形v_iv_jv_k权函数 w(v_iv_jv_k)=p_ip_jp_k,依此权函数的定义，凸多边形P的最优三角剖分所对应的语法树给出矩阵链的最优完全加括号方式。

最优子结构性质

• 凸多边形的最优三角剖分问题有最优子结构性质
• 事实上，若凸(n+1)边形 P = {v₀, v₁, …, v_n-1 }的最优三角剖分T包含三角形 v₀v_kv_n，1 ≤ k ≤ n-1，则T的权为3个部分权的和：三角形v₀v_kv_n的权，子多边形{ v₀, v₁, …, v_k}和 { v_k, v_k+1, …, v_n} 的权之和。可以断言，由T所确定的这2个子多边形的三角剖分也是最优的。因为若有{ v₀, v₁, …, v_k}或{ v_k, v_k+1, …, v_n}的更小权的三角剖分将导致T不是最优三角剖分的矛盾

最优三角剖分的递归结构

• 定义 t [ i ] [ j ]，1 ≤ i < j ≤ n 为凸子多边形 { v_i-1, v_i, …, v_j } 的最优三角剖分所对应的权函数值，即其最优值。为方便起见，设退化的多边形 { v_i-1, v_i}具有权值0。据此定义，要计算的凸(n+1)边形P的最优权值为 t [ 1 ] [ n ]
• t [ i ] [ j ] 的值可以利用最优子结构性质递归地计算。当 j - i ≥ 1时，凸子多边形至少有3个顶点。由最优子结构性质，t[i][j]的值应为t[i][k]的值加上t[k+1][j]的值，再加上三角形vi1vkvj的权值，其中i≤k≤j-1。由于在计算时还不知道k的确切位置，而k的所有可能位置只有j-i个，因此可以在这j-i个位置中选出使t[i][j]值达到最小的位置。由此，t[i][j]可递归地定义为：
• 

#include "stdafx.h"
#include 
#define N 6 //顶点数/边数
int weight[][N] =
{{0,2,2,3,1,4},{2,0,1,5,2,3},{2,1,0,2,1,4},{3,5,2,0,6,2},{1,2,1,6,0,1},{4,3,4,2,1,
0}};
int t[N][N]; //t[i][j]表示多边形{Vi-1 Vk Vj
}的最优权值
int s[N][N]; //s[i][j]记录Vi-1到Vj最优三角剖分的中间点K
int get_weight(const int a, const int b, const int c){return weight[a][b] + weight[b][c] + weight[c][a];
}
void minest_weight_val(){int i,r,k,j;int min;for (i = 1; i < N; i++)t[i][i] = 0;for (r = 2; r < N; r++){for (i = 1; i < N-r+1; i++){j = i + r -1;min = 9999; //假设最小值for (k = i; k < j; k++){t[i][j] = t[i][k] + t[k+1][j] + get_weight(i-1,k,j);if (t[i][j] < min) {//判断是否是最小值min = t[i][j];s[i][j] = k;}}t[i][j] = min;//取得多边形{Vi-1，Vj}的划分三角最小权值}}
}
void back_track(int a, int b){if (a == b)return;back_track(a,s[a][b]);back_track(s[a][b]+1,b);//记得这是要加一printf("最优三角: V%d V%d V%d.\n",a1,s[a][b],b);
}
int main(){minest_weight_val();printf("result:%d\n",t[1][N-1]);back_track(1,5);return 0;
}

多边形游戏

多边形游戏是一个单人玩的游戏，开始时有一个由n个顶点构成的多边形。每个顶点被赋予一个整数值，每条边被赋予一个运算符“+”或“ * ”。所有边依次用整数从1到n编号。
游戏第1步，将一条边删除。随后n-1步按以下方式操作：
(1)选择一条边E以及由E连接着的2个顶点V1和V2；
(2)用一个新的顶点取代边E以及由E连接着的2个顶点V1和V2。将由顶点V1和V2的整数值通过边E上的运算得到的结果赋予新顶点。
最后，所有边都被删除，游戏结束。游戏的得分就是所剩顶点上的整数值。
问题:对于给定的多边形，计算最高得分。
多边形的顶点和边的顺时针序列表示为：op[1],v[1], op[2],v[2],… ,op[n],v[n]
上图的多边形表示为：’+’,-7,’+’,4,’ * ’,2,’ * ’,5

最优子结构性质
在所给多边形中，从顶点 i (1 ≤ i ≤ n)开始，长度为j(链中有 j 个顶点)的顺时针链p(i，j) 可表示为v[i]，op[i+1]，…，v[i+j-1]。

• 如果这条链的最后一次合并运算在op[i+s]处发生(1 ≤ s ≤ j-1)，则可在op[i+s]处将链分割为2个子链p(i，s)和p(i+s，j-s)。
• 设m1是对子链p(i，s)的任意一种合并方式得到的值，而a和b分别是在所有可能的合并中得到的最小值和最大值。m2是p(i+s，j-s)的任意一种合并方式得到的值，而c和d分别是在所有可能的合并中得到的最小值和最大值。依此定义有 a ≤ m1 ≤ b，c ≤ m2 ≤ d
  1. 当op[i+s]=’+'时，显然有a+c≤m≤b+d
  2. 当op[i+s]=’ * '时，有min{ac，ad，bc，bd}≤m≤max{ac，ad，bc，bd} （可能是两个负数相乘）
• 换句话说，主链的最大值和最小值可由子链的最大值和最小值得到。

构造递归函数

• 由上分析可知，为了求链合并的最大值，必须同时求子链合并的最大值和最小值。因此，在整个计算过程中，应同时计算最大值和最小值。
• 设m[i][j][0] 是链p(i,j)合并的最小值，而m[i][j][[1]是最大值。若最优合并在 op[i+s]处将p(i,j)分为2个长度小于j的子链 p(i,i+s)和 p(i+s,j-s)，且从顶点i开始的长度小于j的子链的最大值和最小值均已计算出。为叙述方便，记
  1. a = m [i] [s] [0],
  2. b = m [i] [s] [1],
  3. c = m [i + s] [j - s] [0],
  4. d = m [i + s] [j - s] [1]
• 当op[i+s] = ’+’时，m[i][j][0]=a+c ；m[i][j[1]=b+d
• 当op[i+s] = ’*’时，m[i][j][0] = min{ac,ad,bc,bd}；m[i][j][1] = max{ac,ad,bc,bd}
• 由于最优断开位置s有1<=s<=j-1的j-1种情况，由此可知
  m [i] [j] [0] = min { minf ( i, j, s)} 1<=s<=j-1,1<=i,j<=n
  m [i] [j] [1] = max { maxf ( i, j, s)} 1<=s<=j-1,1<=i,j<=n
  初始边界值显然为：
  m [i] [1] [0] = v[i],1<=i<=n
  m[i] [1] [1] = v[i], 1<=i<=n
  由于多边形是封闭的，在上面的计算中，当i+s>n时，顶点i+s实际编号为（i+s）mod n。按上述递推式计算出的m[i][n][1]即为游戏首次删去第i条边后得到的最大得分。

计算最优值及构造最优解

Void Min_Max (int n, int i,int s,int j,int &minf,int &maxf, int m[][][2],char op[]){//从顶点i开始长度为j顺时针链p(i,j) 表示v[i]，op[i+1]，…，v[i+j-1]int e[4]; //该函数计算minf(i,j,s)和maxf(i,j,s)int r = ( i + s - 1 ) % n + 1,int a = m[i][s][0], b = m[i][s][1]; //p(i,s)int c = m[r][j - s][0], d = m[r][j - s][1];//p(i+s,j-s)if (op[r] == ‘+’){//符号是加号时更新minf和maxfminf = a + c;maxf = b + d;}else{//符号是乘号时，更新minf和maxfe[1]=a*c;e[2]=a*d;e[3]=b*c;e[4]=b*d;minf = maxf = e[1];for (int r = 2; r < 5; r++){if (minf > e[r]) minf = e[r];if (maxf < e[r]) maxf = e[r];}}
}
//对每个顶点i，依链长递增顺序计算链长为j的最大值及最小值
Int Poly_Max(int n){int minf, maxf;for(int j = 2; j <= n; j++)for(int i = 1; i <= n; i++)for(int s = 1; s < j; s++){Min_Max(n, i, s, j, minf, maxf, m, op);if (m[i][j][0] > minf) m[i][j][0] = minf;if (m[i][j][1] < maxf) m[i][j][1] = maxf;}int temp = m[1][n][1];for (int i = 1; i <= n; i++)if (temp < m[i][n][1])temp = m[i][n][1];return temp;
}

电路布线

在一块电路板的上、下2端分别有n个接线柱。根据电路设计，要求用导线(i,π(i))将上端接线柱与下端接线柱相连，如图所示。
其中π(i)是{1,2,…,n}的一个排列。导线(i,π(i))称为该电路板上的第i条连线。对于任何1≤iπ(j)。
在制作电路板时，要求将这n条连线分布到若干绝缘层上。在同一层上的连线不相交。电路布线问题要确定将哪些连线安排在第一层上，使得该层上有尽可能多的连线。换句话说，该问题要求在确定的导线集Nets={(i,π(i)),1≤i≤n}上求其最大不相交子集。

最优子结构性质：

• N(i,j)表示上面节点i与下面节点j连线的左侧区域内（包括i j连线）的连线集合，MNS(i,j)表示连线左侧区域内最大不相交连线子集，Size(i,j)表示MNS(i,j)集合中连线的个数。
• 在这里注意N(i,j)和MNS(i,j)表示的都是集合！！内存储的是连线，Size(i,j)存储的才是最大不相交连线的个数！！
• 
  

递归计算最优值

代码

//动态规划 电路布线问题
#include "stdafx.h"
#include 
using namespace std;
const int N = 10;
void MNS(int C[],int n,int **size){for(int j = 0; j < C[1]; j++)size[1][j] = 0;for(int j = C[1]; j <= n; j++)size[1][j] = 1;for(int i = 2; i < n; i++){for(int j = 0; j < C[i]; j++)size[i][j] = size[i-1][j]; //当jfor(int j = C[i]; j <= n; j++){//当j>=c[i]时，考虑(i，c[i])是否属于MNS(i,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){int j = n;int m = 0;for(int i = n; i > 1; i--){if (size[i][j] != size[i - 1][j]) {//此时,(i,c[i])是最大不相交子集的一条边Net[m++] = i;j = C[i] - 1;//更新扩展连线柱区间}}if (j >= C[1]) {//处理i=1的情形Net[m++] = 1;}
} 
int main(){int c[] = {0,8,7,4,2,5,1,9,3,10,6};//下标从1开始int **size = new int *[N+1];int k;for(int i = 0; i <= N; i++){size[i] = new int[N+1];}MNS(c,N,size);cout<<"电路布线最大不相交连线数目为："<<size[N][N]<<endl;int Net[N],m;Traceback(c,size,N,Net,m);cout<<"最大不相交连线分别为："<<endl;for(int i = m - 1; i >= 0; i--){k = Net[i];cout<<"("<<k<<","<<c[k]<<") ";}cout<<endl;return 0;
} 

MNS时间和空间复杂度为O(n^2)。Traceback时间复杂度为O(n)

这篇算法设计与分析——电路布线问题写的很好

流水作业调度

n个作业{1，2，…，n}要在由2台机器M1和M2组成的流水线上完成加工。每个作业加工的顺序都是先在M1上加工，然后在M2上加工。M1和M2加工作业i所需的时间分别为ai和bi。
流水作业调度问题要求确定这n个作业的最优加工顺序，使得从第一个作业在机器M1上开始加工，到最后一个作业在机器M2上加工完成所需的时间最少。

最优子结构性质：

• 直观上，一个最优调度应使机器M1没有空闲时间，且机器M2的空闲时间最少。在一般情况下，机器M2上会有机器空闲和作业积压2种情况。
• 设全部作业的集合为 N = {1，2，…，n}。S$\subseteq$N是N的作业子集。在一般情况下，机器M1开始加工S中作业时，机器M2还在加工其它作业，要等时间t后才可利用。将这种情况下完成S中作业所需的最短时间记为T(S,t)。流水作业调度问题的最优值为T(N,0)
• 设$\pi$是所给n个流水作业的一个最优调度，它所需的加工时间为a$\pi$(1)+T’。其中T’是在机器M2的等待时间为b$\pi$(1)时，安排作业$\pi$(2)，…，$\pi$(n)所需的时间。
  记S=N-{$\pi$(1)}，则有T’=T(S,b$\pi$(1))。流水作业调度问题具有最优子结构的性质。
  
  Johnson不等式
• 对递归式的深入分析表明，算法可进一步得到简化。
• 设$\pi$是作业集S在机器M2的等待时间为 t 时的任一最优调度。若
  $\pi$(1)=i, $\pi$(2)=j。则由动态规划递归式可得:T(S,t)=a_i+T(S-{i}, b_i+max{t-a_i ,0}) = a_i +a_j+T( S - { i, j}, t_ij)
  
• 如果作业i和j满足min { b_i, a_j} ≥ min { b_j, a_i }，则称作业i和j满足Johnson不等式。
• 交换作业i和作业j的加工顺序，得到作业集S的另一调度，它所需的加工时间为T’(S,t) = a_i + a_j + T ( S - { i , j } , t_ji)
  
  当作业i和j满足Johnson不等式时，有
  
• 由此可见当作业i和作业j不满足Johnson不等式时，交换它们的加工顺序后，不增加加工时间。对于流水作业调度问题，必存在最优调度$\pi$ ，使得作业$\pi$(i)和$\pi$(i+1)满足Johnson不等式。进一步还可以证明，调度满足Johnson法则当且仅当对任意i

算法描述
所有满足Johnson法则的调度均为最优调度

1. 令N_i= { i | a_i < b_i}, N₂= { i | a_i >= b_i};
2. 将N1中作业依ai的非减序排序；将N2中作业依bi的非增序排序；
3. N1中作业接N2中作业构成满足Johnson法则的最优调度。

int FlowShop(int n, int a[], int b[], int c[]){//n是作业个数，a是在M1上的时间，b是在M2上的是时间，c是最终次序class Jobtype{public:int operator <= (Jobtype a) const{return (key <= a.key);}int key;int index;bool job;};Jobtype *d=new Jobtype [n];//用d表示a和b以及附属信息for (int i = 0; i< n; i++) {d[i].key = a[i] > b[i] ? b[i] : a[i];d[i].job = a[i] <= b[i];d[i].index = i;}sort(d, n) //非减排序int j = 0, k = n-1;for (int i = 0; i < n; i++) {//生成N1及N2，由c记录其索引（作业序号）if ( d[i].job ) c[j++] = d[i].index;//如果a[i] <= b[i]，排在N1内，从前排，最前的最小（非减序排序）else c[k--] = d[i].index;//如果a[i] >= b[i]，排在N2内，从后排，最后的最小（非增序排序）}//计算完成所有作业的时间j = a[c[0]];//最优调度下第一个作业在M1上的时间k = j + b[c[0]];//最优调度下第一个作业在M2上的时间for (int i = 1; i < n;i++) {j += a[c[i]];//M1上的时间k = j < k ? k + b[c[i]] : j + b[c[i]];//根据M2上作业是否有积压计算M2的时间}delete d;return k;//最终k为全部时间
}

简单方法：

• 把全部 a_i和b_i分类成非降序列， a_i和b_i分别是第i个作业在两个机器上所需要的时间。
• 按照这一分类次序考察此序列: 如果序列中下一个数是a_j且作业 j 还没调度,那么在还没使用的最左位置调度作业 j ; 如果下个数是 b_j 且作业 j 还没调度,那么在还没使用的最右位置调度作业 j ; 如果已经调度了作业 j,则转到该序列的下一个数。
  

背包问题

给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问:应如何选择装入背包的物品，使得装入背包中物品的总价值最大?

最优子结构

递归关系
设所给0-1背包问题的子问题

m[i][j]中i表示可选物品，j表示背包（剩余）容量，值代表此时前i个物品最优组合的最优值v由0-1背包问题的最优子结构性质，可以建立计算m(i，j)的递归式:

• 此时背包容量为 j，可选择物品为i。出现的可能性有两种：
  1. 包的容量比该商品体积小，装不下，此时的价值与前i-1个的价值是一样的，即m(i,j) = m(i-1,j)；
  2. 还有足够的容量可以装该商品，但装了也不一定达到当前最优价值，所以在装与不装之间选择最优的一个，即m(i,j)=max｛ m(i-1,j)，m(i-1,j-w(i))+v(i) ｝
• 此时在对x_i作出决策之后,问题处于两种状态之一:
  1. 背包剩余容量是 j , 没产生任何效益;
  2. 剩余容量 j - w_i,效益值增长了v_i .

完整代码：

template< class Type >
void Knapsack( Type *v, int *w, int c, int n, Type **m){//m[i][j]中i表示可选物品，j表示背包（剩余）容量，值代表此时前i个物品最优组合的最优值vint jMax = min(w[n]-1, c) //背包剩余容量for (int j = 0; j <= jMax; j++) //背包不同剩余容量j <= jMax < cm[n][j] = 0;for(int j = w[n]; j <= c; j++)m[n][j] = v[n];for(int i = n-1; i > 1; i--){jMax = min(w[i]-1, c);for(int j = 0; j <= jMax; j++) //背包剩余容量j  jMaxm[i][j] = m[i+1][j]; //没产生任何效益//for(int j=w[i]; j<=c; j++) //背包剩余容量j>wim[i][j] = max(m[i+1][j], m[i+1][j-w[i]]+v[i]); //效益值增长vi}m[1][c] = m[2][c];if (c >= w[1])m[1][c] = max(m[1][c], m[2][c-w[1]]+v[1]);
}
Template < class Type >//求最优解xi
void Traceback(Type **m, int w, int c, int n, int x){for(int i = 1; i < n; i++)if (m[i][c] == m[i+1][c]) x[i] = 0;else { x[i] = 1;c = c- w[i]; }x[n] = (m[n][c]) ? 1 : 0;
}

Knapsack算法的另一缺点是要求所给物品的重量w_i（1 <= i <= n）是整数

改进算法

• 为克服以上缺点，引入阶梯函数。利用序偶概念，改进算法的计算时间复杂性为O（2ⁿ ）。而当所给物品的重量w_i是整数时，其计算时间复杂性为
  
  
  
  
  

部分内容来源于动态规划解决01背包问题写得非常好，很详细很通俗易懂
下面是部分摘录

从 n 推至 i +1,i算出最优值 m(i,j) （ i=n,…,1） 。 m(1,c)为最优值。然后用回溯法Traceback找出最优解x_i

• 填表，首先初始化边界条件m(0,j) = m(i,0) = 0；
  
• 然后一行一行的填表，
  1. 如，i=1，j=1，w(1)=2，v(1)=3，有j
  2. 又如i=1，j=2，w(1)=2，v(1)=3，有j=w(1),故m(1,2)=max｛ m(1-1,2)，m(1-1,2-w(1))+m(1) ｝=max｛0，0+3｝=3；
  3. 如此下去，填到最后一个，i=4，j=8，w(4)=5，v(4)=6，有j>w(4)，故m(4,8)=max｛ m(4-1,8)，m(4-1,8-w(4))+m(4) ｝=max｛9，4+6｝=10；所以填完表如下图：
     

void FindMax(){//动态规划int i,j;for(i=1;i<=number;i++){  //填表for(j=1;j<=capacity;j++){if(j<w[i]){//包装不进V[i][j]=V[i-1][j];}else{//能装if(V[i-1][j]>V[i-1][j-w[i]]+v[i]){//不装价值大V[i][j]=V[i-1][j];}else{//前i-1个物品的最优解与第i个物品的价值之和更大V[i][j]=V[i-1][j-w[i]]+v[i];}}}}
}

• 表格填完，最优解即是m( number, capacity) = m(4,8)=10，但还不知道解由哪些商品组成，故要根据最优解回溯找出解的组成，根据填表的原理可以有如下的寻解方式：
  1. m(i,j) = m(i-1,j)时，说明没有选择第i 个商品，则回到m(i-1,j)；
  2. m(i,j) = m(i-1, j-w(i))+m(i)实时，说明装了第i个商品，该商品是最优解组成的一部分，随后我们得回到装该商品之前，即回到m(i-1,j-w(i))；
  3. 一直遍历到i＝0结束为止，所有解的组成都会找到。
     

void FindWhat(int i,int j){//寻找解的组成方式if(i>=0){if(V[i][j]==V[i-1][j]){//相等说明没装item[i]=0;//全局变量，标记未被选中FindWhat(i-1,j);}else if( j-w[i]>=0 && V[i][j]==V[i-1][j-w[i]]+v[i] ){item[i]=1;//标记已被选中FindWhat(i-1,j-w[i]);//回到装包之前的位置}}
}

最优二叉搜索树

给定一个n个不同关键字已排序的序列K=(因此k1

下图显示了对一个n=5个关键字的集合构造的两颗二叉搜索树。每个关键字ki是一个内部结点，而每个伪关键字di是一个叶结点。每次搜索要么成功(找到某个关键字ki)要么失败(找到某个伪关键字di)，因此有如下公式：

由于我们知道每个关键字和伪关键字的搜索频率，因而可以确定在一棵给定的二叉搜索树T中进行一次搜索的期望代价。假定一次搜索的代价等于访问的结点数，即此次搜索找到的结点在T中的深度再加1。那么在T中进行依次搜索的期望代价为：


对于一个给定的概率集合，我们希望构造一棵期望搜索代价最小的二叉搜索树，我们称之为最优二叉搜索树。图15-9(b)所示的二叉搜索树就是给定概率集合的最优二叉搜索树，其期望代价为2.75。这个例子显示二叉搜索树不一定是高度最矮的。而且，概率最高的关键字也不一定出现在二叉树搜索树的根结点。
与矩阵链乘法问题相似，对本问题来说，穷举并检查所有可能的二叉搜索树不是一个高效的算法，需要指数时间。所以，这里使用动态规划方法求解此问题。

最优子结构

• 如果一棵最优二叉搜索树T有一棵包含关键字k(i),…,k(j)的子树T’，那么T’必然是包含关键字k(i),…,k(j)和伪关键字d(i-1),…,d(j)的子问题的最优解。
• 依旧用“剪切-粘贴”法来证明这一结论。如果存在子树T’’，其期望搜索代价比T’低，那么我们将T’从T中删除，将T’'粘贴到相应的位置，从而得到一颗期望搜索代价低于T的二叉搜索树，与T最优的假设矛盾。
• 给定关键字序列k(i),…,k(j)，其中某个关键字，比如说k( r )(i<=r<=j)，是这些关键字的最优子树的根结点。那么k(r )的左子树就包含关键字k(i), …, k(r-1)(和伪关键字d(i-1),…,d(r-1) )，而右子树包含关键字k(r+1),…,k(j)(和伪关键字d(r ), …, d(j) )。只要我们检查所有可能的根结点k(r )(i<=r<=j)，并对每种情况分别求解包含k(i), …, k(r-1)及包含 k(r+1), …, k(j)的最优二叉搜索树，即可保存找到原问题的最优解。
• 这里还有一个值得注意的细节——“空子树”。假定对于包含关键字 k_i, …, k_j 的子问题，我们选定 k_i为根结点。根据前文论证，k(i)的左子树包含关键字 k(i), …, k(i-1)的子问题，我们将此序列解释为不包含任何关键字。但请注意，子树仍然包含伪关键字。

一个递归算法

• 选取子问题域为：求解包含关键字k(i),…,k(j)的最优二叉搜索树，其中 i >= 1，j <= n且j >= i-1 (当j = i-1时，子树不包含实际关键字，只包含伪关键字d(i-1)。定义e[i,j]为包含关键字k(i),…,k(j)的最优二叉搜索树中进行一次搜索的期望代价，最终，我们希望计算出e[1,n]。
• j = i-1的情况最为简单，由于子树只包含伪关键字d(i-1)，期望搜索代价为e[i,i-1] = q (i-1)。
• 当 j >= i 时，我们需要从k(i), …, k(j)中选择一个跟结点k( r)，然后构造一棵包含关键字k(i), …, k(r-1)的最优二叉搜索树作为其左子树，以及一棵包含关键字k(r+1), …, k(j)的二叉搜索树作为其右子树。对于包含关键字 k(i), …, k(j)的子树，所有概率之和为
  
• 因此，若k为包含关键字 k(i), …, k(j)的最优二叉搜索树的根结点，我们有如下公式：e[i,j] = p( r ) + ( e[i,r-1] + w(i,r-1)) + (e[r+1,j] + w(r+1,j) ) 注意，w(i,j) = w(i,r-1) + p(r ) + w(r+1,j)。因此e[i,j]可重写为：
  e[i,j] = e[i,r-1] + e[r+1,j] + w(i,j)。
• 所以，最终的递归公式为
  
  e[i,j]的值给出了最优二叉搜索树的期望搜索代价。为了记录最优二叉搜索树的结构，对于包含关键字k(i),…,k(j)(1<=i<=j<=n)的最优二叉搜索树，我们定义root[i,j]保存根结点k(r )的下标r

计算最优二叉搜索树的期望搜索代价

• 我们可以注意到我们求解最优二叉搜索树和矩阵链乘法的一些相似之处。它们的子问题都由连续的下标子域组成
• 用一个表e[1…n+1,0…n]来保存e[i,j]的值。第一维下标上界为n+1而不是n，原因在于对于只包含伪关键字d(n)的子树，我们需要计算并保存e[n+1,n]。第二维下标下界为0，是因为对于只包含伪关键字d0的子树，我们需要计算并保存e[1,0]。我们只使用表中满足j>=i-1的表项e[i,j]。
• 使用一个表root记录关键字ki,…kj的子树的根。我们只使用此表中满足1<=i<=j<=n的表项root[i,j];
• 了避免每次计算e[i,j]时都重新计算w(i,j)，我们将这些值保存在表w[1…n+1,0…n]中，这样每次可节省Θ(j-i)次加法。对基本情况，令w[i,i-1]=q(i-1)(1<=i<=n+1)。

void optimalBST(double *p,double *q,int n){for (int i = 1;i <= n + 1;++i) {//初始化只包括虚拟键的子树w[i][i - 1] = q[i - 1];m[i][i - 1] = 0;}for (int len = 1;len <= n; ++len) {//由下到上，由左到右逐步计算for (int i = 1;i <= n - len + 1;++i){int j = i + len - 1;m[i][j] = MaxVal;w[i][j] = w[i][j - 1] + p[j] + q[j];for (int k = i;k <= j;++k){//求取最小代价的子树的根double temp = m[i][k - 1] + m[k + 1][j] + w[i][j];if (temp < m[i][j]){m[i][j] = temp;root[i][j] = k;}}}}
}
//打印最优二叉查找树的结构
//打印出[i,j]子树，它是根r的左子树和右子树
void printOptimalBST(int i,int j,int r){int rootChild = root[i][j];//子树根节点if (rootChild == root[1][n]){//输出整棵树的根cout << "k" << rootChild << "是根" << endl;printOptimalBST(i,rootChild - 1,rootChild);printOptimalBST(rootChild + 1,j,rootChild);return;}if (j < i-1)return;else if (j == i-1){//遇到虚拟键if (j < r)cout << "d" << j << "是" << "k" << r << "的左孩子" << endl;elsecout << "d" << j << "是" << "k" << r << "的右孩子" << endl;return;}else{//遇到内部结点if (rootChild < r)cout << "k" << rootChild << "是" << "k" << r << "的左孩子" << endl;elsecout << "k" << rootChild << "是" << "k" << r << "的右孩子" << endl;}printOptimalBST(i, rootChild-1, rootChild);printOptimalBST(rootChild + 1, j, rootChild);
}

算法优化

部分内容来源于最优二叉搜索树（动态规划）

• 以上内容仅复习所用，不妥删

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！