《算法设计与分析》第07章

1第七章动态规划7.1一般方法1.多阶段决策问题多阶段决策过程：问题的活动过程分为若干相互联系的阶段，任一阶段i以后的行为仅依赖于i阶段的过程状态，而与i阶段之前的过程如何达到这种状态的方式无关。在每一个阶段都要做出决策，这一系列的决策称为多阶段决策过程(multistepdecisionprocess)。最优化问题：问题的每一阶段可能有多种可供选择的决策，必须从中选择一种决策。各阶段的决策构成一个决策序列。决策序列不同，所导致的问题的结果可能不同。多阶段决策的最优化问题就是：求能够获得问题最优解的决策序列——最优决策序列。云图V1V2云图VN云图...22.多阶段决策过程的求解策略1）枚举法穷举可能的决策序列，从中选取可以获得最优解的决策序列2）动态规划20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理(principleofoptimality)，把多阶段过程转化为一系列单阶段问题，创立了解决这类过程优化问题的新方法——动态规划。动态规划(dynamicprogramming)是运筹学的一个分支，是求解决策过程(decisionprocess)最优化的数学方法。应用领域：动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。33.最优性原理(PrincipleofOptimality)过程的最优决策序列具有如下性质：无论过程的初始状态和初始决策是什么，其余的决策都必须相对于初始决策所产生的状态构成一个最优决策序列。利用动态规划求解问题的前提1)证明问题满足最优性原理如果对所求解问题证明满足最优性原理，则说明用动态规划方法有可能解决该问题2)获得问题状态的递推关系式获得各阶段间的递推关系式是解决问题的关键。4例7.1[多段图问题]多段图G=(V,E)是一个有向图，且具有特性:结点：结点集V被分成k≥2个不相交的集合Vi，1≤i≤k，其中V1和Vk分别只有一个结点s(源点)和t(汇点)。·每一集合Vi定义图中的一段。边：所有的边(u,v)均具有如下性质：若u,v∈E，则该边将是从某段i指向i+1段，即若u∈Vi，则v∈Vi＋1,1≤i≤k－1。才·每条边(u,v)均附有成本c(u,v)。s到t的路径：从第1段开始，至第2段、第3段、…、最后在第k段终止。路径的成本是这条路径上边的成本和。多段图问题：求由s到t的最小成本路径。512345678910111297324227111181456356425V1V2V3V4V55段图6多段图问题的多阶段决策过程：生成从s到t的最小成本路径是在k-2个阶段（除s和t外）进行某种决策的过程：从s开始，第i次决策决定Vi+1(1≤i≤k-2)中的哪个结点在从s到t的最短路径上。最优性原理对多段图问题成立假设s,v2,v3,…,vk-1,t是一条由s到t的最短路径。●初始状态：s●初始决策：(s,v2)，v2∈V2●初始决策产生的状态：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的路径。与假设矛盾。故，最优性原理成立7例7.2[0/1背包问题]KNAP(l,j,X)已知一个载重为M的背包和n件物品，物品编号从1到n。第i件物品的重量为wi，如果将第i种物品装入背包将获益pi，这里，wi0，pi0，0in。所谓0/1背包问题是指在物品不能分割，只能整件装入背包或不装入的情况下，求一种最佳装载方案使得总收益最大。8•例7.2[0/1背包问题]KNAP(l,j,X)目标函数：约束条件：0/1背包问题：KNAP(1,n,M)jiiixp1jiwpxXxwiiijiii1,0,0,101或9最优性原理对0/1背包问题成立：设y1,y2,…,yn是x1,x2,…,xn的0/1值最优序列。若y1＝0,KNAP(2,n,M)是初始决策产生的状态。则y2,…,yn相对于KNAP(2,n,M)将构成一个最优序列。否则，y1,y2,…,yn将不是KNAP(1,n,M)的最优解若y1＝1,KNAP(2,n,M－w1)是初始决策产生的状态。则y2,…,yn相对于KNAP(2,n,M－w1)将构成一个最优序列。否则，设存在另一0/1序列z1,z2,…,zn,使得且则序列y1,z2,…,zn将是一个对于KNAP(1,n,M)具有更大效益值的序列。故，最优性原理成立niiiwMzw21niniiiiiypzp22107.动态规划模型的基本要素一个多阶段决策过程最优化问题的动态规划模型通常包含以下要素：1)阶段阶段(step)是对整个过程的自然划分。通常根据时间顺序或空间特征来划分阶段，以便按阶段的次序解优化问题。阶段变量一般用k=1,2,..,n表示。12345678910111297324227111181456356425V1V2V3V4V55段图11例7.1[多段图问题]多段图G=(V,E)是一个有向图，且具有特性:结点：结点集V被分成k≥2个不相交的集合Vi，1≤i≤k，其中V1和Vk分别只有一个结点s(源点)和t(汇点)。·每一集合Vi定义图中的一段。边：所有的边(u,v)均具有如下性质：若u,v∈E，则该边将是从某段i指向i+1段，即若u∈Vi，则v∈Vi＋1,1≤i≤k－1。·每条边(u,v)均附有成本c(u,v)。s到t的路径：从第1段开始，至第2段、第3段、…、最后在第k段终止。路径的成本是这条路径上边的成本和。多段图问题：求由s到t的最小成本路径。1212345678910111297324227111181456356425V1V2V3V4V55段图132）状态状态(state)表示每个阶段开始时过程所处的自然状况。它应该能够描述过程的特征并且具有无后向性，即当某阶段的状态给定时，这个阶段以后过程的演变与该阶段以前各阶段的状态无关，即每个状态都是过去历史的一个完整总结。通常还要求状态是直接或间接可以观测的。描述状态的变量称状态变量(statevariable)。变量允许取值的范围称允许状态集合(setofadmissiblestates)。用xk表示第k阶段的状态变量，它可以是一个数或一个向量。用大写Xk表示第k阶段的允许状态集合。状态变量简称为状态143）决策当一个阶段的状态确定后，可以作出各种选择从而演变到下一阶段的某个状态，这种选择手段称为决策(decision)。描述决策的变量称决策变量(decisionvariable)。变量允许取值的范围称允许决策集合(setofadmissibledecisions)。用uk(xk)表示第k阶段处于状态xk时的决策变量，它是xk的函数，用Uk(xk)表示了xk的允许决策集合。决策变量简称决策。154）策略决策组成的序列称为策略(policy)。由初始状态x1开始的全过程（由1到n）的策略记作p1,n(x1)，即p1,n(x1)={u1(x1),u2(x2),...，un(xn)}。由第k阶段的状态xk开始到终止状态（由k到n）的后部子过程的策略记作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)有一定的范围，称为允许策略集合(setofadmissiblepolicies)，用P1,n(x1),Pk,n(xk),Pk,j(xk)表示。165)状态转移方程在确定性过程中，一旦某阶段的状态和决策为已知，下阶段的状态便完全确定。用状态转移方程(equationofstate)表示这种演变规律，写作176)指标函数和最优值函数指标函数(objectivefunction)是衡量过程优劣的数量指标，它是关于策略的数量函数，从阶段k到阶段n的指标函数用Vk,n(xk,pk,n(xk))表示，k=1,2,...,n。能够用动态规划解决的问题的指标函数应具有可分离性，即Vk,n可表为xk,uk,Vk+1,n的函数，记为：195.递推策略1）向前处理法列出根据xi+1,…,xn的最优决策序列求取xi决策值的关系式。从最后一个阶段，逐步向前递推求出各阶段的决策值。决策序列x1,x2,…,xn就是问题的最优解。xn-1,1…xn-1,pn-1xn202）向后处理法列出根据x1,…,xi-1的最优决策序列求取xi决策值的关系式。从第一个阶段，逐步向后递推求出各阶段的决策值。决策序列x1,x2,…,xn就是问题的最优解。21动态规划的基本思想：（1）动态规划方法的关键在于正确写出基本的递推关系式和恰当的边界条件。要做到这一点，必须将问题的过程分成几个相互联系的阶段，恰当选择状态变量，决策变量和定义最优值函数，从而把一个大问题化成一族同类型的子问题，然后逐个求解。即从边界条件开始，逐段递推寻优，在每一个子问题的求解中，均利用了它前面的子问题的最优化结果，依次进行，最后一个子问题的最优解，就是整个问题的最优解。（2）在多阶段决策过程中，动态规划方法是既把当前一段和未来各段分开，又把当前的效益和未来效益综合起来考虑的一种最优化方法。因此，每段决策的选取是从全局来考虑的，与该段的最优选择答案一般是不同的。（3）在求整个问题的最优策略时，由于初始状态是已知的，而每段的决策都是该段状态的函数，故最优策略所经的各段状态便可逐次变换得到，从而确定最优路线。22关于动态规划求解策略的进一步说明采用枚举法：若问题的决策序列由n次决策构成，而每次决策有p种选择，则可能的决策序列将有pn个。利用动态规划策略的求解过程中保存了所有子问题的最优解，而舍去了所有不能导致问题最优解的次优决策序列动态规划：可能有多项式的计算复杂度。23与非线性规划相比，动态规划的优点：（1）易于确定全局最优解。动态规划方法是一种逐步改善法，它把原问题化为一系列结构相似的最优化子问题，而每个子问题的变量个数比原问题少的多，约束集合也要简单得多。（2）能得到一族解，有利于分析结果（3）能利用经验，提高求解的效率。动态规划方法反映了过程逐段演变的前后联系，较之非线性规划与实际过程联系得更紧密。不足之处：（1）没有一个统一的标准模型可供应用。（2）应用的局限性。要求状态变量满足“无后效性”条件，不少实际问题在取其自然特征作为状态变量往往不能满足这条件。（3）在数值求解中，存在“维数障碍”。在计算机中，每递推一段，必须把前一段的最优值函数在相应的状态集合上的全部值存入内存中。当维数增大时，所需的内存量成指数倍增长。24例7.1[多段图问题]多段图G=(V,E)是一个有向图，且具有特性:结点：结点集V被分成k≥2个不相交的集合Vi，1≤i≤k，其中V1和Vk分别只有一个结点s(源点)和t(汇点)。·每一集合Vi定义图中的一段。边：所有的边(u,v)均具有如下性质：若u,v∈E，则该边将是从某段i指向i+1段，即若u∈Vi，则v∈Vi＋1,1≤i≤k－1。·每条边(u,v)均附有成本c(u,v)。s到t的路径：从第1段开始，至第2段、第3段、…、最后在第k段终止。路径的成本是这条路径上边的成本和。多段图问题：求由s到t的最小成本路径。257.2多段图问题1.问题的描述●在多段图中求从s到t的一条最小成本的路径，可以看作是在k-2个段作出某种决策的结果。●第i次决策决定Vi+1中的哪个结点在这条路径上，这里1≤i≤k-2；●最优性原理对多段图问题成立，因此用动态规划方法有可能找到s到t的最小成本路径。本节首先根据上节介绍