动态规划算法举例分析.doc

动态规划算法1. 动态规划算法介绍基本思想是将待求解问题分解成若干子问题，先求解子问题，最后用这些子问题带到原问题，与分治算法的不同是，经分解得到的子问题往往是不是相互独立，若用分治则子问题太多。2. 适用动态规划算法问题的特征（1）最优子结构设计动态规划算法的第一步骤通常是要刻画最优解的结构。当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。问题的最优子结构性质提供了该问题可用动态规划算法求解的重要线索。在动态规划算法中，问题的最优子结构性质使我们能够以自底向下的方式递归地从子问题的最优解逐步构造出整个问题的最优解。同时，它也使我们能在相对小的子问题空间中考虑问题。（2）重叠子问题可用动态规划算法求解的问题应具备的另一基本要素是子问题的重叠性质。在用递归算法自顶向下解此问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只有简单地用常数时间查看一下结果。通常，不同的子问题个数随输入问题的大小呈多项式增长。因此，用动态规划算法通常只需要多项式时间，从而获得较高的解题效率。（3）备忘录方法动态规划算法的一个变形是备忘录方法。备忘录方法也是一个表格来保存已解决的子问题的答案，在下次需要解此子问题时，只要简单地查看该子问题的解答，而不必重新计算。与动态规划算法不同的是，备忘录方法的递归方式是自顶向下的，而动态规划算法则是自底向上递归的。因此，备忘录方法的控制结构与直接递归方法的控制结构相同，区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看，避免了相同子问题的重复求解。备忘录方法为每个子问题建立一个记录项，初始化时，该记录项存入一个特殊的值，表示该子问题尚未求解。在求解过程中，对每个待求的子问题，首先查看其相应的记录项。若记录项中存储的是初始化时存入的特殊值，则表示该子问题是第一次遇到，则此时计算出该子问题的解，并保存在其相应的记录项中。若记录项中存储的已不是初始化时存入的特殊值，则表示该子问题已被计算过，其相应的记录项中存储的是该子问题的解答。此时，只要从记录项中取出该子问题的解答即可。3. 基本步骤 a、找出最优解的性质，并刻画其结构特征。 b、递归地定义最优值。 c、以自底向上的方式计算出最优值。 d、根据计算最优值时得到的信息构造一个最优解。（可省）例1-1 0/1背包问题 问题描述用贪心算法不能保证求出最优解。在0/1背包问题中，需要对容量为c的背包进行装载。从n个物品中选取装入背包的物品，每件物品i的重量为，价值为。对于可行的背包装载，背包中物品的总重量不能超过背包的容量，最佳装载是指所装入的物品价值最高，即取得最大值。约束条件为，。 在这个表达式中，需要求的值。=1表示物品i装入背包中，=0表示物品i不装入背包。1.找出最优解性质考察上述0 / 1背包问题。如前所述，在该问题中需要决定x1，xn的值。假设按i = 1，2，n 的次序来确定xi 的值。如果置x1 = 0，则问题转变为相对于其余物品（即物品2，3，n），背包容量仍为c 的背包问题。若置x1 = 1，问题就变为关于最大背包容量为c-w1 的问题。现设rc，c-w1 为剩余的背包容量。在第一次决策之后，剩下的问题便是考虑背包容量为r 时的决策。不管x1 是0或是1，x2 ，xn 必须是第一次决策之后的一个最优方案，如果不是，则会有一个更好的方案y2，yn ，因而x1，y2，yn 是一个更好的方案。因此最优解符合条件，。例：假设n=3, w=100,14,10, p=20,18,15, c= 116。若设x1 = 1，则在本次决策之后，可用的背包容量为r= 116-100=16 。x2，x3 =0,1 符合容量限制的条件，所得值为1 5，但因为x2，x3 = 1，0 同样符合容量条件且所得值为1 8，因此x2，x3 = 0，1 并非最优策略。即x= 1，0，1 可改进为x= 1，1，0 。若设x1 = 0，则对于剩下的两种物品而言，容量限制条件为11 6。总之，如果子问题的结果x2，x3 不是剩余情况下的一个最优解，则x1，x2，x3 也不会是总体的最优解。2.递归定义最优解在上述例题的0 / 1背包问题中，最优决策序列由最优决策子序列组成。假设m(i,v) 表示例子中剩余容量为j，剩余物品为i，i+1，n 时的最优解的值，即： （1）和 （2）因此，m（1，c）是初始时最优问题的最优解。现在计算xi值，步骤如下：若m(1 ,c) =m( 2 ,c)，则x1 = 0，否则x1 = 1。接下来需从剩余容量c-w1中寻求最优解，用m(2, c-w1) 表示最优解。依此类推，可得到所有的xi (i= 1，2，n) 值。0/1背包问题的C语言实现算法#define N 12void Knapsack(int v,int w,int c,int n,int m6N) int i,j,jMax,k; jMax=(wn-1c?wn-1:c); for(i=0;i=jMax;i+) mni=0; for(i=wn;i1;i-) jMax=(wi-1c?wi-1:c); for(j=0;j=jMax;j+) mij=mi+1j; for(j=wi;j=c;j+) k=j-wi; if(mi+1j=w1) k=c-w1; m1c=(m2cm2k+v1)?m2c:m2k+v1; void Traceback(int m6N,int w,int c,int n,int x) int i; for(i=1;iN;i+) if(mic=mi+1c) xi=0; else xi=1; c-=wi; xn=(mnc)?1:0;main() int i,c=10,n=5,w=0,2,2,6,5,4,v=0,6,3,5,4,6; int m6N=0; int x6=0; int j; Knapsack(v,w,c,n,m); for(i=1;i=n;i+) for(j=1;j=c;j+) printf(%3d,mij); printf(n); Traceback(m,w,c,n,x); for(i=1;i=n;i+) if(xi) printf(%4d:%4d,i,vi); printf(n);例2-1 最短路径问题 问题描述4现有一张地图，各结点代表城市，两结点间连线代表道路，线上数字表示城市间的距离。如图2所示，试找出从结点1到结点7的最短路径。8685 65 79945 图2 有向图1. 找出最优解性质在第一次决策到达了某个节点之后，不管怎样确定，剩下的问题就是选择从到的最短路径。在所有点对最短路径问题（ 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) 之间总有一条不含环路的最短路径。2. 递归定义最优值 上述问题已经转化为寻找从i到j的最短路径。若记最短路径的长度为eej.逊县将其初始值赋值为。 设k为从i到j中节点编号中最大的数，则用C（i，j，k）表示经过节点k的通路的路径长度。若C（i，j，k） eej，则eej =C（i，j，k）。如此寻遍中每条通路，则得到的eej为的最短路径长度。最后递归得到从节点1到节点7的最短路径长度。最短路径问题的C语言算法实现#include #define N 7 /* 顶点数目 */#define I 999 /* 表示无穷大 */int graphNN = /* 图的邻接矩阵 */ I, 4, 5, 8, I, I, I, I, I, I, 6，6, I, I, I, I, I, 5, I, 7, I, I, I, I, I, 8, 9, 9, I, I, I, I, I, I, 5, I, I, I, I, I, I, 4, I, I, I, I, I, I, I;int ListN; /* 存放拓扑序列 */int TopologicalOrder(); /* 拓扑排序函数 */void main() /* 主 函 数 */ int i, j, k, l; int eeN; /* 最短距离 */ int path_eNN, n_eN; /* 记录路径数据 */ /* 初始化数据 */ for (i = 0; i N; i+) n_ei = 0; /* 到 i 的最短路线的结点数 */ eei = I; ee0 = 0; /* 初始化头结点 */ path_e00 = 0; n_e0 = 1; /* 拓扑排序 */ if (!TopologicalOrder() return; /* 对于拓扑序列,运用动态规划步步算出最短路线 */ for (i = 0; i N; i+) k = Listi; /* 提取拓扑序列的元素 */ for (j = 0; j N; j+) /* 更新它所指向顶点的所有数据 */ if (graphkj != I) /* 寻找指向的顶点 */ if (graphkj + eek eej) /* 如果新路径更短 */ eej = graphkj + eek; /* 更新最短路径长度 */ for (l = 0; l n_ek; l+) /* 更新最短路线 */ path_ejl = path_ekl; path_ejl = j; n_ej = l + 1; /* 输出结果到屏幕 */ for (i = 0; i N; i+) printf(shortest(%d): %2d Path: , i + 1, eei); for (j = 0; j n_ei; j+) printf(%d , path_eij + 1); printf(n); int TopologicalOrder() int i, j, top, count; int indegreeN, StackN; top = 0; /* 栈顶标志 */ for (i = 0; i N; i+) indegreei = 0; /* 初始化入度 */ for (j = 0; j N; j+) if (graphji != I) /* 如连通 */ indegreei+; /* 入度自增1 */ if (!indegreei) /* 如入度为零 */ Stacktop+ = i; /* 入栈 */ count = 0; while (top != 0) /* 输出顶点数 */ i = Stack-top; Listcount+ = i; for (j = 0; j N; j+) if (graphij != I) /* 如连通 */ if (!(-indegreej) /* 而且入度为零 */ Stacktop+ = j; /* 入栈 */ /* for */ /* while */ return (count N) ? 0 : 1;例3 航费问题 某航线价格表为：从亚特兰大到纽约或芝加哥，或从洛杉矶到亚特兰大的费用为$ 100；从芝加哥到纽约票价$20；而对于路经亚特兰大的旅客，从亚特兰大到芝加哥的费用仅为$20。从洛杉矶到纽约的航线涉及到对中转机场的选择。如果问题状态的形式为（起点，终点），那么在选择从洛杉矶到亚特兰大后，问题的状态变为（亚特兰大，纽约）。从亚特兰大到纽约的最便宜航线是从亚特兰大直飞纽约，票价$100。而使用直飞方式时，从洛杉矶到纽约的花费为$200。不过，从洛杉矶到纽约的最便宜航线为洛杉矶-亚特兰大-芝加哥-纽约，其总花费为$ 140（在处理局部最优路径亚特兰大到纽约过程中选择了最低花费的路径：亚特兰大-芝加哥-纽约）。如果用三维数组（tag，起点，终点）表示问题状态，其中tag为0表示转飞，tqg为1表示其他情形，那么在到达亚特兰大后，状态的三维数组将变为（ 0，亚特兰大，纽约），它对应的最优路径是经由芝加哥的那条路径。当最优决策序列中包含最优决策子序列时，可建立动态规划递归方程（dy namic-programming recurrence equation），它可以帮助我们高效地解决问题。动态规划算法与其它算法的比较在比较基本的算法设计思想里，动态规划是比较难于理解，难于抽象的一种，但是却又十分重要。动态规划的实质是分治思想和解决冗余，因此它与分治法和贪心法类似，它们都是将问题的实例分解为更小的、相似的子问题，但是动态规划又有自己的特点。贪心法的当前选择可能要依赖于已经作出的选择，但不依赖于还未做出的选择和子问题，因此它的特征是由顶向下，一步一步地做出贪心选择，但不足的是，如果当前选择可能要依赖子问题的解时，则难以通过局部的贪心策略达到全局最优解。相比而言，动态规划则可以处理不具有贪心实质的问题。在用分治法解决问