【精品】K-动态规划教案

《【精品】K-动态规划教案》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、动态规划策略动态规划(dynamicprogramming)是运筹学的一个分支，是求解决策过程(decisionprocess)最优化的数学方法。20世纪50年代初美国数学家R.E.Bollman等人在研究多阶段决策过程(multistepdecisionprocess)的优化问题时，提出了著名的最优化原理(principleofoptimality),把多阶段过程转化为一系列单阶段问题，逐个求解，创立了解决这类过程优化问题的新方法一一动态规划。1957年出版了他的名著DynamicProgramming,这是该领域的第一本著作。动态规划问世以来，在经济管理、生产调度、工程技术

2、和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划(如线性规划、非线性规划)，只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。第一节动态规划的本质一、多阶段决策过程的最优化问题在现实生活屮，有一类活动的过程，由于它的特殊性，可将过程分成若干个互相联系的阶段，在它的每一阶段都需要作出决策，从而使整个过程达到最好的活动效果。因此各个阶段决策的选取不能任意确定，它依赖于当前面临的状

3、态，又影响以后的发展。当各个阶段决策确定后，就组成一个决策序列，因而也就确定了整个过程的一条活动路线。这种把一个问题看作是一个前后关联具有链状结构的多阶段过程(如图)就称为多阶段决策过程，这种问题称为多阶段决策问题。阶段1阶段2决策冬A阶段n在多阶段决策问题中，各个阶段采取的决策，一般来说是与时间有关的，决策依赖于当前状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，故有〃动态〃的含义，我们称这种解决多阶段决策最优化的过程为动态规划方法。应指出，动态规划是考察求解多阶段决策问题的一种途径、一种方法，而不是一种特殊算法。不像线性规划那样，具有一个标准的数学表达

4、式和明确定义的一组规划。因此我们在学习时，除了要对基本概念和方法正确理解外，必须具体问题具体分析处理，以丰富的想象力去建立模型，用创造性的技巧去求解。例如：图中给出了一个地图，地图中每个顶点代表一个城市，两个城市间的连线代表道路，连线上的数值代表道路的长度。现在，我们想从城市A到达城市E,怎样走路程最短，最短路程的长度是多少？解法一：用搜索法对A->E可能的每一条路线进行枚举，把距离算出来，然后互相比较,找出最短者。设Dis[X]为城市X到E的最短路线的长度；(X表示任意一个城市)Map[I,J]表示I,J两个城市间的距离,若Ma讥I,J]二0,则两个城市不连通。算法描述Pro

5、gramli_l;VarSe:未访问的城市集合；FunctionLong(Who:当前访问城市):Integer;{求当前访问城市与城市E的最短距离}BeginIfWho=EThenSearch:=0ElseBeginMin:=Maxint;ForI取遍所有城市DoIf(Map[Who,I]>0)And(IInSe)ThenBeginSe:=Se-[I];J:=Map[Who,I]+Long(I);Se:=Se+[I];IfJ

6、);End.解法分析：这个程序的时间复杂度为0(N!),每次除了已经访问过的城市外，其他城市都要访问，所以，这是一个“指数级”的算法。我们来观察一下这个算法。在求从B1到E的最短路径的时候，先求出从C2到E的最短路径；而在求从B2到E的最短路径的吋候，又求了一遍从C2到E的最短路径。也就是说，从C2到E的最短路径我们求了两遍。同样可以发现，在求从Cl、C2到E的最短路径的过程中，从D1到E的最短路径也被求了两遍。而在整个程序中，从D1到E的最短路径被求了四遍。如果在求解的过程屮，同时将求得的最短路径的距离“记录在案”，随时调用，那么算法就会简洁多了！解法二：由后往前依次推出每个

7、Dis值，直到推出Dis[A]为止。所谓“后”、“前”是我们自己为城市编的序号，当两个城市I，J的前后顺序定为1“前”J“后”时,必须满足这个条件：或者I,J不连通，或者Dis[I]+Map[I,J]>Dis[J]o因为如果I,J连通且Dis[I]+Map[I,J]