第六章动态规划课件.ppt

第六章动态规划本章主要内容:1、一般方法2、多段图3、每对节点之间的最短路径(自学)4、最优二分检索树5、0/1背包问题6、可靠性设计7、货郎担问题8、流水线调度问题1§1、一般方法一、动态规划第六章动态规划定义:若某一问题可分为多个阶段,阶段i以后的行为仅依赖于阶段i时的状态,解决该阶段多决策问题的算法设计方法,称为动态规划,满足该规定的问题,称该问题满足最优性原理。二、动态规划的关键获取多阶段的递推公式2例1多段图G=(V,E)是一个有向图,求s到t的最短路径12969123457810117347281111221654365245st§1、一般方法第六章动态规划V1V2V3V4V53多段图G=<V,E>是一个满足如下特性的有向图,V被划分成K个不相交的集合Vi,其中V1只有一个结点s(源点),Vk只有一个结点t(汇点),并且每边赋有成本C(u,v),试求从s到t得最小成本结点。§1、[0/1背包问题]此问题除了限定Xi必须取0或1值外,。用KNAP(1,j,x)来表示这个问题。极大化:约束条件:()§1、一般方法第六章动态规划转下页51、多段图问题满足最优性原理证明证明:由于s到t的路径分为k段,当s到k-1段的各结点的最短路径求出后,s到t的最短路径即可求出,故该问题满足最优性原理。2、0/1背包问题满足最优性原理证明证明:设L1….Ln分别为X1….Xn的0/1值的最优序列,若L1=0,则§1、一般方法第六章动态规划三、最优性原理证明L2….Ln必相对于KNAP(2,n,M)的最优解,若L1=1,则L2….Ln必相对于KNAP(2,n,M-w1)的最优解,否则若存在另一个序列s2….sn,使得KNAP(2,n,M-w1)为最优序列的话,则1s2….sn对KNAP(1,n,M)构成最优解,这与前提L1….Ln为X1….Xn的最优解的前提矛盾。证毕。6四、动态规划的向前处理法根据的最优决策序列来列出求取的关系式,称为动态规划的向前处理法。例3:在k段图问题中,设设是由到t的最短路径,则s到t的最短路径是§1、一般方法第六章动态规划若设是s到t的一条最短路径,vi是路径上的中间节点,则和到t,就应该分别是由s到和由到t的最短路径。中最短的那条路径。,设是KNAP(j+1,n,x)最优解的值,显然是KNAP(1,n,M)最优解的值。由于可能的取值是0或1,因此可得由于可能的取值也是0或1,因此可以得出递推关系式动态规划关键:递推关系式7/76xj+1=0xj+1=1§1、一般方法第六章动态规划五、动态规划向后处理法根据的那些最优决策序列,列出求的决策值的递推关系式,称为动态规划的向后处理法。,设又设是由s到的最短路径,那么s到t的最短路径就是中最短的那条路径。§1、,设fi(x)是KNAP(1,i,x)最优解的值,由向后处理法可列出如下的递推关系式:xi=0xi=1§1、一般方法第六章动态规划10