K-动态规划教案.doc

动态规划策略
动态规划(dynamic programming)是运筹学的一个分支,是求解决策过程(decision process)最优化的数学方法。(multistep decision process)的优化问题时,提出了著名的最优化原理(principle of optimality),把多阶段过程转化为一系列单阶段问题,逐个求解,创立了解决这类过程优化问题的新方法——动态规划。1957年出版了他的名著Dynamic Programming,这是该领域的第一本著作。
动态规划问世以来,在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题,用动态规划方法比用其它方法求解更为方便。
虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题,但是一些与时间无关的静态规划(如线性规划、非线性规划),只要人为地引进时间因素,把它视为多阶段决策过程,也可以用动态规划方法方便地求解。
第一节动态规划的本质
一、多阶段决策过程的最优化问题
    在现实生活中,有一类活动的过程,由于它的特殊性,可将过程分成若干个互相联系的阶段,在它的每一阶段都需要作出决策,从而使整个过程达到最好的活动效果。因此各个阶段决策的选取不能任意确定,它依赖于当前面临的状态,又影响以后的发展。当各个阶段决策确定后,就组成一个决策序列,因而也就确定了整个过程的一条活动路线。这种把一个问题看作是一个前后关联具有链状结构的多阶段过程(如图)就称为多阶段决策过程,这种问题称为多阶段决策问题。
阶段1
阶段2
……
阶段n
决策1
决策2
决策n-1
    在多阶段决策问题中,各个阶段采取的决策,一般来说是与时间有关的,决策依赖于当前状态,又随即引起状态的转移,一个决策序列就是在变化的状态中产生出来的,故有"动态"的含义,我们称这种解决多阶段决策最优化的过程为动态规划方法。
    应指出,动态规划是考察求解多阶段决策问题的一种途径、一种方法,而不是一种特殊算法。不像线性规划那样,具有一个标准的数学表达式和明确定义的一组规划。因此我们在学****时,除了要对基本概念和方法正确理解外,必须具体问题具体分析处理,以丰富的想象力去建立模型,用创造性的技巧去求解。
例如:图中给出了一个地图,地图中每个顶点代表一个城市,两个城市间的连线代表道路,连线上的数值代表道路的长度。现在,我们想从城市A到达城市E,怎样走路程最短,最短路程的长度是多少?
解法一:用搜索法对A->E可能的每一条路线进行枚举,把距离算出来,然后互相比较,找出最短者。
设Dis[X]为城市X到E的最短路线的长度;(X表示任意一个城市)
Map[I,J]表示I,J两个城市间的距离,若Map[I,J]=0,则两个城市不连通。
算法描述
Program li_1;
Var Se:未访问的城市集合;
Function Long(Who:当前访问城市):Integer;
{求当前访问城市与城市E的最短距离}
Begin
If Who=E Then Search:=0
Else Begin Min:=Maxint;
For I取遍所有城市 Do
If (Map[Who,I]>0) And (I In Se) Then
Begin Se:=Se-[I]; J:=Map[Who,I]+Long(I);Se:=Se+[I];
If J<Min Then Min:=J;
End;
Long:=Min;
End;
End;
Begin {main}
Se:=除A外所有城市的集合; Dis[A]:=Long(A);
End.
解法分析:这个程序的时间复杂度为O(N!),每次除了已经访问过的城市外,其他城市都要访问,所以,这是一个“指数级”的算法。
我们来观察一下这个算法。在求从B1到E的最短路径的时候,先求出从C2到E的最短路径;而在求从B2到E的最短路径的时候,又求了一遍从C2到E的最短路径。也就是说,从C2到E的最短路径我们求了两遍。同样可以发现,在求从C1、C2到E的最短路径的过程中,从D1到E的最短路径也被求了两遍。而在整个程序中,从D1到E的最短路径被求了四遍。如果在求解的过程中,同时将求得的最短路径的距离“记录在案”,随时调用,那么算法就会简洁多了!
解法二:由后往前依次推出每个Dis值,直到推出Dis[A]为止。
所谓“后”、“前”是我们自己为城市编的序号,当两个城市I,J的前后顺序定为I“前”J“后”时,必须满足这个条件:或者I,J不连通,或者Dis[I]+Ma