算法201506-动态规划

算法分析与设计动态规划DynamicProgramming动态规划DynamicProgramming动态规划的基本思想多段图问题矩阵链乘积最长公共子序列0/1背包问题流水作业调度问题旅行售货员问题在实际生活中，有这么一类问题，它们的活动过程可以分为若干个阶段，而且在任一阶段后的行为都依赖于第i阶段的过程状态，而与第i阶段之前的过程是如何达到这个状态的方式无关，这样的过程就构成了一个多阶段决策过程。根据问题的多阶段决策的特性，R.E.Bellman等提出了解决这类问题的“最优化原理”，从而创建了最优化问题的一种新的算法设计方法——动态规划。动态规划的基本思想1,3,21021FFnFFFnnn动态规划是运筹学（OperationalResearch）的一个分支，是求解决策过程(DecisionProcess)最优化(Optimization)的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistepdecisionprocess)的优化问题时，提出了著名的最优化原理(PrincipleofOptimality)，将多阶段决策过程转化为一系列的单阶段决策问题，并创立了解决这类过程优化问题的新方法—动态规划，于1957年出版了他的名著《DynamicProgramming》，是该领域的第一本著作。在多阶段决策过程的每一个阶段，都可能有多种选择的决策，但必须从中选取一种决策。一旦各种阶段的决策选定之后，就构成了解决这一问题的一个决策序列。决策序列不同，导致的问题结果也不同。动态规划的目标就是要在所有容许选择的决策序列中选取一个会获得问题（整体）最优解的决策序列，即最优决策序列。动态规划的基本思想动态规划算法常用于求解这样一类问题：问题的解可以表示成一个解向量(x1,x2,…,xn)(n2)，算法分为n步进行，每一步确定解向量中一个分量的取值。动态规划算法的基本思想是：每一步都列出各种可能的局部解，然后通过计算，舍去那些不满足约束条件的局部解和那些已经肯定不可能发展成为全局最优解的局部解。在此基础上，对存留的局部解考察下一步(下一个分量)的取值。动态规划算法求解问题的类型向前/向后处理法向前处理方法(forwardapproach)从最后阶段开始，以逐步向前递推的方式列出求前一阶段决策值的递推关系式，即根据xi+1,…,xn的那些最优决策序列来列出求取xi决策值的关系式，这就是动态规划的向前处理法。列出关系式后，由最后阶段开始，回溯求解这些关系式得出最优决策序列。由该决策序列所得到的结果就是问题的最优解。向后处理方法(backwardapproach)就是从初始阶段开始，以逐步向后递推的方式列出求后一阶段决策值的递推关系式，即根据x1,…,xi-1的那些最优决策序列列出求xi的递推关系式。多段图问题多段图问题123458761110912st97324227111118654356524V1V2V3V4V5多段图问题多段图G＝(V,E)是—个有向图。它具有如下特性：图中的结点被划分成k≥2个不相交的集合Vi,1≤i≤k,其中V1和Vk分别只有一个结点s(源点)和t(汇点)。图中所有的边u,v均具有如下性质：若u∈Vi，则v∈Vi+1,1≤i≤k,且每条边u,v均附有成本c(u,v)。从s到t的一条路径成本是这条路径上边的成本和。多段图问题(multistagegraphproblem)是求由s到t的最小成本路径。123458761110912st97324227111118654356524V1V2V3V4V5游戏的多段图描述玩游戏的过程本质为一个多阶段决策过程，即玩家目前所采取的操作（决策）影响以后的游戏状态以及决策，玩家经过多个决策过程成才可将游戏玩完通关。游戏可描述为多段图（并且游戏多为关卡回合制）即游戏关卡的拓扑结构可以用多段图来表示。从而可以利用多段图来描述游戏的某些性质。游戏好玩度为游戏性质之一，因此，可以用多段图理论对此游戏性质进行量化评价，并且可用多段图理论指导游戏关卡设计.•可以使用多段图的路径总数来度量游戏好玩度，路径总数越多则玩法越多，则玩家越认为好玩。•最长路径代表游戏最长通关时间，因此若发现最长路径太长，玩家会厌倦，则调整边，使之适合。•若出现环，则游戏无法结束，则为游戏设计的失败。•最短路径代表游戏的最短通关时间，若路径太短，则代表游戏有Bug，使玩家进入无敌状态，游戏很快被玩完，则为游戏设计失败。流水装配线多段图问题的最优化原理证明证明最优化原理对多段图成立：假设s,v2,v3,…,vk-1,t是一条由s到t的最短路径再假设从源点s开始，已作出了到结点v2的决策，因此v2就是初始决策所产生的状态如果把v2看成是原问题的一个子问题的初始状态，解决这个子问题就是找出一条由v2到t的最短路径这条最短路径显然是v2,v3,…,vk-1,t如果不是，设v2,q3,…,qk-1,t由v2到t的一条更短路径，则s,v2,q3,…,qk-1,t是一条比路径s,v2,v3,…,vk-1,t更短的由s到t的路径。这与假设矛盾，因此最优性原理成立。求解多段图问题的动态规划算法多段图向前处理的算法设P(i,j)是一条从Vi中的节点j到汇点t的最小成本路径，COST(i,j)表示这条路径的成本，根据向前处理方法有:首先根据前面介绍的向前处理法列出求取s到t的最小成本路径的递推式。123458761110912st97324227111118654356524V1V2V3V4V5)},1(),({min)ji,(,1liCOSTljcCOSTEljVli边的成本若j,t∈E成立,有COST(k-1,j)=c(j,t),若j,t∈E不成立，则有COST(k-1,j)=∞，所以可以通过如下步骤解式公式（5-1），并最终求出COST(1,s)。首先对于所有j∈Vk-2，计算COST(k-2,j)，然后对所有的j∈Vk-3，计算COST(k-3,j)等等，最后计算出COST(1,s)多段图的向前处理算法123458761110912st97324227111118654356524V1V2V3V4V5例子中5段图的实现计算步骤：•COST(4,9)=4•COST(4,10)=2•COST(4,11)=5COST(3,6)=min{6+COST(4,9),5+COST(4,10)}=7COST(3,7)=min{4+COST(4,9),3+COST(4,10)}=5COST(3,8)=min{5+COST(4,10),6+COST(4,11)}=7123458761110912st97324227111118654356524V1V2V3V4V5123458761110912st97324227111118654356524V1V2V3V4V5COST(2,2)=min{4+COST(3,6),2+COST(3,7),1+COST(3,8)}=7COST(2,3)=min{2+COST(3,6),7+COST(3,7)}=9COST(2,4)=min{11+COST(3,8)}=18COST(2,5)=min{11+COST(3,7),8+COST(3,8)}=15COST(1,1)=min{9+COST(2,2),7+COST(2,3),3+COST(2,4),2+COST(2,5)}=16123458761110912st97324227111118654356524V1V2V3V4V5例子中5段图的计算步骤：在计算每一个COST(i,j)的同时，记下每个状态(结点j)所做出的决策（即，使c(j,l)+cost(i+1,l)取最小值的l值），设它为D(i,j)，则可容易地求出这条最小成本路径。D(3,6)=10D(3,7)=10D(3,8)=10D(2,2)=7D(2,3)=6D(2,4)=8D(2,5)=8D(1,1)=2123458761110912st97324227111118654356524V1V2V3V4V5设这条最小成本路径是s＝l,v2,v3,…,vk-1,t=12。则可得知：v2＝D(1,1)＝2，v3=D(2,D(1,1))=D(2,2)=7和v4＝D(3,D(2,D(1,1)))＝D(3,D(2,2))=D(3,7)＝10所以最短路径的结点序列为：s-2-7-10-t。123458761110912st97324227111118654356524V1V2V3V4V5多段图的向前处理算法为了使写出的算法更简单一些，可事先对结点集V的结点按下述方式排序：首先将s结点编成1号，然后对V2中的结点编号，V3的结点接着V2中的最后一个编号继续往下编……最后将t编成n号。经过这样编号，Vi+1中结点的编号Vi均大于中结点的编号。于是，COST和D都可按n-1,n-2,……,1的次序计算，而无需考虑COST、P和D中标识结点所在段数的第一下标，因此它们的第一下标可在算法中略去。多段图的向前处理算法LineprocedureFGRAP(E,k,n,P)realCOST(n),integerD(n-1),P(k),r,j,k,nCOST(n)0forjn-1to1by–1do设r是一个这样的结点,j,r∈E且使c(j,r)+COST(r)取小值COST(j)c(j,r)+COST(r)D(j)rrepeatP(1)1;P(k)nforj2tok-1doP(j)D(P(j-1))repeatEndFGRAPH计算出COST(j)的值，并找出一条最小成本路径找出最小成本路径上的第j个结点123458761110912st97324227111118654356524V1V2V3V4V5n=12,k=5;COST(n)=COST(12)=0；执行For循环，计算出各COST(j)的值：j=n-1=11,COST(11)=5,D(11)=12;j=n-2=10,COST(10)=2,D(10)=12;j=n-3=9,COST(9)=4,D(9)=12;j=n-4=8,COST(8)=7,D(8)=10;j=n-5=7,COST(7)=5,D(7)=10;j=n-6=6,COST(6)=7,D(6)=10;j=n-7=5,COST(5)=15,D(5)=8;123458761110912st97324227111118654356524V1V2V3V4V5j=n-8=4,COST(4)=18,D(4)=8;j=n-9=3,COST(3)=9,D(3)=6;j=n-10=2,COST(2)=7,D(2)=7;j=n-11=1,COST(1)=16,D(1)=2;找出最小成本路径上的各个结点编号：P(1)=1;P(k)=P(5)=n=12;执行For循环，求出各P(j)的值：P(2)=D(P(1))=D(1)=2;P(3)=D(P(2))=D(2)=7;P(4)=D(P(3))=D(7)=10;最小成本路径上的各个结点编号为：P(1:5)={1，2，7，10，12}。多段图的向后处理算法向后处理方法(backwardapproach)就是根据x1,…,xi-1的那些最优决策序列列出求xi的递推关系式。123458761110912st97324227111118654356524V1V2V3V4V5多段图的向后处理算法设BP(i,j)是一条由源点s到Vi中结点j的最小成本路径，BCOST(i,j)表示BP(i,j)的成本，由向后处理方法得到（5-2）：即由源点s到Vi中结点j的最小成本，等于由源点s到Vi-1中任一结点l的最小成本加上Vi-1中结点l到Vi中结点j的边长,所得的所有和中最小的那个值。)},(),1({min)ji,(,l1jlcliBCOSTBCOSTEjVli因为，若