算法设计与分析6章 动态规范算法.pptVIP

第6章 动态规范算法 6.1 一般方法 6.2 多段图 6.3 每对节点之间的最短路径 6.4 最优二分检索树 6.5 0/1背包问题 6.6 可靠性设计 6.7 货郎担问题 6.8 流水线调度问题 学习要点: 理解动态规划算法的概念。 掌握动态规划算法的基本要素 （1）最优子结构性质 （2）重叠子问题性质 掌握设计动态规划算法的步骤。 (1)找出最优解的性质，并刻划其结构特征。 (2)递归地定义最优值。 (3)以自底向上的方式计算出最优值。 (4)根据计算最优值时得到的信息，构造最优解。 通过应用范例学习动态规划算法设计策略。 (1) 多段图 （2） 每对节点间的最短路径 （3）最优二分检索树； （4）0/1 背包问题 （5）可靠性设计； （6）货郎担问题 （7）流水作业调度； 6.1 一般方法 把已知问题分为许多阶段或许多子问题，然后按顺序求解各个子问题。 在每种情况下，列出各种可能的局部解，然后根据某些条件，从局部中挑选中那些有可能产生最优结果的解 前一个子问题的解为后一个子问题的求解提供有用的信息，从而大大减少了计算量 最优性原理： 不论初始状态和第一步决策是什么，余下的决策必须按照前一次决策所产生的新状态构成一个最优决策序列。 不论前面的状态和策略如何，后面的最优策略只取决于由最初策略所决定的当前状态 动态规划的向前处理法： 从最后阶段开始，以逐步向前递推的方式求出前一阶段决策值的递推关系式，即根据xi+1,…,xn的那些最优决策来求取xi决策值的关系式 列出关系式后，由最后阶段开始，回溯求解这些关系式得出最优决策序列 6.2 多段图 多段图G=(V,E)是一个有向图。它具有如下的特性：图中的节点被划分成k=2个不相交的集合Vi, 1=i=k， 其中Vi和Vk分别只有一个节点s(源点）和t（汇聚点）。 图中的所有的边u,v均具有如下性质： 若u ∈Vi, 则v ∈Vi+1,1=ik-1, 且没条边均附有成本c(u,v); 从s到t的一条路径成本是这条路径上边的成本和。多段图问题是求由s到t的最小成本路径 假设s, V2,V3,…,Vk-1, t是由s到t的最短路径，同时假定从源点s(初始状态）开始，已作出了到结点V2的决策（初始决策），因此V2就是初始决策所产生的状态。 如果把V2看成是原问题的一个子问题的初始状态，解这个子问题就是找出一条由v2到t的最短路径。这条最短路径是V2,V3,…,Vk-1, t 否则设V2,q3,…,qk-1, t是一条由V2到t的更短路径，则s, V2,q3,…,qk-1, t是一条比s, V2,V3,…,Vk-1, t更短的由s到t的路径。与假设相矛盾，故最优性原理成立。 设P(i,j)是一条从Vi中的节点j到汇点t的最小成本路径，COST(i,j)是这条路径的成本。那么，由向前处理法可以得到 COST(i,j)=min{c(j,1)+COST(j+1,1)} 当j,t∈E时， COST(k-1,j)=c(j,t), 如果j,t 不属于E时， COST(k-1,j)=无穷大 FGRAPH(Elemtype E[], int k, int n, Elemtype P[k]) 1 COSt[n]?0 2 for j?n-1 to 1 by -1 3 do {设r是这样的一个节点，j,r属于E，且使c[j][r]+COST[r]取最小值 4 COST[j]?c[j][r]+COST[r]; 5 D[j]?r; 6 } P[1]?1; P[k]?n 8 for j?2 to k-1 9 do { P[j]?D[P[j-1]];} 6.3 每对节点之间的最短路径 设G=（V,E）是一个有n个节点的有向图。又设C是G的成本邻接矩阵，其中C(i,j)=0, 1=i=n; 当i,j∈E (G)时，C(i,j)表示边i,j的长度；ij 6.4 最优二分检索树 检索一个二分检索树的算法： 输入：二分检索树T和被查找元素X 输出：如果X不在T中，则置i=0，否则将i置成INDEX[i]=X SEACH(Elemtype T, Elemtype X) 1 int i?t; 2 while i0; 3 do { 4 if (xINDEX[i]) 5 {i?LCHILD[i];} 6 else if (xINDEX[i] 7 {i?RCHILD[i])} 8 else x?INDEX[i]; 9 return i; 10 } 0/1背包问题(0/1 Knapsack) 问题描述 有n种可选物品1,…,n ，