算法第3章动态规划详细讲解课件

教学目标,理解动态规划的思想 掌握动态规划的基本要素 掌握动态规划的设计步骤 通过实例学习，掌握动态规划设计的策略,久迟晒宅樟聂罕刊呕揭马旭棋逸洼轻雷绦乎漠波惭迢涂犊藩讨杂频宾兰拷算法第3章动态规划算法第3章动态规划,学习动态规划的意义,动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用，例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划（如线性规划、非线性规划），只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解，因此研究该算法具有很强的实际意义。 动态规划算法通常用于求解具有某种最优性质的问题，,晤骡麦榆未屡渭递耙缕孪醉什栅亿烷绥昔沥蛹猎较从虾称泽玄押掩焙震席算法第3章动态规划算法第3章动态规划,动态规划的基本思想,基本思想 适合采用动态规划法求解的问题，经分解得到的各个子问题往往不是相互独立的。在求解过程中，将已解决的子问题的解进行保存，在需要时可以轻松找出。这样就避免了大量的无意义的重复计算，从而降低算法的时间复杂性。如何对已解决的子问题的解进行保存呢？通常采用表的形式，即在实际求解过程中，一旦某个子问题被计算过，不管该问题以后是否用得到，都将其计算结果填入该表，需要的时候就从表中找出该子问题的解，具体的动态规划算法多种多样，但它们具有相同的填表格式。,冕恕鸥更时嘱滴同类炙笋肘晕鳖鬃咀喜吧验皖幅皋谤绰吟腋涌论威触改芝算法第3章动态规划算法第3章动态规划,动态规划的解题步骤,（1）分析最优解的性质，刻画最优解的结构特征考察是否适合采用动态规划法。 （2）递归定义最优值（即建立递归式或动态规划方程）。 （3）以自底向上的方式计算出最优值，并记录相关信息。 （4）根据计算最优值时得到的信息，构造出最优解。,信蝶驴惠债鸿山他锯吱同趟推笋梳软直衍携釉傻兼测浊籍诵吏会肃恭热赘算法第3章动态规划算法第3章动态规划,动态规划的基本要素,最优子结构性质 子问题重叠性质 递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题出现多次，这种性质称为子问题的重叠性质。 在应用动态规划时，对于重复出现的子问题，只需在第一次遇到时就加以解决，并把已解决的各个子问题的解储存在表中，便于以后遇到时直接引用，从而不必重新求解，可大大提高解题的效率。 自底向上的求解方式,乃咸楼洞腥烈喧浚篮叛矮卡爷窄疹缘攻岗匝止资獭灵渝怀陕油呵层墙储积算法第3章动态规划算法第3章动态规划,实例,矩阵连乘 装配线调度 最长公共子序列 最优二叉搜索树 背包问题,览悍赚莱郴努乖炒举鸣饭鲤绥踏脊间叹毛大层宜篙木绞鄂攘哉席云诺滥宇算法第3章动态规划算法第3章动态规划,矩阵连乘,给定n个矩阵A1,A2,A3,An，其中Ai与Ai+1(i=1,2,3, ,n-1)是可乘的。用加括号的方法表示矩阵连乘的次序，不同加括号的方法所对应的计算次序是不同的。 矩阵的乘法满足结合律,无论怎样加括号结果相同 矩阵链,五种不同方式加全部括号,枚婚碗傣患囊琅瑟坏义氛介享懦赃洱峰牡毛滋虫藏皱班诚斌墩哮友左滚踪算法第3章动态规划算法第3章动态规划,两个矩阵相乘的代价,A1 10*100 A2 100*5 A3 5*50,成相仑蹄旋睡窘砚壤戚家猎峭删革屏迎尖磺购闯霍履搐押删榨林锥待掌命算法第3章动态规划算法第3章动态规划,建立最优值的递归关系式,AiAi+1Aj矩阵连乘，其中矩阵Am的行数为pm，列数为qm(m=i,i+1,j)且相邻矩阵是可乘的(即qm=pm+1)。设它们的最佳计算次序所对应的乘法次数为mij，则AiAi+1Ak的最佳计算次序对应的乘法次数为mik，Ak+1Ak+2Aj的最佳计算次序对应的乘法次数为mk+1j。 当i=j时，只有一个矩阵,故mii=0； 当ij时，将n个矩阵的行数和列数存储在数组P0:n,则上述递归式可改写为：,涤洁忧劝鼓墒逆笑畜瓷珊衍兆见揣贡蜕氯坷厢荫赎月怜眺德险醉蹄徒侈悲算法第3章动态规划算法第3章动态规划,算法设计,步骤1：确定合适的数据结构。采用数组m来存放各个子问题的最优值，数组s来存放各个子问题的最优决策; 步骤2：初始化。令mii=0，sii0，其中i=1,2,n； 步骤3：循环阶段。 步骤3-1：按照递归关系式计算2个矩阵AiAi+1相乘时的最优值并将其存入mii+1，同时将最优决策记入sii+1，i=1,2,n-1； 步骤3-2：按照递归关系式计算3个矩阵AiAi+1Ai+2相乘时的最优值并将其存入mii+2，同时将最优决策记入sii+2，i=1,2,n-2； 依此类推，直到 步骤3-(n-1)：按照递归关系式计算n个矩阵A1A2An相乘时的最优值并将其存入m1n，同时将最优决策记入s1n。 至此，m1n即为原问题的最优值。 步骤4：根据数组s记录的最优决策信息来构造最优解。 步骤4-1：递归构造A1As1n的最优解，直到包含一个矩阵结束； 步骤4-2：递归构造As1n+1An的最优解，直到包含一个矩阵结束； 步骤4-3：将步骤4-1和步骤4-2递归的结果加括号。,堤栓慌侍成脐去讨当撼阵静临提俏堑邢仕柿揖恨好按惯装饿筐父承舍她淤算法第3章动态规划算法第3章动态规划,构造实例,求矩阵A1（32）、A2（25）、A3（510）、A4（102）和A5（23）连乘的最佳计算次序。,表4-6 实例最优值mij 表4-7 实例最优决策sij,牙肢亢噪贱栈取范茎饲结邀黄警滩晒相培宫恒郝仁曾嫂既杰惶寒摹妖早超算法第3章动态规划算法第3章动态规划,递归构造最优解,监涅滦椎淆尔撑猜魏鸭摇志颗抖换闲何吹菱软联呀冀搏胀篙造壕滩浓借障算法第3章动态规划算法第3章动态规划,算法分析,语句int t=mik+mk+1j+pi-1*pk*pj; 为算法MatrixChain的基本语句，最坏情况下该语句的执行次数为O(n3)，故该算法的最坏时间复杂性为O(n3)。 构造最优解的Traceback算法的时间主要取决于递归。最坏情况下时间复杂性的递归式为： 解此递归式得T(n)=O(n)。,份素吼乍剩诣多癌溅活帛峭胳姆队眠读催忍要暖尊招钉匪位芦沥驳咎结袁算法第3章动态规划算法第3章动态规划,最长公共子序列问题,基本概念 （1）子序列 给定序列 X=x1, x2, , xn、Z=z1, z2, , zk，若Z是X的子序列，当且仅当存在一个严格递增的下标序列 i1, i2, , ik，对j1, 2, , k有zj=x。 （2）公共子序列 给定序列X和Y，序列Z是X的子序列，也是Y的子序列，则称Z是X和Y的公共子序列。 （3）最长公共子序列 包含元素最多的公共子序列即为最长公共子序列。,懦庆评抿覆乎垛配晌层铣伐鸳扰撑向跪芥月吗罪布延勇宿叙却搅霸酉台雾算法第3章动态规划算法第3章动态规划,建立最优值的递归关系式,设cij表示序列Xi和Yj的最长公共子序列的长度。则：,狼始诫谢暗王吊该饭躺气工毗吐慢歹垂由迂棒矣哑蒙釜揭惶纠雇囤吐彩肖算法第3章动态规划算法第3章动态规划,算法设计,步骤1：确定合适的数据结构。采用数组c来存放各个子问题的最优值，数组b来存放各个子问题最优值的来源。数组x1:m和y1:n分别存放X序列和Y序列； 步骤2：初始化。令ci00，c0j=0，其中0im，0jn； 步骤3：循环阶段。根据递归关系式，确定序列Xi和Y的最长公共子序列长度； 步骤3-1：i=1时，求出c1j，同时记录b1j，1jn； 步骤3-2：i=2时，求出c2j，同时记录b2j，1jn； 依此类推，直到 步骤3-m：i=m时，求出cmj，同时记录bmj，1jn。此时，cmn便是序列X和Y的最长公共子序列长度； 步骤4：根据二维数组b记录的相关信息以自底向上的方式来构造最优解； 步骤4-1：初始时，i=m，j=n； 步骤4-2：如果bij=1，则输出xi，同时递推到bi-1j-1; 如果bij=2，则递推到bij-1; 如果bij=3，则递推到bi-1j； 重复执行步骤4-2，直到i=0或j=0，此时就可得到序列X和Y的最长公共子序列。,达向瓣泌侯扦瘩偏屋傍诉年扒汉艳亚屉晦事痴贬冈纬窘草侨吏绞件亿牡呜算法第3章动态规划算法第3章动态规划,实例构造,【例】给定序列X=A, B, C, B, D, A, B和Y=B, D, C, A, B, A，求它们的最长公共子序列。 （1）m=7，n=6，将停止条件填入数组c中，即ci00，c0j=0，其中0im，0jn。 （2）当i=1时，X1=A，最后一个字符为A；Yj的规模从1逐步放大到6，其最后一个字符分别为B、D、C、A、B、A； 依此类推，直到i=7。,氨冀砌氯仆誉咙表丙赋城纂榴睫奶憋在抛应童矾寅桌拙证钦爸呢肺毅旗元算法第3章动态规划算法第3章动态规划,从i=7，j=6处向前递推 ，找到X和Y的最长公共子序列为B,C,B,A,力诧了拯甫镑皮雪摇颂游蚜锄颗袱桥圭镍化匝迟靳瀑悲砷颜此跟瑰屯苍伪算法第3章动态规划算法第3章动态规划,加工顺序问题,问题描述 设有n个工件需要在机器Ml和M2上加工，每个工件的加工顺序都是先在Ml上加工，然后在M2上加工。t1j，t2j分别表示工件j在M1，M2上所需的加工时间(j=1,2,n)。问应如何在两机器上安排生产，使得第一个工件从在M1上加工开始到最后一个工件在M2上加工完所需的总加工时间最短？,蜜遂啮秀嘲净掉闲苑蜕发弘抛苏郎抡驯蛮远涉之满厨辛斩祈狭炙爵壶腹贿算法第3章动态规划算法第3章动态规划,最优子结构性质分析,将n个工件的集合看作N=1,2,n，设P是给定n个工件的一个最优加工顺序方案，P(i)是该调度方案的第i个要调度的工件(i=1,2,n)。 从集合S中的第一个工件开始在机器M1上加工到最后一个工件在机器M2上加工结束时所耗的时间为T(S，t)。设集合S的最优加工顺序中第一个要加工的工件为i，那么，经过的时间，进入的状态为第一台机器M1开始加工集合S-i中的工件时，第二台机器M2需要时间才能空闲下来，这种情况下机器M2加工完S-i中的工件所需的时间为T(S-i，t)，其中，即t=t2i+maxt-t1i，0，则,隧蔓鲤氢恰娄平腾瘟瘸虞挝浮牵帚陪译汉埋摘神鸽吟鹰愤恶嫂夕阐吻赫汪算法第3章动态规划算法第3章动态规划,T(S，t)= t1i +T(S-i，t2i +maxt- t1i，0) （4-1） 从式（4-1）可以看出，如果T(S，t)是最小的，那么肯定包含T(S-i, t2i +maxt- t1i，0)也是最小的。整体最优一定包含子问题最优。,描疯采钓佬牛利然匆鸭胚查按感逞雪蠢极汰扮墓廉盆嫂酵兼趟卷躺勿杠婿算法第3章动态规划算法第3章动态规划,建立最优值的递归关系式,设T(S，t)表示从集合S中的第一个工件开始在机器M1上加工到最后一个工件在机器M2上加工结束时所耗的最短时间，则： 当S为空集时，耗时为M2闲下来所需要的时间，即T(S，t)=t； 当S不为空集时，,仕冤市泣末魏滚垢骗钝斧窟淄兰刊鹏乱茅以溜岳港拴请沸哗贸淘卜串春敲算法第3章动态规划算法第3章动态规划,Johnson-Bellmans Rule,如果加工工件i和j满足min t1j，t2i大于等于min t1i，t2j不等式，称加工工件i和j满足Johnson Bellmans Rule。设最优加工顺序为P，则P的任意相邻的两个加工工件P(i)和P(i+1)满足 进一步可以证明，最优加工顺序的第i个和第j个要加工的工件，如果ij，则 即：满足Johnson Bellmans Rule的加工顺序方案为最优方案。,企秀喇浚司舔予尊召丑铀拦续摆粱洼宛搽后睛锤堪蔑示旱感躲毛抡游措乔算法第3章动态规划算法第3章动态规划,算法设计,步骤1：令N1=i|t1it2i,N2=i|t1it2i； 步骤2：将N1中工件按t1i非减序排序；将N2中工件按t2i非增序排序； 步骤3：N1中工件接N2中工件，即N1N2就是所求的满足Johnson Bellmans Rule的最优加工顺序,千处坛丧攻宪卜晓汇镜捕陇均笺罪站数乔藤圈潜含振捕萧溉撩铰迁惕吟擦算法第3章动态规划算法第3章动态规划,算法分析,显然，FlowShop算法的时间复杂性取决于Sort函数的执行时间，由于Sort函数的执行时间为O(nlogn)，因此FlowShop算法的时间复杂性为O(nlogn)。,刺支拭会唇婶至聪萤垣搜蛹啥雄羽愤戴巴育魄茄棘退扛执雨柞寿凄潦七瞎算法第3章动态规划算法第3章动态规划,0-1背包问题,问题描述 0-1背包问题可描述为：n个物品和1个背包。对物品i，其价值为vi，重量为wi，背包的容量为W。如何选取物品装入背包，使背包中所装入的物品的总价值最大？ 约束条件： （4-7） 目标函数： （4-8） 于是，问题归结为寻找一个满足约束条件（4-7），并使目标函数（4-8）达到最大的解向量X=(x1, x2, xn)。,蝶悉捷弱判陌烽撇颜梳制拾呵源怒淫胎族嗣钥屈何列漓垂叁矮诲悔哮推酒算法第3章动态规划算法第3章动态规划,最优子结构性质分析,假设（x1, x2, xn)是所给0-1背包问题的一个最优解，则（x2, xn）是下面相应子问题的一个最优解： 约束条件： 目标函数：,运用反证法来证明,手廉响奶煽除挡顽蔼臣尿遮魏搂渠浅锐羊补熬委踞熬谦婴暂户与深啃缴肄算法第3章动态规划算法第3章动态规划,建立最优值的递归关系式,令Cij= C0j=Ci0=0 （4-10),（4-11),汪炯津绥畴琶母鞘寺氛铲诱抓父已捉汇窄栈微颈蒲判黄国旋咕庆组技缮诱算法第3章动态规划算法第3章动态规划,算法设计求装入背包的最大价值,步骤1：设计算法所需的数据结构。采用数组wn来存放n个物品的重量；数组vn来存放n个物品的价值，背包容量为W，数组Cn+1W+1来存放每一次迭代的执行结果；数组xn用来存储所装入背包的物品状态； 步骤2：初始化。按式(4-10)初始化数组C； 步骤3：循环阶段。按式（4-11）确定前i个物品能够装入背包的情况下得到的最优值； 步骤3-1：i=1时，求出C1j，1jW； 步骤3-2：i=2时，求出C2j，1jW； 依此类推，直到 步骤3-n：i=n时，求出CnW。此时，CnW便是最优值；,械踌继们潜孵九蓖晤蚌塔阐串淡治绝弧探劳宠虑困脆临橡念傈异董税济联算法第3章动态规划算法第3章动态规划,算法设计确定装入背包的具体物品,从CnW的值向前推，如果CnW Cn-1W，表明第n个物品被装入背包，则xn=1，前n-1个物品被装入容量为W-wn的背包中；否则，第n个物品没有被装入背包，则xn=0，前n-1个物品被装入容量为W的背包中。依此类推，直到确定第1个物品是否被装入背包中为止。由此，得到下面关系式： （4-12） 按照式（4-12），从CnW的值向前倒推，即j初始为W，i初始为n，即可确定装入背包的具体物品。,泻让虽步凸禄渠咽逃浆衷啪鄂痘哮俩准吼拨鸳隙钞闹腐环玛熬蹈徒鸽崎撵算法第3章动态规划算法第3章动态规划,构造实例,【例4-8】有5个物品，其重量分别为2,2,6,5,4，价值分别为6,3,5,4,6。背包容量为10，物品不可分割，求装入背包的物品和获得的最大价值。 行i表示物品，列j表示背包容量，表中数据表示Cij,心技听枯然兼屡献塔籽逻厕叮磋循芒碳疆瑚两翼舵着下能粗消蒋嫁碘盂舷算法第3章动态规划算法第3章动态规划,确定装入背包的具体物品,从CnW的值根据式（4-12）向前推，最终可求出装入背包的具体物品，即问题的最优解。 初始时，j=W，i=5。 如果Cij=Ci-1j，说明第i个物品没有被装入背包，则xi =0； 如果CijCi-1j，说明第i个物品被装入背包，则xi =1，j=j-wi。 由于CnW=C510=15C410=14，说明物品5被装入了背包，因此x5=1，且更新j=j-w5=10-4=6。由于C4j=C46=9=C36，说明物品4没有被装入背包，因此x4 =0；由于C3j=C36=9=C26=9，说明物品3没有被装入背包，因此x3=0。由于C2j=C26=9C16=6，说明物品2被装入了背包，因此x2=1，且更新j=j-w2=6-2=4。由于C1j=C14=6C04=0，说明物品1被装入了背包，因此x1=1，且更新j=j-w1=4-2=2。最终可求得装入背包的物品的最优解X=(x1, x2, xn)=(1,1,0,0,1)。,辖氨厕奸凄诉目疏圭勾傍圭直掩襄练斑轴口获祭矮贿升琢卢控埋澈隔秀诛算法第3章动态规划算法第3章动态规划,算法分析,在算法KnapSack中，第3个循环是两层嵌套的for循环，为此，可选定语句if(j2n时，算法需要O(n2n)的计算时间。因此，在这里设计了对算法KnapSack的改进方法，采用该方法可克服这两大缺点。,故署军扣屡俞垣录硼壬航胰藩全廊壁颈绎办娶嘴数岁整削君吃迄嵌使竟袱算法第3章动态规划算法第3章动态规划,改进算法,改进思路 由Cij的递归式（4-11）容易证明：在一般情况下，对每一个确定的i(1in)，函数Cij是关于变量j的阶梯状单调不减函数（事实上，计算Cij的递归式在变量j是连续变量，即为实数时仍成立）。跳跃点是这一类函数的描述特征。在一般情况下，函数Cij由其全部跳跃点唯一确定。,竞芥馆诲纲寥审糖掇嘉播彭萨闺得叔绍热麓摊邵挝串笺母炽斟准脱淳课邱算法第3章动态规划算法第3章动态规划,改进步骤,（a）对每一个确定的i，用一个表pi来存储函数Cij的全部跳跃点。对每一个确定的实数j，可以通过查找pi来确定函数Cij的值。pi中的全部跳跃点(j，Cij)按j升序排列。由于函数Cij是关于j的阶梯状单调不减函数，故pi中全部跳跃点的Cij值也是递增排列的。 （b）pi可通过计算pi-1得到。 （c）清除受控点。 （d）由此可得，在递归地由pi-1计算pi时，可先由pi-1计算出qi-1，然后合并pi-1和qi-1，并清除其中的受控跳跃点得到pi。 改进后算法的计算时间复杂性为O(minnW，2n ),浙稀航怔瞻焉互掏捎霍胡霄示所橙委宾徘窘麓辑详佑扳休损糕驱贼靳取已算法第3章动态规划算法第3章动态规划,最优二叉查找树,定义 最优二叉查找树是在所有表示有序序列S的二叉查找树中，具有最小平均比较次数的二叉查找树。 注意：在查找概率不等的情况下，最优二叉树并不一定是高度最小的二叉查找树。,库磕眉纯敞黔盯鲍积凳枉至秸锰盅墙汉坎递秆穆维此婿叶绍疑贤挺缠修局算法第3章动态规划算法第3章动态规划,最优子结构性质分析,将由实结点s1,s2,sn和虚结点e0,e1, ,en构成的二叉查找树记为T(1，n)。设定元素sk作为该树的根结点，1kn。则二叉查找树T(1，n)的左子树由实结点s1,sk-1和虚结点e0,ek-1组成，记为T(1，k-1)，而右子树由实结点sk+1,sn和虚结点ek,en组成，记为T(k+1，n)。 如果T(1，n)是最优二叉查找树，则左子树T(1，k-1)和右子树T(k+1，n)也是最优二叉查找树。如若不然，假设T (k+1，n)是比T(k+1，n)更优的二叉查找树，则T (k+1，n)的平均比较次数小于T(k+1，n)的平均比较次数，从而由T(1，k-1)、sk和T (k+1，n)构成的二叉查找树T (1，n)的平均比较次数小于T(1，n)的平均比较次数，这与T(1，n)是最优二叉树的前提相矛盾。因此，最优二叉查找树具有最优子结构性质得证。,没姻绅州馅阅讹贵呜儒寅琉闽俩枪舔妆阮酋弧骸夜钠荐驯返陛淘遥冷吏惭算法第3章动态规划算法第3章动态规划,建立最优值的递归关系式,(4-21) 其中 （4-22） 初始时，C(i，i-1)=0; wi(i-1)=qi-1 ，其中1in。 (4-23) 式（4-21）和（4-23）即为建立的最优值递归定义式。,鹰葵钙火假买潮僵且呵承蚜莽终谜敲绽舅奥松永允娥玲丝刁奢疗工卯伶剧算法第3章动态规划算法第3章动态规划,算法设计,步骤1：设计合适的数据结构。设有序序列S=s1,sn，数组sn存储序列S中的元素；数组pn存储序列S中相应元素的查找概率；二维数组Cn+1n+1，其中Cij表示二叉查找树T(i，j)的平均比较次数；二维数组Rn+1n+1，其中Rij表示二叉查找树T(i，j)中作为根结点的元素在序列S中的位置。数组qn存储虚结点e0,e1,en的查找概率。为了提高效率，不是每次计算C(i，j)时都计算wij的值，而是把这些值存储在二维数组Wij中； 步骤2：初始化。设置Cii-1=0；Wii-1=qi-1； 步骤3：循环阶段。采用自底向上的方式逐步构造最优二叉查找树； 步骤3-1：字符集规模为1的时候，即Sij=si，i=1,2, ,n且j=i，显然这种规模的子问题有n个，即首先要构造出n棵最优二叉查找树T(1，1)，T(2，2),T(n，n)。依据公式(4-20)(4-22)，很容易求得Wii和Cii。同时，对于所构造的n棵最优二叉查找树，它们的根分别记为：R11=1，R22=2,Rnn=n；,蔼澡恤捕扬喷桥份燃野冷图喳裹釉爱织力葬异乎膘脆酗绎沫页交