文档介绍：、问题的提出首先,例举一个典型的且很直观的多阶段决策问题:[例]下图表示城市之间的交通路网,线段上的数字表示费用,单向通行由A->E。求A->E的最省费用。如图从A到E共分为4个阶段,即第一阶段从A到B,第二阶段从B到C,第三阶段从C到D,第四阶段从D到E。除起点A和终点E外,其它各点既是上一阶段的终点又是下一阶段的起点。例如从A到B的第一阶段中,A为起点,终点有B1,B2,B3三个,因而这时走的路线有三个选择,一是走到B1,一是走到B2,一是走到B3。若选择B2的决策,B2就是第一阶段在我们决策之下的结果,它既是第一阶段路线的终点,又是第二阶段路线的始点。在第二阶段,再从B2点出发,对于B2点就有一个可供选择的终点集合(C1,C2,C3);若选择由B2走至C2为第二阶段的决策,则C2就是第二阶段的终点,同时又是第三阶段的始点。同理递推下去,可看到各个阶段的决策不同,线路就不同。很明显,当某阶段的起点给定时,它直接影响着后面各阶段的行进路线和整个路线的长短,而后面各阶段的路线的发展不受这点以前各阶段的影响。故此问题的要求是:在各个阶段选取一个恰当的决策,使由这些决策组成的一个决策序列所决定的一条路线,其总路程最短。具体情况如下:(1)由目标状态E向前推,可以分成四个阶段,即四个子问题。如上图所示。(2)策略:每个阶段到E的最省费用为本阶段的决策路径。(3)D1,D2是第一次输人的结点。他们到E都只有一种费用,在D1框上面标5,D2框上面标2。目前无法定下,那一个点将在全程最优策略的路径上。第二阶段计算中,5,2都应分别参加计算。(4)C1,C2,C3是第二次输入结点,他们到D1,D2各有两种费用。此时应计算C1,C2,C3分别到E的最少费用。C1的决策路径是min{(C1D1),(C1D2)}。计算结果是C1+D1+E,在C1框上面标为8。同理C2的决策路径计算结果是C2+D2+E,在C2框上面标为7。同理C3的决策路径计算结果是C3+D2+E,在C3框上面标为12。此时也无法定下第一,二阶段的城市那二个将在整体的最优决策路径上。(5)第三次输入结点为B1,B2,B3,而决策输出结点可能为C1,C2,C3。仿前计算可得Bl,B2,B3的决策路径为如下情况。Bl:B1C1费用12+8=20,路径:B1+C1+D1+EB2:B2C1费用6+8=14,路径:B2+C1+D1+EB3:B2C2费用12+7=19,路径:B3+C2+D2+E此时也无法定下第一,二,三阶段的城市那三个将在整体的最优决策路径上。(6)第四次输入结点为A,决策输出结点可能为B1,B2,B3。同理可得决策路径为A:AB2,费用5+14=19,路径A+B2+C1+D1+E。此时才正式确定每个子问题的结点中,那一个结点将在最优费用的路径上。19将结果显然这种计算方法,符合最优原理。子问题的决策中,只对同一城市(结点)比较优劣。而同一阶段的城市(结点)的优劣要由下一个阶段去决定。,各个阶段采取的决策,一般来说是与时间有关的,决策依赖于当前状态,又随即引起状态的转移,一个决策序列就是在变化的状态中产生出来的,故有“动态”的含义,称这种解决多阶段决策最优化问题的方法为动态规划方法。与穷举法相比,动态规划的方法有两个明显的优点:(1)大大减少了计算量(2)丰富了计算结果从上例的求解结果中,我们不仅得到由A点出发到终点E的最短路线及最短距离,而且还得到了从所有各中间点到终点的最短路线及最短距离,这对许多实际问题来讲是很有用的。动态规划的最优化概念是在一定条件下,我到一种途径,在对各阶段的效益经过按问题具体性质所确定的运算以后,使得全过程的总效益达到最优。应用动态规划要注意阶段的划分是关键,必须依据题意分析,寻求合理的划分阶段(子问题)方法。而每个子问题是一个比原问题简单得多的优化问题。而且每个子问题的求解中,均利用它的一个后部子问题的最优化结果,直到最后一个子问题所得最优解,它就是原问题的最优解。,动态规划不是万能的,它只适于解决一定条件的最优策略问题。或许,大家听到这个结论会很失望:其实,这个结论并没有削减动态规划的光辉,因为属于上面范围内的问题极多,还有许多看似不是这个范围中的问题都可以转化成这类问题。上面所说的“满足一定条件”主要指下面两点:(1)状态必须满足最优化原理;(2)状态必须满足无后效性。动态规划的最优化原理是无论过去的状态和决策如何,对前面的决策所形成的当前状态而言,余下的诸决策必须构成最优策略。可以通俗地理解为子问题的局部最优将导致整