算法设计和分析6章 动态规范算法ppt课件.ppt

《算法设计和分析6章 动态规范算法ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第6章动态规范算法6.1一般方法6.2多段图6.3每对节点之间的最短路径6.4最优二分检索树6.50/1背包问题6.6可靠性设计6.7货郎担问题6.8流水线调度问题学习要点:理解动态规划算法的概念。掌握动态规划算法的基本要素（1）最优子结构性质（2）重叠子问题性质掌握设计动态规划算法的步骤。(1)找出最优解的性质，并刻划其结构特征。(2)递归地定义最优值。(3)以自底向上的方式计算出最优值。(4)根据计算最优值时得到的信息，构造最优解。通过应用范例学习动态规划算法设计策略。(1)多段图（2）每对节点间的最短路径（3）最优二分

2、检索树；（4）0/1背包问题（5）可靠性设计；（6）货郎担问题（7）流水作业调度；6.1一般方法把已知问题分为许多阶段或许多子问题，然后按顺序求解各个子问题。在每种情况下，列出各种可能的局部解，然后根据某些条件，从局部中挑选中那些有可能产生最优结果的解前一个子问题的解为后一个子问题的求解提供有用的信息，从而大大减少了计算量最优性原理：不论初始状态和第一步决策是什么，余下的决策必须按照前一次决策所产生的新状态构成一个最优决策序列。不论前面的状态和策略如何，后面的最优策略只取决于由最初策略所决定的当前状态动态规划的向前处理法：从

3、最后阶段开始，以逐步向前递推的方式求出前一阶段决策值的递推关系式，即根据xi+1,…,xn的那些最优决策来求取xi决策值的关系式列出关系式后，由最后阶段开始，回溯求解这些关系式得出最优决策序列6.2多段图多段图G=(V,E)是一个有向图。它具有如下的特性：图中的节点被划分成k>=2个不相交的集合Vi,1<=i<=k，其中Vi和Vk分别只有一个节点s(源点）和t（汇聚点）。图中的所有的边均具有如下性质：若u∈Vi,则v∈Vi+1,1<=i

4、成本和。多段图问题是求由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的路径。与假设相矛盾，故最优性原理成立

5、。123456781291110StV2V3V497324227111186543156425设P(i,j)是一条从Vi中的节点j到汇点t的最小成本路径，COST(i,j)是这条路径的成本。那么，由向前处理法可以得到COST(i,j)=min{c(j,1)+COST(j+1,1)}当∈E时，COST(k-1,j)=c(j,t),如果不属于E时，COST(k-1,j)=无穷大FGRAPH(ElemtypeE[],intk,intn,ElemtypeP[k])1COSt[n]02forjn-1to1by-

6、13do{设r是这样的一个节点，属于E，且使c[j][r]+COST[r]取最小值4COST[j]c[j][r]+COST[r];5D[j]r;6}P[1]1;P[k]n8forj2tok-19do{P[j]D[P[j-1]];}6.3每对节点之间的最短路径设G=（V,E）是一个有n个节点的有向图。又设C是G的成本邻接矩阵，其中C(i,j)=0,1<=i<=n;当∈E(G)时，C(i,j)表示边的长度；i<>j6.4最优二分检索树检索一个二分检索树的算法：输入：二分检索树T和被查找元

7、素X输出：如果X不在T中，则置i=0，否则将i置成INDEX[i]=XSEACH(ElemtypeT,ElemtypeX)1intit;2whilei<>0;3do{4if(xINDEX[i]7{iRCHILD[i])}8elsexINDEX[i];9returni;10}查找成功与不成功的概率二查找树的期望耗费有个节点的二叉树的个数为：穷举搜索法的时间复杂度为指数级二叉查找树的期望耗费二叉查找树的期望耗费示例最优二叉搜索树最优二叉搜索树Tij的平均

8、路长为pij，则所求的最优值为p1,n。由最优二叉搜索树问题的最优子结构性质可建立计算pij的递归式如下记wi,jpi,j为m(i,j)，则m(1,n)=w1,np1,n=p1,n为所求的最优值。计算m(i,j)的递归式为注意到，可以得到O(n2)的算法0/1背包问题(0/1Knapsac