文档介绍：、问题的提出首先,例举一个典型的且很直观的多阶段决策问题:[例]下图表示城市之间的交通路网,线段上的数字表示费用,单向通行由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将结果显然这种计算方法,符合最优原理。子问题的决策中,只对同一城市(结点)比较优劣。而同一阶段的城市(结点)的优劣要由下一个阶段去决定。,各个阶段采取的决策,一般来说是与时间有关的,决策依赖于当前状态,又随即引起状态的转移,一个决策序列就是在变化的状态中产生出来的,故有“动态”的含义,称这