第5章动态规划.ppt

《第5章动态规划.ppt》由会员分享，可在线阅读，更多相关《第5章动态规划.ppt（127页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第5章动态规划 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望本章教学要求及重点难点本章教学要求及重点难点n理解动态规划的基本思想；理解动态规划的基本思想；n掌握动态规划的一般方法求最优二分检索掌握动态规划的一般方法求最优二分检索树；树；n掌握掌握0/1背包问题的求解方法；背包问题的求解方法；n掌握货郎担问题的求解方法。掌握货郎担问题的求解方法。n重点：最优二分检索树和重点：最优二分检索树和0/1背包问题的求背包问题的求解方法；解方法；n难点：用动态规划法求解货郎

2、担问题并分难点：用动态规划法求解货郎担问题并分析其时间复杂度。析其时间复杂度。2.多阶段决策过程的求解策略多阶段决策过程的求解策略1）枚举法）枚举法 穷举穷举可能的决策序列，从中选取可以获得最优解的决策序列可能的决策序列，从中选取可以获得最优解的决策序列2）动态规划）动态规划 20世纪世纪50年代初美国数学家年代初美国数学家R.E.Bellman等人在研究多阶段决策等人在研究多阶段决策过程的优化问题时，提出了著名的过程的优化问题时，提出了著名的最优化原理最优化原理(principle of optimality)，把，把多阶段多阶段过程转化为一系列过程转化为一系列单阶段单阶段问题，创立了解决这

3、问题，创立了解决这类过程优化问题的新方法类过程优化问题的新方法动态规划动态规划。动态规划动态规划(dynamic programming)是是运筹学运筹学的一个分支，是求解的一个分支，是求解决策过程决策过程(decision process)最优化的数学方法。最优化的数学方法。应用领域：动态规划问世以来，在经济管理、生产调度、工程技应用领域：动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它资源分配、设备更新、排序、装载

4、等问题，用动态规划方法比用其它方法求解更为方便。方法求解更为方便。3.最优性原理最优性原理(Principle of Optimality)过程的过程的最优决策序列最优决策序列具有如下性质：无论过程的具有如下性质：无论过程的初始状初始状态态和和初始决策初始决策是什么，其余的决策都必须相对于初始决策所是什么，其余的决策都必须相对于初始决策所产生的状态构成一个最优决策序列。产生的状态构成一个最优决策序列。利用动态规划求解问题的前提利用动态规划求解问题的前提 1)证明问题满足最优性原理证明问题满足最优性原理 如果对所求解问题证明满足最优性原理，则说明用动态如果对所求解问题证明满足最优性原理，则说明用

5、动态规划方法有可能解决该问题规划方法有可能解决该问题 2)获得问题状态的递推关系式获得问题状态的递推关系式 获得各阶段间的递推关系式是解决问题的关键。获得各阶段间的递推关系式是解决问题的关键。例例4.1 多段图问题多段图问题多段图多段图G=(V,E)是一个有向图，且具有特性是一个有向图，且具有特性:结点结点：结点集：结点集V被分成被分成k22个不相交的集合个不相交的集合V Vi i，1ik1ik，其中其中V V1 1和和V Vk k分别只有一个结点分别只有一个结点s(s(源点源点)和和t(t(汇点汇点)。每一集合每一集合V Vi i定义图中的定义图中的一段一段。边边：所有的边所有的边(u,v)

6、(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的的最小成本路径最小成本路径。12345678910111297

7、324227111181456356425V1V2V3V4V55段图 多段图问题的多段图问题的多阶段决策过程多阶段决策过程：生成从：生成从s到到t的最小成本路径的最小成本路径是在是在k-2个阶段（除个阶段（除s和和t外）进行某种决策的过程：从外）进行某种决策的过程：从s开始，开始，第第i次次决策决定决策决定Vi+1(1ik-2)中的哪个结点在从中的哪个结点在从s到到t的最短路径上。的最短路径上。最优性原理对多段图问题成立最优性原理对多段图问题成立 假设假设s,v2,v3,vk-1,t是一条由是一条由s到到t的最短路径。的最短路径。初始状态初始状态：s 初始决策初始决策：(s,v2)，v2VV2

8、 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更短的从更短的从s到到t的路径。的路径。与假设矛盾。与假设矛盾。故，最优性原理成立故，最优性原理成立n例例4.20/1背包问题背包问题 KNAP(l,j,X)目标函数目标函数：约束条件约束条件：0/1背包问题：背包问题：KNA

9、P(1,n,M)最优性原理对最优性原理对0/1背包问题成立：背包问题成立：设设y1,y2,yn是是x1,x2,xn的的0/1值最优序列。值最优序列。若若y10,KNAP(2,n,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)将构成一个最优序列。将构成一个最优序列。否则，设存在另一否则，设存在另一

10、0/1序列序列z1,z2,zn,使得使得 且且 则序列则序列y1,z2,zn将是一个对于将是一个对于KNAP(1,n,M)具有更大效益具有更大效益值的序列。值的序列。故，最优性原理成立故，最优性原理成立4.动态规划模型的基本要素动态规划模型的基本要素一个多阶段决策过程最优化问题的动态规划模型通常包含以一个多阶段决策过程最优化问题的动态规划模型通常包含以下要素：下要素：1)阶段阶段 阶段阶段(step)是对整个过程的自然划分。通常根据时间顺是对整个过程的自然划分。通常根据时间顺序或空间特征来划分阶段，以便按阶段的次序解优化问题。序或空间特征来划分阶段，以便按阶段的次序解优化问题。阶段变量一般用阶

11、段变量一般用k=1,2,.,n表示。表示。2）状态状态 状态状态(state)表示每个阶段开始时过程所处的自然状况。它应表示每个阶段开始时过程所处的自然状况。它应该能够描述过程的特征并且具有该能够描述过程的特征并且具有无后向性无后向性，即当某阶段的状态给，即当某阶段的状态给定时，这个阶段以后过程的演变与该阶段以前各阶段的状态无关，定时，这个阶段以后过程的演变与该阶段以前各阶段的状态无关，即每个状态都是过去历史的一个完整总结。通常还要求状态是直即每个状态都是过去历史的一个完整总结。通常还要求状态是直接或间接可以观测的。接或间接可以观测的。描述状态的变量称描述状态的变量称状态变量状态变量(stat

12、e variable)。变量允许取值。变量允许取值的范围称允许的范围称允许状态集合状态集合(set of admissible states)。用。用xk表示第表示第k阶段的状态变量，它可以是一个数或一个向量。用阶段的状态变量，它可以是一个数或一个向量。用Xk表示第表示第k阶段阶段的允许状态集合。的允许状态集合。状态变量简称为状态状态变量简称为状态3）决策）决策 当一个阶段的状态确定后，可以作出各种选择从而演变到下当一个阶段的状态确定后，可以作出各种选择从而演变到下一阶段的某个状态，这种选择手段称为一阶段的某个状态，这种选择手段称为决策决策(decision)。描述决策的变量称决策变量描述决策

13、的变量称决策变量(decision variable)。变量允许。变量允许取值的范围称允许决策集合取值的范围称允许决策集合(set of admissible decisions)。用。用uk(xk)表示第表示第k阶段处于状态阶段处于状态xk时的决策变量，它是时的决策变量，它是xk的函数，用的函数，用Uk(xk)表示了表示了xk的允许决策集合。的允许决策集合。决策变量简称决策。决策变量简称决策。4）策略）策略 决策组成的序列称为策略决策组成的序列称为策略(policy)。由初始状态。由初始状态x1开始开始的全过程的策略记作的全过程的策略记作p1,n(x1)，即，即p1,n(x1)=u1(x1)

14、,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(xj)。对于每一个阶段对于每一个阶段k的某一给定的状态的某一给定的状态xk，可供选择的策略，可供选择的策略pk,j(xk)有一定的范围，称为允许策略集合有一定的范围，称为允许策略集合(set of admissible

15、 policies)，用，用P1,n(x1),Pk,n(xk),Pk,j(xk)表示。表示。5)状态转移方程状态转移方程 在确定性过程中，一旦某阶段的状态和决策为已知，在确定性过程中，一旦某阶段的状态和决策为已知，下阶段的状态便完全确定。用状态转移方程下阶段的状态便完全确定。用状态转移方程(equation of state)表示这种演变规律，写作表示这种演变规律，写作6)指标函数和最优值函数指标函数和最优值函数 指标函数指标函数(objective function)是衡量过程优劣的数是衡量过程优劣的数量指标，它是关于策略的数量函数，从阶段量指标，它是关于策略的数量函数，从阶段k到阶段到阶段

16、n的的指标函数用指标函数用Vk,n(xk,pk,n(xk)表示，表示，k=1,2,.,n。能够用动态规划解决的问题的指标函数应具有可分能够用动态规划解决的问题的指标函数应具有可分离性，即离性，即Vk,n可表为可表为xk,uk,Vk+1,n 的函数，记为：的函数，记为：7.最优策略和最优轨线最优策略和最优轨线 使指标函数使指标函数Vk,n达到最优值的策略是从达到最优值的策略是从k开始的后部子过开始的后部子过程的最优策略，记作程的最优策略，记作pk,n*=uk*,.un*,p1,n*又是全过程的最又是全过程的最优策略，简称最优策略优策略，简称最优策略(optimal policy)。从初始状态。从

17、初始状态x1(=x1*)出发，过程按照出发，过程按照p1,n*和状态转移方程演变所经历的和状态转移方程演变所经历的状态序列状态序列x1*,x2*,.,xn+1*称最优轨线称最优轨线(optimal trajectory)。5.递推策略递推策略1）向前处理法）向前处理法 列出根据列出根据xi+1,xn的最优决策序列求取的最优决策序列求取xi决策决策值的关系式。值的关系式。从最后一个阶段，逐步从最后一个阶段，逐步向前向前递推求出各阶段的递推求出各阶段的决策值。决策序列决策值。决策序列x1,x2,xn就是问题的最优解。就是问题的最优解。xn-1,1xn-1,pn-1xn 例例4.3 利用向前处理法求

18、解利用向前处理法求解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 例例4.4 利用向前处理法求解利用向前处理法求解k段图问题段图问题 设设 V2，1j2p2,|V2|=p2;是由是由 到到t的最短路径，的最短路径，则s

19、到到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的最短路径将是：的最短路径将是：min(|Vi+1,1ji+1pi+1)2）向后处理法向后处理法 列出根据列出根据x1,xi-1的最优决策序列求取的最优决策序列求取xi决决策值的关系式。策值的关系式。从第一个阶段，逐步从第一个

20、阶段，逐步向后向后递推求出各阶段的递推求出各阶段的决策值。决策序列决策值。决策序列x1,x2,xn就是问题的最优解。就是问题的最优解。例例4.5 0/1背包问题（向后处理策略）背包问题（向后处理策略）设设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 例例4.6 k段图问题（向后处理策略）段图问题（向后处理策略）设设 Vk-1，1jk-1pk-1，|Vk-1|=pk-1;是由是由s到到 的最短路径，的最

21、短路径，则s到到t的最短路径是的最短路径是 t|Vk-1,1jk-1pk-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)动态规划的基本思想：动态规划的基本思想：（1）动态规划方法的关键在于正确写出基本的递推关系式）动态规划方法的关键在于正确写出基本的

22、递推关系式和恰当的边界条件。要做到这一点，必须将问题的过程分和恰当的边界条件。要做到这一点，必须将问题的过程分成几个相互联系的阶段，恰当选择状态变量，决策变量和成几个相互联系的阶段，恰当选择状态变量，决策变量和定义最优值函数，从而把一个大问题化成一族同类型的子定义最优值函数，从而把一个大问题化成一族同类型的子问题，然后逐个求解。即从边界条件开始，逐段递推寻优，问题，然后逐个求解。即从边界条件开始，逐段递推寻优，在每一个子问题的求解中，均利用了它前面的子问题的最在每一个子问题的求解中，均利用了它前面的子问题的最优化结果，依次进行，最后一个子问题的最优解，就是整优化结果，依次进行，最后一个子问题的

23、最优解，就是整个问题的最优解。个问题的最优解。（2）在多阶段决策过程中，动态规划方法是既把当前一段）在多阶段决策过程中，动态规划方法是既把当前一段和未来各段分开，又把当前的效益和未来效益综合起来考和未来各段分开，又把当前的效益和未来效益综合起来考虑的一种最优化方法。因此，每段决策的选取是从全局来虑的一种最优化方法。因此，每段决策的选取是从全局来考虑的，与该段的最优选择答案一般是不同的。考虑的，与该段的最优选择答案一般是不同的。（3）在求整个问题的最优策略时，由于初始状态是已知的，）在求整个问题的最优策略时，由于初始状态是已知的，而每段的决策都是该段状态的函数，故最优策略所经的各而每段的决策都是

24、该段状态的函数，故最优策略所经的各段状态便可逐次变换得到，从而确定最优路线。段状态便可逐次变换得到，从而确定最优路线。关于动态规划求解策略的进一步说明关于动态规划求解策略的进一步说明采用枚举法：若问题的决策序列由采用枚举法：若问题的决策序列由n次决策构成，而每次次决策构成，而每次决策有决策有p种选择，则可能的决策序列将有种选择，则可能的决策序列将有pn个。个。利用动态规划策略的求解过程中保存了所有子问题的最优利用动态规划策略的求解过程中保存了所有子问题的最优解，而舍去了所有不能导致问题最优解的次优决策序列解，而舍去了所有不能导致问题最优解的次优决策序列动态规划：可能有多项式的计算复杂度。动态规

25、划：可能有多项式的计算复杂度。与非线性规划相比，动态规划的优点：与非线性规划相比，动态规划的优点：（1）易于确定全局最优解。动态规划方法是一种逐步改善法，）易于确定全局最优解。动态规划方法是一种逐步改善法，它把原问题化为一系列结构相似的最优化子问题，而每个子它把原问题化为一系列结构相似的最优化子问题，而每个子问题的变量个数比原问题少得多，约束集合也要简单得多。问题的变量个数比原问题少得多，约束集合也要简单得多。（2）能得到一族解，有利于分析结果）能得到一族解，有利于分析结果（3）能利用经验，提高求解的效率。动态规划方法反映了过）能利用经验，提高求解的效率。动态规划方法反映了过程逐段演变的前后联

26、系，较之非线性规划与实际过程联系得程逐段演变的前后联系，较之非线性规划与实际过程联系得更紧密。更紧密。不足之处不足之处：（1）没有一个统一的标准模型可供应用。）没有一个统一的标准模型可供应用。（2）应用的局限性。要求状态变量满足）应用的局限性。要求状态变量满足“无后效性无后效性”条件，条件，不少实际问题在取其自然特征作为状态变量往往不能满足这不少实际问题在取其自然特征作为状态变量往往不能满足这条件。条件。（3）在数值求解中，存在）在数值求解中，存在“维数障碍维数障碍”。在计算机中，每递。在计算机中，每递推一段，必须把前一段的最优值函数在相应的状态集合上的推一段，必须把前一段的最优值函数在相应的

27、状态集合上的全部值存入内存中。当维数增大时，所需的内存量成指数倍全部值存入内存中。当维数增大时，所需的内存量成指数倍增长。增长。4.2 多段图问题多段图问题1.问题的描述问题的描述 在多段图中求从在多段图中求从s到到t的一条最小成本的路径，可以看的一条最小成本的路径，可以看 作是在作是在k-2个段作出某种决策的结果。个段作出某种决策的结果。第第i次决策决定次决策决定Vi+1中的哪个结点在这条路径上，这里中的哪个结点在这条路径上，这里 1ik-2ik-2；最优性原理对多段图问题成立最优性原理对多段图问题成立2.向前处理策略求解向前处理策略求解 设设 P(i,j)是一条从是一条从Vi中的结点中的结

28、点j到汇点到汇点t的最小成本路径，的最小成本路径，COST(i,j)是这条路径的成本。是这条路径的成本。1)向前递推式向前递推式 2)递推过程递推过程 第第k-1k-1段段 c(j,t)EE COST(k-1,j)=l1l2.lpi+1tjViVi+112345678910111297324227111181456356425V1V2V3V4V55段图各递推结果各递推结果第第4段段 COST(4,9)=c(9,12)=4 COST(4,10)=c(10,12)=2 COST(4,11)=c(11,12)=5第第3段段 COST(3,6)=min6+COST(4,9),5+COST(4,10)=

29、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(2,3),3+COST(2,4),2+COST(2,5)=16S到到t的最小成本路径的成本的最小成本路径的成本 16 最小路径的求取最小路径的求取 记记 D(i,j)D(i

30、,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)=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

31、 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)=10 故由故由s s到到t t的的最小成本路径最小成本路径是：是：12710121271012 3)算法描述算法描述 结点的编号规则结点的编号规则 源点源点s s编号为编号为1 1,然后依次对然后依次对V V2 2、V V3 3VVk-1k-1中的结点编号，中的结点编号，汇点汇点t t编号为编号为n n。目的：使对目的：使对COSTCOST和和D D的计算仅按的计算仅按n-1,n

32、-2,1n-1,n-2,1的次序计的次序计算即可，算即可，无需考虑无需考虑标示结点所在标示结点所在段段的第一个下标。的第一个下标。算法描述算法描述算法算法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/计

33、算算COST(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算法的时间复杂度算法的时间复杂度 若若G采用邻接表表示，总计算时间为：采用邻接表表示，总计算时间为：3.向后处理策略求解向后处理策略求解 设设 BP(i,j)是一条从源点是一条从源点s到到Vi中的结点中的结点j的最小成本

34、路径，的最小成本路径，BCOST(i,j)是这条路径的成本。是这条路径的成本。1)向后递推式向后递推式 2)递推过程递推过程 第第2 2段段 c(1,j)EE BCOST(2,j)=12345678910111297324227111181456356425V1V2V3V4V55段图各递推结果各递推结果第第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,BCO

35、ST(2,5)+11=11 BCOST(3,8)=minBCOST(2,4)+11,BCOST(2,5)+8=10第第4段段 BCOST(4,9)=minBCOST(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 最小路径的求取最小路径的求取

36、 记记 BD(i,j)BD(i,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)的决策值的决策值向前向前递推求取最小成本路径：

37、递推求取最小成本路径：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 12345678910111265434227111181456356425V1V2V3V4V55段图算法算法4.2 多段图的向后处理算法多段图的向后处理算法 procedure BGRAPH(E,k,n,P)/输入

38、是按段的顺序给结点输入是按段的顺序给结点编号编号的，有的，有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 do/计算算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

39、 /找路径上的第找路径上的第j个个结点点/P(j)D(P(j+1)/回溯求出回溯求出该路径路径/repeat end BGRAPH4.多段图问题的应用实例多段图问题的应用实例 将将n个资源分配给个资源分配给r个项目的问题：如果把个项目的问题：如果把j个资源，个资源，0jnjn，分配给项目，分配给项目i i，可以获得，可以获得N(i,j)N(i,j)的净利。的净利。问题：如何将这问题：如何将这n个资源分配给个资源分配给r个项目才能获得最大可个项目才能获得最大可能的净利。转换成一个多段图问题。能的净利。转换成一个多段图问题。用用r1段图段图描述该问题：描述该问题：段段：1到到r之间的段之间的段i表

40、示项目表示项目i。结点结点：i=1时，只有一个结点时，只有一个结点源点源点s=V(1,0)V(1,0)当当2irir时，每段有时，每段有n+1n+1个结点，每个结点具有形式个结点，每个结点具有形式 V(i,j)V(i,j)：表示到项目表示到项目i i之前为止，共把之前为止，共把j j个资源分配给了个资源分配给了 项目项目1,2,i-11,2,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-

41、jl-j个资源所可能获得的净利。个资源所可能获得的净利。当当jnjn且且i=ri=r时，此时的边为：时，此时的边为：,该边赋该边赋 予成本：予成本：实例：将实例：将4个资源分配给个资源分配给3个项目。构成一个个项目。构成一个4段图。段图。问题的解：资源的最优分配方案是由问题的解：资源的最优分配方案是由s到到t的一条的一条最大成本最大成本的路径给出的路径给出改变边成本的改变边成本的符号符号，从而将问题转换成为求取最小成本路径问题。，从而将问题转换成为求取最小成本路径问题。4.3 每对结点之间的最短路径每对结点之间的最短路径1.问题描述问题描述 设设G=(V,E)是一个有是一个有n个结点的有向图，

42、个结点的有向图，C是是G的成本邻接矩阵，的成本邻接矩阵，C中元素有：中元素有：0 ，i j c(i,j)=边边的成本，的成本，ij且且E(G)，ij且且 其中，其中，1i，jn 每对结点之间的最短路径问题每对结点之间的最短路径问题：求满足下述条件的矩阵：求满足下述条件的矩阵A，A中的任一元素中的任一元素A(i,j)代表结点代表结点i到结点到结点j的的最短路径长度最短路径长度。分析：分析：n 利用利用单源最短路径单源最短路径算法求解算法求解 计算计算n个结点的单源最短路径。个结点的单源最短路径。时间复杂度：时间复杂度：(n(n3 3)n利用利用动态规划动态规划策略求解策略求解 将求解将求解G G

43、中每对结点之间的最短路径问题转化成一个中每对结点之间的最短路径问题转化成一个多多阶段决策过程阶段决策过程。决策什么？决策什么？最优性原理对于该问题是否成立？最优性原理对于该问题是否成立？2.动态规划求解策略动态规划求解策略1）最优性原理对于每对结点之间的最短路径问题成立最优性原理对于每对结点之间的最短路径问题成立 对对G的一条由的一条由i到到j的最短路径（假设该路径中不包含环），的最短路径（假设该路径中不包含环），设设k是该路径上的一个中间结点：是该路径上的一个中间结点：i,.,k,j 由由i到到k的最短路径的最短路径 k是中间结点是中间结点 由由k到到i的最短路径的最短路径 则，由则，由i到

44、到k和和k到到j的两条的两条子路径子路径将分别是由将分别是由i到到k和由和由k到到j的最短路径。否则的最短路径。否则i,.,k,j也将不是由也将不是由i到到j的最短路径。的最短路径。故，最优性原理对于该问题成立。故，最优性原理对于该问题成立。2）多阶段决策过程多阶段决策过程 设设k是由是由i到到j的最短路径上编号（假设所有的最短路径上编号（假设所有n个结点依次有从个结点依次有从1到到n的编号）最高的中间结点：的编号）最高的中间结点：i,.,k,j k是编号最高的中间结点是编号最高的中间结点 则由则由i到到k的子路径上将不会有比编号的子路径上将不会有比编号k-1更大的结点；同理，更大的结点；同理

45、，由由k到到i的子路径上也将不会有比编号的子路径上也将不会有比编号k-1更大的结点。更大的结点。构造构造多阶段决策过程多阶段决策过程：对由：对由i到到j的最短路径，首先决策哪一个的最短路径，首先决策哪一个结点是该路径上具有结点是该路径上具有最大编号最大编号的中间结点的中间结点k，然后再去求取由，然后再去求取由i到到k和由和由k到到j的最短路径的最短路径其中应不包含比其中应不包含比k-1还大的中间结点。还大的中间结点。3）递推关系式）递推关系式 记记Ak(i,j)表示从表示从i到到j并且不经过比并且不经过比k还大的结点的还大的结点的最短最短路径长度路径长度。则，。则，A(i,j)=An(i,j)

46、即，由即，由i到到j的最短路径不通过比编号的最短路径不通过比编号n还大的结点。还大的结点。注：该路径可以注：该路径可以经过经过结点结点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结点结点 对任意的对任意的k，k11，有，有，Ak(i,j)=minAk-1(i,j)，Ak-1(i,k)+Ak-1(

47、k,j)不经过结点不经过结点k 刚好经过结点刚好经过结点k 初值初值：A0(i,j)=C(i,j)，1inin，1jn1jn递推计算：递推计算：A1(i,j),A2(i,j),An(i,j)=A(i,j)3.算法描述算法描述算法算法4.3 每对结点之间的最短路径长度每对结点之间的最短路径长度 procedure ALL-PATHS(COST,A,n)/COST(n,n)是是n结点图的成本邻接矩阵；结点图的成本邻接矩阵；A(i,j)是结点是结点vi到到vj的最短路的最短路 径的成本；径的成本；COST(i,i)=0,1in/integer I,j,k,n;real COST(n,n),A(n,n

48、)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算法的设计说明算法的设计说明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(

49、i,k)+Ak-1(k,j)在算法的计算过程中取消了在算法的计算过程中取消了A A的上标，并保证了每次计算的上标，并保证了每次计算 的的 Ak(i,j)即为即为 minAk-1(i,j),Ak-1(i,k)+Ak-1(k,j)2）如何求每对结点之间的路径？）如何求每对结点之间的路径？例例4.8 有向图如图所示有向图如图所示A012310411260233 0A11231041126023370A2123104626023370A3123104625023370642 113v1v2v312310411260233 0求图中所有结点间的最短路径矩阵求图中所有结点间的最短路径矩阵A：注：注：A(i

50、,j)=表明表明G G中从中从i i到到j j没有有向路径没有有向路径性能分析性能分析 计算时间计算时间 注：该时间与注：该时间与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 的处理 设M是E中最大成本的一条边的成本，则An(i,j)(n-1)*M，则表明G中没有由i到j的有向路径。4.4 最优二分检索树最优二分检索树1.问题的描述问题的描述1）二分检索树定义）二分检索树定义 二