检测WordPress网站的安全性,竖导航网站,山西省交通建设工程监理有限责任公司网站,企业查官网入口1.动态规划基础
1.1动态规划的基本思想 动态规划建立在最优原则的基础上#xff0c;在每一步决策上列出可能的局部解#xff0c;按某些条件舍弃不能得到最优解的局部解#xff0c;通过逐层筛选减少计算量。每一步都经过筛选#xff0c;以每一步的最优性来保证全局的最优性…1.动态规划基础
1.1动态规划的基本思想 动态规划建立在最优原则的基础上在每一步决策上列出可能的局部解按某些条件舍弃不能得到最优解的局部解通过逐层筛选减少计算量。每一步都经过筛选以每一步的最优性来保证全局的最优性。具体来说动态规划算法仍然是将待求解的问题的若干子问题采用列表技术将从小到大的子问题的计算答案存储于一张表中由于将原问题分解后的各个子问题可能存在重复所以当重复遇到该子问题时只需要查表继续问题的求解而不需要重复计算。所以动态规划算法的基本思想是记录子问题并不断填表。
1.2动态规划的基本要素 通常一个可以用动态规划算法求解的问题应该具有3个要素最优子结构、无后效性和子问题重叠性。 最优子结构动态规划算法的关键在于正确的找出基本的递推关系式和恰当的边界条件。要做到这一点必须将原问题分解为几个相互联系的阶段在每一个子问题的求解中均利用它前面子问题的最优化结果依次进行最有一个子问题所得的最优解就是整个问题的最优解。 无后效性将各个阶段依次排好之后一旦某阶段的状态已经确定它以前各阶段的状态无法直接影响未来的决策并且当前状态的决策只是对以往决策的总结。 子问题重叠性动态规划计算最优值时每次计算所产生的子问题并不总是新问题有些问题被重复计算多次但是动态规划将这些子问题的解存放在表格中不需要重复计算提高了程序的效率。
1.3动态规划的基本方法 动态规划问题千奇百怪有诸多变种但是动态规划具有比较鲜明的特征即最优子结构和重叠子问题。解决动态规划问题的思路很重要掌握下面五步之后再加以练习能够解决许多动态规划问题。
确定dp的含义dp数组中存放的是每个子问题的最优解。推导动态转移方程在动态规划问题中dp的初始化遍历顺序打印表格
2.矩阵连乘问题 给定个矩阵其中矩阵的维数为×且与是可乘的考察这个矩阵的连乘积。由于矩阵乘法满足结合律所以计算矩阵的连乘可以有许多不同的计算次序这种计算次序可以用加括号的方式来确定。如何确定计算矩阵连乘积的计算次序使得依此次序计算矩阵连乘积需要的数乘次数最少 设有四个矩阵A、B、C、D它们的维数分别是50×1010×4040×3030×5其完全加括号方式为(A((BC)D))(A(B(CD)))((AB)(CD))(((AB)C)D)((A(BC))D)所需的乘法次数分别为1600010500360008750034500。 对于个矩阵的连乘积设其不同的计算次序为。每种加括号方式都可以分解为两个矩阵的加括号方式其递推式为 卡特兰数是组合数学中一个常出现在各种计数问题中的数列。其递推式如下 该递推关系的解为。 卡特兰数的渐近增长为 ~ 2.1分析最优子结构 设个矩阵连乘的最佳计算次序为则与连乘的计算次序都是最优的。矩阵连乘计算次序问题的最优解包含着子问题的最优解。这种性质称为最优子结构性质问题的最优子结构性质是该问题可用DP方法求解的显著特征。
2.2递归关系建立 将矩阵连乘积记为这里。的总计算量为的计算量加上的计算量再加上和相乘的计算量。 设计算的最佳计算次序所对应的乘法次数为则原问题的最优解为 当时,因此 当时
2.3代码分析
#includestdio.h
#define N 7
void MatrixChain(int *p,int n,int m[][N],int s[][N])
{for(int i 0; i n; i) m[i][i] 0;//自乘的消耗为0for(int r 2; r n; r){for(int i 1; i n - r 1; i){int j i r - 1;m[i][j] m[i1][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[k1][j] p[i-1]*p[k]*p[j];if(t m[i][j]){m[i][j] t; s[i][j] k;}}}}
}void Traceback(int i, int j, int s[][N]){if(i j) printf(A%d,i);else{printf(();Traceback(i,s[i][j],s);Traceback(s[i][j]1,j,s);printf());}
} int main()
{int p[N]{30,35,15,5,10,20,24};int m[N][N],s[N][N];MatrixChain(p,N-1,m,s);printf(矩阵的最佳乘积方式为);Traceback(1,6,s);return 0;
}
3.电路布线问题 在一块电路板的上、下两端分别有个接线柱。根据电路设计要求用导线将上端接线柱与下端接线柱相连如图所示 其中是的一个排列导线称为该电路的第条连线。对于任何第条连线和第条连线相交的充分且必要条件是。 在制作电路板时要求将这条连线分布到若干绝缘层上。在同一层上的连线不可相交。电路布线问题要确定将那些连线安排在第一层上使得该层上要有尽可能多的连线。换句话说该问题要确定导线集的最大不相交子集。
3.1最优子结构分析 记。的最大不相交子集为。。
1当时。
2当时 若。此时。所以从而。 若。此时 如果则对任意的有且。在这种情况下是的最大不相交子集从而。 如果则对任意的有。从而。因此。另一方面有因此又有从而有。
3.2递归关系建立
1当时
2当时 电路布线问题的最优值为。
3.3代码分析
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 1; j C[i]; j) size[i][j] size[i-1][j];for(int 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);
}
4.最长公共子序列 若给定子序列则是X的子序列是指存在一个严格递增下标序列使得对于所有的有。 给定两个序列和当另一序列既是的子序列又是的子序列时称是序列和的公共子序列。我们的问题是给定两个序列和找出和的最长公共子序列。
4.1最优子结构分析 设序列和的最长公共子序列为则
1若则且是和的最长公共子序列。
2若且则是和的最长公共子序列。
3若且则是和的最长公共子序列。
由此可见两个序列的最长公共子序列包含了这两个序列的前缀的最长公共子序列。因此最长公共子序列问题具有最优子结构性质。
4.2递归关系建立 设二维数组记录序列和的最长公共子序列的长度。其中。当或时空序列是它们的最长公共子序列此时其它情况下 4.3代码分析
void LCSLength()
{for(int i 1; i m; i) c[i][0] 0;//存放各个子问题的最优值for(int j 1; j n; j) b[0][j] 0;//存放各个子问题最优值的来源for(int i 1; i m; i){for(int j 1; i n; j){if(x[i]y[j]){c[i][j] c[i-1][j-1] 1;b[i][j] 1;}else if(c[i-1][j] c[i][j-1]){c[i-1] c[i-1][j];b[i][j] 3;}else {c[i][j] c[i][j-1];b[i][j] 2;}}}
}
5.图像压缩问题 图像的变位压缩存储格式将所给的像素点序列,分割个连续段。第个像素段中有个像素且该段中每个像素都只用位表示。设则第个像素段为 设则。因此需要用3位表示如果限制则需要用8位来表示。因此第个像素段所需要的存储空间为位。按此格式存储像素序列则需要位的空间。 图像压缩问题要求确定像素序列的最优分段使得依此分段所需要的存储空间最少。每个分段的长度不超过255位。
5.1最优子结构分析 设、是的最优分段。显而易见、是的最优分段。图像压缩问题满足最优子结构性质。 设是像素序列的最优分段所需的存储位数。 其中。
5.2代码分析
void Compress(int n, int p[], int s[], int l[], int b[]) {const int Lmax 256;const int header 11;s[0] 0;for (int i 1; i n; i) {b[i] length(p[i]); // 计算像素点 p[i] 需要的存储位数int bmax b[i];s[i] s[i - 1] bmax; // 赋初值l[i] 1;for (int k 2; k i k Lmax; k) {if (bmax b[i - k 1]) {bmax b[i - k 1];}if (s[i] s[i - k] k * bmax) {s[i] s[i - k] k * bmax;l[i] k;}}s[i] header; // 添加头部信息的开销}
}6.凸多边形最优三角剖分 凸多边形一个简单多边形及其内部构成一个闭凸集时称该简单多边形为凸多边形即凸多边形边界上或内部的任意两点所连成的直线段上所有点均在凸多边形的内部或边界上。 为方便描述用多边形顶点的逆时针序列表示凸多边形即表示具有条边的凸多边形。 若与是多边形上的不相邻的两个顶点则线段称为多边形的一条弦。弦将多边形分割成两个多边形和。 多边形的三角剖分是将多边形分割成互不相交的三角形的弦的集合T。 凸多边形的最优三角剖分给定凸多边形P以及定义在由多边形的边和弦组成的三角形上的权函数w要求确定该凸多边形的三角剖分使得该三角剖分中诸三角形上权之和为最小。
6.1最优子结构分析 假设存在一个凸多边形的最优剖分它的一个子凸多边形不是最优剖分。也就是说存在一个代价更小的三角剖分。如果是这样的话使用替换在保证其它子三角剖分不变的情况下会产生一个新的整体三角剖分它的代价更小则与是最优三角剖分的假设矛盾。所以凸多边形的最优三角剖分具有最优子结构性。
6.2递归关系建立 定义为凸子多边形的最优三角剖分所对应的权函数值取其最优值。为方便起见退化的多边形具有权值0。根据此定义要凸多边形P的最有权值为。 的值可以利用最优子结构性质递归地计算。当时凸子多边形至少有3个顶点。由最优子结构性质的值应为代表该三角形的权值其中。因此 6.3代码分析 void MinWeightTriangulation(int *weights, int n) {int t[N][N] {0}; // 用于存储子问题的最优解int s[N][N] {0}; // 用于存储分割点// 初始化for (int i 1; i n; i) {t[i][i] 0;}// 动态规划计算for (int r 2; r n; r) {for (int i 1; i n - r 1; i) {int j i r - 1;t[i][j] t[i 1][j] get_weight(i - 1, i, j, weights);s[i][j] i;// 尝试所有分割点for (int k i 1; k j; k) {int u t[i][k] t[k 1][j] get_weight(i - 1, k, j, weights);if (u t[i][j]) {t[i][j] u;s[i][j] k;}}}}
}7.0-1背包问题 给定个物品和1个背包。物品的重量是其价值为背包的容量为。如何选择装入背包的物品使得装入背包中物品的总价值最大? 通常称物体不可分割的背包问题为0-1背包问题。 问题的形式化描述为给定要求找出元0-1向量满足 7.1最优子结构性分析 假设是所给0-1背包问题的已给最优解则是下面相应子问题的一个最优解 7.2递归关系建立 令表示子问题的最优解。表示该问题的子问题的最优解。 最优解的递归关系式为 7.3代码分析
void knapsack(int W, int* p, int *w, int size)
{int C[size][W];//用于存储子问题的最优解for(int i 0; i size; i)for(int j 0; j W; j)C[i][j] 0;for(int i 1; i size; i)for(int j 1; j W; j){if(w[i-1] j){C[i][j]max(C[i-1][j],C[i-1][j-w[i-1]p[i-1]);}else C[i][j] C[i-1][j];}
}
8.最优二叉查找树 给定个关键字组成的有序序列用这些关键字构造一棵二叉查找树 该树具有性质存储于每个节点的元素大于左子树中任一个节点中的元素小于其右子树中任意节点的元素。 通常用平均比较次数来作为衡量不同二叉查找树查找效率的标准。设在表示为的二叉查找树中元素的结点深度为查找概率为虚节点为的结点深度为查找概率为。那么平均比较次数通常被定义为 最优二叉查找树是在所有表示有序序列的二叉查找树中具有最小平均比较次数的二叉树。 8.1最优子结构分析 将由实结点和虚结点构成的二叉查找树记为。设定元素作为该树的根结点。则二叉查找树的左子树由实结点和虚结点组成记为而右子树由实结点和虚结点组成记为 。 如果是最优二叉查找树假设它的左子树不是一个最优二叉查找树也就是说存在另一个二叉查找树有更小的查找次数那么在右子树不变的情况下拥有该左子树的二叉查找树的效率比原树更高那么原树就不是最优二叉查找树。则左子树和右子树也是最优二叉查找树。
8.2递归关系建立 设的一棵由实结点和虚节点构成的最优二叉查找子树为则表示 的平均比较次数。选定结点作为的根结点则左子树为右子树相应的比较次数分别为和。用表示查找实结点的概率用表示需节点的查找概率。 其中
令
得到
其中
8.3代码分析
#include iostream
#include vector
#include climitsusing namespace std;void build_optimal_bst(vectorint s, vectordouble p, vectordouble q) {int n s.size();// 初始化 C 和 R 数组vectorvectordouble C(n 1, vectordouble(n 1, 0));vectorvectorint R(n 1, vectorint(n 1, 0));// 计算 W 数组vectorvectordouble W(n 1, vectordouble(n 1, 0));for (int i 1; i n; i) {W[i][i - 1] q[i - 1];}// 动态规划填充 C 和 R 数组for (int l 1; l n; l) { // 子树长度从1到nfor (int i 0; i n - l; i) {int j i l;C[i][j] numeric_limitsdouble::max();for (int r i; r j; r) {double t W[i][j] C[i][r] C[r 1][j];if (t C[i][j]) {C[i][j] t;R[i][j] r;}}}}// 更新 W 数组for (int l 1; l n; l) {for (int i 0; i n - l; i) {int j i l;W[i][j] W[i][j - 1] p[j] q[j 1];}}cout Cost matrix C: endl;for (int i 0; i n; i) {for (int j 0; j n; j) {cout C[i][j] ;}cout endl;}cout \nRoot position matrix R: endl;for (int i 0; i n; i) {for (int j 0; j n; j) {cout R[i][j] ;}cout endl;}
}int main() {vectorint s {1, 3, 5, 7}; // 有序序列 Svectordouble p {0.15, 0.1, 0.25, 0.1}; // 查找概率 pvectordouble q {0.05, 0.15, 0.1, 0.15, 0.05}; // 边界及间隙概率 q// 构建 OBSTbuild_optimal_bst(s, p, q);return 0;
}
