NOIP初赛复习14基本算法思想

1、NOIP初赛复习14基本算法思想一个程序往往要包含两个方面的描述：一是对数据组织的描述，就是数据的类型和数据的组织形式（例如数组），称作数据结构；一是对程序操作流程的描述，就是程序的操作步骤，也就是所谓算法。正如著名的计算机科学家沃思（Nikiklaus Wirth）提出的公式：数据结构+算法=程序。算法，广义地讲就是解决问题的方法和过程。可以使用自然语言、伪代码、流程图等多种不同的方法来描述。如果把一个程序比喻成一个具有生命的人，那么数据结构就是这个人的躯体，而算法则是这个人的灵魂。枚举枚举法，又称穷举法，或称为暴力破解法，是一种针对于密码的破译方法，即将密码进行逐个推算直到找出真正的密码为

2、止。基本思想：在可能的解空间中穷举出每一种可能的解，并对每一个可能解进行判断，从中得到问题的答案。虽然枚举法本质上属于搜索策略，但是它与后面讲的回溯法或宽度优先搜索有所不同。总的来说，枚举就是通过列举所有的可能性进行一一判断检查。适用条件：1、可预先确定每个状态的元素个数n。2、可预先确定每个状态元素a1,a2,an的值域。注意事项：使用枚举思想解决实际问题，最关键的步骤是划定问题的解空间，并在该解空间中一一枚举每一个可能的解。这里有两点需要注意。一是解空间的划定必须保证覆盖问题的全部解。如果解空间集合用H表示，问题的解集用h表示，那么只有当时，才能使用枚举法求解。二是解空间集合及问题的解集一

3、定是离散的集合，也就是说集合中的元素是可列的、有限的。常见类型：枚举排列、枚举子集。常见方法：递归地枚举，这种方法往往更为直观；递推（循环）地枚举，这种方法往往写起来更为简洁。主要优点：由于枚举算法一般是现实问题的“直译”，且是建立在考察大量状态、甚至是穷举所有状态的基础之上的，因此比较直观，易于理解，其算法的正确性也比较容易证明。主要缺点：枚举算法的效率取决于枚举状态的数量以及单个状态枚举的代价，因此效率比较低。在某些情况下，我们可以通过利用题目的特点去除相当大的一部分情况的列举，从而提高枚举的效率。算法优化：1、提取有效信息;2、减少重复计算;3、将原问题化为更小的问题;4、根据问题的性质

4、进行截枝;5、引进其他算法。例：NOIP2016玩具谜题、NOIP2014生活大爆炸版石头剪刀布等递推递推是一种用若干步可重复的简运算（规律）来描述复杂问题的方法。给定一个数的序列H0,H1,Hn,若存在整数n0，使当nn0时,可以用等号(或大于号、小于号)将Hn与其前面的某些项Hi(0iCatalan数是比较复杂的递推关系，尤其在竞赛的时候，选手很难在较短的时间里建立起正确的递推关系。当然，Catalan数类的问题也可以用搜索的方法来完成，但是，搜索的方法与利用递推关系的方法比较起来，不仅效率低，编程复杂度也陡然提高。5、第二类Stirling数在五类典型的递推关系中，第二类Stirling

5、是最不为大家所熟悉的。也正因为如此，我们有必要先解释一下什么是第二类Strling数。定义：n个有区别的球放到m个相同的盒子中，要求无一空盒，其不同的方案数用S(n,m)表示，称为第二类Stirling数。下面就让我们根据定义来推导带两个参数的递推关系第二类Stirling数。解：设有n个不同的球，分别用b1,b2,bn表示。从中取出一个球bn，bn的放法有以下两种：1、bn独自占一个盒子；那么剩下的球只能放在m-1个盒子中，方案数为S2(n-1,m-1)；2、bn与别的球共占一个盒子；那么可以事先将b1,b2,bn-1这n-1个球放入m个盒子中，然后再将球bn可以放入其中一个盒子中，方案数为

6、mS2(n-1,m)。综合以上两种情况，可以得出第二类Stirling数定理：S2(n,m)=mS2(n-1,m)+S2(n-1,m-1) (n1,m1)边界条件可以由定义2推导出：S2(n,0)=0；S2(n,1)=1；S2(n,n)=1；S2(n,k)=0(kn)。小结：通过上面对五种典型的递推关系建立过程的探讨，可知对待递推类的题目，要具体情况具体分析，通过找到某状态与其前面状态的联系，建立相应的递推关系。递归一个函数、过程、概念或数学结构，如果在其定义或说明内部又直接或间接地出现有其本身的引用，则称它们是递归的或者是递归定义的。在程序设计中，过程或函数直接或者间接调用自己，就被称为递归

7、调用。其中直接调用自己称为直接递归，而将A调用B，B以调用A的递归叫做间接递归。基本思想：1、递归是借助于一个递归工作栈来实现。递归=递推+回归。2、递推：问题向一极推进, 这一过程叫做递推。这一过程相当于压栈。3、回归：问题逐一解决，最后回到原问题，这一过程叫做回归。这一过程相当于弹栈。注意事项：1、递归就是在过程或函数里调用自身；2、在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。主要优点：采用递归方法编写的问题解决程序具有结构清晰，可读性强等优点，且递归算法的设计比非递归算法的设计往往要容易一些，所以当问题本身是递归定义的，或者问题所涉及到的数据结构是递归定义的，或者是问题

8、的解决方法是递归形式的时候，往往采用递归算法来解决。主要缺点：执行的效率很低，尤其在边界条件设置不当的情况下，极有可能陷入死循环或者内存溢出的窘境。递归实现的代价是巨大的栈空间的耗费，那是因为过程每向前递推一次，程序将本层的实在变量（值参和变参）、局部变量构成一个“工作记录”压入工作栈的栈顶，只有退出该层递归时，才将这一工作记录从栈顶弹出释放部分空间。由此可以想到，减少每个“工作记录”的大小便可节省部分空间。例如某些变参可以转换为全局变量，某些值参可以省略以及过程内部的精简。应用分类：1、递归的定义问题。树结构是由递归定义的。因此，在解决与树有关的问题时，常常可以采用递归的方法。2、解决搜索问

9、题。因为搜索产生的节点成树状结构，所以可以用递归方法解决。这类例子很多，如“N皇后”问题，全排列，哈密顿回路，图的可着色性等搜索问题。3、实现分治思想。不难发现，在各种时间复杂度为nlogn排序方法中，大都采用了递归的形式。因为无论是分治合并排序，还是堆排序、快速排序，都存在有分治的思想。只要分开处理，就可以采用递归。其实进行分治，也是一个建树的过程。4、用于输出动态规划的中间过程。动态规划对空间要求较高，若要保存中间过程用于输出，则可能要增加一倍的空间需求。此时，如果采用递归输出，就完全不需要浪费这宝贵的空间。【例】 给定n（n=1）,用递归的方法计算1+2+3+4+.+(n-1)+n。算法

10、分析：本题可以用递归方法求解，其原因在于它符合递归的三个条件：1、本题是累加问题：当前和=前一次和+当前项，而前一次和的计算方法与其相同，只是数据不同s(n)=s(n-1)+n;2、给定n,所以是有限次的递归调用；3、结束条件是当n=1，则s=1。【参考程序】#includeusing namespace std;int fac(int);/递归函数int main()int t;cint;/输入t的值couts=fac(t)endl; /计算1到t的累加和，输出结果int fac(int n)if (n=1) return 1;return (fac(n-1)+n);/调用下一层递归运行程序

11、，当T=5时，输出结果：S=15，其递归调用执行过程如下图：（设T=3）递归调用过程，实质上是不断调用过程或函数的过程，由于递归调用一次，所有子程序的变量（局部变量、变参等）、地址在计算机内部都有用特殊的管理方法栈（先进后出）来管理，一旦递归调用结束，计算机便开始根据栈中存储的地址返回各子程序变量的值，并进行相应操作。递归递推适合解决的问题1.问题本身是递归定义的，或者问题所涉及到的数据结构是递归定义的，或者是问题的解决方法是递归形式的2.需要利用分治思想解决的问题3.回溯、深度优先搜索4.输出动态规划的中间过程1.能够用递推式计算的数学题2.动态规划（必须使用递推或记忆化搜索）特点结构清晰、

12、可读性强目的性强速度较快、比较灵活思路不易想到编码方式在函数中调用自己迭代（使用for循环等）替代方法问题的性质不同，改写的方法也不同。 有的问题可以根据程序本身的特点，使用栈来模拟递归调用。 有的问题可以改写成递推或迭代算法。在拓扑关系不明显时，可以采用记忆化搜索。搜索搜索，某种意义上就是对于枚举算法的一种改进，通过在枚举的过程中，不断排除一些不可能达到的情况，从而达到优化复杂度的效果。常见方法：1、深度优先搜索（DFS）主要思想：从一个顶点沿一条路一直走，如果发现到不了目标节点，则返回上一个节点，沿另一条路一直走到底。总体来说，DFS就是一个一个一直处理到底，发现无法得到结果之后，逐步返回

13、寻求其它的出路。算法优化：1、最优化剪枝：求最优值时，当前的状态无论如何不可能比最优值更优，则退出，可与展望结合剪枝；2、可行性剪枝：提前判断该状态是否能得到可行解，如不能则退出；3、记忆化搜索：对于已经搜索过的状态直接退出；4、改变搜索顺序：对于看起来希望更大的决策先进行搜索；5、优化搜索策略；6、预处理找到大体搜索翻译；7、改写成IDA*算法。2、宽度优先搜索（BFS）主要思想：首先访问起始节点的所有邻接点，然后再访问较远的区域，逐步扩大范围，直到找到了目标节点。BFS是一个处理不含边权的图当中求解最短路径的一个非常有效的方法。这一算法也是很多重要的图的算法的原型。Dijkstra单源最短

14、路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。注意事项：1、每生成一个子结点，就要提供指向它们父亲结点的指针。当解出现时候，通过逆向跟踪，找到从根结点到目标结点的一条路径。当然不要求输出路径，就没必要记父亲。2、生成的结点要与前面所有已经产生结点比较，以免出现重复结点，浪费时间和空间，还有可能陷入死循环。3、如果目标结点的深度与“费用”（如：路径长度）成正比，那么，找到的第一个解即为最优解，这时，搜索速度比深度搜索要快些，在求最优解时往往采用宽度优先搜索；如果结点的“费用”不与深度成正比时，第一次找到的解不一定是最优解。4、宽度优先搜索的效率还有赖于目标结点所在位置情况，如

15、果目标结点深度处于较深层时，需搜索的结点数基本上以指数增长。算法优化：1、判重的优化：hash，二叉排序树；2、双向广搜或启发式搜索；3、改写成A*算法；4、二分优化。DFSBFS优势1. 比较适合回溯类搜索2. 参数传递、状态修改和恢复都比较方便3. 自顶向下地处理问题4. 记忆化搜索容易实现5. 能很快到达解答树的底端1. 解决“最少步数”、“深度最小”问题2. 问题的解靠近解答树的根结点3. 启发式搜索在BFS中更容易实现4. 能立刻停止搜索缺点1. 使用递归算法容易导致栈溢出2. 有时不容易输出方案3. 不易立即结束搜索1. 空间一般比DFS大2. 状态重复的排除有时耗时多3、迭代加深

16、搜索深度优先搜索的优点在于能较高效地逼近解，缺点在于初始递归方向错误会带来很严重后果；宽度优先搜索的优点在于能迅速找到答案不算大的解，缺点在于解答案较大时所耗时间与空间都比较大。于是，在综合以上两个算法之后，出现了一个折中的方法：迭代加深搜索。主要思想：通过限定下界k，然后允许深度优先搜索搜索k层，一旦仍没有找到有效解，则增大下界。主要优点：相对于深度优先搜索并没有大很多的时间开销，但能部分解决深度优先搜索的局限；无需宽度优先搜索一般的大空间需求。【例】迷宫问题如下图所示，给出一个N*M的迷宫图和一个入口、一个出口。编一个程序，打印一条从迷宫入口到出口的路径。这里黑色方块的单元表示走不通（用-

17、1表示），白色方块的单元表示可以走（用0表示）。只能往上、下、左、右四个方向走。如果无路则输出“no way.”。入口0-1000000-10000-1000-1-100000-1-1-100-1-100000出口0000000-1-1算法分析：只要输出一条路径即可，所以是一个经典的回溯算法问题，本例给出了回溯（深搜）程序和宽搜程序。【深搜参考程序】#include using namespace std;intn,m,desx,desy,soux,souy,totstep,a51,b51,map5151;bool f;int move(int x, int y,int step)mapxy=

18、step; /走一步，作标记，把步数记下来astep=x; bstep=y;/记路径 if(x=desx)&(y=desy) f=1;totstep=step; else if(y!=m)&(mapxy+1=0)move(x,y+1,step+1);/向右 if(!f)&(x!=n)&(mapx+1y=0) move(x+1,y,step+1);/往下 if(!f)&(y!=1)&(mapxy-1=0) move(x,y-1,step+1);/往左 if(!f)&(x!=1)&(mapx-1y=0) move(x-1,y,step+1);/往上 int main() int i,j;cinnm

19、;/n行m列的迷宫 for(i=1;i=n;i+) /读入迷宫，0表示通，-1表示不通for (j=1;jmapij;coutsouxsouy;/入口coutdesxdesy;/出口 f=0; /f=0表示无解；f=1表示找到了一个解move(soux,souy,1); if (f) for(i=1;i=totstep;i+)/输出直迷宫的路径coutai,biendl; elsecoutno way.endl;return 0;【宽搜参考程序】#include using namespace std;int u5=0,0,1,0,-1,w5=0,1,0,-1,0;intn,m,i,j,des

20、x,desy,soux,souy,head,tail,x,y,a51,b51,pre51,map5151;bool f;int print(int d) if (pred!=0)print (pred);/递归输出路径coutad,bdnm;/n行m列的迷宫 for(i=1;i=n;i+) /读入迷宫，0表示通，-1表示不通for (j=1;jmapij;coutsouxsouy;/入口coutdesxdesy;/出口 head=0;tail=1; f=0;mapsouxsouy=-1;atail=soux; btail=souy;pretail=0; while(head!=tail) /队

21、列不为空head+; for(i=1;i0)&(x0)&(y=m)&(mapxy=0) /本方向上可以走tail+;atail=x; btail=y; pretail=head;mapxy=-1;if (x=desx)&(y=desy) /扩展出的结点为目标结点f=1;print(tail);break; if(f) break; if (!f)coutno way.endl; return 0;输入1：输出1：输入2：输出2：8 5-1 -1 -1 -1 -10 0 0 0 -1-1 -1 -1 0 -1-1 0 0 0 -1-1 0 0 -1 -1-1 0 0 0 -1-1 -1 -1 0

22、 -1-1 0 0 0 -12 18 42,12,22,32,43,44,44,35,36,38 5-1 -1 -1 -1 -10 0 0 0 -1-1 -1 -1 0 -1-1 0 0 0 -1-1 0 0 -1 -1-1 0 0 0 -1-1 -1 -1 -1 -1-1 0 0 0 -12 18 4no way.分治基本思想：将一个较大规模的问题分成多个（一般是2个）较小规模的互相独立且与原问题相同或相似的子问题，再把子问题分成更小的子问题直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。当我们将问题分解成两个较小问题求解时的分治方法称之为二分法。适用条件：1、该问题的规模缩

23、小到一定的程度就可以容易地解决；2、该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；3、利用该问题分解出的子问题的解可以合并为该问题的解；4、该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。递归与分治的算法思想往往是相伴而生的，它们在各类算法中使用非常频繁，应用递归和分治的算法思想有时可以设计出代码简洁且比较高效的算法来。解题步骤：1、分解，将要解决的问题划分成若干规模较小的同类问题；2、求解，当子问题划分得足够小时，用较简单的方法解决；3、合并，按原问题的要求，将子问题的解逐层合并构成原问题的解。应用分类：二分搜索；大整数乘法；Strassen

24、矩阵乘法；棋盘覆盖；合并排序；快速排序；线性时间选择；最接近点对问题；循环赛日程表；汉诺塔等。例：NOIP2012借教室；NOIP2013转圈游戏等【例】用递归算法实现二分查找即：有n个已经从小到大排序好的数据，输入一个数m，用二分查找算法，判断它是否在这n个数中。#includeusing namespace std;int jc(int,int);int n,a1000,m;int main() intx,y,i;cinn; x=1;y=n; for(i=1;iai;cinm; /输入要查找的数jc(x,y);/递归过程coutendl;int jc(int x,int y) /递归过程

25、int k;k=(x+y)/2;/取中间位置点 if(ak=m) coutthennum in ky)coutno findendl; /找不到该数else if (akm) jc(x,k-1);/在前半中查找 贪心基本思想：贪心，又称贪婪算法。指的是在对问题求解过程中，总是做出目前来看最优的选择，也就是说贪心算法不会考虑全局最优解，而只会不断考虑局部最优解。是一种对某些求最优解问题的更简单、更迅速的设计技术。往往可以以较低的代码复杂度与时间复杂度而得到较优的结果，对于求解近似值的作用很大。贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择。必须注意的是，贪心算法不是对所有问题都能得到

26、整体最优解，选择的贪心策略必须具备无后效性，即某个状态以后的过程不会影响以前的状态，只与当前状态有关。当存在一些题目的正解想不出来，并且一个贪心原则又效果不好的情况下，可以采取多个贪心原则同时用，并取最优的方案来解决。但对于相当一部分需要求解最优值的问题，实际上我们会发现我们通常可以采用动态规划或者网络流的方法取代贪心算法。适用条件：1、可通过局部的贪心选择来达到问题的全局最优解。运用贪心策略解题，一般来说需要一步步的进行多次的贪心选择。在经过一次贪心选择之后，原问题将变成一个相似的，但规模更小的问题，而后的每一步都是当前看似最佳的选择，且每一个选择都仅做一次。2、原问题的最优解包含子问题的最

27、优解，即问题具有最优子结构的性质。在下面示例的背包问题中，第一次选择单位重量价值最大的货物，它是第一个子问题的最优解，第二次选择剩下的货物中单位重量价值最大的货物，同样是第二个子问题的最优解，依次类推。3、其次，如何选择一个贪心标准？正确的贪心标准可以得到问题的最优解，在确定采用贪心策略解决问题时，不能随意的判断贪心标准是否正确，尤其不要被表面上看似正确的贪心标准所迷惑。在得出贪心标准之后应给予严格的数学证明。解题步骤：1、建立数学模型来描述问题；2、把求解的问题分成若干个子问题；3、对每一子问题求解，得到子问题的局部最优解；4、把子问题的解局部最优解合成原来解问题的一个解。例：NOIP201

28、2国王游戏；NOIP2013积木大赛；NOIP2015跳石头等。【例】部分背包问题给定一个最大载重量为M的卡车和N种食品，有食盐，白糖，大米等。已知第i种食品的最多拥有Wi公斤，其商品价值为Vi元/公斤，编程确定一个装货方案，使得装入卡车中的所有物品总价值最大。算法分析：因为每一个物品都可以分割成单位块，单位块的利益越大显然总收益越大，所以它局部最优满足全局最优，可以用贪心法解答，方法如下：先将单位块收益按从大到小进行排列，然后用循环从单位块收益最大的取起，直到不能取为止便得到了最优解。因此我们非常容易设计出如下算法：问题初始化； /读入数据按Vi从大到小将商品排序；i=1;do if (m=

29、0) break; /如果卡车满载则跳出循环 m=m-wi; if (m=0)/将第i种商品全部装入卡车 else 将(m+wi) 重量的物品i装入卡车; i=i+1; /选择下一种商品while (m0&i=n);在解决上述问题的过程中，首先根据题设条件，找到了贪心选择标准(Vi)，并依据这个标准直接逐步去求最优解，这种解题策略被称为贪心法。回溯基本思想：在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去；如果该结点不包含问题的解，那就说明以该结点为根结点的子树一定不包

30、含问题的最终解，因此要跳过对以该结点为根的子树的系统探索，逐层向其祖先结点回溯。这个过程叫做解空间树的“剪枝”操作。如果应用回溯法求解问题的所有解，要回溯到解空间树的树根，这样根结点的所有子树都被探索到才结束。如果只要求解问题的一个解，那么在探索解空间树时，只要搜索到问题的一个解就可以结束了。【例】素数环:从1到20这20个数摆成一个环，要求相邻的两个数的和是一个素数。算法分析：非常明显，这是一道回溯的题目。从1开始，每个空位有20种可能，只要填进去的数合法：与前面的数不相同；与左边相邻的数的和是一个素数。第20个数还要判断和第1个数的和是否素数。算法流程：1、数据初始化；2、递归填数：判断第

31、i个数填入是否合法A、如果合法：填数；判断是否到达目标（20个已填完）：是，打印结果；不是，递归填下一个；B、如果不合法：选择下一种可能。【参考程序】#include#include#include#includeusing namespace std;bool b21=0;int total=0,a21=0;int search(int);/回溯过程int print(); /输出方案bool pd(int,int);/判断素数int main() search(1);couttotalendl;/输出总方案数int search(int t) int i; for(i=1;i=20;i+)

32、/有20个数可选 if(pd(at-1,i)&(!bi)/判断与前一个数是否构成素数及该数是否可用 at=i;bi=1; if(t=20) if (pd(a20,a1) print();else search(t+1);bi=0; int print() total+;couttotal; for (intj=1;j=20;j+)coutaj ;coutendl; bool pd(int x,int y) intk=2,i=x+y; while(ksqrt(i) return 1; elsereturn 0;动态规划基本思想：在多阶段决策的问题中，各个阶段采取的决策，一般来说是与时间或空间有关

33、的。决策依赖于当前状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来，故有“动态”的含义，我们称这种解决多阶段决策最优化的过程为动态规划方法。基本概念：阶段：把所求问题的过程按照时间或空间恰当地分成若干个相互联系的阶段。状态：表示每个阶段的客观状态，它既是某阶段的出发位置，又是前一阶段的终点。无后效性：如果给定某一阶段的状态，则在这一阶段以后过程的发展不受这阶段以前各段状态的影响，所以各阶段确定时，整个过程也就确定了。决策：一个阶段的状态给定以后，从该状态演变到下一阶段状态的一种选择(行动)。策略：由每个阶段的决策组成的序列。最优性原理：把一个大问题划分成多个子问题，对于整个问

34、题必须最优的情况时，问题也必须最优，即问题具备最优子结构的性质。适用条件：1、最优子结构。如果问题的一个最优解中包含了子问题的最优解，则该问题具有最优子结构。也称最优化原理。最优子结构也可以理解为“整体最优则局部最优”。反之不一定成立。2、重叠子问题。在解决整个问题时，要先解决其子问题，要解决这些子问题，又要先解决他们的子子问题 。而这些子子问题又不是相互独立的，有很多是重复的，这些重复的子子问题称为重叠子问题。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只解一次，而后将其解保存在一个表中，以后再遇到这些相同问题时直接查表就可以，而不需要再重复计算，每次查表的时间为常数。3、无后

35、效性原则。已经求得的状态，不受未求状态的影响。解题步骤：1、判断问题是否具有最优子结构性质，若不具备，则不能用动态规划；2、把问题分成若干个子问题(分阶段)；3、建立状态转移方程(递推公式)；4、找出边界条件；5、设定初始值；6、递推求解。状态转移方程的构造是动态规划过程中最重要的一步，也是最难的一步。对于大多数的动态规划，寻找状态转移方程有一条十分高效的通道，就是寻找变化中的不变量（已经求得的值）。例：背包型动态规划：POJ1014,1068；序列型动态规划：POJ 1044,1576,3027；区间型动态规划：POJ 1048,1154,1166；棋盘性动态规划：POJ 1010,1169

36、,1219,1220；划分型动态规划：POJ 1017,1039,1040；树型动态规划：POJ 1163,1380等【例1】最短路径问题下图给出了一个地图，地图中的每个顶点代表一个城市，两个城市间的一条连线代表道路，连线上的数值代表道路的长度。现在想从城市A到达城市E，怎样走路程最短？最短路程的长度是多少？算法分析：把A到E的全过程分成四个阶段，用K表示阶段变量，第1阶段有一个初始状态A，有两条可供选择的支路A-B1、A-B2；第2阶段有两个初始状态B1、B2，B1有三条可供选择的支路，B2有两条可供选择的支路。用DK（XI，X+1J）表示在第K阶段由初始状态XI到下阶段的初始状态X+1J的

37、路径距离，FK（XI）表示从第K阶段的XI到终点E的最短距离，利用倒推的方法，求解A到E的最短距离。具体计算过程如下：S1： K = 4 有F4（D1）= 3，F4（D2）= 4，F4（D3）= 3；S2： K = 3 有F3（C1）= MIN D3（C1，D1）+ F4（D1），D3（C1，D2）+ F4（D2） = MIN 5+3，6+4 = 8F3（C2）= D3（C2，D1）+ F4（D1）= 5+3 = 8F3（C3）= D3（C3，D3）+ F4（D3）= 8+3 = 11F3（C4）= D3（C4，D3）+ F4（D3）= 3+3 = 6S3： K = 2 有F2（B1）= MI

38、N D2（B1，C1）+ F3（C1），D2（B1，C2）+ F3（C2），D2（B1，C3）+ F3(C3) = MIN 1+8,6+8,3+11 = 9F2（B2）= MIN D2（B2，C2）+ F3（C2），D2（B2，C4）+ F3（C4） = MIN 8+8，4+6 = 10S4： K = 1 有F1（A）= MIN D1（A，B1）+ F2（B1），D1（A，B2）+ F2（B2） = MIN 5+9，3+10 = 13因此由A点到E点的全过程最短路径为AB2C4D3E；最短路程长度为13。从以上过程可以看出，每个阶段中，都求出本阶段的各个初始状态到终点E的最短距离，当逆序倒推到过程起点A时，便得到了全过程的最短路径和最短距离。在上例的多阶段决策问题中，各个阶段采取的决策，一般来说是与阶段有关的，决策依赖于当前状态，又随即引起状态的转移，一个决策序列就是在变化的状态