动态规划法

算法与算法复杂性王涛长春工业大学计算机科学与工程学院[e-mail]第六章动态规划法6.1概述6.2图问题中的动态规划法6.3组合问题中的动态规划法6.4查找问题中的动态规划法6.1概述6.1.1最优化问题6.1.2最优性原理6.1.3动态规划法的设计思想动态规划(Dynamicprogramming)是一种算法设计技术，是用来解决一种多段决策过程最优的通用方法。动态规划方法是一种对具有交叠子问题进行求解的技术。动态规划建议，对交叠子问题的每个较小子问题求解一次后记录在表中，就可以从表中得到原始问题的解。对一个最优问题应用动态规划方法要求该问题满足最优性原则：一个最优问题的任何实例的最优解是由该实例的子实例的最优解组成的。付款问题：超市的自动柜员机（POS机）要找给顾客数量最少的现金。例如，要找4元6角现金，如果POS机送出一大堆硬币，比如46个1角钱，就让人笑话了，而最好找2个2元、1个5角和1个1角。假定POS机中有n张面值为pi(1≤i≤n)的货币，用集合P={p1,p2,…,pn}表示，如果POS机需支付的现金为A，那么，它必须从P中选取一个最小子集S，使得（式6.1）miiiSmApSp1|)|(,如果用向量X=(x1,x2,…,xn)表示S中所选取的货币，则（式6.2）SpSpxiii016.1.1最优化问题那么，POS机支付的现金必须满足（式6.3）Apxniii1niixd1min集合P是该问题的输入，满足式6.1的解称为可行解，式6.2是解的表现形式，因为向量X中有n个元素，每个元素的取值为0或1，所以，可以有2n个不同的向量，所有这些向量的全体构成该问题的解空间，式6.3是该问题的约束条件，式6.4是该问题的目标函数，使式6.4取得极小值的解称为该问题的最优解。并且（式6.4）该问题有n个输入，它的解由这n个输入的一个子集组成，这个子集必须满足某些事先给定的条件，这些条件称为约束条件，满足约束条件的解称为问题的可行解。满足约束条件的可行解可能不只一个，为了衡量这些可行解的优劣，事先给出一定的标准，这些标准通常以函数的形式给出，这些标准函数称为目标函数，使目标函数取得极值（极大或极小）的可行解称为最优解，这类问题就称为最优化问题。6.1.2最优性原理对于一个具有n个输入的最优化问题，其求解过程往往可以划分为若干个阶段，每一阶段的决策仅依赖于前一阶段的状态，由决策所采取的动作使状态发生转移，成为下一阶段决策的依据。如图6.1所示，S0是初始状态，依据此状态作出决策P1，按照P1所采取的动作，使状态转换为S1，依据状态S1作出决策P2，按照P2所采取的动作，使状态S1转换为S2，……，经过一系列的决策和状态转换，到达最终状态Sn，从而，一个决策序列在不断变化的状态中产生。这个决策序列产生的过程称为多阶段决策过程。S0P1P2Pn图6.1多阶段决策过程S1S2Sn-1Sn例最优性原理（OptimalPrinciple）：无论决策过程的初始状态和初始决策是什么，其余的决策都必须相对于初始决策所产生的当前状态，构成一个最优决策序列。换言之，在多阶段决策中，各子问题的解只与它前面的子问题的解相关，而且各子问题的解都是相对于当前状态的最优解，整个问题的最优解是由各个子问题的最优解构成。如果一个问题满足最优性原理通常称此问题具有最优子结构性质。最优性原理无论过程的初始状态和初始决策是什么，其余的决策都必须相对于初始决策所产生的状态构成一个最优决策序列。原理告诉我们，一个最优问题的任何实例的最优解是由该实例的子实例的最优解组成。一般来说，如果所求解问题对于最优性原理成立，则说明用动态规划方法有可能解决该问题。而解决问题的关键在于获取各阶段问的递推关系式。6.1.3动态规划法的设计思想动态规划法将待求解问题分解成若干个相互重叠的子问题，每个子问题对应决策过程的一个阶段，一般来说，子问题的重叠关系表现在对给定问题求解的递推关系（也就是动态规划函数）中，将子问题的解求解一次并填入表中，当需要再次求解此子问题时，可以通过查表获得该子问题的解而不用再次求解，从而避免了大量重复计算。为了达到这个目的，可以用一个表来记录所有已解决的子问题的解，这就是动态规划法的设计思想。具体的动态规划法是多种多样的，但他们具有相同的填表形式。原问题的解原问题图6.3动态规划法的求解过程……填表子问题1子问题2子问题n划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。选择状态：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。确定决策并写出状态转移方程：状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。写出规划方程（包括边界条件）：动态规划的基本方程是规划方程的通用形式化表达式。动态规划算法的基本步骤可以用动态规划法求解的问题除了能够分解为相互重叠的若干子问题外，还要满足最优性原理（也称最优子结构性质），这类问题具有如下特征：该问题的最优解中也包含着其子问题的最优解。在分析问题是否满足最优性原理时，通常先假设由问题的最优解导出的子问题的解不是最优的，然后再设法说明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾。动态规划法利用问题的最优性原理，以自底向上的方式从子问题的最优解逐步构造出整个问题的最优解。应用动态规划法设计算法一般分成三个阶段：（1）分段：将原问题分解为若干个相互重叠的子问题；（2）分析：分析问题是否满足最优性原理，找出动态规划函数的递推式；（3）求解：利用递推式自底向上计算，实现动态规划过程。6.2图问题中的动态规划法6.2.1TSP问题6.2.2多段图的最短路径问题6.2.1TSP问题TSP问题是指旅行家要旅行n个城市，要求各个城市经历且仅经历一次然后回到出发城市，并要求所走的路程最短。各个城市间的距离可以用代价矩阵来表示，如果(i,j)E，则cij＝∞。573246325763)(ijcC假设从顶点i出发，令d(i,V')表示从顶点i出发经过V'中各个顶点一次且仅一次，最后回到出发点i的最短路径长度，开始时，V'＝V－{i}，于是，TSP问题的动态规划函数为：d(i,V')=min{cik+d(k,V－{k})}(k∈V')（式6.5）d(k,{})=cki(k≠i)（式6.6）从城市0出发，经城市1、2、3然后回到城市0的最短路径长度是：d(0,{1,2,3})=min{c01+d(1,{2,3}),c02+d(2,{1,3}),c03+d(3,{1,2})}这是最后一个阶段的决策，它必须依据d(1,{2,3})、d(2,{1,3})和d(3,{1,2})的计算结果，而：573246325763)(ijcCd(1,{2,3})=min{c12+d(2,{3}),c13+d(3,{2})}d(2,{1,3})=min{c21+d(1,{3}),c23+d(3,{1})}d(3,{1,2})=min{c31+d(1,{2}),c32+d(2,{1})}这一阶段的决策又依赖于下面的计算结果：d(1,{2})=c12+d(2,{})d(2,{3})=c23+d(3,{})d(3,{2})=c32+d(2,{})d(1,{3})=c13+d(3,{})d(2,{1})=c21+d(1,{})d(3,{1})=c31+d(1,{})而下式可以直接获得（括号中是该决策引起的状态转移）：d(1,{})=c10=5(1→0)d(2,{})=c20=6(2→0)d(3,{})=c30=3(3→0)再向前推导，有：d(1,{2})=c12+d(2,{})=2+6=8(1→2)d(1,{3})=c13+d(3,{})=3+3=6(1→3)d(2,{3})=c23+d(3,{})=2+3=5(2→3)d(2,{1})=c21+d(1,{})=4+5=9(2→1)d(3,{1})=c31+d(1,{})=7+5=12(3→1)d(3,{2})=c32+d(2,{})=5+6=11(3→2)再向推导，有：d(1,{2,3})=min{c12+d(2,{3}),c13+d(3,{2})}=min{2+5,3+11}=7(1→2)d(2,{1,3})=min{c21+d(1,{3}),c23+d(3,{1})}=min{4+6,2+12}=10(2→1)d(3,{1,2})=min{c31+d(1,{2}),c32+d(2,{1})}=min{7+8,5+9}=14(3→2)最后有：d(0,{1,2,3})=min{c01+d(1,{2,3}),c02+d(2,{1,3}),c03+d(3,{1,2})}=min{3+7,6+10,7+14}=10(0→1)从顶点0出发的TSP问题的最短路径长度为10，路径是0→1→2→3→0。假设对n个顶点分别用0～n-1的数字编号，考虑从顶点0出发求解TSP问题的填表形式。首先，按个数为1、2、…、n-1的顺序生成1～n-1个元素的子集存放在数组V[2n-1]中，例如当n=4时，V[1]={1},V[2]={2},V[3]={3},V[4]={1,2},V[5]={1,3},V[6]={2,3},V[7]={1,2,3}。设数组d[n][2n-1]存放迭代结果，其中d[i][j]表示从顶点i经过子集V[j]中的顶点一次且仅一次，最后回到出发点0的最短路径长度。首先，根据式6.6将数组d的第0列初始化，然后根据式6.5逐列计算，其填表过程如图所示。ji{}{1}{2}{3}{1,2}{1,3}{2,3}{1,2,3}0101586726951033121114图6.7动态规划法的填表过程设顶点之间的代价存放在数组c[n][n]中，动态规划法求解TSP问题的算法如下：算法6.1——TSP问题1．for(i=1;in;i++)//初始化第0列d[i][0]=c[i][0];2．for(j=1;j2n-1-1;j++)for(i=1;in;i++)//依次进行第i次迭代if(子集V[j]中不包含i)对V[j]中的每个元素k，计算d[i][j]=min(c[i][k]+d[k][j-1]);3．对V[2n-1-1]中的每一个元素k，计算d[0][2n-1-1]=min(c[0][k]+d[k][2n-1-2]);4．输出最短路径长度d[0][2n-1-1];算法6.1的时间复杂性为O(2n)。和蛮力法相比，动态规划法求解TSP问题，把原来的时间复杂性是O(n!)的排列问题，转化为组合问题，从而降低了算法的时间复杂性，但它仍需要指数时间。6.2.2多段图的最短路径问题设图G=(V,E)是一个带权有向连通图，如果把顶点集合V划分成k个互不相交的子集Vi（2≤k≤n,1≤i≤k），使得E中的任何一条边(u,v)，必有u∈Vi，v∈Vi+m（1≤i＜k,1＜i+m≤k），则称图G为多段图，称s∈V1为源点，t∈Vk为终点。多段图的最短路径问题是求从源点到终点的最小代价路径。由于多段图将顶点划分为k个互不相交的子集，所以，多段图划分为k段，每一段包含顶点的一个子集。根据多段图的定义，每个子集中的顶点互不邻接。不失一般性，将多段图的顶点按照段的顺序进行编号，同一段内顶点的相互顺序无关紧要。假设图中的顶点个数为n，则源点s的编号为0，终点t的编号为n-1，并且，对图中的任何一条边(u,v)，顶点u的编号小于顶点v的编号。2120345678949387684756866537图6.8一个多段图设G是一个有向加权图，则G从顶点i到顶点j之间的最短路径问题满足最优性原理。证明：设i～ip～iq～j是一条最短路径，但其中子路径ip～iq～j不是最优的，假设最优的路径为ip～iq’～j，则我们重新构造一条路径：i～ip～iq’～j显然该路径长度小于i～ip～iq～j，与i～ip～iq～j是顶点i到顶点j的最短路径相矛盾.所以，原问题满足最优性原理。对多段图的边