《第5章动态规划》由会员分享，可在线阅读，更多相关《第5章动态规划（127页珍藏版）》请在金锄头文库上搜索。
1、第四章第四章 动态规划动态规划4.1 一般方法一般方法1. 多阶段决策问题多阶段决策问题 多阶段决策过程多阶段决策过程：问题的活动过程分为若干相互联系的阶段，任一：问题的活动过程分为若干相互联系的阶段，任一阶段阶段i以后的行为仅依赖于以后的行为仅依赖于i阶段的过程状态，而与阶段的过程状态，而与i阶段之前的过程如何阶段之前的过程如何达到这种状态的方式无关。在每一个阶段都要做出决策，这一系列的决达到这种状态的方式无关。在每一个阶段都要做出决策，这一系列的决策称为多阶段决策过程策称为多阶段决策过程(multistep decision process) 。 最优化问题最优化问题：问题的每一阶段可能有
2、多种可供选择的决策，必须从：问题的每一阶段可能有多种可供选择的决策，必须从中选择一种决策。各阶段的决策构成一个决策序列。决策序列不同，所中选择一种决策。各阶段的决策构成一个决策序列。决策序列不同，所导致的问题的结果可能不同。导致的问题的结果可能不同。 多阶段决策的最优化问题多阶段决策的最优化问题就是：求能够获得问题最优解的决策序列就是：求能够获得问题最优解的决策序列最优决策序列。最优决策序列。晾每倔转渔院瞳惭沼狸释睦筷橱浆饭钙驴焉靴耪松闰垃浊花胯窥邪兆惜侮第5章动态规划第5章动态规划本章教学要求及重点难点本章教学要求及重点难点n理解动态规划的基本思想；理解动态规划的基本思想； n掌握动态规划的
3、一般方法求最优二分检索掌握动态规划的一般方法求最优二分检索树；树； n掌握掌握0/1背包问题的求解方法；背包问题的求解方法； n掌握货郎担问题的求解方法。掌握货郎担问题的求解方法。 n重点：最优二分检索树和重点：最优二分检索树和0/1背包问题的求背包问题的求解方法；解方法； n难点：用动态规划法求解货郎担问题并分难点：用动态规划法求解货郎担问题并分析其时间复杂度。析其时间复杂度。 训蜀险锻桓妆鹰亢手佃躁瞎墒姬根惺汛砌惯怨铲喝磷梦恰芯沁掸燎嘎憨毫第5章动态规划第5章动态规划2. 多阶段决策过程的求解策略多阶段决策过程的求解策略1）枚举法）枚举法 穷举穷举可能的决策序列，从中选取可以获得最优解的决
4、策序列可能的决策序列，从中选取可以获得最优解的决策序列2）动态规划）动态规划 20世纪世纪50年代初美国数学家年代初美国数学家R.E.Bellman等人在研究多阶段决策等人在研究多阶段决策过程的优化问题时，提出了著名的过程的优化问题时，提出了著名的最优化原理最优化原理(principle of optimality)，把，把多阶段多阶段过程转化为一系列过程转化为一系列单阶段单阶段问题，创立了解决这问题，创立了解决这类过程优化问题的新方法类过程优化问题的新方法动态规划动态规划。 动态规划动态规划(dynamic programming)是是运筹学运筹学的一个分支，是求解的一个分支，是求解决策过程
5、决策过程(decision process)最优化的数学方法。最优化的数学方法。 应用领域：动态规划问世以来，在经济管理、生产调度、工程技应用领域：动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。方法求解更为方便。呸怖社诵搪公烯萄葵征勋宜把泥酶禾婿欲效酶伍兢募朵寥革叼丈馅浆埂疤第5章动态规划第5章动态规划3. 最优性原理最优性原理(Princ
6、iple of Optimality) 过程的过程的最优决策序列最优决策序列具有如下性质：无论过程的具有如下性质：无论过程的初始状初始状态态和和初始决策初始决策是什么，其余的决策都必须相对于初始决策所是什么，其余的决策都必须相对于初始决策所产生的状态构成一个最优决策序列。产生的状态构成一个最优决策序列。 利用动态规划求解问题的前提利用动态规划求解问题的前提 1) 证明问题满足最优性原理证明问题满足最优性原理 如果对所求解问题证明满足最优性原理，则说明用动态如果对所求解问题证明满足最优性原理，则说明用动态规划方法有可能解决该问题规划方法有可能解决该问题 2) 获得问题状态的递推关系式获得问题状态
7、的递推关系式 获得各阶段间的递推关系式是解决问题的关键。获得各阶段间的递推关系式是解决问题的关键。酬剪哥叹锣鼎宛珍倦恭鄙见痔反吐扮熙斟坠拟挑咎梭锁售嗡销吝铝早菩谦第5章动态规划第5章动态规划例例4.1 多段图问题多段图问题多段图多段图G=(V,E)是一个有向图，且具有特性是一个有向图，且具有特性: 结点结点：结点集：结点集V被分成被分成k22个不相交的集合个不相交的集合V Vi i，1ik1ik， 其中其中V V1 1和和V Vk k分别只有一个结点分别只有一个结点s(s(源点源点) )和和t(t(汇点汇点) )。 每一集合每一集合V Vi i定义图中的定义图中的一段一段。 边边： 所有的边所
8、有的边(u,v)(u,v)均具有如下性质：均具有如下性质： 若若EE，则，则 该边将是从某段该边将是从某段i i指向指向i+1i+1段，即若段，即若uVuVi i，则，则vVvVi i1 1, , 1ik 1ik1 1。 每条边每条边(u,v)(u,v)均附有成本均附有成本c(u,v)c(u,v)。 s s到到t t的路径的路径：从第：从第1 1段开始，至第段开始，至第2 2段、第段、第3 3段、段、最后、最后 在第在第k k段终止。路径的段终止。路径的成本成本是这条路径上边的成本是这条路径上边的成本 和。和。 多段图问题多段图问题：求由：求由s s到到t t的的最小成本路径最小成本路径。嗜拣
9、哟通挥警豺花细奴钦朱禄很捐荡挤瞎骑碧俞陡呛琴诧纸痔墨滦聚摘萄第5章动态规划第5章动态规划12345678910111297324227111181456356425V1V2V3V4V55段图喇杨并涅抚滚夸赋肃埔项桂歪笑虑碾洲阉凌纽激初官体急展懦套誉磁杆蚂第5章动态规划第5章动态规划 多段图问题的多段图问题的多阶段决策过程多阶段决策过程：生成从：生成从s到到t的最小成本路径的最小成本路径是在是在k-2个阶段（除个阶段（除s和和t外）进行某种决策的过程：从外）进行某种决策的过程：从s开始，开始，第第i次次决策决定决策决定Vi+1(1ik-2)中的哪个结点在从中的哪个结点在从s到到t的最短路径上。的
10、最短路径上。最优性原理对多段图问题成立最优性原理对多段图问题成立 假设假设s,v2,v3,vk-1,t是一条由是一条由s到到t的最短路径。的最短路径。 初始状态初始状态：s 初始决策初始决策：(s,v2)， v2VV2 2 初始决策产生的状态初始决策产生的状态：v2 则，其余的决策：则，其余的决策：v3,.,vk-1相对于相对于v2将构成一个最优决策序将构成一个最优决策序列列最优性原理成立。最优性原理成立。 反证反证：若不然，设：若不然，设v2,q3,qk-1,t是一条由是一条由v2到到t的更短的路径，的更短的路径，则则s, v2,q3,qk-1,t将是比将是比s,v2,v3,vk-1,t更短
11、的从更短的从s到到t的路径。的路径。与假设矛盾。与假设矛盾。 故，最优性原理成立故，最优性原理成立攀斟溢硒敌疯土痊吱渭霉洪蘸剖十殷苹诫数艺馈矗做言奎垃瞬技钒腺肪骸第5章动态规划第5章动态规划n例例4.20/1背包问题背包问题 KNAP(l,j,X) 目标函数目标函数： 约束条件约束条件： 0/1背包问题：背包问题：KNAP(1,n,M) 士匪绊慢赋游档宵痢册体纺枝认犯京瞳窟闻耪纳有火迭款恫棺击额铭更宵第5章动态规划第5章动态规划最优性原理对最优性原理对0/1背包问题成立：背包问题成立： 设设y1,y2,yn是是x1,x2,xn的的0/1值最优序列。值最优序列。 若若y10, KNAP(2,n,
12、M)是初始决策产生的状态。则是初始决策产生的状态。则y2,yn相对于相对于KNAP(2,n,M)将构成一个最优序列。否则，将构成一个最优序列。否则，y1,y2,yn将将不是不是KNAP(1,n,M)的最优解的最优解 若若y11, KNAP(2,n,Mw1)是初始决策产生的状态。则是初始决策产生的状态。则y2,yn相对于相对于KNAP(2,n,Mw1)将构成一个最优序列。将构成一个最优序列。 否则，设存在另一否则，设存在另一0/1序列序列z1,z2,zn,使得使得 且且 则序列则序列y1,z2,zn将是一个对于将是一个对于KNAP(1,n,M)具有更大效益具有更大效益值的序列。值的序列。 故，最
13、优性原理成立故，最优性原理成立须亭勋弗滦都燕超攒疵巢询刑涅淤驹渗搜倡祷拳替俐惩湍敝疑榆肇改枪厄第5章动态规划第5章动态规划4. 动态规划模型的基本要素动态规划模型的基本要素一个多阶段决策过程最优化问题的动态规划模型通常包含以一个多阶段决策过程最优化问题的动态规划模型通常包含以下要素：下要素：1) 阶段阶段 阶段阶段(step)是对整个过程的自然划分。通常根据时间顺是对整个过程的自然划分。通常根据时间顺序或空间特征来划分阶段，以便按阶段的次序解优化问题。序或空间特征来划分阶段，以便按阶段的次序解优化问题。阶段变量一般用阶段变量一般用k=1,2,.,n表示。表示。穷蕴秦椿廷广滔盯锗彩纶肘益擅扬鹏蛆
14、耽哎盐蜘位方扳孜团哦旋业丘真瘤第5章动态规划第5章动态规划2） 状态状态 状态状态(state)表示每个阶段开始时过程所处的自然状况。它应表示每个阶段开始时过程所处的自然状况。它应该能够描述过程的特征并且具有该能够描述过程的特征并且具有无后向性无后向性，即当某阶段的状态给，即当某阶段的状态给定时，这个阶段以后过程的演变与该阶段以前各阶段的状态无关，定时，这个阶段以后过程的演变与该阶段以前各阶段的状态无关，即每个状态都是过去历史的一个完整总结。通常还要求状态是直即每个状态都是过去历史的一个完整总结。通常还要求状态是直接或间接可以观测的。接或间接可以观测的。 描述状态的变量称描述状态的变量称状态变
15、量状态变量(state variable)。变量允许取值。变量允许取值的范围称允许的范围称允许状态集合状态集合(set of admissible states)。用。用xk表示第表示第k阶段的状态变量，它可以是一个数或一个向量。用阶段的状态变量，它可以是一个数或一个向量。用Xk表示第表示第k阶段阶段的允许状态集合。的允许状态集合。 状态变量简称为状态状态变量简称为状态旅撮疆尊炎妹裔脑旺坷窗久蛋鹅笼诺蜀蓄阜攫娘批蜕当胎逮京薪版杀撞榴第5章动态规划第5章动态规划3）决策）决策 当一个阶段的状态确定后，可以作出各种选择从而演变到下当一个阶段的状态确定后，可以作出各种选择从而演变到下一阶段的某个状态
16、，这种选择手段称为一阶段的某个状态，这种选择手段称为决策决策(decision) 。 描述决策的变量称决策变量描述决策的变量称决策变量(decision variable)。变量允许。变量允许取值的范围称允许决策集合取值的范围称允许决策集合(set of admissible decisions)。用。用uk(xk)表示第表示第k阶段处于状态阶段处于状态xk时的决策变量，它是时的决策变量，它是xk的函数，用的函数，用Uk(xk)表示了表示了xk的允许决策集合。的允许决策集合。 决策变量简称决策。决策变量简称决策。惫烃亦疚扔泄惹茹秉称以抑惭刑缺揖库晕铜迹塑款河速带怠触滋拉樟音由第5章动态规划第5
17、章动态规划4）策略）策略 决策组成的序列称为策略决策组成的序列称为策略(policy)。由初始状态。由初始状态x1开始开始的全过程的策略记作的全过程的策略记作p1,n(x1)，即，即p1,n(x1)=u1(x1),u2(x2),.，un(xn)。 由第由第k阶段的状态阶段的状态xk开始到终止状态的后部子过程的策略开始到终止状态的后部子过程的策略记作记作pk,n(xk)，即，即pk,n(xk)=uk(xk),uk+1(xk+1),.，un(xn)。类似地，类似地， 由第由第k到第到第j阶段的子过程的策略记作阶段的子过程的策略记作 pk,j(xk)=uk(xk),uk+1(xk+1),.，uj(x
18、j)。 对于每一个阶段对于每一个阶段k的某一给定的状态的某一给定的状态xk，可供选择的策略，可供选择的策略pk,j(xk)有一定的范围，称为允许策略集合有一定的范围，称为允许策略集合(set of admissible policies)，用，用P1,n(x1),Pk,n(xk),Pk,j(xk)表示。表示。市吟卯尊师谭钉佳训洁瘪噶倘藏符鹅望惰书袋指渐芥济腥妮拼宽谎抚才算第5章动态规划第5章动态规划5) 状态转移方程状态转移方程 在确定性过程中，一旦某阶段的状态和决策为已知，在确定性过程中，一旦某阶段的状态和决策为已知，下阶段的状态便完全确定。用状态转移方程下阶段的状态便完全确定。用状态转移方
19、程(equation of state)表示这种演变规律，写作表示这种演变规律，写作吁贸釉薛绰剃陌包炽伍烈褂屏庐皮灾栖妒涵没铺懦泌滑亩置洒郝生捎炽莽第5章动态规划第5章动态规划6) 指标函数和最优值函数指标函数和最优值函数 指标函数指标函数(objective function)是衡量过程优劣的数是衡量过程优劣的数量指标，它是关于策略的数量函数，从阶段量指标，它是关于策略的数量函数，从阶段k到阶段到阶段n的的指标函数用指标函数用Vk,n(xk,pk,n(xk)表示，表示，k=1,2,.,n。 能够用动态规划解决的问题的指标函数应具有可分能够用动态规划解决的问题的指标函数应具有可分离性，即离性，
20、即Vk,n可表为可表为xk,uk,Vk+1, n 的函数，记为：的函数，记为：怜刽爸厅赶庚抓阐擦衫苍周眷霞您夫滞涂科代摹惮袒举舆面舶遵纲拇稳鹿第5章动态规划第5章动态规划7.最优策略和最优轨线最优策略和最优轨线 使指标函数使指标函数Vk,n达到最优值的策略是从达到最优值的策略是从k开始的后部子过开始的后部子过程的最优策略，记作程的最优策略，记作pk,n*=uk*,.un*,p1,n*又是全过程的最又是全过程的最优策略，简称最优策略优策略，简称最优策略(optimal policy)。从初始状态。从初始状态x1(=x1*)出发，过程按照出发，过程按照p1,n*和状态转移方程演变所经历的和状态转移
21、方程演变所经历的状态序列状态序列x1*,x2*,.,xn+1*称最优轨线称最优轨线(optimal trajectory)。焕把煎沁贯学款冤脸匡锰徐灭撮遇法鹏雅厚话稠哪进哪巳巫避巷诺碧褥暇第5章动态规划第5章动态规划5. 递推策略递推策略1）向前处理法）向前处理法 列出根据列出根据xi+1,xn的最优决策序列求取的最优决策序列求取xi决策决策值的关系式。值的关系式。 从最后一个阶段，逐步从最后一个阶段，逐步向前向前递推求出各阶段的递推求出各阶段的决策值。决策序列决策值。决策序列x1,x2,xn就是问题的最优解。就是问题的最优解。 xn-1,1xn-1,pn-1xn钝肾子膘捻旺陋皖郡费脐说饱葡隅
22、寺竹顷奖帽蕉播所讹遗霸曹寄稚淫紫澡第5章动态规划第5章动态规划 例例4.3 利用向前处理法求解利用向前处理法求解0/1背包问题背包问题 设设gi(x)是是KNAP(i+1,n,X)的最优解。的最优解。 g0(M)：KNAP(1,n,M)的最优解。由于的最优解。由于x1的取值等于的取值等于1或或0,可得：可得： g0(M)=maxg1(M),g1(M-w1)+p1 对于某个对于某个xi，xi等于等于1或或0，则有：，则有： gi(X)=maxgi+1(X),gi+1(X-wi+1)+pi+1 初始值：初始值： 0 X0 0 gn(X) = - X0蹬鬃您贸疲犊疼农渔尚彤焕拼痒荚奉冀约终荐造驻曼士
23、雨惫忧褒耻步凑誉第5章动态规划第5章动态规划 例例4.4 利用向前处理法求解利用向前处理法求解k段图问题段图问题 设设 V2，1j2p2,|V2|=p2; 是由是由 到到t的最短路径，的最短路径，则s到到t的最短路径是的最短路径是 s | V2,1j2p2中最短的那条路径。中最短的那条路径。 若若s,v2,v3,vi,vk-1,t是是s到到t的一条最短路径，的一条最短路径，vi是其中是其中的一个中的一个中间点，点，则s,v2,v3,vi和和 vi,vk-1,t分分别是由是由s到到vi和和vi到到t的最短路径（最的最短路径（最优性原理）性原理） 从从Vi中的中的结点点ji到到t的最短路径将是：的
24、最短路径将是： min( | Vi+1,1ji+1pi+1)蚜捌谈蠢梨蛆蹈易判耙镊睁圾防芒下浴脯止容抒询效佯挝钨琶明扩撮搽亚第5章动态规划第5章动态规划2） 向后处理法向后处理法 列出根据列出根据x1,xi-1的最优决策序列求取的最优决策序列求取xi决决策值的关系式。策值的关系式。 从第一个阶段，逐步从第一个阶段，逐步向后向后递推求出各阶段的递推求出各阶段的决策值。决策序列决策值。决策序列x1,x2,xn就是问题的最优解。就是问题的最优解。 斩爱辩然幽译酬扯沉脾翰姓幕腆恶球疑肛层孝油摊你眼绑虽诡惰捞设变矗第5章动态规划第5章动态规划 例例4.5 0/1背包问题（向后处理策略）背包问题（向后处理
25、策略） 设设fi(x)是是KNAP(1,i,X)的最优解。的最优解。 则，则，fn(M) = KNAP(1,n,M) 向后递推关系式：向后递推关系式： fi(X)=maxfi-1(X),fi-1(X-wi)+pi 初始值：初始值： 0 X0 0 f0(X) = - X0晓赞切赌旁店逻察漏踊夫丧核纷菠庄踞狙媳毙探丰四绘里贱佯吟津楷钾夹第5章动态规划第5章动态规划 例例4.6 k段图问题（向后处理策略）段图问题（向后处理策略） 设设 Vk-1，1jk-1pk-1，|Vk-1|=pk-1; 是由是由s到到 的最短路径，的最短路径，则s到到t的最短路径是的最短路径是 t | Vk-1,1jk-1pk-
26、1中最短的那条路中最短的那条路径。径。 若若s,v2,v3,vi,vk-1,t是是s到到t的一条最短路径，的一条最短路径，vi是其中是其中的一个中的一个中间点，点，则s,v2,v3,vi和和 vi,vk-1,t分分别是由是由s到到vi和和vi到到t的最短路径（最的最短路径（最优性原理）性原理） 从从s到到Vi中的中的结点点ji的最短路径将是：的最短路径将是： min( | Vi+1,1ji+1pi+1)泣陵加盎蹦企他爵妒斗停叫阉恩削帆总翠中馏校运积概南煮困嫌慎振咯毛第5章动态规划第5章动态规划动态规划的基本思想：动态规划的基本思想：（1）动态规划方法的关键在于正确写出基本的递推关系式）动态规划
27、方法的关键在于正确写出基本的递推关系式和恰当的边界条件。要做到这一点，必须将问题的过程分和恰当的边界条件。要做到这一点，必须将问题的过程分成几个相互联系的阶段，恰当选择状态变量，决策变量和成几个相互联系的阶段，恰当选择状态变量，决策变量和定义最优值函数，从而把一个大问题化成一族同类型的子定义最优值函数，从而把一个大问题化成一族同类型的子问题，然后逐个求解。即从边界条件开始，逐段递推寻优，问题，然后逐个求解。即从边界条件开始，逐段递推寻优，在每一个子问题的求解中，均利用了它前面的子问题的最在每一个子问题的求解中，均利用了它前面的子问题的最优化结果，依次进行，最后一个子问题的最优解，就是整优化结果
28、，依次进行，最后一个子问题的最优解，就是整个问题的最优解。个问题的最优解。（2）在多阶段决策过程中，动态规划方法是既把当前一段）在多阶段决策过程中，动态规划方法是既把当前一段和未来各段分开，又把当前的效益和未来效益综合起来考和未来各段分开，又把当前的效益和未来效益综合起来考虑的一种最优化方法。因此，每段决策的选取是从全局来虑的一种最优化方法。因此，每段决策的选取是从全局来考虑的，与该段的最优选择答案一般是不同的。考虑的，与该段的最优选择答案一般是不同的。（3）在求整个问题的最优策略时，由于初始状态是已知的，）在求整个问题的最优策略时，由于初始状态是已知的，而每段的决策都是该段状态的函数，故最优
29、策略所经的各而每段的决策都是该段状态的函数，故最优策略所经的各段状态便可逐次变换得到，从而确定最优路线。段状态便可逐次变换得到，从而确定最优路线。额飘宇宜征冲轧半谎难咒酌挚羚静伪卉操涩酵羊穗丛帐箕匡淫绞寻吨揩虫第5章动态规划第5章动态规划关于动态规划求解策略的进一步说明关于动态规划求解策略的进一步说明采用枚举法：若问题的决策序列由采用枚举法：若问题的决策序列由n次决策构成，而每次次决策构成，而每次决策有决策有p种选择，则可能的决策序列将有种选择，则可能的决策序列将有pn个。个。利用动态规划策略的求解过程中保存了所有子问题的最优利用动态规划策略的求解过程中保存了所有子问题的最优解，而舍去了所有不
30、能导致问题最优解的次优决策序列解，而舍去了所有不能导致问题最优解的次优决策序列动态规划：可能有多项式的计算复杂度。动态规划：可能有多项式的计算复杂度。匪樱演辙凹棱大柜龟兰志索又菠谱腻澎侯吵篷凭噎狮灵霜少蚀遏嘻岛砌成第5章动态规划第5章动态规划与非线性规划相比，动态规划的优点：与非线性规划相比，动态规划的优点：（1）易于确定全局最优解。动态规划方法是一种逐步改善法，）易于确定全局最优解。动态规划方法是一种逐步改善法，它把原问题化为一系列结构相似的最优化子问题，而每个子它把原问题化为一系列结构相似的最优化子问题，而每个子问题的变量个数比原问题少得多，约束集合也要简单得多。问题的变量个数比原问题少得
31、多，约束集合也要简单得多。（2）能得到一族解，有利于分析结果）能得到一族解，有利于分析结果（3）能利用经验，提高求解的效率。动态规划方法反映了过）能利用经验，提高求解的效率。动态规划方法反映了过程逐段演变的前后联系，较之非线性规划与实际过程联系得程逐段演变的前后联系，较之非线性规划与实际过程联系得更紧密。更紧密。不足之处不足之处：（1）没有一个统一的标准模型可供应用。）没有一个统一的标准模型可供应用。（2）应用的局限性。要求状态变量满足）应用的局限性。要求状态变量满足“无后效性无后效性”条件，条件，不少实际问题在取其自然特征作为状态变量往往不能满足这不少实际问题在取其自然特征作为状态变量往往不
32、能满足这条件。条件。（3）在数值求解中，存在）在数值求解中，存在“维数障碍维数障碍”。在计算机中，每递。在计算机中，每递推一段，必须把前一段的最优值函数在相应的状态集合上的推一段，必须把前一段的最优值函数在相应的状态集合上的全部值存入内存中。当维数增大时，所需的内存量成指数倍全部值存入内存中。当维数增大时，所需的内存量成指数倍增长。增长。踢完釜愤俏寞咖琐汝陛抿干籽戊富结歉夫卑椰歧斩莱悍会假檀吼两线侥戮第5章动态规划第5章动态规划4.2 多段图问题多段图问题1. 问题的描述问题的描述 在多段图中求从在多段图中求从s到到t的一条最小成本的路径，可以看的一条最小成本的路径，可以看 作是在作是在k-2
33、个段作出某种决策的结果。个段作出某种决策的结果。 第第i次决策决定次决策决定Vi+1中的哪个结点在这条路径上，这里中的哪个结点在这条路径上，这里 1ik-2ik-2； 最优性原理对多段图问题成立最优性原理对多段图问题成立厢毒惹危怪娃琳喉到教嘱部擅伯补晦干禁袁痘劫精滦链丝岛欺皿绅矢沮铸第5章动态规划第5章动态规划2. 向前处理策略求解向前处理策略求解 设设 P(i,j)是一条从是一条从Vi中的结点中的结点j到汇点到汇点t的最小成本路径，的最小成本路径， COST(i,j)是这条路径的成本。是这条路径的成本。 1) 向前递推式向前递推式 2) 递推过程递推过程 第第k-1k-1段段 c(j,t)
34、EE COST(k-1,j) = 哗立妇樱鼎德弃旬震骆耽迟滞涧迈斟赡雅采澳联葱矛结把夹斗压帮叉纂歉第5章动态规划第5章动态规划l1l2.lpi+1tjViVi+1俩怕抵命菲磅疯弘姿幢抡湖翻胖葵憎毙棵疼沪憎苇老檄戍认恢膨延盯兵堑第5章动态规划第5章动态规划12345678910111297324227111181456356425V1V2V3V4V55段图锚裔眶陈甫涸鞋漆狡运救赏盅虐鹿褒接煽色伍夜欢件层治瘦爆舀履舔诀御第5章动态规划第5章动态规划各递推结果各递推结果第第4段段 COST(4,9) = c(9,12) = 4 COST(4,10) = c(10,12) = 2 COST(4,11)
35、 = c(11,12) = 5第第3段段 COST(3,6) = min6+COST(4,9),5+COST(4,10) = 7 COST(3,7) = min4+COST(4,9),3+COST(4,10) = 5 COST(3,8) = min5+COST(4,10),6+COST(4,11) = 7第第2段段 COST(2,2) = min4+COST(3,6) , 2+COST(3,7), 1+COST(3,8) = 7 COST(2,3) = 9 COST(2,4) = 18 COST(2,5) = 15第第1段段 COST(1,1) = min9+COST(2,2),7+COST(
36、2,3), 3+COST(2,4),2+COST(2,5) = 16S到到t的最小成本路径的成本的最小成本路径的成本 16雌捅刺诚学迹宰达递缠巧破耪糠竟控膨开慨朴令施疹旧偷抢屋殊牙收诧醋第5章动态规划第5章动态规划 最小路径的求取最小路径的求取 记记 D(i,j) D(i,j)每一每一COST(i,j)COST(i,j)的决策的决策 即，使即，使c(j,l)+COST(i+1,l)c(j,l)+COST(i+1,l)取得取得最小值最小值的的l l值。值。 例：例：D(3,6) = 10, D(3,7)= 10 D(3,8) = 10D(3,6) = 10, D(3,7)= 10 D(3,8)
37、= 10 D(2,2) = 7, D(2,3) = 6,D(2,4) = 8,D(2,5) = 8 D(2,2) = 7, D(2,3) = 6,D(2,4) = 8,D(2,5) = 8 D(1,1) = 2 D(1,1) = 2 根据根据D(1,1)D(1,1)的决策值的决策值向后向后递推求取最小成本路径：递推求取最小成本路径： v v2 2=D(1,1)=2=D(1,1)=2 v v3 3 = D(2,D(1,1) = 7 = D(2,D(1,1) = 7 v v4 4 = D(3,D(2,D(1,1) = D(3,7) = 10 = D(3,D(2,D(1,1) = D(3,7) =
38、10 故由故由s s到到t t的的最小成本路径最小成本路径是：是：12710121271012 虽膜贰窿骋描瓮裸符寞师洋丰骇谩沦帅来伎瑰县悍饿月寅精近在盂严兔抹第5章动态规划第5章动态规划3) 算法描述算法描述 结点的编号规则结点的编号规则 源点源点s s编号为编号为1 1, ,然后依次对然后依次对V V2 2、V V3 3V Vk-1k-1中的结点编号，中的结点编号，汇点汇点t t编号为编号为n n。 目的：使对目的：使对COSTCOST和和D D的计算仅按的计算仅按n-1,n-2,n-1,n-2,1,1的次序计的次序计算即可，算即可，无需考虑无需考虑标示结点所在标示结点所在段段的第一个下标
39、。的第一个下标。 算法描述算法描述搀测补框剃鲸胸袒熙赣陕哄峨解面着潮坊业假葡吭秋薪又惋尔零瓤殴蔗魁第5章动态规划第5章动态规划算法算法4.1 多段图的向前处理算法多段图的向前处理算法 procedure FGRAPH(E,k,n,P) /输入是按段的顺序给结点输入是按段的顺序给结点编号编号的，有的，有n个结点的个结点的k段图。段图。E是边是边 集，集，c(i,j)是边是边的成本。的成本。P(1:k)带出最小成本路径带出最小成本路径/ real COST(n); integer D(n-1),P(k),r,j,k,n COST(n)0 for jn-1 to 1 by -1 do /计算算COS
40、T(j)/ 设r是具有性是具有性质：E且使且使c(j,r)+COST(r)取最小取最小值的的结点点 COST(j)c(j,r) + COST(r) D(j) r /记录决策决策值/ repeat P(1)1; P(k)n for j2 to k-1 do /找路径上的第找路径上的第j个个结点点/ P(j) D(P(j-1) /回溯求出回溯求出该路径路径/ repeat end FGRAPH宣踪朗勒荣桩皱悼祝绪爱宫臀室胜鼠辞蛙冶铀当怪缀腕返乎油洲舔喻熙诱第5章动态规划第5章动态规划算法的时间复杂度算法的时间复杂度 若若G采用邻接表表示，总计算时间为：采用邻接表表示，总计算时间为：元痹淄马德物葬邓
41、碗剿伍败俩札积烁秽婶共遭翁我谁停褪俘粕席城呆俏暖第5章动态规划第5章动态规划3. 向后处理策略求解向后处理策略求解 设设 BP(i,j)是一条从源点是一条从源点s到到Vi中的结点中的结点j的最小成本路径，的最小成本路径， BCOST(i,j)是这条路径的成本。是这条路径的成本。 1) 向后递推式向后递推式 2) 递推过程递推过程 第第2 2段段 c(1,j) EE BCOST(2,j) = 艘欧狈冈榆私姿战紧猴镶蓑游项尝春折驯切滋管橱拖囤渺赔贯君燕菊聊麦第5章动态规划第5章动态规划12345678910111297324227111181456356425V1V2V3V4V55段图惫负酶倍森签
42、灯饵马耕桥值苏液眶砾玖乏想镐率尊砰乍哥涝跳睫箭区胯宴第5章动态规划第5章动态规划各递推结果各递推结果第第2段段 BCOST(2,2) = 9 BCOST(2,3) = 7 BCOST(2,4) = 3 BCOST(2,5) = 2第第3段段 BCOST(3,6) = minBCOST(2,2)+4,BCOST(2,3)+2 = 9 BCOST(3,7) = minBCOST(2,2)+2,BCOST(2,3)+7, BCOST(2,5)+11 = 11 BCOST(3,8) = minBCOST(2,4)+11, BCOST(2,5)+8 = 10第第4段段 BCOST(4,9) = minB
43、COST(3,6)+6,BCOST(3,7)+4 = 15 BCOST(4,10) = minBCOST(3,6)+5,BCOST(3,7)+3, BCOST(3,8)+5 = 14 BCOST(4,11) = minBCOST(3,8)+6 = 16第第5段段 BCOST(5,12) = minBCOST(4,9)+4,BCOST(4,10)+2, BCOST(4,11)+5 = 16S到到t的最小成本路径的成本的最小成本路径的成本 16纳灸设甜予前辱的讲胶氯备候仅凳柴兜澜店奏斥咸巢卡琵父贝开揩宠另颂第5章动态规划第5章动态规划 最小路径的求取最小路径的求取 记记 BD(i,j) BD(i,
44、j)每一每一COST(i,j)COST(i,j)的决策的决策 即，使即，使COST(i-1,l)+c(l,j)COST(i-1,l)+c(l,j)取得取得最小值最小值的的l l值。值。 例：例：BD(3,6) = 3, BD(3,7)= 2 ,BD(3,8) = 5BD(3,6) = 3, BD(3,7)= 2 ,BD(3,8) = 5 BD(4,9) = 6, BD(4,10) = 7, BD(4,11) = 8 BD(4,9) = 6, BD(4,10) = 7, BD(4,11) = 8 BD(5,12) = 10 BD(5,12) = 10 根据根据D(5,12)D(5,12)的决策值
45、的决策值向前向前递推求取最小成本路径：递推求取最小成本路径： v v4 4 = BD(5,12)=10= BD(5,12)=10 v v3 3 = BD(4,BD(5,12) = 7 = BD(4,BD(5,12) = 7 v v2 2 = BD(3,BD(4,BD(5,12) = BD(3,7) = 2 = BD(3,BD(4,BD(5,12) = BD(3,7) = 2 故由故由s s到到t t的的最小成本路径最小成本路径是：是：12710121271012 替澳撅乖杠烽勺订酶景胳漾薪裕说缓袄瘟二蹄袜逼臂渺帧翰劣滚鸳痞缘隐第5章动态规划第5章动态规划12345678910111265434
46、227111181456356425V1V2V3V4V55段图钓良掌动顶霜辈荷魁履嚣祭慧挝株充嚣傻耻孽逊暑焊擂枣肚抒沾泉敖蛇放第5章动态规划第5章动态规划算法算法4.2 多段图的向后处理算法多段图的向后处理算法 procedure BGRAPH(E,k,n,P) /输入是按段的顺序给结点输入是按段的顺序给结点编号编号的，有的，有n个结点的个结点的k段图。段图。E是边是边 集，集，c(i,j)是边是边的成本。的成本。P(1:k)带出最小成本路径带出最小成本路径/ real BCOST(n); integer BD(n-1),P(k),r,j,k,n BCOST(1)0 for j2 to n d
47、o /计算算BCOST(j)/ 设r是具有是具有E且使且使BCOST(r)+ c(r,j)取最小取最小值性性质的的结点点 BCOST(j) BCOST(r)+ c(r,j) BD(j) r /记录决策决策值/ repeat P(1)1; P(k)n for jk-1 to 2 by -1 do /找路径上的第找路径上的第j个个结点点/ P(j) D(P(j+1) /回溯求出回溯求出该路径路径/ repeat end BGRAPH决渭秧韵霓酪紊猿蝎侧诈刑筹联吝弦笑爆也之酬孰翠段德轨挡埠辰庚款豺第5章动态规划第5章动态规划4. 多段图问题的应用实例多段图问题的应用实例 将将n个资源分配给个资源分配
48、给r个项目的问题：如果把个项目的问题：如果把j个资源，个资源，0jnjn，分配给项目，分配给项目i i，可以获得，可以获得N(i,j)N(i,j)的净利。的净利。 问题：如何将这问题：如何将这n个资源分配给个资源分配给r个项目才能获得最大可个项目才能获得最大可能的净利。转换成一个多段图问题。能的净利。转换成一个多段图问题。阴题快捷跌前沥久所吱俐枯伴痹铸喂天盏疤忱百蚀囚靴逐际尹馏魔僳戊石第5章动态规划第5章动态规划 用用r1段图段图描述该问题：描述该问题： 段段： 1到到r之间的段之间的段i表示项目表示项目i。 结点结点： i=1时，只有一个结点时，只有一个结点源点源点s =V(1,0)V(1,
49、0) 当当2irir时，每段有时，每段有n+1n+1个结点，每个结点具有形式个结点，每个结点具有形式 V(i,j)V(i,j)：表示到项目表示到项目i i之前为止，共把之前为止，共把j j个资源分配给了个资源分配给了 项目项目1,2,1,2,i-1,i-1 汇点汇点t t=V(r+1,n)=V(r+1,n) 边的一般形式边的一般形式：,jl,1irjl,1ir 成本：成本： 当当jljl且且1ir1ir时，边时，边赋予成本赋予成本 N(i,l-j), N(i,l-j),表示给项目表示给项目i i分配分配l-jl-j个资源所可能获得的净利。个资源所可能获得的净利。 当当jnjn且且i=ri=r时
50、，此时的边为：时，此时的边为：,该边赋该边赋 予成本：予成本：房鳞喘镜役差桨搏轧乾丝犁茎所翁谴招惫恋枕茅欠在帕柏涕冈民蔗害燎履第5章动态规划第5章动态规划实例：将实例：将4个资源分配给个资源分配给3个项目。构成一个个项目。构成一个4段图。段图。 问题的解：资源的最优分配方案是由问题的解：资源的最优分配方案是由s到到t的一条的一条最大成本最大成本的路径给出的路径给出改变边成本的改变边成本的符号符号，从而将问题转换成为求取最小成本路径问题。，从而将问题转换成为求取最小成本路径问题。瘪灶惦抒标韶桶溢牧员戊澳氨借拄卡纱筏啼付轧倘怎磋研农没确蜒悬迈伟第5章动态规划第5章动态规划4.3 每对结点之间的最短
51、路径每对结点之间的最短路径1. 问题描述问题描述 设设G=(V,E)是一个有是一个有n个结点的有向图，个结点的有向图，C是是G的成本邻接矩阵，的成本邻接矩阵，C中元素有：中元素有： 0 ，i j c(i,j)= 边边的成本，的成本，ij且且E(G) ，ij且且 其中，其中，1i，jn 每对结点之间的最短路径问题每对结点之间的最短路径问题：求满足下述条件的矩阵：求满足下述条件的矩阵A，A中的任一元素中的任一元素A(i,j)代表结点代表结点i到结点到结点j的的最短路径长度最短路径长度。涝忠猪彪碘洪池颅敝允交锹躯烦苑息拐懊肇校妈蛛别豆侧泽准蝎仲铡瑞吁第5章动态规划第5章动态规划分析：分析：n 利用利
52、用单源最短路径单源最短路径算法求解算法求解 计算计算n个结点的单源最短路径。个结点的单源最短路径。 时间复杂度：时间复杂度：(n(n3 3) )n利用利用动态规划动态规划策略求解策略求解 将求解将求解G G中每对结点之间的最短路径问题转化成一个中每对结点之间的最短路径问题转化成一个多多阶段决策过程阶段决策过程。 决策什么？决策什么？ 最优性原理对于该问题是否成立？最优性原理对于该问题是否成立？苑叛篇匪昔肿届芥续捣减兵王懒熟累应与架塌猛穿礁袭撼丰誊脾焚相损宣第5章动态规划第5章动态规划2. 动态规划求解策略动态规划求解策略1）最优性原理对于每对结点之间的最短路径问题成立最优性原理对于每对结点之间
53、的最短路径问题成立 对对G的一条由的一条由i到到j的最短路径（假设该路径中不包含环），的最短路径（假设该路径中不包含环），设设k是该路径上的一个中间结点：是该路径上的一个中间结点： i,.,k,j 由由i到到k的最短路径的最短路径 k是中间结点是中间结点 由由k到到i的最短路径的最短路径 则，由则，由i到到k和和k到到j的两条的两条子路径子路径将分别是由将分别是由i到到k和由和由k到到j的最短路径。否则的最短路径。否则i,.,k,j也将不是由也将不是由i到到j的最短路径。的最短路径。 故，最优性原理对于该问题成立。故，最优性原理对于该问题成立。寐撕沼涟钩勿销窍垂菜蠕愿民倾尧狠十三蒲告危裂渝垢凹
54、迫瘟捐了惜斟级第5章动态规划第5章动态规划2）多阶段决策过程多阶段决策过程 设设k是由是由i到到j的最短路径上编号（假设所有的最短路径上编号（假设所有n个结点依次有从个结点依次有从1到到n的编号）最高的中间结点：的编号）最高的中间结点： i,.,k,j k是编号最高的中间结点是编号最高的中间结点 则由则由i到到k的子路径上将不会有比编号的子路径上将不会有比编号k-1更大的结点；同理，更大的结点；同理，由由k到到i的子路径上也将不会有比编号的子路径上也将不会有比编号k-1更大的结点。更大的结点。 构造构造多阶段决策过程多阶段决策过程：对由：对由i到到j的最短路径，首先决策哪一个的最短路径，首先决
55、策哪一个结点是该路径上具有结点是该路径上具有最大编号最大编号的中间结点的中间结点k，然后再去求取由，然后再去求取由i到到k和由和由k到到j的最短路径的最短路径其中应不包含比其中应不包含比k-1还大的中间结点。还大的中间结点。摘份节召笨俗黄捐陕苏嘛铱橡弄童肖檀顷咆云菌克赎氓尝霖辩为柜蚁筹阴第5章动态规划第5章动态规划3）递推关系式）递推关系式 记记Ak(i,j)表示从表示从i到到j并且不经过比并且不经过比k还大的结点的还大的结点的最短最短路径长度路径长度。则，。则， A(i,j) = An(i,j) 即，由即，由i到到j的最短路径不通过比编号的最短路径不通过比编号n还大的结点。还大的结点。 注：
56、该路径可以注：该路径可以经过经过结点结点n，也可以，也可以不经过不经过结点结点n。 若该路径经过结点若该路径经过结点n，则，则 An(i,j) An-1(i,n) + An-1(n,j) 若该路径不经过结点若该路径不经过结点n，则，则 An(i,j) An-1(i,j) 故可得，故可得， An(i,j) = minAn-1(i,j) ，An-1(i,n) + An-1(n,j) 不经过不经过n结点结点 经过经过n结点结点霓舀凶袱陆感氯省鞠颁痰包廖裴推佳澄铡云剐掀靛藕身葛地挟方属衫庇讥第5章动态规划第5章动态规划 对任意的对任意的k， k11，有，有， Ak(i,j) = minAk-1(i,j
57、) ，Ak-1(i,k) + Ak-1(k,j) 不经过结点不经过结点k 刚好经过结点刚好经过结点k 初值初值： A0(i,j)= C(i,j)，1inin，1jn1jn递推计算：递推计算： A1(i,j), A2(i,j), An(i,j)= A (i,j)邹傈棉滁盒跃澈涟焰悯哄所慧兢昔霉川宛疫荚伟季贵概挛眉睬细姿蓑互改第5章动态规划第5章动态规划3. 算法描述算法描述算法算法4.3 每对结点之间的最短路径长度每对结点之间的最短路径长度 procedure ALL-PATHS(COST,A,n) /COST(n,n)是是n结点图的成本邻接矩阵；结点图的成本邻接矩阵；A(i,j)是结点是结点v
58、i到到vj的最短路的最短路 径的成本；径的成本；COST(i,i)=0,1in/ integer I,j,k,n; real COST(n,n),A(n,n) for i1 to n do for j1 to n do A(i,j) COST(i,j) /用用COST(i,j)对A0赋初初值/ repeat repeat for k1 to n do for i1 to n do for j1 to n do A (i,j) minA (i,j) ，A (i,k) + A (k,j) repeat repeat repeat end ALL-PATHS边浮呢急流但琅倘傈呛砍封枷雅兹恒争徽实因房
59、噎亨掩胃驴蛮纂卵耍枉俘第5章动态规划第5章动态规划算法的设计说明算法的设计说明1） Ak(i,k) = Ak-1(i,k) Ak(k,j) = Ak-1(k,j) Ak(i,j) minAk-1(i,j), Ak(i,k) + Ak-1(k,j) Ak(i,j) minAk-1(i,j), Ak-1(i,k) + Ak-1(k,j) 在算法的计算过程中取消了在算法的计算过程中取消了A A的上标，并保证了每次计算的上标，并保证了每次计算 的的 Ak(i,j)即为即为 minAk-1(i,j), Ak-1(i,k) + Ak-1(k,j) 2）如何求每对结点之间的路径？）如何求每对结点之间的路径？
60、噬锻疮纬翠肠溅淋史孺佐埂帐朝娘垂凋嘛哪泌煤哥养娜厂拘皇板樊倪操撕第5章动态规划第5章动态规划例例4.8 有向图如图所示有向图如图所示A012310411260233 0A1123104112602337 70A212310462602337 70A312310462502337 70642 113v1v2v312310411260233 0求图中所有结点间的最短路径矩阵求图中所有结点间的最短路径矩阵A：注：注： A(i,j) = 表明表明G G中从中从i i到到j j没有有向路径没有有向路径逆判耙炎远瓦杖略芥乘蒂蝉逮窑蓄苹背邑傀堪遣孰蝇荧挝凋炭扶溯馈熟惟第5章动态规划第5章动态规划性能分析性能
61、分析 计算时间计算时间 注：该时间与注：该时间与A A的值无关：的值无关： for k1 to n do 迭代迭代n次次 for i1 to n do 迭代迭代n次次 for j1 to n do 迭代迭代n次次 A (i,j) minA (i,j) ，A (i,k) + A (k,j) repeat repeat repeat 侍社企独诀寅展褒存焕酸沏苞早敲藐雷瓷铆企茧撵露灼扇峪派魁喻拓智汀第5章动态规划第5章动态规划的处理 设M是E中最大成本的一条边的成本，则An(i,j) (n-1)*M，则表明G中没有由i到j的有向路径。贮缉钮借抡耪晃长釜堑冗波吧叁傻罕焙一战瘩榔摘赌宅胞秤滁辖缘倡晾蹈第
62、5章动态规划第5章动态规划4.4 最优二分检索树最优二分检索树1. 问题的描述问题的描述1）二分检索树定义）二分检索树定义 二分检索树是一棵二分检索树是一棵二元树二元树，它或者为，它或者为空空，或者其每个，或者其每个结点含有一个可以比较大小的数据元素，且有：结点含有一个可以比较大小的数据元素，且有：的的左子树左子树的所有元素比根结点中的元素小；的所有元素比根结点中的元素小；的的右子树右子树的所有元素比根结点中的元素大；的所有元素比根结点中的元素大；的左子树和右子树也是二分检索树。的左子树和右子树也是二分检索树。 注：注： 二分检索树要求树中所有结点的元素值二分检索树要求树中所有结点的元素值互异
63、互异宦摹褥橱揍械望咱南诌典厂谜句浮困横许吟玫影坡墩汽继腮咎醋菏魔撩她第5章动态规划第5章动态规划ifforwhilerepeatloopifforrepeatloopwhile 对于一个给定的对于一个给定的标识符标识符集合，可能有集合，可能有若干棵若干棵不同的二不同的二分检索树分检索树: :不同形态的二分检索树对标识符的不同形态的二分检索树对标识符的检索性能检索性能是是不同不同的。的。兼栅丢呜足淆跺曾着黎劳天频攀郎闲轮比纫械挞折谁涝咆长著秋碑馒凭分第5章动态规划第5章动态规划2）二分检索树的检索）二分检索树的检索 算法算法4.4 SEARCH(T,X,i) /为为X检索二分检索树检索二分检索树
64、T，如果，如果X不在不在T中，则置中，则置i=0； 否则否则i有有IDENT(i)=X/ iT while i0 do case :XIDENT(i):iLCHILD(i) /若若X小于小于IDENT(i)，则在左子在左子树中中继续查找找/ :XIDENT(i):return /X等于等于IDENT(i)，则返回返回/ :XIDENT(i):iRCHILD(i) /若若X大于大于IDENT(i)，则在右子在右子树中中继续查找找/ endcase repeat end SEARCH只馁饰妓炔材浓凳玄皂界庞状课豺逝涯逝软鹰很灵页机挨凑滥傅妄忍筹挎第5章动态规划第5章动态规划二分检索树的性能特征二分
65、检索树的性能特征 例例 图图(a)： 最坏情况最坏情况下查找标识符下查找标识符loop需要做需要做4次比较；次比较； 成功检索成功检索平均平均需要做需要做12/5次比较次比较; 图图(b)： 最坏情况最坏情况下查找标识符下查找标识符loop/while需要做需要做3次比较；次比较； 成功检索成功检索平均平均需要做需要做11/5次比较次比较 查找概率查找概率 可以期望不同标识符的可以期望不同标识符的检索频率检索频率是不同的。如是不同的。如 PforPwhile Ploop 不成功检索不成功检索 可以期望不成功检索出现的可以期望不成功检索出现的频率频率也是不同的。也是不同的。胚瓢铃小瘩配艰孰陨拢酮
66、咨渡奢溉帐贯勾森幕脯猎严育检胚韭浊拴剥潮镶第5章动态规划第5章动态规划3）最优二分检索树问题）最优二分检索树问题 设给定的标识符集合是设给定的标识符集合是a1,a2,an，并假定，并假定a1a2 an 。 设，设，P(i)是对是对ai检索的概率，检索的概率，Q(i)是正被检索的标识符是正被检索的标识符X恰好满足：恰好满足： ai Xai+1，0inin（设（设a a0 0=-,a=-,an+1n+1=+)=+)时的概率，即一种不成功检索时的概率，即一种不成功检索情况下的概率。情况下的概率。则则 表示所有成功检索的概率表示所有成功检索的概率 表示所有不成功检索的概率表示所有不成功检索的概率 考虑
67、所有可能的成功和不成功检索情况，共考虑所有可能的成功和不成功检索情况，共2n+12n+1种可能的情况，有种可能的情况，有 元密乃蛾圆熊噬蛇胚记一搀隧脑狄筏界慑肮买疏尾琶瞎吕氯遗眼辟浙召赡第5章动态规划第5章动态规划二分检索树二分检索树 内结点内结点：代表成功检索情况，刚好有：代表成功检索情况，刚好有n n个个 外结点外结点：代表不成功检索情况，刚好有：代表不成功检索情况，刚好有n n1 1个个 关于关于a1,a2,an的的最优二分检索树最优二分检索树含义如下：含义如下：祖荐硝苫杆潍聂娇惫畴查幅寓饲肩榨磁烽搀伦吮钙射串黑枢硼嫉锹族贩炙第5章动态规划第5章动态规划二分检索树的预期成本二分检索树的预
68、期成本 预期成本预期成本：算法对于所有可能的成功检索情况和不成功检：算法对于所有可能的成功检索情况和不成功检索情况，平均所要做的比较次数。根据期望值计算方法，索情况，平均所要做的比较次数。根据期望值计算方法， 平均检索成本平均检索成本每种情况出现的每种情况出现的概率概率该情况下所需的比较该情况下所需的比较次数次数 平均检索成本的平均检索成本的构成构成：成功检索成分成功检索成分不成功检索成分不成功检索成分 成功检索成功检索：在：在l级内结点终止的成功检索，需要做级内结点终止的成功检索，需要做l次比次比较运算（基于二分检索树结构）。该级上的任意结点较运算（基于二分检索树结构）。该级上的任意结点ai
69、的的成本成本检索的成本分担额检索的成本分担额为：为： P(i)*level(ai) ； 其中，其中，level(ai) = 结点结点ai 的级数的级数=l陪赚苏喊闲歹脐汲栽碘掣暮滁枫鱼克搁吟忘裸拘樱颓薯搽逸澈竞蜂层空酣第5章动态规划第5章动态规划 不成功检索不成功检索： 不成功检索的不成功检索的等价类等价类：每种不成功检索情况定义了一个等：每种不成功检索情况定义了一个等价类，共有价类，共有n+1个等价类个等价类Ei(0in)。其中，。其中， E0=X|Xa0 Ei=X|aiXai+1(1in) En=X|Xan 若若Ei处于处于l级，则算法需作级，则算法需作l-1次迭代。则，次迭代。则，l级上
70、的外部结点级上的外部结点的的不成功检索的成本分担额不成功检索的成本分担额为：为： Q(i)*(level(Ei)-1) 则预期总的成本公式表示如下：则预期总的成本公式表示如下：摧岁耘馒成街鞠胚济湿彦均抠廷早茧轨元挑赃鉴七噪遭放浚员古荤拷适袄第5章动态规划第5章动态规划最优二分检索树问题最优二分检索树问题： 求一棵使得求一棵使得预期成本预期成本最小最小的二分检索树的二分检索树例例4.9 标识符集合（标识符集合（a1,a2,a3）=（do,if,stop）。可能的二）。可能的二分检索树如下所示。分检索树如下所示。n 成成 功功 检检 索：索：3种种n 不成功情况：不成功情况：4种种凑秸巧杖慢硝封百
71、摔岩窘缨菩悬馁绑缘泼侣磋咙器苛肛剃熔任组屎专塞择第5章动态规划第5章动态规划stopdoifdoifstopstopifdoifdostopdostopif(a)(b)(c)(d)(e)瞩做颠道渊衬望实欢哄啄菏规顺荆滴蹭窒靖力苫擞抠充情吓坛易捎唐柱瞩第5章动态规划第5章动态规划 1) 等概率：等概率：P(i)=Q(i)=1/7 cost(a) = 15/7 cost(b) = 13/7 最优最优 cost(c) = 15/7 cost(d) = 15/7 cost(e) = 15/7 2）不等概率：）不等概率： P(1)=0.5 P(2)=0.1 P(3)=0.05 Q(0)=0.15 Q(1
72、)=0.1 Q(2)=0.05 Q(3)=0.05 cost(a) = 2.65 cost(b) = 1.9 cost(c) = 1.5 最优最优 cost(d) = 2.15 cost(e) = 1.6ifdostopdostopif(b)(c)召舰安窑铣充隋陛庶秦圭像夷绎扭斥检庆骇糖枣刃疮遇猫威侥刹刑钝剑溺第5章动态规划第5章动态规划2. 多阶段决策过程多阶段决策过程 把构造二分检索树的过程看成一系列决策的结果。把构造二分检索树的过程看成一系列决策的结果。 决策的策略：决策树根，如果决策的策略：决策树根，如果a1,a2,an存在一棵二存在一棵二分检索树，分检索树，ak是该树的根，则内结点是
73、该树的根，则内结点a1,a2,ak-1和外部结和外部结点点E0,E1,Ek-1将位于根将位于根ak的左子树中，而其余的结点将位的左子树中，而其余的结点将位于右子树中。于右子树中。ak由ak1, ak+2, ,an及Ek,Ek+1,En构成的二分检索树由a1,a2,ak-1及E0,E1,Ek-1构成的二分检索树磁栗捣矩翰市逗豌涅教绩诀度阻冤初柜垮妄细坍童坍痹烫磁衰粒蔽弯褐税第5章动态规划第5章动态规划定义：定义：含义：含义： 左、右子树左、右子树的的预期成本预期成本左、右子树的左、右子树的根根处于处于第一级第一级 左、右子树中所有结点的级数相对于子树的根测定，而相对于原左、右子树中所有结点的级数
74、相对于子树的根测定，而相对于原树的根少树的根少1撮杭樱忠订委匠浮可乘邹赋缆斯功篆轮缠渝殊秘肛患损烘斤路非屁右姐华第5章动态规划第5章动态规划记：记： 则，原二分检索树的预期成本可表示为：则，原二分检索树的预期成本可表示为： COST(T)=P(k)+COST(L)+COST(R)+W(0,k-1)+W(k,n) 最优二分检索树最优二分检索树：COST(T)有最小值有最小值最优性原理成立最优性原理成立 若若T最优二分检索树，则最优二分检索树，则COST(L)和和COST(R)将分别是包含将分别是包含a1,a2,ak-1和和E0,E1,Ek-1、及、及ak1, ak+2, ,an和和Ek,Ek+1
75、,En的最的最优二分检索优二分检索(子子)树。树。 记由记由ai+1,ai+2,aj和和Ei,Ei+!,Ej构成的二分检索树的成本为构成的二分检索树的成本为C(i,j)，则对于最优二分检索树，则对于最优二分检索树T有，有， COST(L) = C(0,k-1) COST(R) = C(k,n)篡碎祷缔纹峙萝袁署淄童实枯眷旬倦棘眠趋塔揉波混狰堕盐屉菌滞啃岳汹第5章动态规划第5章动态规划则，则，对任何对任何C(i,j)有，有，向前递推过程：向前递推过程： 首先计算所有首先计算所有j-i=1的的C(i,j) 然后依次计算然后依次计算j-i=2,3,n的的C(i,j)。 C(0,n)=最优二分检索树的
76、成本。最优二分检索树的成本。 初始值初始值 C(i,i) = 0 W(i,i) = Q(i)，0inin悲沉斗盆二鹰池兆松扫或残窝太懦澈铀杯特哮供藉钥颐旗型虽急持擒徘果第5章动态规划第5章动态规划最优二分检索树的构造最优二分检索树的构造 在计算在计算C(i,j)的过程中，记下使之取得最小值的的过程中，记下使之取得最小值的k值，值，即树即树Tij的根，记为的根，记为R(i,j)。 依据依据R(0,n)，推导树的形态，推导树的形态在盾齐要抒汛帕壬闪其口钳凋碑桩里夷屑捣戌浙玄荧慑职装研平雹尼弯葱第5章动态规划第5章动态规划例例.10 设设n=4,且且(a1,a2,a3,a4)=(do,if,read
77、,while)。 设设P(1:4) = (3,3,1,1)，Q(0:4) = (2,3,1,1,1) (概率值概率值“扩大扩大”了了16倍倍)初始：初始：W(i,i)=Q(i) C(i,i)=0 R(i,i)=0且有，且有，W(i,j)=P(j)+Q(j)+W(i,j-1)j-i=1阶段（只有一个结点）的计算阶段（只有一个结点）的计算： W(0,1)=P(1)+Q(1)+W(0,0) = 8 C(0,1)=W(0,1)+minC(0,0)+C(1,1) = 8 R(0,1) = 1 W(1,2)=P(2)+Q(2)+W(1,1) = 7 C(1,2)=W(1,2)+minC(1,1)+C(2,
78、2) = 7 R(1,2) = 2 W(2,3)=P(3)+Q(3)+W(2,2) = 3 C(2,3)=W(2,3)+minC(2,2)+C(3,3) = 3 R(2,3) = 3 W(3,4)=P(4)+Q(4)+W(3,3) = 3 C(3,4)=W(3,4)+minC(3,3)+C(4,4) = 3 R(3,4) = 4肌桨趴蝗彭吾献孩咕奉兜桌醒宫同岸蔷梭瓮份又嗓汪奶挝律呕建褒荆舶巳第5章动态规划第5章动态规划nj-i=2阶段（有两个结点）的计算阶段（有两个结点）的计算：nW(0,2)=p(2)+Q(2)+W(0,1)=3+1+8=12nC(0,2)=W(0,2)+min(C(0,0)
79、+C(1,2),(C(0,1)+C(2,2)=12+min7,8=n 12+7=19nR(0,2)=1(表明当表明当k=1（do为根结点）时使得为根结点）时使得C取最小值取最小值）nW(1,3)=P(3)+Q(3)+W(1,2)=1+1+7=9nC(1,3)=W(1,3)+min(C(1,1)+C(2,3),(C(1,2)+C(3,3)=9+min3,7n =9+3=12nR(1,3)=2(表明当表明当k=2时（时（if为根结点）使得为根结点）使得C取最小值取最小值）nW(2,4)=P(4)+Q(4)+ W(2,3)=1+1+3=5nC(2,4)=W(2,4)+min(C(2,2)+C(3,4
80、),(C(2,3)+C(4,4)=5+min3,3=8nR(2,4)=3 or 4(表明当表明当k=3 or 4 （read或或while为根结点）时使得为根结点）时使得C取取最小值最小值）琳踞梦炳鼠它拿效疹么迪野澄妙略包索尊胳砖朱摄职痞黔郎钎根顺取暗奴第5章动态规划第5章动态规划nj-i=3阶段（有三个结点）的计算阶段（有三个结点）的计算：nW(0,3)=p(3)+Q(3)+W(0,2)=1+1+12=14nC(0,3)=W(0,3)+min(C(0,0)+C(1,3),(C(0,1)+C(2,3),(C(0,2)+C(3,3) =14+min12,8+3,19=14+11=25nR(0,3
81、)=2(表明当表明当k=2（if为根结点）时使得为根结点）时使得C取最小值取最小值）nW(1,4)=P(4)+Q(4)+W(1,3)=1+1+9=11nC(1,4)=W(1,4)+min(C(1,1)+C(2,4),(C(1,2)+C(3,4),(C(1,3)+C(4,4) =11+min8,7+3,12=11+8=19nR(1,4)=2(表明当表明当k=2 （if为根结点）时使得为根结点）时使得C取最小值取最小值）nj-i=4阶段（有四个结点）的计算阶段（有四个结点）的计算：nW(0,4)=P(4)+Q(4)+W(0,3)=1+1+14=16nC(0,4)=W(0,4)+min(C(0,0)
82、+C(1,4),(C(0,1)+C(2,4),(C(0,2)+C(3,4),( C(0,3)+C(4,4)=16+min19,8+8,19+3,25=16+16=32nR(0,4)=2(表明当表明当k=2 （if为根结点）时使得为根结点）时使得C取最小值取最小值） 忆回亏耶哑箍旬扶杖箍底寇踏发俘虫阂迅饮诉还瘸恤吃扳藏壮旨竭恿宛振第5章动态规划第5章动态规划C(i,j),W(i,j),R(i,j)计算结果计算结果则，则，C(0,4)=32二分检索树：二分检索树： T04=2 =T01(左子树），左子树），T24(右子树）右子树） T01=1 =T00(左子树），左子树），T11(右子树）右子树）
83、 T24=3 =T22(左子树），左子树），T34(右子树）右子树） 0123402,0,03,0,01,0,01,0,01,0,018,8,17,7,23,3,33,3,4212,19,19,12,25,8,3316,25,211,19,2416,32,2W(j,j+i),C(j,j+i),R(j,j+i)性惩悠硅从召曲撒诅扛首司鬃译窗其拥共肖坡光肌芥莽舅被仙味议煤潘生第5章动态规划第5章动态规划n树的形态树的形态ifdoreadwhile侄堂躺贷涪胞横锥搓吝导账隆饯沤嘘猜豹艾进溅茶领职细惰饼羞还凿揣厉第5章动态规划第5章动态规划3.计算时间计算时间 当当j-i=m时，有时，有n-m+1个个
84、C(i,j)要计算要计算 C(i,j)的计算：的计算：(m) 每个每个C(i,j)要求找出要求找出m个量中的最小值。个量中的最小值。 则，则，n-m+1个个C(i,j)的计算时间：的计算时间： (nm-m2) 对所有可能的所有可能的m，总计算算时间为： 一种改一种改进措施（克努特）：最措施（克努特）：最优的的kR(i,j-1),R(i+1,j) 付憎婶羹料绩拱稗舶辜郸桅拍需杠鸦僧瞥樱孽悲家隋连垢戍协萎吗亢乘响第5章动态规划第5章动态规划4.算法描述算法描述 procedure OBST(P,Q,n) /给定给定n个标识符个标识符a1a2a2anan。已知成功检索的概率。已知成功检索的概率P(i
85、),P(i),不成功检索概率不成功检索概率Q(i), Q(i), 0in 0in。算法对于标识符。算法对于标识符ai+1,ai+1,aj,aj计算最优二分检索树计算最优二分检索树TijTij的成本的成本C(i,j)C(i,j)、根、根 R(i,j) R(i,j)、权、权W(i,j) W(i,j) / real P(1:n),Q(1:n),C(0:n,0:n),W(0:n,0:n);integer R(0:n,0:n) for i0 to n-1 do (W(i,i), R(i,i), C(i,i)(Q(i),0,0) /置初置初值/ (W(i,i+1), R(i,i+1), C(i,i+1)(
86、Q(i)+Q(i+1)+P(i+1),i+1, Q(i)+Q(i+1)+P(i+1) repeat /含有一个含有一个结点的最点的最优树/ (W(n,n), R(n,n), C(n,n)(Q(n),0,0) for m2 to n do /找有找有m个结点的最优树个结点的最优树/ for i0 to n-m do ji+m W(i,j) W(i,j-1)+P(j)+Q(j) k区区间R(i,j-1), R(i+1,j)中使中使C(i,l-1)+C(l,j)取最小取最小值的的l值 /Knuth结论/ C(i,j) W(i,j)+C(i,k-1)+C(k,j) R(i,j)k repeat rep
87、eat end OBST剩俩阮危闪湖投宽锗柠拄卵咳亭晒凶垦逸涣娜密煌雨婪轮计枕殃器滩冲磕第5章动态规划第5章动态规划OBST算法的计算时间算法的计算时间:(n2)倪却炬馁东每驱少跋迁杖手栓材衫界瑚执冻忆蹭诡叫纷猾坟到联挨偶十诸第5章动态规划第5章动态规划1. 问题描述问题描述 1) KNAP(1,j,X) 目标函数目标函数： 约束条件约束条件： 0/1背包问题：背包问题：KNAP(1,n,M) 最优性原理最优性原理对于对于0/1背包问题成立背包问题成立 求解策略：求解策略：向前递推向前递推、向后递推向后递推 4.5 0/1背包问题背包问题襄侧鄙领闰暗奉贡酉逞垫塞埋翻首宾稳辟列硼伺只欢圆下勘彼衰
88、传覆辜丹第5章动态规划第5章动态规划2) 向后递推关系式向后递推关系式 记记fj(X)是是KNAP(1,j,X)的最优解，则的最优解，则fn(M)有有 fn(M) = maxfn-1(M),fn-1(M-wn)+pn 对于任意的对于任意的fi(X)，i0,有有 fi(X) = maxfi-1(X),fi-1(X-wi)+pi 递推过程：递推过程： 初始值初始值 0 X00 f0= X0 0 求出所有可能的求出所有可能的X对应的对应的fi值。值。 fn(M)=KNAP(1,n,M)蝎妈陷团辗宴卫朔铡骄夫医威吕幻扰壶掳委蜡绳轨萨浑咙悍猪饮汞标镀匙第5章动态规划第5章动态规划例例4.11 背包问题背
89、包问题 n=3,(w1,w2,w3)=(2,3,4),(p1,p2,p3)=(1,2,5)，M=6 递推计算过程递推计算过程 X0 f0(X)= 0 X0 X0 f1(X)= max0,+1=0 0X2 max0,0+1 = 1 X2 X0 0 0X2 f2(X)= 1 2X3 max1,0+2=2 3X5 max1,1+2 = 3 X5 f3(M)= max3,1+5 = 6 fi(X) = maxfi-1(X),fi-1(X-wi)+pi墒蔑友麻潜顺搔遂锑钥疵潦诚在帝椎赞恫潦增奈申缔匠玫参瞄鹿唉闻锐牲第5章动态规划第5章动态规划解向量的推导解向量的推导 f3(M)=6 x3=1 P=6-p
90、3=1 KNAP(1,3,6)=6 M=6-w3=2 X=(1,0,1) f2(M)=1 x2=0 f1(M)=1 x1=1 匪稽游净牺熊梯既朵钓葡铜扶赌擞嫁堰青久件央托逐拍土贵体棱童宵件榷第5章动态规划第5章动态规划f1,f2,f3计算过程（图解）计算过程（图解）1234567012f0(x)=0i:fi-1(x-wi) + pii=0:函数不存在1234567012i1:f0(x-w1) + p11234567012f1(x)1234567012i2:f1(x-w2) + p23xxxx12345670123xf2(x)税夕避彪拉茶蔚妨眷衫既斋辊值抢损废嘘参浆簧伦蔬招质妊竞怨灌携孙辅第5章
91、动态规划第5章动态规划12345670678x1234589i3:f2(x-w3) + p312345670678x1234589f3(x)10注： fi-1(X-wi)+pi曲线的构造：将曲线的构造：将fi-1(X)的曲线在的曲线在X轴上右移轴上右移wi个单位，然后上个单位，然后上 移移pi个单位而得到；个单位而得到； fi(X)曲线的构造：由曲线的构造：由fi-1(X) 和和fi-1(X-wi)+pi的曲线按的曲线按X相同时相同时取大值取大值的规的规 则归并而成则归并而成麓呛榔霍眯斌至磷炙弓桶明普拍时撂概邓侈粗朵彬攻剪苟范迁郊娃甜姻附第5章动态规划第5章动态规划2. 序偶表示序偶表示 记记
92、 fi的序偶集合为的序偶集合为 Si = (Pj,Wj)|Wj是是fi曲线中使得曲线中使得fi产生一次阶跃的产生一次阶跃的X值，值，0jr 即即Pj=fi(Wj) (P0,W0)=(0,0) 共有共有r个阶跃值，分别对应个阶跃值，分别对应r个个(Pj,Wj)序偶，序偶， 1jr 若若WjWj+1,则则PjPj+1，0jr 若若WjXWj+1，fi(X)=fi(Wj) 若若XWr，fi(X)=fi(Wr)仓手羹镁竭注第艘罐妒壮迎憋躺展谈逆相挎史万喻蠢东装浅伍捡擞拍骇京第5章动态规划第5章动态规划 Si的构造的构造 记记 是是fi-1(X-wi)+pi的所有序偶的集合，则的所有序偶的集合，则 其中
93、，其中，Si-1是是fi-1的所有序偶的集合的所有序偶的集合 Si的构造的构造：由：由Si-1和和 按照按照支配规则支配规则合并而成。合并而成。 支配规则支配规则：如果：如果Si-1和和 之一有序偶之一有序偶(Pj,Wj),另一有另一有(Pk,Wk)， 且有且有 WjWk , Pj Pk， 则序偶则序偶(Pj,Wj)将被舍弃。将被舍弃。 （即取最大值规则）。（即取最大值规则）。 注：注： Si中的所有序偶是背包问题中的所有序偶是背包问题KNAP(1,i,X)在在X各种各种 取值下的最优解取值下的最优解斟钠小敌昨态晋般速麻室缅砾嘴讣洲碾帜需稽暴革渤佩念诉蓉辽龟烛奔会第5章动态规划第5章动态规划例
94、例4.12 例例4.11的序偶计算的序偶计算 S0=(0,0) =(1,2) S1=(0,0),(1,2) =(2,3),(3,5) S2=(0,0),(1,2), (2,3),(3,5) =(5,4),(6,6), (7,7),(8,9) S3=(0,0),(1,2), (2,3),(5,4),(6,6), (7,7),(8,9) 注：序偶注：序偶(3,5)被被(5,4)“支配支配”而删除而删除枝扔宗喻嘉椭嫁识栏狡墙宾驹丹仙甄醒印渠腕臻经荫醋寸麻拄侈般妒灭刁第5章动态规划第5章动态规划KNAP(1,n,M)问题的解问题的解 Sn是是KNAP(1,n,X)在在0XM各种取值下的最优解各种取值下
95、的最优解 KNAP(1,n,M)的最优解由的最优解由Sn的最后一对的最后一对有效序偶有效序偶给出。给出。xi的推导的推导 xn: 设设Sn的最后一对的最后一对有效序偶有效序偶是是(P1,W1)，则，则(P1,W1)或者或者 是是Sn1的最末一对序偶，或者是的最末一对序偶，或者是(Pj+pn,Wj+wn)，其中，其中 (Pj,Wj) Sn1且且Wj是是Sn1中满足中满足Wj+wnM的最大值。的最大值。 若若(P1,W1) Sn1，则，则Xn0；否则，；否则， (P1pn,W1-wn) Sn1 ，Xn1 xn-1: 若若xn=0，则判断，则判断(P1,W1) Sn2？，以确定？，以确定Xn-1的值
96、的值 若若xn=1，则依据，则依据(P1pn,W1-wn) Sn2？，以判断？，以判断Xn-1的的值值 xn-2,x1将依次推导得出将依次推导得出 琵坞相噬奶骂挣毙林预职削炼最芯咯赏求纯鲜常合梁态蔬镑冤悦葛驹岁炔第5章动态规划第5章动态规划例例4.13 （例（例4.12) S0=(0,0) S1=(0,0),(1,2) S2=(0,0),(1,2), (2,3),(3,5) S3=(0,0),(1,2), (2,3),(5,4),(6,6), (7,7),(8,9) M=6，f3(6)由由S S3 3中的序偶中的序偶(6,6)给出。给出。 1) (6,6) S 1) (6,6) S2 2 x
97、x3 3=1=1 2) (6-p 2) (6-p3 3,6-w,6-w3 3)=(1,2)S)=(1,2)S2 2且且(1,2)S(1,2)S1 1 x x2 2=0=0 3) (1,2) S 3) (1,2) S0 0 x x1 1=1=1陈诽及阔挝助蛹冒尿腐继对贫使指谓括括掣邢乎凳碟闽境鳖鞘盂奋莹卯狄第5章动态规划第5章动态规划算法算法4.6 非形式的背包算法非形式的背包算法 procedure DKP(p,w,n,M) S0 (0,0) for i1 to n-1 do (P1,W1)|(P1-pi,W1-wi) Si-1 and W1M Si MERGE-PURGE(Si-1, ) r
98、epeat (PX,WX) Sn-1的最末一个有效序偶的最末一个有效序偶 (PY,WY)(P1pn,W1+wn)，其中，其中，W1是是Sn-1中使得中使得WwnM的的 所有序偶中取最大所有序偶中取最大值得得W /沿沿Sn-1, S1回溯确定回溯确定xn,xn-1,x1的取的取值/ if PXPY then xn0 /PX将是将是Sn的最末序偶的最末序偶/ else xn1 /PY将是将是Sn的最末序偶的最末序偶/ endif 回溯确定回溯确定xn-1,x1 end DKP洼彭忧补便忧煎磊丸予各忘冯铀炬撰哇滔肋柄店向盼继富藉古检哉醛嫩跃第5章动态规划第5章动态规划3. DKP的实现的实现1)序偶
99、集序偶集Si的存储结构的存储结构 使用两个一维数组使用两个一维数组P和和W存放所有的序偶存放所有的序偶(P1,W1),其中其中P存放存放P1值，值，W存放存放W1值值 序偶集序偶集S0, S1, Sn-1顺序顺序、连续连续存放于存放于P和和W中；中； 用指针用指针F(i)表示表示Si中第一个元素在数组中第一个元素在数组 (P,W)中的下标位置，中的下标位置，0in; F(n)Sn-1中最末元素位置中最末元素位置1 1 2 3 4 5 6 7 P 0 0 1 0 1 2 3 W 0 0 2 0 2 3 5 F(0)F(1) F(2) F(3)剃梳蚌法往缮雕冷律恭篮颐减球铲列犹堕熊两掣准昔师掉醛匡
100、允约粳娇半第5章动态规划第5章动态规划2) 序偶的生成与合并序偶的生成与合并 Si的序偶将按照的序偶将按照P和和W的递增次序生成的递增次序生成 中序偶的生成将与中序偶的生成将与 和和Si-1的合并同时进行的合并同时进行 设设 生成的下一序偶是生成的下一序偶是(PQ,WQ)；对；对所有所有的的(PQ,WQ)，根据支配规则，根据支配规则处理如下：处理如下： 将将Si-1中所有中所有W值值小于小于WQ的序偶直接计入的序偶直接计入Si中；中； 根据支配规则，若根据支配规则，若Si-1中有中有W值小于值小于WQ的序偶的序偶支配支配 (PQ,WQ)，则，则(PQ,WQ)将被舍弃，否则将被舍弃，否则(PQ,
101、WQ)计入计入Si中；并清除中；并清除 Si-1中所有可被支配的序偶，这些序偶有中所有可被支配的序偶，这些序偶有WWQWQ且且PPQPPQ 对所有的对所有的(PQ,WQ)重复上述处理；重复上述处理； 将最后将最后Si-1中剩余的序偶直接计入中剩余的序偶直接计入Si中；中； 所有计入所有计入Si中的新序偶依次存放到由中的新序偶依次存放到由F(i)指示的指示的Si的存放位的存放位 置上。置上。 注：不需要存放注：不需要存放 的的专用空间专用空间沫裴剔羽左桩赫热寡桶嚼触沏乙壕珠勾羡近就族刺溢堵塌禹邱卤靶逮忻青第5章动态规划第5章动态规划3) 算法的实现算法的实现算法算法4.7 0/1背包问题的算法描
102、述背包问题的算法描述 procedure DKNAP(p,w,n,M,m) real p(n), w(n), P(m), W(m),pp,ww,M；integer F(0:n),l,h,u,i,j,p,next F(0)1;P(1)W(1)0 /S0/ lh1 / S0 的首端和末端；的首端和末端；l是是Si-1的首端，的首端，h是是Si-1的末端的末端/ F(1)next2 /P和和W中第一个空位；中第一个空位；next指示指示P/W中可以存放中可以存放(P,W)序偶的第一个位置序偶的第一个位置/ for i1 to n-1 do /生成生成Si/ kl u在在lrh中使得中使得W(r)+w
103、iM的最大的最大r /u指示由指示由Si-1生成生成 的最大有效位置的最大有效位置/ for jl to u do /生成生成 ，同，同时进行行归并并/ (pp,ww)(P(j)+pi,W(j)+wi) /生成生成 中的下一个元素中的下一个元素/ while kh and W(k)ww do /从从Si-1中取元素并归并中取元素并归并/ P(next)P(k);W(next)W(k) /所有所有W(k)ww 的序偶直接的序偶直接归并并/ nextnext+1;kk1 repeat 执驭锡彻陡墩惯讽畔呀怜赌蛙蕊颐受飞妮勋氢亿柿缩樟季陆暮闺庇辑痉狸第5章动态规划第5章动态规划 /按照支配按照支配规
104、则考考虑(pp,ww)及及Si-1中的序偶中的序偶/ if kh and W(k)=ww then ppmax(pp,P(k) kk+1 endif if ppP(next-1) then (P(next), W(next)(pp,ww) nextnext+1 endif /清除清除Si-1中的序偶中的序偶/ while kh and P(k)P(next-1) do kk+1 repeat repeat /将将Si-1中剩余的元素并入中剩余的元素并入Si / while kh do (P(next),W(next)(P(k),W(k) nextnext+1; kk+1 repeat /对Si
105、+1置初置初值 / lh+1; hnext -1; F(i+1)next repeat CALL PARTS /递推求取推求取Xn,Xn-1,x1/ END DKNAP且眷队灼援溜妙损撕脑悦傣搞然咸杰阁委怒烽饯滥哑嫉烟联舔业捞鞘这墒第5章动态规划第5章动态规划4. 过程过程DKNAP的分析的分析1) 空间复杂度空间复杂度 记记Si中的序偶数为：中的序偶数为：|Si| 则有，则有， |Si| |Si-1| | 又，又， | | |Si-1| 所以，所以， |Si|22|Si-1| 最坏情况下有（由最坏情况下有（由Si-1生成生成 和和Si时没有序偶被支配）时没有序偶被支配） ： 故，故，DKNA
106、P所需的空间复杂度（所需的空间复杂度（P、W数组）为数组）为:(2(2n n) )徐哨灿颊叉阁宙察琅晾岸岳霸艇喷衍利疲吾毒刁饼绳亨侩闭杭镭约妊瞎熬第5章动态规划第5章动态规划2) 时间复杂度时间复杂度 由由Si-1生成生成Si的时间为：的时间为： ，0iin-1 故，故，DKNAP计算所有的计算所有的Si所需的时间为：所需的时间为： 注：注： 若每件物品的重量若每件物品的重量wi和效益值和效益值pi均为均为整数整数，则，则Si中每个序偶中每个序偶(P,W)的的P值和值和W值也是整数，且有值也是整数，且有 ，WMM 又，在任一又，在任一Si中的所有序偶具有互异中的所有序偶具有互异P值和值和W值，
107、故有值，故有 且且 载漫筏变脯樊拂恕沪随袒精披低齿聂忆拨暮昧慰江椿魁荣瑰苹熔嘎恋灾勺第5章动态规划第5章动态规划 在所有在所有w wj j和和p pj j均为均为整数整数的情况下，的情况下，DKNAPDKNAP的时间和空间复的时间和空间复杂度将为：杂度将为：蔷晃衍芒评酌侄肮飘彝离甲词询泻敛绥烹镑蝶创斗坏她讲书睡鹅邹酒欣附第5章动态规划第5章动态规划5. 序偶集合的一种启发式生成策略序偶集合的一种启发式生成策略 设设L是最优解的估计值，且有是最优解的估计值，且有fn(M)LL 设设PLEFT(i)=PLEFT(i)= 若正在生成的序偶若正在生成的序偶(P,W)(P,W)有有P PPLEFT(i)
108、PLEFT(i)L L，则，则(P,W)(P,W)将将不计入不计入S Si i中。中。 L L的选择：的选择： 取取S Si i的最末序偶的最末序偶(P,W)(P,W)的的P P作为作为L L，PfPfn n(M)(M) 将某些剩余物品的将某些剩余物品的p p值值P P作为作为L L造顺说狠磅镜扫霍勿熊冗靡清辖佩蛾榜轿奈滑浴戊嚣恩劳甥闹烁及躯龙椿第5章动态规划第5章动态规划例例4.15 0/1背包问题背包问题 n=6,(p1,p2,p3,p4,p5,p6)=(w1,w2,w3,w4,w5,w6)=(100,50,20,10,7,3),M=165 不使用启发方法的序偶集不使用启发方法的序偶集S0
109、=0S1=0,100S2=0,50,100,150S3=0,20,50,70,100,120,150S4=0,10,20,30,50,60,70,80,100,110,120,130,150，160S5=0,7,10,17,20,27,30,37,50,57,60,67,70,77,80,87,100, 107,110,117,120,127,130,137,150,157,160则，则，f6(165)=163 注：每对序偶注：每对序偶(P,W)仅用单一量仅用单一量P（或（或W）表示）表示拓戈挽考裴藤葬瓦乞鸳炒菏定读永他晕泊团顿戳里药桔柳勒菠酚介揉桑赖第5章动态规划第5章动态规划启发式规则求解
110、启发式规则求解 分析：将物品分析：将物品1,2,4,6装入背包，将占用装入背包，将占用163的重量并产生的重量并产生163的效益。的效益。 故，取期望值故，取期望值L163. 按照启发式生成规则，从按照启发式生成规则，从Si中删除所有中删除所有PPLEFT(i)L的序偶，则有的序偶，则有 PLEFT(0)=p1+p2+p3+p4+p5+p6=190 S0=0 =100 PLEFT(1)=p2+p3+p4+p5+p6=90 S1=100 =150 PLEFT(2)=p3+p4+p5+p6=40 S2=150 = PLEFT(3)=p4+p5+p6=20 (w3=20) S3=150 =160 P
111、LEFT(4)=p5+p6=10 S4=160 = PLEFT(5)=p6=3 (w5=7) S5=160 PLEFT(6)=0 f6(165)=160+3 163足巳捎瞻司骤先千驮赠窄泽灰寅涡吱粘血盔尊胺益踩亡吩诈刺获杨传庶坎第5章动态规划第5章动态规划第五章第五章 基本检索与周游基本检索与周游1.检索与周游检索与周游 检索检索：以某种方法检查给定的数据对象，找出满足某些：以某种方法检查给定的数据对象，找出满足某些给定性质的结点的过程称为给定性质的结点的过程称为检索检索 周游周游：当检索过程必须检索到数据对象的每一个结点时，：当检索过程必须检索到数据对象的每一个结点时，则该检索过程称为则该检
112、索过程称为周游周游 访问结点访问结点：当算法对一个结点的信息段进行处理时，称：当算法对一个结点的信息段进行处理时，称该结点该结点被访问被访问。紧奄仆遂泞这罕畜消味乞滞札鹤恤梗厌勘钱戒噎农呢冗案解赴任月素釜综第5章动态规划第5章动态规划2. 二元树周游（遍历）二元树周游（遍历）1）周游次序）周游次序 在二元树的周游中，以在二元树的周游中，以D、L、R分别代表访问结点的信分别代表访问结点的信息段、访问左子树、访问右子树。则可能的顺序有：息段、访问左子树、访问右子树。则可能的顺序有： LDR：中根次序周游（中根遍历）：中根次序周游（中根遍历） LRD：后根次序周游（后根遍历）：后根次序周游（后根遍历
113、） DLR：先根次序周游（先根遍历）：先根次序周游（先根遍历） RDL：逆中根次序周游：逆中根次序周游 RLD：逆后根次序周游：逆后根次序周游 DRL：逆先根次序周游：逆先根次序周游霄炎羡卉丧旧俭志口普朴朽馋悍络拈吊假停优轴舶谐顶滥纲攀撤幢尿兢敷第5章动态规划第5章动态规划2）二元树周游算法）二元树周游算法 中根次序周游中根次序周游 算法算法5.1 5.1 中根次序周游的递归表示中根次序周游的递归表示 procedure INORDER(T) procedure INORDER(T) /T /T是一棵二元树。是一棵二元树。T T的每个结点有三个信息段的每个结点有三个信息段:LCHILD,:LC
114、HILD, DATA,RCHILD/ DATA,RCHILD/ if T0 then if T0 then call INORDER(LCHILD(T) call INORDER(LCHILD(T) call VISIT(T) call VISIT(T) call INORDER(RCHILD(T) call INORDER(RCHILD(T) endif endif end INORDER end INORDER 抛蝗屏坡贪求螺荫痛学坯光效闹蘑傍某啥枣娄叙夷业翁歼窗帆节举刃选毅第5章动态规划第5章动态规划先先根次序周游根次序周游 算法算法5.2 5.2 先先根次序周游的递归表示根次序周游的递
115、归表示 procedure PREORDER(T) procedure PREORDER(T) /T /T是一棵二元树。是一棵二元树。T T的每个结点有三个信息段的每个结点有三个信息段:LCHILD,:LCHILD, DATA,RCHILD/ DATA,RCHILD/ if T0 then if T0 then call VISIT(T) call VISIT(T) call PREORDER(LCHILD(T) call PREORDER(LCHILD(T) call PREORDER(RCHILD(T) call PREORDER(RCHILD(T) endif endif end PRE
116、ORDER end PREORDER缔净败帧完衡瘪沿互吼择团尧咏贷胳装钩盐玲太燎衍菩危胳廷谢札俐无娱第5章动态规划第5章动态规划后根次序周游后根次序周游 算法算法5.2 5.2 后根次序周游的递归表示后根次序周游的递归表示 procedure POSTORDER(T) procedure POSTORDER(T) /T /T是一棵二元树。是一棵二元树。T T的每个结点有三个信息段的每个结点有三个信息段:LCHILD,:LCHILD, DATA,RCHILD/ DATA,RCHILD/ if T0 then if T0 then call POSTORDER(LCHILD(T) call POS
117、TORDER(LCHILD(T) call POSTORDER(RCHILD(T) call POSTORDER(RCHILD(T) call VISIT(T) call VISIT(T) endif endif end PREORDER end PREORDER仆腆容戊侵惦量诺聊农吻颤均获蔡榨高涯这荧浩副尧邑链拍措隘梨尼觉铜第5章动态规划第5章动态规划n中根次序周游：中根次序周游：FDHGIBEACFDHGIBEACn先根次序周游先根次序周游: ABDFGHIEC: ABDFGHIECn后根次序周游后根次序周游: FHIGDEBCA: FHIGDEBCAABDEGCHFI举般宫焙殆糙漓憎睹绢
118、旷怠幅搭瘟豫钝脐戌协骑寒翟六廷兽从短漫募按描第5章动态规划第5章动态规划注：注： 一棵二元树可由中根遍历序列先根遍历序列、或中一棵二元树可由中根遍历序列先根遍历序列、或中根遍历序列后根遍历序列根遍历序列后根遍历序列唯一唯一确定。但确定。但不能不能由先根遍由先根遍历序列后根遍历序列唯一确定。历序列后根遍历序列唯一确定。 如已知一棵二元树的中根遍历次序是：如已知一棵二元树的中根遍历次序是：DGBEAFHC 先根遍历次序是：先根遍历次序是：ABDGECFH 则这棵二元树唯一确定如下则这棵二元树唯一确定如下:ABDEGCFH嫂崎帽荤檬辛阁陈翅莉栽稚舍植烦兔失抨俩垂造舆诌沼莎青皿俯淡挫斧平第5章动态规划
119、第5章动态规划定理定理5.1 当输入的树当输入的树T有有n00个结点时，设个结点时，设t(n)t(n)和和s(n)s(n)分别表示这些周游算分别表示这些周游算法中的任意一个算法所需要的最大时间和空间。如果访问法中的任意一个算法所需要的最大时间和空间。如果访问一个结点一个结点所需要所需要的时间和空间是的时间和空间是(1)(1)，则，则t(n)=(n), s(n)=(n)t(n)=(n), s(n)=(n)。证明：证明：时间时间：由于已知访问一个结点所需要的时间是：由于已知访问一个结点所需要的时间是(1)(1)，故可用常数，故可用常数c c1 1限界。限界。 设设T T的左子树中的结点数是的左子树
120、中的结点数是n n1 1，则，则t(n)t(n)有：有： t(n)=max t(n)=maxn1n1t(nt(n1 1)+t(n-n)+t(n-n1 1-1)+c-1)+c1 1 n1 n1 其中，其中，t(0)ct(0)c1 1。 归纳法证明归纳法证明t(n)ct(n)c2 2n+cn+c1 1，其中，其中c c2 2是一使得是一使得c c2 22c2c1 1的常数。的常数。 1) 1)当当n=0n=0时，成立时，成立 2) 2)假定当假定当n=0,1,n=0,1,m-1,m-1时均成立。则当时均成立。则当n=mn=m时有，时有， 设设T T是一棵有是一棵有m m个结点的树，个结点的树，T
121、T左子树结点数为左子树结点数为n n1 1, ,则则 t(n) t(n)maxmaxn1n1t(nt(n1 1)+t(n-n)+t(n-n1 1-1)+c-1)+c1 1 max maxn1n1cc2 2n n1 1+c+c1 1+c+c2 2(n-n(n-n1 1-1)+c-1)+c1 1+c+c1 1 maxmaxn1n1cc2 2n+3cn+3c1 1-c-c2 2 c c2 2n+cn+c1 1 同理，存在同理，存在cc2 2和和cc1 1有有t(n)ct(n)c2 2n+cn+c1 1。所以。所以t(n)=(n)t(n)=(n)空间空间：若：若T T的深度为的深度为d d，则所需空间
122、为，则所需空间为(d), dn(d), dn，所以，所以s(n)=(n)s(n)=(n)。怂水揪轧钱肢始慢腿扭千雨焉删纸膘棺盅朱房官沉元鲤谁搽菩誊砌击寿被第5章动态规划第5章动态规划3. 树的周游树的周游 1) 树的子树顺序树的子树顺序 无序无序有序有序 2) 2)树的周游树的周游 树的先根次序周游树的先根次序周游 树的中根次序周游树的中根次序周游 树的后根次序周游树的后根次序周游朝药靳傍沟稀籽溢办娠垢规依乍墓兽旗归估逆船屏蹄剩痹则殖别原羹柞例第5章动态规划第5章动态规划4. 图的检索和周游图的检索和周游4.1 宽度优先检索和周游宽度优先检索和周游1) 宽度优先检索宽度优先检索 从结点从结点v
123、开始，给开始，给v标上标上已到达已到达（或（或访问访问）标记）标记此时称此时称结点结点v还没有被还没有被检测检测，而当算法访问了邻接于某结点的所有结点时，而当算法访问了邻接于某结点的所有结点时，称该结点被检测了。称该结点被检测了。 访问邻接于访问邻接于v且尚未被访问的所有结点且尚未被访问的所有结点这些结点是新这些结点是新的未被检测的结点。将这些结点依次放置到一的未被检测的结点。将这些结点依次放置到一未检测结点表未检测结点表(队列队列Q)中（末端插入）中（末端插入） 。 标记标记v已被已被检测检测。 若未检测结点表为空，则算法终止；否则若未检测结点表为空，则算法终止；否则 从未检测结点表的表头取
124、一结点作为下一个待检测结点，从未检测结点表的表头取一结点作为下一个待检测结点， 重复上述过程。重复上述过程。飘涟缉泥货态条氨树胞倦嗣纹要匆捅讨现何望倍千明怠触姬蕴设娄丽盖歧第5章动态规划第5章动态规划算法算法5.6 宽度优先检索算法宽度优先检索算法 procedure BFS(v) /宽度优先检索宽度优先检索G，它从结点，它从结点v开始。所有已访问结点被标记为开始。所有已访问结点被标记为VISITED(i)=1。/ VISITED(v)1;uv /VISITED(n)是一个标示数组，初始值是一个标示数组，初始值 VISITED(i)=0, 1inin / 将将Q初始化为空初始化为空 /Q是未检
125、测结点的队列是未检测结点的队列/ loop for 邻接于邻接于u的所有结点的所有结点w do if VISITED(w)=0 then /w未被检测未被检测/ call ADDQ(w,Q) /ADDQ将将w加入到队列加入到队列Q的末端的末端/ VISITED(w)1 /同时标示同时标示w已被访问已被访问/ endif repeat if Q 为空为空 then return endif call DELETEQ(u,Q) /DELETEQ取出队列取出队列Q的表头，并赋给变量的表头，并赋给变量u/ repeat end BFS对拉此圆乏宅岗语厚拽膏狗眨创愁蛙暑赠蘑愚淡域判硼吨拭牢仆槐珐解茨第5
126、章动态规划第5章动态规划定理定理5.2 算法算法BFS可以访问由可以访问由v可到达的所有结点可到达的所有结点证明：设证明：设G=(V,E)是一个是一个(有向或无向有向或无向)图，图，vVV。 归纳法证明定理结论正确。归纳法证明定理结论正确。 记记d(v,w)d(v,w)是由是由v v到达某一可到达结点到达某一可到达结点w(wV)w(wV)的最短路径长度。的最短路径长度。 若若d(v,w)1d(v,w)1，则显然这样的所有，则显然这样的所有w w都将被访问。都将被访问。 假设对所有假设对所有d(v,w)rd(v,w)r的结点都可被访问。则当的结点都可被访问。则当d(v,w)=r+1d(v,w)=
127、r+1时时有：有： 设设w w是是V V中中d(v,w)=r+1d(v,w)=r+1的一个结点的一个结点 设设u u是从是从v v到到w w的最短路径上紧挨着的最短路径上紧挨着w w的的前一个前一个结点。则有结点。则有 d(v,u)=r d(v,u)=r。 所以，所以，u u可通过可通过BFSBFS被访问到。被访问到。 假设假设uv,uv,且且r1r1。根据。根据BFSBFS的处理规则，的处理规则，u u将在被访问之前的某将在被访问之前的某个时刻被放到未被检测结点队列个时刻被放到未被检测结点队列Q Q上，而在另一时刻上，而在另一时刻u u将从队列将从队列Q Q中移中移出。此时，所有邻接于出。此
128、时，所有邻接于u u且尚未被访问的结点将被访问。若结点且尚未被访问的结点将被访问。若结点w w在这在这之前未被访问，则此刻将被访问到。之前未被访问，则此刻将被访问到。 由上，定理得证由上，定理得证冀僚塌椒至乍吓淌霉毖睹覆皇煽鸯妓毙哦舶档骨困莆琐骆权守跟彻垂肌腊第5章动态规划第5章动态规划定理定理5.3 设设t(n,e)和和s(n,e)是算法是算法BFS在任一具有在任一具有n个结点和个结点和e条边的图条边的图G上上所花的最大时间和最大附加空间。所花的最大时间和最大附加空间。 若若G由邻接表表示，则由邻接表表示，则t(n,e)=(n+e)(n+e)和和s(n,e)=(n)(n)。 若若G G由邻接
129、矩阵表示，则由邻接矩阵表示，则t(n,e)=(n(n2 2) )和和s(n,e)=(n)(n)证明：证明： 1) 1)空间分析空间分析 根据算法的处理规则，结点根据算法的处理规则，结点v v不会放到队列不会放到队列Q Q中。结点中。结点w w，wVwV且且wv,wv,仅在仅在VISITED(w)=0VISITED(w)=0时由时由ADDQ(w,Q)ADDQ(w,Q)加入队列，并置加入队列，并置VISITED(w)=1VISITED(w)=1，所以每个，所以每个结点（除结点（除v)v)至多只有一次被放入队列至多只有一次被放入队列Q Q中。中。 至多有至多有n-1n-1个这样的结点考虑，故总共至多
130、做个这样的结点考虑，故总共至多做n-1n-1次结点加入队列的操次结点加入队列的操作。需要的队列空间至多是作。需要的队列空间至多是n-1n-1。所以。所以s(n,e)=(n)(s(n,e)=(n)(其余变量所需的空间其余变量所需的空间为为(1)(1) 当当G G是一个具有是一个具有v v与其余的与其余的n-1n-1个结点相连的图，则邻接于个结点相连的图，则邻接于v v地全部地全部n-1n-1个个结点都将在结点都将在“同一时刻同一时刻”被放在队列上（被放在队列上（Q Q至少应有至少应有(n)(n)的空间）。的空间）。 同时，同时，VISITED(n)VISITED(n)本身需要本身需要(n) (n
131、) 的空间。的空间。 所以所以s(n,e)=(n)s(n,e)=(n)这一结论与使用邻接表或邻接矩阵无关。这一结论与使用邻接表或邻接矩阵无关。蔽奔盐烤错昏织伸五药范仙钾奠掺远案抱聊昌窘逐际左山米稻组速追阶悍第5章动态规划第5章动态规划 2) 时间分析时间分析 G采用邻接表表示采用邻接表表示 判断邻接于判断邻接于u的结点将在的结点将在d(u)时间内完成：若时间内完成：若G是无向图，则是无向图，则d(u)是是u的度；若的度；若G是有向图，则是有向图，则d(u)是是u的出度。的出度。 所有结点的处理时间：所有结点的处理时间：(d(u)=(e)(d(u)=(e)。 注：嵌套循环中注：嵌套循环中对对G中
132、的每一个结点中的每一个结点至多至多考虑考虑一次一次。 VISITED VISITED数组的初始化时间：数组的初始化时间：(n)(n) 算法总时间：算法总时间：(n+e)(n+e)。 G采用邻接矩阵表示采用邻接矩阵表示 判断邻接于判断邻接于u的所有结点需要的所有结点需要的的时间：时间：(n)(n) 所有结点的处理时间：所有结点的处理时间：(n(n2 2) ) 算法总时间：算法总时间：(n(n2 2) ) 如果如果G G是一个由是一个由v v可到达所有结点的图，则将检测到可到达所有结点的图，则将检测到V V中的所有结点，中的所有结点，所以上两种情况所需的总时间至少应是所以上两种情况所需的总时间至少
133、应是(n+e)(n+e)和和(n(n2 2) )。 所以，所以，t(n,e)=(n+e) t(n,e)=(n+e) 使用邻接表表示使用邻接表表示 或，或， t(n,e)=(n t(n,e)=(n2 2) ) 使用邻接矩阵表示使用邻接矩阵表示应弯凑灸鼠腕葫瘩鹊惰坷斥旱匡款砷插崭撕效斋怨篇盆铆色老颜抓迈芬纂第5章动态规划第5章动态规划2) 宽度优先周游宽度优先周游 算法算法5.7 宽度优先图的周游算法宽度优先图的周游算法 procedure BFT(G,n) /G的宽度优先周游的宽度优先周游/ int VISITED(n) for i1 to n do VISITED(i)0 repeat for
134、 i1 to n do /反复调用反复调用BFS/ if VISITED(i)=0 then call BFS(i) endif repeat end BFT 注：若注：若G是无向连通图或强连通有向图，则是无向连通图或强连通有向图，则一次一次调用调用BFS即可即可完成对完成对T的周游。否则，需要的周游。否则，需要多次多次调用。调用。n 果延最独廓泻理蛋售靖酚菊优晦婿忧川壁弧乌谆叹酥弹约拐锋殊群寿切南第5章动态规划第5章动态规划图周游算法的应用图周游算法的应用 判定判定图G的的连通性通性：若：若调用用BFS的次数多于的次数多于1次，次，则G为非非连通的通的 生成生成图G的的连通分通分图：一次：一
135、次调用用BFS中可以中可以访问到的所有到的所有结点及点及连接接这些些结点的点的边构成一个构成一个连通分通分图。 无向无向图自反自反传递闭包矩包矩阵A* 宽度度优先生成先生成树 向前向前边：BFS中由中由u达到未达到未访问结点点w的的边(u,w)称称为向前向前边。 记T是是BFS中所中所处理的所有向前理的所有向前边集合。集合。 宽度度优先生成先生成树：若：若G是是连通通图，则BFS终止止时，T构成一棵生成构成一棵生成树。12345678无向图G12345678G的宽度优先生成树钙读涎舆益后啸揖含鸵丝鼓览啊颈疤系郴狸科恐淌麻釉苛酵晓恤堕帐捏监第5章动态规划第5章动态规划 定理定理5.4 修改算法修
136、改算法BFS，在第，在第1行和第行和第6行分别增加语句行分别增加语句T和和TT(u,w)(u,w)。修改后的算法称。修改后的算法称为BFSBFS* *。若。若v v是无向是无向图中任一中任一结点，点，调用用BFSBFS* *，算法，算法终止止时，T T中的中的边组成成G G的一棵生成的一棵生成树。 procedure BFSBFS* *(v) VISITED(v)1;uv T 将将Q初始化为空初始化为空 loop for 邻接于邻接于u的所有结点的所有结点w do if VISITED(w)=0 then /w未被检测未被检测/ TT(u,w)(u,w) call ADDQ(w,Q) /ADD
137、Q将将w加入到队列加入到队列Q的末端的末端/ VISITED(w)1 /同时标示同时标示w已被访问已被访问/ endif repeat if Q 为空为空 then return endif call DELETEQ(u,Q) /DELETEQ取出队列取出队列Q的表头，并赋给变量的表头，并赋给变量u/ repeat end BFSBFS* *天促重油涂但褥暂滤叁言岁来摧银友海踢驶庆麦退意好一爪壕野淳风赂软第5章动态规划第5章动态规划 证明：明： 若若G G是是n n个个结点的点的连通通图，则这n n个个结点都要被点都要被访问。除起始点。除起始点v v以外，其它以外，其它n-1n-1个个结点都将
138、被放且点都将被放且仅将被放到将被放到队列列Q Q上一次，从而上一次，从而T T将正好包含将正好包含n-1n-1条条边，且，且这些些边是各不相同的。即是各不相同的。即T T是关于是关于n n个个结点点n-1n-1边的无向的无向图。 同同时，对于于连通通图G G，T T将包含由起始将包含由起始结点点v v到其它到其它结点的路径，点的路径，所以所以T T是是连通通的。的。 则T T是是G G的一棵的一棵生成生成树。 注：注：对于于n n个个结点且正好有点且正好有n-1n-1条条边的的连通通图是一棵是一棵树。邻沿撤植异批卸糟甄巫猪国吩怕仇酱瑚案亦慧茧竿熙紧客袖茫臆觉酪僳场第5章动态规划第5章动态规划4
139、.2 深度优先检索和周游深度优先检索和周游1) 深度优先检索深度优先检索 从结点从结点v开始，首先给开始，首先给v标上标上已到达已到达（或（或访问访问）标记，同时中止对）标记，同时中止对v的检的检测，并开始对邻接于测，并开始对邻接于v且尚未被访问的结点且尚未被访问的结点u检测。在这样的检测。在这样的u均被检测后，均被检测后，再恢复对再恢复对v的检测。当所有可到达的结点全部被检测完毕后，算法终止。的检测。当所有可到达的结点全部被检测完毕后，算法终止。算法算法5.8 图的深度优先检索图的深度优先检索 procedure DFS(v) /已知一个已知一个n结点的无向（或有向）图结点的无向（或有向）图
140、G(V,E)以及初值已置为零的数组以及初值已置为零的数组VISITED(1:n)。 这个算法访问由这个算法访问由v可以到达的所有结点。可以到达的所有结点。/ VISITED(v)1 for 邻接于接于v的每个的每个结点点w do if VISITED(w)0 then call DFS(w) endif repeat end DFS吕琐惯夜炉化乳坊皋众壁头裁愈鸿葬坛吧甘叔仍豪外辟汰激释竹仁疡霄走第5章动态规划第5章动态规划性质：性质： DFS可以访问由可以访问由v可到达的所有结点可到达的所有结点 如果如果t(n,e)和和s(n,e)表示表示DFS对一对一n结点结点e条边的图所花的最条边的图所花
141、的最大时间和最大附加空间，则大时间和最大附加空间，则 s(n,e)=(n) t(n,e)= (n+e) G采用采用邻接表接表表示，或表示，或 t(n,e)= (n2) G采用采用邻接矩接矩阵表示表示2) 2) 深度深度优先周游算法先周游算法DFTDFT 反复反复调用用DFS,DFS,直到所有直到所有结点均被点均被检测到。到。 应用：用： 判定判定图G的的连通性通性 连通分通分图 无向无向图自反自反传递闭包矩包矩阵 深度深度优先生成先生成树官缕午查岸跋酒拿郊弓馏岸巩需庆帚旁串观宣苍鄙猛玫瘴南黍毫贫钝战烦第5章动态规划第5章动态规划 深度优先生成树算法深度优先生成树算法procedure DFS*
142、(v) T VISITED(v)1 for 邻接于接于v的每个的每个结点点w do if VISITED(w)0 then TT(u,w)(u,w) call DFS(w) endif repeat end DFS*杭侦宦翠潞初沿顽寿蝎惶贬昏疲鲁辩撅恫裴宰倦逼厦凝萌挚莽皂汉囊烯汗第5章动态规划第5章动态规划12345678无向图G12345678G的宽度优先生成树12345678G的深度优先生成树箍拧林耕朔拖淋喻贺扭广航月怨杜虾盆短严砌贰煞忌寇控撼哦币捕敞甥霞第5章动态规划第5章动态规划4.3 BFS、DFS、D_Search算法比较算法比较 BFS：使用：使用队列队列保存未被检测的结点。结点
143、按照保存未被检测的结点。结点按照宽度优先宽度优先的次的次序被访问和进、出队列。序被访问和进、出队列。 DFS：使用：使用栈栈保存未被检测的结点，结点按照保存未被检测的结点，结点按照深度优先深度优先的次序的次序被访问并依次被压入栈中，并以相反的次序出栈进行新的检测。被访问并依次被压入栈中，并以相反的次序出栈进行新的检测。 D_Search：使用：使用栈栈保存未被检测的结点，结点按照保存未被检测的结点，结点按照宽度优先宽度优先的次序被访问并被依次压入栈中，然后以相反的次序出栈进行新的的次序被访问并被依次压入栈中，然后以相反的次序出栈进行新的检测。新的检测结点是最新被访问但未被检测的结点。检测。新的
144、检测结点是最新被访问但未被检测的结点。 BFS检测序列：检测序列： 1 2 3 4 5 6 7 8 DFS检测序列：检测序列： 1 2 4 8 5 6 3 7 D_Search检测序列：检测序列： 1 3 7 8 5 4 6 212345678无向图G镣诌律宠避训玻淄坠幼簇探蛙磊牢憾嘎像裸耳男恩宽陇贺趁炒恶娃疹疤驹第5章动态规划第5章动态规划阿蚂弓慈贫涸伞臆陌宠撕遮漏巾寡绰叫淡耻粟佣丑慧兴掉橡村叉拆蒋辖伐第5章动态规划第5章动态规划3. 贪心方法的抽象化控制描述贪心方法的抽象化控制描述 procedure GREEDY(A,n) /A(1:n)包含包含n个输入个输入/ solution /将解
145、向量将解向量solution初始化初始化为空空/ for i1 to n do xSELECT(A) /按照度量按照度量标准，从准，从A中中选择一个一个输入，其入，其值赋予予x 并将之从并将之从A中中删除除/ if FEASIBLE(solution,x) then /判定判定x是否可以包含在解向量中，是否可以包含在解向量中， 即是否能共同构成可行解即是否能共同构成可行解/ solutionUNION(solution,x) /将将x和当前的解向量合并成新的解和当前的解向量合并成新的解 向量，并修改目向量，并修改目标函数函数/ endif repeat return(solution) end
146、 GREEDY 歹腑义膨挛姨阀斤后寺秃冠僚卜挥胸堡文泪乔谨拒邑啤难喻蕊拣寿宋式区第5章动态规划第5章动态规划procedure GREEDYP(A,L,S) for i1 to n do S(i)0 /将解向量初始化为空将解向量初始化为空/ repeat cuL /cu是磁带的剩余容量是磁带的剩余容量/ for i1 to n do if a(i) cu then exit endif S(i) 1 cu cu-a(i) repeatend GREEDY-KNAPSACK驶喇贱霖己绊于婉薛烷属执眺挽砖停绞肿度陶臣攘醒榨茵寿琼宏即僚观谴第5章动态规划第5章动态规划n设设n = 4，且，且(a1, a2, a3, a4) = (end, goto, print, stop)，又设，又设P(1:4) = (1/20, 1/5, 1/10, 1/20)，Q(0:4) = (1/5, 1/10, 1/5, 1/20, 1/20)，利用动态规划，利用动态规划方法，分别计算方法，分别计算C(i,j), W(i,j), R(i,j)，并根据结果画出最优二分检索树。并根据结果画出最优二分检索树。 琵盟砂饲颈嗣黑砍轴寨廉卵侗蝴捉教糖酗毕棱陡蛊吊拟卸涝适闻披惶愉坤第5章动态规划第5章动态规划
