算法 第四章动态规划精.ppt

算法 第四章 动态规划2022/12/31第1页，本讲稿共120页第四章 动态规划4.1 一般方法一般方法1.多阶段决策问题多阶段决策问题 多阶段决策过程多阶段决策过程：问题的活动过程分为若干相互联系的阶段，任一阶段：问题的活动过程分为若干相互联系的阶段，任一阶段i以后的行为以后的行为仅依赖于仅依赖于i阶段的过程状态，而与阶段的过程状态，而与i阶段之前的过程如何达到这种状态的方式无关。在每一阶段之前的过程如何达到这种状态的方式无关。在每一个阶段都要做出决策，这一系列的决策称为多阶段决策过程个阶段都要做出决策，这一系列的决策称为多阶段决策过程(multistep decision process)。最优化问题最优化问题：问题的每一阶段可能有多种可供选择的决策，必须从中选择一种决策。：问题的每一阶段可能有多种可供选择的决策，必须从中选择一种决策。各阶段的决策构成一个决策序列。决策序列不同，所导致的问题的结果可能不同。各阶段的决策构成一个决策序列。决策序列不同，所导致的问题的结果可能不同。多阶段决策的最优化问题多阶段决策的最优化问题就是：求能够获得问题最优解的决策序列就是：求能够获得问题最优解的决策序列最优决策最优决策序列。序列。2022/12/32第2页，本讲稿共120页2.多阶段决策过程的求解策略多阶段决策过程的求解策略1）枚举法）枚举法 穷举穷举可能的决策序列，从中选取可以获得最优解的决策序列可能的决策序列，从中选取可以获得最优解的决策序列2）动态规划）动态规划 20世纪世纪50年代初美国数学家年代初美国数学家R.E.Bellman等人在研究多阶段决策过程的优等人在研究多阶段决策过程的优化问题时，提出了著名的化问题时，提出了著名的最优化原理最优化原理(principle of optimality)，把，把多阶段多阶段过程转过程转化为一系列化为一系列单阶段单阶段问题，创立了解决这类过程优化问题的新方法问题，创立了解决这类过程优化问题的新方法动态规划动态规划。动态规划动态规划(dynamic programming)是是运筹学运筹学的一个分支，是求解的一个分支，是求解决策过程决策过程(decision process)最优化的数学方法。最优化的数学方法。应用领域：动态规划问世以来，在经济管理、生产调度、工程技术和最优控应用领域：动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。排序、装载等问题，用动态规划方法比用其它方法求解更为方便。2022/12/33第3页，本讲稿共120页3.最优性原理最优性原理(Principle of Optimality)过程的过程的最优决策序列最优决策序列具有如下性质：无论过程的具有如下性质：无论过程的初始状态初始状态和和初始决初始决策策是什么，其余的决策都必须相对于初始决策所产生的状态构成一个最是什么，其余的决策都必须相对于初始决策所产生的状态构成一个最优决策序列。优决策序列。对于一个多阶段过程问题，上述最优决策是否存在依赖于该问题对于一个多阶段过程问题，上述最优决策是否存在依赖于该问题是否有是否有最优子结构性质最优子结构性质：原问题的最优解包含了其子问题的最优解。而：原问题的最优解包含了其子问题的最优解。而能否采用动态规划的方法还要看该问题的子问题是否具有重叠性质。问能否采用动态规划的方法还要看该问题的子问题是否具有重叠性质。问题的题的子结构性质和子问题重叠性质子结构性质和子问题重叠性质是采用动态规划算法的两个基本是采用动态规划算法的两个基本要素。要素。子问题重叠性质子问题重叠性质:在求解具有最优子结构的问题时，每次产生的子问题并不总是新问题，在求解具有最优子结构的问题时，每次产生的子问题并不总是新问题，有些问题被反复计算多次。有些问题被反复计算多次。2022/12/34第4页，本讲稿共120页 利用动态规划求解问题的前提利用动态规划求解问题的前提 1)证明问题满足最优性原理证明问题满足最优性原理 如果对所求解问题证明满足最优性原理，则说明如果对所求解问题证明满足最优性原理，则说明用动态规划方法有可能解决该问题用动态规划方法有可能解决该问题 2)获得问题状态的递推关系式获得问题状态的递推关系式 获得各阶段间的递推关系式是解决问题的关键。获得各阶段间的递推关系式是解决问题的关键。2022/12/35第5页，本讲稿共120页例例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)(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的的最小成本路径最小成本路径。2022/12/36第6页，本讲稿共120页12345678910111297324227111181456356425V1V2V3V4V55段图2022/12/37第7页，本讲稿共120页 多段图问题的多段图问题的多阶段决策过程多阶段决策过程：生成从：生成从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 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的路径。与假设矛盾。的路径。与假设矛盾。故，最优性原理成立故，最优性原理成立2022/12/38第8页，本讲稿共120页n例例4.20/1背包问题背包问题 KNAP(1,j,X)目标函数目标函数：约束条件约束条件：0/1背包问题：背包问题：KNAP(1,n,M)2022/12/39第9页，本讲稿共120页最优性原理对最优性原理对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)将构成一个最优序列。将构成一个最优序列。否则，设存在另一否则，设存在另一0/1序列序列z2,z3,zn,使得使得 且且 则序列则序列y1,z2,zn将是一个对于将是一个对于KNAP(1,n,M)具有更大效益值得具有更大效益值得序列。序列。故，最优性原理成立故，最优性原理成立2022/12/310第10页，本讲稿共120页4.动态规划模型的基本要素动态规划模型的基本要素一个多阶段决策过程最优化问题的动态规划模型通常包含以下要一个多阶段决策过程最优化问题的动态规划模型通常包含以下要素：素：1)阶段阶段 阶段阶段(step)是对整个过程的自然划分。通常根据时间顺序或是对整个过程的自然划分。通常根据时间顺序或空间特征来划分阶段，以便按阶段的次序解优化问题。阶段变量空间特征来划分阶段，以便按阶段的次序解优化问题。阶段变量一般用一般用k=1,2,.,n表示。表示。2022/12/311第11页，本讲稿共120页2）状态状态 状态状态(state)表示每个阶段开始时过程所处的自然状况。它应该能够描述表示每个阶段开始时过程所处的自然状况。它应该能够描述过程的特征并且具有过程的特征并且具有无后向性无后向性，即当某阶段的状态给定时，这个阶段以，即当某阶段的状态给定时，这个阶段以后过程的演变与该阶段以前各阶段的状态无关，即每个状态都是过去后过程的演变与该阶段以前各阶段的状态无关，即每个状态都是过去历史的一个完整总结。通常还要求状态是直接或间接可以观测的。历史的一个完整总结。通常还要求状态是直接或间接可以观测的。描述状态的变量称描述状态的变量称状态变量状态变量(state variable)。变量允许取值的范围。变量允许取值的范围称允许称允许状态集合状态集合(set of admissible states)。用。用xk表示第表示第k阶段的状阶段的状态变量，它可以是一个数或一个向量。用态变量，它可以是一个数或一个向量。用Xk表示第表示第k阶段的允许状态阶段的允许状态集合。集合。状态变量简称为状态状态变量简称为状态2022/12/312第12页，本讲稿共120页3）决策）决策 当一个阶段的状态确定后，可以作出各种选择从而演变到下一阶段当一个阶段的状态确定后，可以作出各种选择从而演变到下一阶段的某个状态，这种选择手段称为的某个状态，这种选择手段称为决策决策(decision)。描述决策的变量称决策变量描述决策的变量称决策变量(decision variable)。变量允许取。变量允许取值的范围称允许决策集合值的范围称允许决策集合(set of admissible decisions)。用。用uk(xk)表示第表示第k阶段处于状态阶段处于状态xk时的决策变量，它是时的决策变量，它是xk的函数，用的函数，用Uk(xk)表示了表示了xk的允许决策集合。的允许决策集合。决策变量简称决策。决策变量简称决策。2022/12/313第13页，本讲稿共120页4）策略）策略 决策组成的序列称为策略决策组成的序列称为策略(policy)。由初始状态。由初始状态x1开始的全开始的全过程的策略记作过程的策略记作p1n(x1)，即，即p1n(x1)=u1(x1),u2(x2),.，un(xn)。由第由第k阶段的状态阶段的状态xk开始到终止状态的后部子过程的策略记作开始到终止状态的后部子过程的策略记作pkn(xk)，即，即pkn(xk)=uk(xk),uk+1(xk+1),.，un(xn)。类似地，。类似地，由第由第k到第到第j阶段的子过程的策略记作阶段的子过程的策略记作 pkj(xk)=uk(xk),uk+1(xk+1),.，uj(xj)。对于每一个阶段对于每一个阶段k的某一给定的状态的某一给定的状态xk，可供选择的策略，可供选择的策略pkj(xk)有有一定的范围，称为允许策略集合一定的范围，称为允许策略集合(set of admissible policies)，用用P1n(x1),Pkn(xk),Pkj(xk)表示。表示。2022/12/314第14页，本讲稿共120页5)状态转移方程状态转移方程 在确定性过程中，一旦某阶段的状态和决策为已知，下阶段的在确定性过程中，一旦某阶段的状态和决策为已知，下阶段的状态便完全确定。用状态转移方程状态便完全确定。用状态转移方程(equation of state)表示这种表示这种演变规律，写作演变规律，写作2022/12/315第15页，本讲稿共120页6)指标函数和最优值函数指标函数和最优值函数 指标函数指标函数(objective function)是衡量过程优劣的数量是衡量过程优劣的数量指标，它是关于策略的数量函数，从阶段指标，它是关于策略的数量函数，从阶段k到阶段到阶段n的指标的指标函数用函数用Vkn(xk,pkn(xk)表示，表示，k=1,2,.,n。能够用动态规划解决的问题的指标函数应具有可分离能够用动态规划解决的问题的指标函数应具有可分离性，即性，即Vkn可表为可表为xk,uk,Vk+1 n 的函数，记为：的函数，记为：2022/12/316第16页，本讲稿共120页7.最优策略和最优轨线最优策略和最优轨线 使指标函数使指标函数Vkn达到最优值的策略是从达到最优值的策略是从k开始的后部子过程的最优开始的后部子过程的最优策略，记作策略，记作pkn*=uk*,.un*,p1n*又是全过程的最优策略，简称最又是全过程的最优策略，简称最优策略优策略(optimal policy)。从初始状态。从初始状态x1(=x1*)出发，过程按照出发，过程按照p1n*和状态转移方程演变所经历的状态序列和状态转移方程演变所经历的状态序列x1*,x2*,.,xn+1*称最优称最优轨线轨线(optimal trajectory)。2022/12/317第17页，本讲稿共120页4.最优决策序列的表示最优决策序列的表示 设设 S0：问题的初始状态：问题的初始状态 n次决策：问题需要做次决策：问题需要做n次决策次决策 xi：i阶段的决策值，阶段的决策值，1inin。设设X X1 1=r=r1,11,1,r,r1,21,2,r,r1,p11,p1 是是x x1 1可能的决策值的集合，可能的决策值的集合，S S1,j11,j1是在选择决策是在选择决策值值r r1,j11,j1之后所产生的状态之后所产生的状态初始决策所产生的状态初始决策所产生的状态。设设1,j11,j1是相应于状态是相应于状态S S1,j11,j1的最优决策序列的最优决策序列。则，相应于则，相应于S S0 0的最优决策序列就是的最优决策序列就是rr1,j11,j11,j11,j1|1j|1j1 1pp1 1 中最优的序列，记中最优的序列，记为为 2022/12/318第18页，本讲稿共120页s0r1,1r1,2.r1,p1sn1,j12022/12/319第19页，本讲稿共120页 若已经做了若已经做了k-1k-1次决策，次决策，1k-11k-1n n，设，设x x1 1,x,x2 2,x,xk-1k-1的最优决策值是的最优决策值是r r1 1,r,r2 2,r,rk-1k-1，所产生的状态依次为，所产生的状态依次为S S1 1,S,S2 2,S,Sk-1k-1。设设X Xk k=r=rk,1k,1,r,rk,2k,2,r,rk,pkk,pk 是是x xk k可能的决策值的集合，可能的决策值的集合，S Sk,jkk,jk是在选择决策是在选择决策值值r rk,jkk,jk之后所产生的状态之后所产生的状态,1j,1jk kppk k。k,jkk,jk是相应于状态是相应于状态S Sk,jkk,jk的最优决的最优决策序列。策序列。则，相应于则，相应于S Sk-1k-1的最优决策序列是的最优决策序列是 相应于相应于S S0 0的最优决策序列为的最优决策序列为r r1 1,r,rk-1k-1，r rk k,k k2022/12/320第20页，本讲稿共120页5.递推策略递推策略1）向前处理法）向前处理法 列出根据列出根据xi+1,xn的最优决策序列求取的最优决策序列求取xi决策决策值的关系式。值的关系式。从最后一个阶段，逐步从最后一个阶段，逐步向前向前递推求出各阶段的递推求出各阶段的决策值。决策序列决策值。决策序列x1,x2,xn就是问题的最优解。就是问题的最优解。xn-1,1xn-1,pn-1xn2022/12/321第21页，本讲稿共120页 例例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)=-X02022/12/322第22页，本讲稿共120页 例例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的最短路径将是：的最短路径将是：min(|Vi+1,1ji+1pi+1)2022/12/323第23页，本讲稿共120页2）向后处理法向后处理法 列出根据列出根据x1,xi-1的最优决策序列求取的最优决策序列求取xi决策决策值的关系式。值的关系式。从第一个阶段，逐步从第一个阶段，逐步向后向后递推求出各阶段的递推求出各阶段的决策值。决策序列决策值。决策序列x1,x2,xn就是问题的最优解。就是问题的最优解。2022/12/324第24页，本讲稿共120页 例例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)=-X02022/12/325第25页，本讲稿共120页 例例4.6 k段图问题（向后处理策略）段图问题（向后处理策略）设设 Vk-1，1jk-1pk-1，|Vk-1|=pk-1;是由是由s到到 的最短路径，的最短路径，则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)2022/12/326第26页，本讲稿共120页关于动态规划求解策略的进一步说明关于动态规划求解策略的进一步说明n采用枚举法：若问题的决策序列由采用枚举法：若问题的决策序列由n次决策构成，而每次决策有次决策构成，而每次决策有p种选择，则可能的决策序列将有种选择，则可能的决策序列将有pn个。个。n利用动态规划策略的求解过程中保存了所有子问题的最优解，利用动态规划策略的求解过程中保存了所有子问题的最优解，而舍去了所有不能导致问题最优解的次优决策序列而舍去了所有不能导致问题最优解的次优决策序列n动态规划：可能有动态规划：可能有多项式多项式的计算复杂度。的计算复杂度。2022/12/327第27页，本讲稿共120页4.2 多段图问题1.问题的描述问题的描述 在多段图中求从在多段图中求从s到到t的一条最小成本的路径，可以看的一条最小成本的路径，可以看 作是在作是在k-2个段作出某种决策的结果。个段作出某种决策的结果。第第i次决策决定次决策决定Vi+1中的哪个结点在这条路径上，这里中的哪个结点在这条路径上，这里 1ik-2ik-2；最优性原理对多段图问题成立最优性原理对多段图问题成立2022/12/328第28页，本讲稿共120页2.向前处理策略求解向前处理策略求解 设设 P(i,j)是一条从是一条从Vi中的结点中的结点j到汇点到汇点t的最小成本路径，的最小成本路径，COST(i,j)是这条路径的成本。是这条路径的成本。1)向前递推式向前递推式 i表示表示Vi，j表示表示Vi中的结点号中的结点号2)递推过程递推过程 第第k-1k-1段段 c(j,t)EE COST(k-1,j)=2022/12/329第29页，本讲稿共120页l1l2.lpi+1tjViVi+12022/12/330第30页，本讲稿共120页12345678910111297324227111181456356425V1V2V3V4V55段图2022/12/331第31页，本讲稿共120页各递推结果各递推结果第第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)=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的最小成本路径的成本的最小成本路径的成本 162022/12/332第32页，本讲稿共120页 最小路径的求取最小路径的求取 记记 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,6)=10,D(3,7)=10，D(3,8)=10D(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 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 2022/12/333第33页，本讲稿共120页3)算法描述算法描述 结点的编号规则结点的编号规则 源点源点s s编号为编号为1 1,然后依次对然后依次对V V2 2、V V3 3VVk-1k-1中的结点编号，汇点中的结点编号，汇点t t编编号为号为n n。目的：使对目的：使对COSTCOST和和D D的计算仅按的计算仅按n-1,n-2,1n-1,n-2,1的次序计算即可，的次序计算即可，无需考虑无需考虑标示结点所在标示结点所在段段的第一个下标。的第一个下标。算法描述算法描述2022/12/334第34页，本讲稿共120页算法算法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/计算算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 FGRAPH2022/12/335第35页，本讲稿共120页算法的时间复杂度算法的时间复杂度 若若G采用邻接表表示，总计算时间为：采用邻接表表示，总计算时间为：2022/12/336第36页，本讲稿共120页3.向后处理策略求解向后处理策略求解 设设 BP(i,j)是一条从源点是一条从源点s到到Vi中的结点中的结点j的最小成本路径，的最小成本路径，BCOST(i,j)是这条路径的成本。是这条路径的成本。1)向后递推式向后递推式 2)递推过程递推过程 第第2 2段段 c(1,j)E COST(2,j)=2022/12/337第37页，本讲稿共120页12345678910111297324227111181456356425V1V2V3V4V55段图2022/12/338第38页，本讲稿共120页各递推结果各递推结果第第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)=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的最小成本路径的成本的最小成本路径的成本 162022/12/339第39页，本讲稿共120页 最小路径的求取最小路径的求取 记记 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)的决策值的决策值向前向前递推求取最小成本路径：递推求取最小成本路径：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 2022/12/340第40页，本讲稿共120页算法算法4.2 多段图的向后处理算法多段图的向后处理算法 procedure BGRAPH(E,k,n,P)/输入是按段的顺序给结点输入是按段的顺序给结点编号编号的，有的，有n个结点的个结点的k段图。段图。E是边是边 集，集，c(i,j)是边是边的成本。的成本。P(1:k)是最小成本路径是最小成本路径/real BCOST(n);integer D(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)D(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 BGRAPH2022/12/341第41页，本讲稿共120页4.多段图问题的应用实例多段图问题的应用实例 将将n个资源分配给个资源分配给r个项目的问题：如果把个项目的问题：如果把j个资源，个资源，0jnjn，分，分配给项目配给项目i i，可以获得，可以获得N(i,j)N(i,j)的净利。的净利。问题：如何将这问题：如何将这n个资源分配给个资源分配给r个项目才能获得最大可能的个项目才能获得最大可能的净利。转换成一个多段图问题。净利。转换成一个多段图问题。2022/12/342第42页，本讲稿共120页 用用r1段图段图描述该问题：描述该问题：段段：1到到r之间的段之间的段i表示项目表示项目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-jl-j个资源所可能获得的净利个资源所可能获得的净利。当当jnjn且且i=ri=r时，此时的边为：时，此时的边为：,该边赋该边赋 予成本：予成本：2022/12/343第43页，本讲稿共120页实例：将实例：将4个资源分配给个资源分配给3个项目。构成一个个项目。构成一个4段图。段图。问题的解：资源的最优分配方案是由问题的解：资源的最优分配方案是由s到到t的一条的一条最大成本最大成本的路径给出的路径给出改变边成改变边成本的本的符号符号，从而将问题转换成为求取最小成本路径问题。，从而将问题转换成为求取最小成本路径问题。2022/12/344第44页，本讲稿共120页4.3 每对结点之间的最短路径每对结点之间的最短路径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的的最短路径长度最短路径长度。2022/12/345第45页，本讲稿共120页分析：分析：n 利用利用单源最短路径单源最短路径算法求解算法求解 计算计算n个结点的单源最短路径。个结点的单源最短路径。时间复杂度：时间复杂度：(n(n3 3)n利用利用动态规划动态规划策略求解策略求解 将求解将求解G G中每对结点之间的最短路径问题转化成一个中每对结点之间的最短路径问题转化成一个多阶段多阶段决策过程决策过程。决策什么？决策什么？最优性原理对于该问题是否成立？最优性原理对于该问题是否成立？2022/12/346第46页，本讲稿共120页2.动态规划求解策略动态规划求解策略1）最优性原理对于每对结点之间的最短路径问题成立最优性原理对于每对结点之间的最短路径问题成立 对对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的最短路径。的最短路径。故，最优性原理对于该问题成立。故，最优性原理对于该问题成立。2022/12/347第47页，本讲稿共120页2）多阶段决策过程多阶段决策过程 设设k是由是由i到到j的最短路径上编号（假设所有的最短路径上编号（假设所有n个结点依次有从个结点依次有从1到到n的编的编号）最高的中间结点：号）最高的中间结点：i,.,k,j k是编号最高的中间结点是编号最高的中间结点 则由则由i到到k的子路径上将不会有比编号的子路径上将不会有比编号k-1更大的结点；同理，由更大的结点；同理，由k到到j的子的子路径上也将不会有比编号路径上也将不会有比编号k-1更大的结点。更大的结点。构造构造多阶段决策过程多阶段决策过程：对由：对由i到到j的最短路径，首先决策哪一个结点是该路的最短路径，首先决策哪一个结点是该路径上具有径上具有最大编号最大编号的中间结点的中间结点k，然后再去求取由，然后再去求取由i到到k和由和由k到到j的最短的最短路径路径其中应不包含比其中应不包含比k-1还大的中间结点。还大的中间结点。2022/12/348第48页，本讲稿共120页3）递推关系式）递推关系式 记记Ak(i,j)表示从表示从i到到j并且不经过比并且不经过比k还大的结点的最短路径长度。还大的结点的最短路径长度。则，则，A(i,j)=An(i,j)即，即，由由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结点结点2022/12/349第49页，本讲稿共120页 对任意的对任意的k，k11，有，有，Ak(i,j)=minAk-1(i,j)，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)2022/12/350第50页，本讲稿共120页3.算