《算法设计与 第6章 动态规划法》由会员分享，可在线阅读，更多相关《算法设计与 第6章 动态规划法（53页珍藏版）》请在金锄头文库上搜索。
1、第六章 动态规划法,1,2,3,4,概述,图问题中的动态规划法,组合问题中的动态规划法,5,查找问题中的动态规划法,小结,五个海盗抢了一百颗钻石，每颗都价值连城。五个海盗都很贪婪，他们都希望自己能分得最多的钻石，但同时又都很明智。于是他们按照抽签的方法排出一个次序。首先由抽到一号签的海盗说出一套分钻石的方案，如果5个人中有50（或以上）的人同意，那么便依照这个方案执行，否则的话，这个提出方案的人将被扔到海里喂鱼，接下来再由抽到二号签的海盗继续说出一套方案，然后依次类推到第五个。记住，五个海盗都很聪明哦！,海盗分钻石问题,你想到了什么？,历史及研究问题,动态规划是运筹学的一个分支，20世纪50年
2、代初美国数学家Bellman等人在研究多阶段决策过程的优化问题时，提出了著名的最优性原理，创立了解决这类过程优化问题的新方法动态规划法。 多阶段决策问题：求解的问题可以划分为一系列相互联系的阶段，每个阶段都需要做出决策，而且一个阶段决策的选择会影响下一个阶段的决策，从而影响整个过程的活动路线，求解的目标是选择各个阶段的决策是整个过程达到最优。,动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划（如线性规划、非线性规划），可以人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。 动态规划是考察问题的一种途径，或是求解某类问题的一种方法。
3、动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比其它方法求解更为方便。,历史及研究问题,概 述多阶段决策过程,当某问题有n个输入，问题的解由这n个输入的一个子集组成，这个子集必须满足某些事先给定的条件，这些条件称为约束条件，满足约束条件的解称为问题的可行解。满足约束条件的可行解可能不只一个，为了衡量这些可行解的优劣，通常以函数的形式给出一定的标准，这些标准函数称为目标函数（或评价函数），使目标函数取得极值（极大或极小）的可行解称为最优解，这类问题称为最优化问题 。,概 述多阶段决策过
4、程,在0/1背包问题中，物品i或者被装入背包，或者不被装入背包，设xi表示物品i装入背包的情况，则当xi=0时，表示物品i没有被装入背包，xi=1时，表示物品i被装入背包。根据问题的要求，有如下约束条件和目标函数：,付款问题：超市的自动柜员机（POS机）要找给顾客数量最少的现金。 假定POS机中有n张面值为pi(1in)的货币，用集合P=p1, p2, , pn表示，若POS机需支付的现金为A，则必须从P中选取一个最小子集S，使得 （式6.1）,如果用向量X=( x1, x2, , xn)表示S中所选取的货币，则 （式6.2）,最优化问题,则，POS机支付的现金必须满足 （式6.3）,集合P是
5、该问题的输入，满足式6.1的解称为可行解，式6.2是解的表现形式，因向量X中有n个元素，每个元素的取值为0或1，所有这些向量的全体构成该问题的解空间，式6.3是该问题的约束条件，式6.4是该问题的目标函数，使式6.4取得极小值的解称为该问题的最优解。,并且 （式6.4）,最优化问题,最优性原理, 状态：表示每个阶段开始时，问题或系统所处的客观状况。状态既是该阶段的某个起点，又是前一个阶段的某个终点。通常一个阶段有若干个状态。 状态无后效性：如果某个阶段状态给定后，则该阶段以后过程的发展不受该阶段以前各阶段状态的影响，也就是说状态具有马尔科夫性。 适于动态规划法求解的问题具有状态的无后效性 策略
6、：各个阶段决策确定后，就组成了一个决策序列，该序列称之为一个策略。由某个阶段开始到终止阶段的过程称为子过程，其对应的某个策略称为子策略。,最优性原理,具有n个输入的最优化问题，其求解过程划分为若干个阶段，每一阶段的决策仅依赖于前一阶段的状态，由决策所采取的动作使状态发生转移，成为下一阶段决策的依据。 一个决策序列在不断变化的状态中产生。这个决策序列产生的过程称为多阶段决策过程。,最优性原理：无论决策过程的初始状态和初始决策如何，其余的决策都必须相对于初始决策所产生的当前状态，构成一个最优决策序列。 换言之，在多阶段决策中，各子问题的解只与它前面的子问题的解相关，而且各子问题的解都是相对于当前状
7、态的最优解，整个问题的最优解是由各个子问题的最优解构成。如果一个问题满足最优性原理通常称此问题具有最优子结构性质。,最优性原理,原问题E的解依赖于子问题C和D的解，子问题D的解依赖于子问题C和B的解，子问题C的解依赖于子问题A和B的解，子问题B的解依赖于子问题A的解，因此，动态规划的求解过程从初始子问题A开始，逐步求解并记录各子问题的解，直至得到原问题E的解。,最优性原理,最优性原理表明，一个最优问题的任何实例的最优解是由该实例的子实例的最优解组成。 一般来说，如果所求解问题对于最优性原理成立，则说明用动态规划方法有可能解决该问题。而解决问题的关键在于获取各阶段问的递推关系式。,最优性原理,动
8、态规划法的设计思想,动态规划法将待求解问题分解成若干个相互重叠的子问题，每个子问题对应决策过程的一个阶段，一般来说，子问题的重叠关系表现在对给定问题求解的递推关系（也就是动态规划函数）中，将子问题的解求解一次并填入表中，当需要再次求解此子问题时，可以通过查表获得该子问题的解而不用再次求解，从而避免了大量重复计算。为了达到这个目的，可以用一个表来记录所有已解决的子问题的解，这就是动态规划法的设计思想。具体的动态规划法是多种多样的，但他们具有相同的填表形式。,动态规划法的设计思想,（1）划分子问题：将原问题分解为若干个子问题，每个子问题对应一个决策阶段，并且子问题之间具有重叠关系； （2）确定动态
9、规划函数：根据子问题之间的重叠关系找到子问题满足的递推关系式（即动态规划函数），这是动态规划法的关键； （3）填写表格：设计表格，以自底向上的方式计算各个子问题的解并填表，实现动态规划过程。,动态规划法的求解过程,一个简单的例子数塔问题,问题描述：从数塔的顶层出发，在每一个结点可以选择向左走或向右走，一直走到最底层，要求找出一条路径，使得路径上的数值和最大。,数塔问题想法,数塔问题想法,求解初始子问题：底层的每个数字可以看作1层数塔，则最大数值和就是其自身； 再求解下一阶段的子问题：第4层的决策是在底层决策的基础上进行求解，可以看作4个2层数塔，对每个数塔进行求解； 再求解下一阶段的子问题：第
10、3层的决策是在第4层决策的基础上进行求解，可以看作3个2层的数塔，对每个数塔进行求解； 以此类推，直到最后一个阶段：第1层的决策结果就是数塔问题的整体最优解。,1. 初始化数组maxAdd的最后一行为数塔的底层数据： for (j = 0; j n; j+) maxAddn-1j = dn-1j; 2. 从第n-1层开始直到第 1 层对下三角元素maxAddij执行下述操作： 2.1 maxAddij = dij + maxmaxAddi+1j, maxAddi+1j+1； 2.2 如果选择下标j的元素，则pathij = j， 否则pathij = j+1； 3. 输出最大数值和maxAdd
11、00； 4. 根据path数组确定每一层决策的列下标，输出路径信息；,数塔问题算法,图问题中的动态规划法多段图最短路径,问题描述：设图G=(V, E)是一个带权有向图，如果把顶点集合V划分成k个互不相交的子集Vi (2kn, 1ik)，使得E中的任何一条边(u, v)，必有uVi，vVi+m (1ik, 1i+mk)，则称图G为多段图，称sV1为源点，tVk为终点。多段图的最短路径问题求从源点到终点的最小代价路径。,W先生每天驾车去公司上班。W先生的住所位于A，公司位于F，图中的直线段代表公路，交叉点代表路口，直线段上的数字代表两路口之间的平均行驶时间。现在W先生的问题是要确定一条最省时的上班
12、路线。,多段图最短路径实例,多段图最短路径想法,由于多段图将顶点划分为k个互不相交的子集，所以，可以将多段图划分为k段，每一段包含顶点的一个子集，根据多段图的定义，每个子集中的顶点互不邻接。不失一般性，将多段图的顶点按照段的顺序进行编号，同一段内顶点的顺序无关紧要。假设图中的顶点个数为n，则源点s的编号为0，终点t的编号为n-1，并且对图中的任何一条边，顶点u的编号小于顶点v的编号。,设cuv表示多段图的有向边上的权值，将从源点s到终点t的最短路径长度记为d(s, t)，考虑原问题的部分解d(s, v)，显然有下式成立： d(s, v) =csv （E） d(s, v) = mind(s, u
13、) + cuv （E）,证明多段图的最短路径问题满足最优性原理。,首先求解初始子问题，可直接获得： d(0, 1)=c014(01) d(0, 2)=c022(02) d(0, 3)=c033(03) 再求解下一个阶段的子问题，有： d(0, 4)=mind(0, 1)+c14, d(0, 2)+c24=min4+9, 2+6=8(24) d(0, 5)=mind(0, 1)+c15, d(0, 2)+c25, d(0, 3)+c35=min4+8, 2+7, 3+4 =7(35) d(0, 6)=mind(0, 2)+c26, d(0, 3)+c36=min2+8, 3+7=10(26) 再
14、求解下一个阶段的子问题，有： d(0, 7)=mind(0, 4)+c47, d(0, 5)+c57, d(0, 6)+c67=min8+5, 7+8, 10+6 =13(47) d(0, 8)=mind(0, 4)+c48, d(0, 5)+c58, d(0, 6)+c68=min8+6, 7+6, 10+5 =13(58) 直到最后一个阶段，有： d(0, 9)=mind(0, 7)+c79, d(0, 8)+c89=min13+7, 13+3=16(89) 再将状态进行回溯，得到最短路径03589，最短路径长度16。,多段图最短路径实例求解过程,多段图最短路径实例求解过程,多段图最短路径
15、问题的填表过程,算法6.2：多段图的最短路径问题 输入：多段图的代价矩阵 输出：最短路径长度及路径 1. 循环变量j从1n-1重复下述操作，执行填表工作： 1.1 考察顶点j的所有入边，对于边(i, j)E： 1.1.1 costj=mincosti+cij; 1.1.2 pathj=使costi+cij最小的i; 1.2 j+; 2. 输出最短路径长度costn-1; 3. 循环变量i=pathn-1，循环直到pathi=0： 3.1 输出pathi; 3.2 i=pathi;,多段图最短路径算法,图问题中的动态规划法 TSP问题,TSP问题是指旅行家要旅行n个城市,要求各个城市经历且仅经历一次然后回到出发城市，并要求所走的路程最短。,TSP问题 想法,TSP问题满足最优性原理。 对于图G=(V, E)，假设从顶点i出发，令V=V-i，则d(i, V)表示从顶点i出发经过V中各个顶点一次且仅一次，最后回到出发点i的最短路径长度， 显然，初始子问题是d(k, )，即从顶点i出发只经过顶点k回到顶点i。现在考虑原问题的一部分，d(k, V-k)表示从顶点k出发经过V-k中各个顶点一次且仅一次，最后回到出发点i的最短路径长度，则： d(k, )=cki d(i, V)=mincik + d(k, V-k)（kV）,首先计算初始子问题，可以直接获得：d(1,
