第8章 程序设计基本算法和应用.ppt

《第8章 程序设计基本算法和应用.ppt》由会员分享，可在线阅读，更多相关《第8章 程序设计基本算法和应用.ppt（33页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第8章 程序设计基本算法与应用8.1 8.1 迭代法迭代法8.2 8.2 递推法递推法8.3 8.3 递归法递归法8.4 8.4 穷举法穷举法8.5 8.5 回朔法回朔法8.6 8.6 贪心法贪心法8.7 8.7 分治法分治法8.8 8.8 动态规划动态规划8.1 迭代法：方程求根（牛顿迭代法）迭代法：方程求根（牛顿迭代法）迭代法是一种不断用变量的旧值递推新值的过程。迭代法是一种不断用变量的旧值递推新值的过程。迭代法是一种不断用变量的旧值递推新值的过程。迭代法是一种不断用变量的旧值递推新值的过程。运用迭代法的基本步骤：运用迭代法的基本步骤：运用迭代法的基本步骤：运用迭代法的基本步骤：（1 1）

2、确定迭代的变量）确定迭代的变量）确定迭代的变量）确定迭代的变量（2 2）建立迭代关系）建立迭代关系）建立迭代关系）建立迭代关系（3 3）对迭代过程进行控制）对迭代过程进行控制）对迭代过程进行控制）对迭代过程进行控制 设设设设r r r r是是是是f(xf(xf(xf(x)=0)=0)=0)=0的根，选取的根，选取的根，选取的根，选取x0 x0 x0 x0作为作为作为作为r r r r初始近似值，初始近似值，初始近似值，初始近似值，过点（过点（过点（过点（x0,f(x0)x0,f(x0)x0,f(x0)x0,f(x0)）做曲线）做曲线）做曲线）做曲线y=y=y=y=f(xf(xf(xf(x)的切

3、线的切线的切线的切线L L L L，L L L L的方程的方程的方程的方程为为为为y=f(x0)+f(x0)(x-x0)y=f(x0)+f(x0)(x-x0)y=f(x0)+f(x0)(x-x0)y=f(x0)+f(x0)(x-x0)，求出，求出，求出，求出L L L L与与与与x x x x轴交点的横坐轴交点的横坐轴交点的横坐轴交点的横坐标标标标 x1=x0-f(x0)/f(x0)x1=x0-f(x0)/f(x0)x1=x0-f(x0)/f(x0)x1=x0-f(x0)/f(x0)，称，称，称，称x1x1x1x1为为为为r r r r的一次近似值。的一次近似值。的一次近似值。的一次近似值。过

4、点（过点（过点（过点（x1,f(x1)x1,f(x1)x1,f(x1)x1,f(x1)）做曲线）做曲线）做曲线）做曲线y=y=y=y=f(xf(xf(xf(x)的切线，并求该切的切线，并求该切的切线，并求该切的切线，并求该切线与线与线与线与x x x x轴交点的横坐标轴交点的横坐标轴交点的横坐标轴交点的横坐标 x2=x1-f(x1)/f(x1)x2=x1-f(x1)/f(x1)x2=x1-f(x1)/f(x1)x2=x1-f(x1)/f(x1)，称，称，称，称x2x2x2x2为为为为r r r r的二次近似值。重复以上过程，得的二次近似值。重复以上过程，得的二次近似值。重复以上过程，得的二次近

5、似值。重复以上过程，得r r r r的近似值序列，的近似值序列，的近似值序列，的近似值序列，其中其中其中其中x(n+1)=x(n+1)=x(n+1)=x(n+1)=x(nx(nx(nx(n)f(x(n)/f(x(nf(x(n)/f(x(nf(x(n)/f(x(nf(x(n)/f(x(n)，称为，称为，称为，称为r r r r的的的的n+1n+1n+1n+1次次次次近似值，上式称为牛顿迭代公式。近似值，上式称为牛顿迭代公式。近似值，上式称为牛顿迭代公式。近似值，上式称为牛顿迭代公式。8.1 迭代法：方程求根（牛顿迭代法）迭代法：方程求根（牛顿迭代法）#include#include math.h

6、math.h#include#include stdio.hstdio.h float float fun(floatfun(float a,floata,float b,floatb,float c,floatc,float d)d)float x=0.5,y;float x=0.5,y;do do y=x;y=x;x=x-(a*x=x-(a*x+bx+b)*)*x+cx+c)*x+d)/(3*a*x+2*b)*)*x+d)/(3*a*x+2*b)*x+cx+c););while(fabs(x-ywhile(fabs(x-y)=0.0000001);)=0.0000001);return x

7、;return x;8.1 迭代法：方程求根（牛顿迭代法）迭代法：方程求根（牛顿迭代法）main()float a,b,c,d;printf(nplease input a,b,c,d:);scanf(%f%f%f%f,&a,&b,&c,&d);printf(x=%10.7fn,fun(a,b,c,d);8.1 迭代法：方程求根（牛顿迭代法）迭代法：方程求根（牛顿迭代法）8.2 递推法：斐波那契数列递推法：斐波那契数列2递推法是利用问题本身所具有的一种递推关系求解问递推法是利用问题本身所具有的一种递推关系求解问题的方法。题的方法。斐波那契（斐波那契（FibonacciFibonacci）数列：

8、数列）数列：数列1 1、1 1、2 2、3 3、55，是著名的斐波那契数列，其递推通项公式为：，是著名的斐波那契数列，其递推通项公式为：f(0)f(0)0;0;f(1)=1;f(1)=1;f(nf(n)=f(n-2)+f(n-1)(n1)=f(n-2)+f(n-1)(n1)，请编写程序输出，请编写程序输出斐波那契数列的前斐波那契数列的前2020项。项。8.2 递推法：斐波那契数列递推法：斐波那契数列#define N 20main()long fN=0,1;int i;for(i=2;iN;i+)fi=fi-2+fi-1;printf(“Fibonacci%d=%ldn”,i,fi);8.2

9、递推法：斐波那契数列递推法：斐波那契数列 一般而言，兔子在出生两个月后，就有繁殖能力，一般而言，兔子在出生两个月后，就有繁殖能力，一般而言，兔子在出生两个月后，就有繁殖能力，一般而言，兔子在出生两个月后，就有繁殖能力，一对兔子每个月能生出一对小兔子来。如果所有兔都一对兔子每个月能生出一对小兔子来。如果所有兔都一对兔子每个月能生出一对小兔子来。如果所有兔都一对兔子每个月能生出一对小兔子来。如果所有兔都不死，那么一年以后可以繁殖多少对兔子？不死，那么一年以后可以繁殖多少对兔子？不死，那么一年以后可以繁殖多少对兔子？不死，那么一年以后可以繁殖多少对兔子？我们不妨拿新出生的一对小兔子分析一下：我们不妨

10、拿新出生的一对小兔子分析一下：我们不妨拿新出生的一对小兔子分析一下：我们不妨拿新出生的一对小兔子分析一下：第一个月小兔子没有繁殖能力，所以还是一对第一个月小兔子没有繁殖能力，所以还是一对第一个月小兔子没有繁殖能力，所以还是一对第一个月小兔子没有繁殖能力，所以还是一对;两个月后，生下一对小兔民数共有两对两个月后，生下一对小兔民数共有两对两个月后，生下一对小兔民数共有两对两个月后，生下一对小兔民数共有两对;三个月以后，老兔子又生下一对，因为小兔子还三个月以后，老兔子又生下一对，因为小兔子还三个月以后，老兔子又生下一对，因为小兔子还三个月以后，老兔子又生下一对，因为小兔子还没有繁殖能力，所以一共是三

11、对没有繁殖能力，所以一共是三对没有繁殖能力，所以一共是三对没有繁殖能力，所以一共是三对;8.2 递推法：斐波那契数列递推法：斐波那契数列依次类推可以列出下表：依次类推可以列出下表：依次类推可以列出下表：依次类推可以列出下表：所经过月数：所经过月数：所经过月数：所经过月数：0 0 0 0、1 1 1 1、2 2 2 2、3 3 3 3、4 4 4 4、5 5 5 5、6 6 6 6、7 7 7 7、8 8 8 8、9 9 9 9、10101010、11111111、12 12 12 12 兔子对数：兔子对数：兔子对数：兔子对数：1 1 1 1、1 1 1 1、2 2 2 2、3 3 3 3、5

12、5 5 5、8 8 8 8、13131313、21212121、34343434、55555555、89898989、144144144144、233 233 233 233 表中数字表中数字表中数字表中数字1 1 1 1，1 1 1 1，2 2 2 2，3 3 3 3，5 5 5 5，8 8 8 8构成了一个序构成了一个序构成了一个序构成了一个序列。这个数列有关十分明显的特点，那是：前面相邻列。这个数列有关十分明显的特点，那是：前面相邻列。这个数列有关十分明显的特点，那是：前面相邻列。这个数列有关十分明显的特点，那是：前面相邻两项之和，构成了后一项。两项之和，构成了后一项。两项之和，构成了后

13、一项。两项之和，构成了后一项。8.3 递归法：斐波那契数列递归法：斐波那契数列 一个过程或函数在其定义或说明中又直接或间接一个过程或函数在其定义或说明中又直接或间接一个过程或函数在其定义或说明中又直接或间接一个过程或函数在其定义或说明中又直接或间接调用自身的一种方法，它通常把一个大型复杂的问题调用自身的一种方法，它通常把一个大型复杂的问题调用自身的一种方法，它通常把一个大型复杂的问题调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求层层转化为一个与原问题相似的规模较小的问题来求层层转化为一个与原问题相似的规模较小的问题来求层层转化为一个与原问题相似的规

14、模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所解，递归策略只需少量的程序就可描述出解题过程所解，递归策略只需少量的程序就可描述出解题过程所解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。需要的多次重复计算，大大地减少了程序的代码量。需要的多次重复计算，大大地减少了程序的代码量。需要的多次重复计算，大大地减少了程序的代码量。一般来说，递归需要有边界条件、递归前进段和递归一般来说，递归需要有边界条件、递归前进段和递归一般来说，递归需要有边界条件、递归前进段和递归一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归

15、前进；当边界条返回段。当边界条件不满足时，递归前进；当边界条返回段。当边界条件不满足时，递归前进；当边界条返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。件满足时，递归返回。件满足时，递归返回。件满足时，递归返回。8.3 递归法：斐波那契数列递归法：斐波那契数列注意：注意：注意：注意：任何一个递归都包含两部分的内容：任何一个递归都包含两部分的内容：递归体：递归体：递归所进行的操作。递归所进行的操作。递归出口递归出口 ：为了防止递归调用无终止地进行，必：为了防止递归调用无终止地进行，必须在函数内有终止递归调用的手段。常用的办法是加须在函数内有终止递归调用的手段。常用的办法是加条

16、件判断，满足某种条件后就不再作递归调用，然后条件判断，满足某种条件后就不再作递归调用，然后逐层返回。逐层返回。8.3 递归法：斐波那契数列递归法：斐波那契数列#define N 20main()int i;for(i=0;i1)return fib(n-1)+fib(n-2);8.4 穷举法穷举法：水仙花数水仙花数 穷举法是对可能是解的所有候选解进行逐一穷举法是对可能是解的所有候选解进行逐一穷举法是对可能是解的所有候选解进行逐一穷举法是对可能是解的所有候选解进行逐一检验，从中找出满足要求的解。检验，从中找出满足要求的解。检验，从中找出满足要求的解。检验，从中找出满足要求的解。main()int

17、 i,j,k,n;printf(water flowernumber is:);for(n=100;n1000;n+)i=n/100;/*分解出百位分解出百位*/j=n/10%10;/*分解出十位分解出十位*/k=n%10;/*分解出个位分解出个位*/if(i*100+j*10+k=i*i*i+j*j*j+k*k*k)printf(%-5d,n);回溯法回溯法(探索与回溯法探索与回溯法)是一种选优搜索法，按选是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新发现原先选择并不优或达不

18、到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为足回溯条件的某个状态的点称为“回溯点回溯点”。1 1、问题描述、问题描述 从出发点（入口）开始，在给定的空间中，沿可从出发点（入口）开始，在给定的空间中，沿可行的路径进行探索，直到达到目标（出口）。行的路径进行探索，直到达到目标（出口）。在资源勘探中，在战争或游戏中，都会有类似的在资源勘探中，在战争或游戏中，都会有类似的情景，在给定的空间中，如森林、山洞、沙漠等，搜情景，在给定的空间中，如森林、山洞、沙漠等，搜索特定目标，如出路、人或物等。索特定目标，如

19、出路、人或物等。这类问题都可以归结为迷宫问题。这类问题都可以归结为迷宫问题。8.5 回朔法：迷宫问题回朔法：迷宫问题2 2、需要需要解决解决的的问题问题u如何表示给定的空间和可行的路径？如何表示给定的空间和可行的路径？u 如何表示入口和出口？如何表示入口和出口？u 当有多条可行的路径时如何选择？当有多条可行的路径时如何选择？u 当某条路径在某一点再没有可行之路时如何处理？当某条路径在某一点再没有可行之路时如何处理？前两个问题属于数据结构选择和设计，前两个问题属于数据结构选择和设计，后两个问题涉及后两个问题涉及算法设计算法设计。8.5 回朔法：迷宫问题回朔法：迷宫问题3 3、迷宫表示迷宫表示 可

20、以用一个可以用一个m m行行n n列的二维数组列的二维数组mazemnmazemn 来表来表示迷宫空间（或称迷宫地图），并约定：示迷宫空间（或称迷宫地图），并约定：当数组元素当数组元素mazeijmazeij=0=0，表示通路，表示通路，mazeijmazeij=1=1，表示不通；，表示不通；入口为左上角入口为左上角maze11maze11，出口为右下角出口为右下角mazemnmazemn；8.5 回朔法：迷宫问题回朔法：迷宫问题 迷宫地图简化迷宫地图简化 为了使探索方向个数一致，可在原来的迷宫地图为了使探索方向个数一致，可在原来的迷宫地图四周都扩展一个点，即增加两行和两列，并将迷宫四四周都扩

21、展一个点，即增加两行和两列，并将迷宫四周增加点的值全部置为周增加点的值全部置为1 1，表示是墙，不能通行。，表示是墙，不能通行。这样做使得原迷宫地图中的所有点都成为了中间这样做使得原迷宫地图中的所有点都成为了中间点，不用再判断当前点是点，不用再判断当前点是角点、边点、还是中间点角点、边点、还是中间点，每个点的探索方向均为每个点的探索方向均为8 8个。个。8.5 回朔法：迷宫问题回朔法：迷宫问题 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11111111111114 4、增量数组、增量数组DeltaXYDeltaXY在某一点（在某一点（x x，y y），有），有

22、8 8个可以探索的方向：个可以探索的方向：x-1，y-1x，y-1x+1，y-1 x-1，yx，y x+1，yx-1，y+1x，y+1x+1，y+1假设：从正东方向开始，沿顺时针方向假设：从正东方向开始，沿顺时针方向依次进行探索，则增量数组依次进行探索，则增量数组DeltaXYDeltaXY 为：为：8.5 回朔法：迷宫问题回朔法：迷宫问题5 5、已解决问题和、已解决问题和还未解决的问题还未解决的问题（1 1）二维数组二维数组mazem+2n+2mazem+2n+2来表示迷宫，解决来表示迷宫，解决了迷宫地图的存储；了迷宫地图的存储；（2 2）一维数组）一维数组DeltaXY8DeltaXY8来

23、记载了来记载了8 8个探索方向的个探索方向的坐标增量，将坐标增量，将8 8个探索方向数字化为个探索方向数字化为0 0到到7 7，并将向下，并将向下一点前进的操作统一为当前点的坐标一点前进的操作统一为当前点的坐标+沿该探索方向沿该探索方向的增量，即可得到下一点的坐标；的增量，即可得到下一点的坐标；（3 3）当某点无路可通行时当某点无路可通行时，需要从该点返回到前，需要从该点返回到前一点，再从前一点选择下一个方向继续进行探索，一点，再从前一点选择下一个方向继续进行探索，即需要知道前一点和前一点当前探索的方向。因此，即需要知道前一点和前一点当前探索的方向。因此，我们需要保留依次到达的各点的坐标和到达

24、该点的我们需要保留依次到达的各点的坐标和到达该点的方向；方向；8.5 回朔法：迷宫问题回朔法：迷宫问题（4 4）如何保留到达各点的）如何保留到达各点的坐标坐标和到达时的探索和到达时的探索方向方向？1 1）还需要防止重复到达某点还需要防止重复到达某点，避免在迷宫中，避免在迷宫中兜死圈子，需要记载已到达过的点。兜死圈子，需要记载已到达过的点。2 2）可以选用一个数据结构）可以选用一个数据结构-栈，栈，该栈中元素是由行号该栈中元素是由行号x x、列号、列号y y和到达该点的探索方和到达该点的探索方向向d d组成的三元组（组成的三元组（x x，y y，d d），），其中其中x x为到达点的横坐标或行号

25、，为到达点的横坐标或行号，y y为到达点的纵坐为到达点的纵坐标或列号，标或列号，d d为为0707中的一个数字，表示到达坐标为中的一个数字，表示到达坐标为（x x，y y）的点的方向。）的点的方向。例如从（例如从（2 2，2 2）点沿东南方向到达（）点沿东南方向到达（3 3，3 3）点时，）点时，在栈中要记录一个三元组（在栈中要记录一个三元组（3 3，3 3，1 1）。）。8.5 回朔法：迷宫问题回朔法：迷宫问题（5 5）如何避免在迷宫中）如何避免在迷宫中兜死圈子兜死圈子？可以用以下两种方法解决该问题：可以用以下两种方法解决该问题：1 1）设置一个标志数组）设置一个标志数组markmnmark

26、mn，所有元素初始化，所有元素初始化为为0 0；在探索中，当所探索的点；在探索中，当所探索的点(i(i，j)j)对应的对应的markijmarkij=0=0时，才进入该点，并将时，才进入该点，并将markijmarkij 置为置为1 1；当所探索的点；当所探索的点(i(i，j)j)对应的对应的markijmarkij=1=1时，表明已探索过，不需要再进入。时，表明已探索过，不需要再进入。2 2）当到达某点（当到达某点（i i，j j）后，在迷宫地图的该点坐）后，在迷宫地图的该点坐标上标记特殊值，例如将标上标记特殊值，例如将mazeijmazeij 置置 -1-1，以，以便区别未到达过的点。便区

27、别未到达过的点。8.5 回朔法：迷宫问题回朔法：迷宫问题迷宫算法实现迷宫算法实现int path(int mazemn,item DeltaXY8)SeqStack s;datetype temp;int x,y,d,i,j;temp.x=1;temp.y=1;temp.d=-1;Stack_Push(s，temp);while(!Stack_Empty(s)Stack_Pop(s,temp);x=temp.x;y=temp.y;d=temp.d+1;while (d8)i=x+DeltaXYd.x;j=y+DeltaXYd.y;if (mazeij=0)temp=x,y,d;Stack_Pu

28、sh(s,temp);x=i;y=j;mazexy=-1;/*标记该点已到过标记该点已到过*/if (x=m&y=n)return 1;/*找到出口，迷宫有路找到出口，迷宫有路*/else d=0;/*进入新点，按第一个方向（正东）搜索进入新点，按第一个方向（正东）搜索*/else d+;/*该方向不通时，按下一方向搜索该方向不通时，按下一方向搜索*/return 0;/迷宫无路迷宫无路 数据结构有两大用途：数据结构有两大用途：一是用于一是用于存放要处理的数据存放要处理的数据，如迷宫地图；，如迷宫地图；二是用于二是用于实现算法策略实现算法策略，如迷宫例子中探索方向增量数组、回溯的栈、避免如迷宫

29、例子中探索方向增量数组、回溯的栈、避免重复走的标志数组或特殊标记）重复走的标志数组或特殊标记）6 6、迷宫问题小结、迷宫问题小结使用了哪些数据结构？他们的作用？使用了哪些数据结构？他们的作用？存放迷宫的地图存放迷宫的地图mazemaze及边角点的处理及边角点的处理 方向数组方向数组DeltaXYDeltaXY：8 8个方向个方向 回溯的栈回溯的栈s s：三元组（：三元组（x x，y y，d d）避免重复走：走过的点计为特殊值避免重复走：走过的点计为特殊值-1-18.5 回朔法：迷宫问题回朔法：迷宫问题8.6 贪心法：装箱问题贪心法：装箱问题 贪心算法（又称贪婪算法）是指，在对问题求解贪心算法（

30、又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。生整体最优解或者是整体最优解的近似解。8.6 贪心法：装箱问题贪心法：装箱问题 设有编号为设有编号为0 0，1 1，n-1n-1的的n n种物品，体积分别为种物品

31、，体积分别为V0V0，V1V1，Vn-1Vn-1。将这。将这n n种物品装到容量都为种物品装到容量都为V V的若干箱子的若干箱子里。约定这里。约定这n n种物品的体积均不超过种物品的体积均不超过V V，即对于，即对于0in0in，有，有00ViVViV。不同的装箱方案所需要的箱子数目可能。不同的装箱方案所需要的箱子数目可能不同。装箱问题要求使装尽这不同。装箱问题要求使装尽这n n种物品的箱子数要少。种物品的箱子数要少。设有设有6 6种物品，它们的体积分别为：种物品，它们的体积分别为：6060，4545，3535，2020，2020，2020单位体积，箱子的容量为单位体积，箱子的容量为10010

32、0个单位体积。个单位体积。按照贪心法的思想，需要按照贪心法的思想，需要3 3只箱子，各箱子所装物只箱子，各箱子所装物品分别为：第品分别为：第1 1只箱子装物品只箱子装物品1 1，3 3；第；第2 2只箱子装物品只箱子装物品2 2，4 4，5 5；第；第3 3只箱子装物品只箱子装物品6 6。而最优解为。而最优解为2 2只箱子，分只箱子，分别装物品别装物品1 1，4 4，5 5和和2 2，3 3，6 6。8.7 分治法：分治法：在计算机科学中，分治法是一种很重要的算法。在计算机科学中，分治法是一种很重要的算法。字面上的解释是字面上的解释是“分而治之分而治之”，就是把一个复杂的，就是把一个复杂的问题

33、分成两个或更多的相同或相似的子问题，再把问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题子问题分成更小的子问题直到最后子问题可以直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。简单的直接求解，原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础。这个技巧是很多高效算法的基础。8.8 动态规划：动态规划：最优路径最优路径 动态规划法是动态规划法是动态规划法是动态规划法是20202020世纪世纪世纪世纪50505050年代由贝尔曼（年代由贝尔曼（年代由贝尔曼（年代由贝尔曼（R.R.R.R.BellmanBellmanBellmanBellman）等人提出，用

34、来解决多阶段决策过程问题的）等人提出，用来解决多阶段决策过程问题的）等人提出，用来解决多阶段决策过程问题的）等人提出，用来解决多阶段决策过程问题的一种最优化方法。所谓多阶段决策过程，就是把研究问一种最优化方法。所谓多阶段决策过程，就是把研究问一种最优化方法。所谓多阶段决策过程，就是把研究问一种最优化方法。所谓多阶段决策过程，就是把研究问题分成若干个相互联系的阶段，由每个阶段都作出决策题分成若干个相互联系的阶段，由每个阶段都作出决策题分成若干个相互联系的阶段，由每个阶段都作出决策题分成若干个相互联系的阶段，由每个阶段都作出决策，从而使整个过程达到最优化。实际上，动态规划法就，从而使整个过程达到最

35、优化。实际上，动态规划法就，从而使整个过程达到最优化。实际上，动态规划法就，从而使整个过程达到最优化。实际上，动态规划法就是分多阶段进行决策，其基本思路是：按时空特点将复是分多阶段进行决策，其基本思路是：按时空特点将复是分多阶段进行决策，其基本思路是：按时空特点将复是分多阶段进行决策，其基本思路是：按时空特点将复杂问题划分为相互联系的若干个阶段，在选定系统行进杂问题划分为相互联系的若干个阶段，在选定系统行进杂问题划分为相互联系的若干个阶段，在选定系统行进杂问题划分为相互联系的若干个阶段，在选定系统行进方向之后，逆着这个行进方向，从方向之后，逆着这个行进方向，从方向之后，逆着这个行进方向，从方向

36、之后，逆着这个行进方向，从终点向始点终点向始点终点向始点终点向始点计算，逐计算，逐计算，逐计算，逐次对每个阶段寻找某种决策，使整个过程达到最优，故次对每个阶段寻找某种决策，使整个过程达到最优，故次对每个阶段寻找某种决策，使整个过程达到最优，故次对每个阶段寻找某种决策，使整个过程达到最优，故又称为又称为又称为又称为逆序决策过程逆序决策过程逆序决策过程逆序决策过程。8.8 动态规划：动态规划：最优路径最优路径 如下图所示，从结点如下图所示，从结点如下图所示，从结点如下图所示，从结点1 1 1 1要铺设一条管道到结点要铺设一条管道到结点要铺设一条管道到结点要铺设一条管道到结点16161616，中间必

37、须经过中间必须经过中间必须经过中间必须经过5 5 5 5个中间站，第一站可以在个中间站，第一站可以在个中间站，第一站可以在个中间站，第一站可以在2 2 2 2和和和和3 3 3 3两个结点两个结点两个结点两个结点中任选一个，类似地，第二、三、四、五可供选择的结中任选一个，类似地，第二、三、四、五可供选择的结中任选一个，类似地，第二、三、四、五可供选择的结中任选一个，类似地，第二、三、四、五可供选择的结点分别是：点分别是：点分别是：点分别是：4444，5 5 5 5，6 6 6 6，7777，8888，9 9 9 9，10101010，11111111，12121212，13131313，141

38、41414，15151515。连接结点间管道的距离（或造价）用。连接结点间管道的距离（或造价）用。连接结点间管道的距离（或造价）用。连接结点间管道的距离（或造价）用连线上的数字表示，要求选一条从连线上的数字表示，要求选一条从连线上的数字表示，要求选一条从连线上的数字表示，要求选一条从1 1 1 1到到到到16161616的铺管线路，的铺管线路，的铺管线路，的铺管线路，使总距离最短（或总造价最小）。使总距离最短（或总造价最小）。使总距离最短（或总造价最小）。使总距离最短（或总造价最小）。8.8 动态规划：动态规划：最优路径最优路径8.8 动态规划：动态规划：最优路径最优路径 设设f(xf(x)表

39、示由表示由x x（x=1x=1，2 2，315315）到）到1616的最短的最短距离，则距离，则f(14)=4 f(14)=4，f(f(1515)=3)=3。f(11)=mind(11,14)+f(14),d(11,15)+f(15)=7 f(12)=mind(12,14)+f(14),d(12,15)+f(15)=5 f(13)=mind(13,14)+f(14),d(13,15)+f(15)=9 f(8)=mind(8,11)+f(11),d(8,12)+f(12)=7 f(9)=mind(9,12)+f(12),d(9,13)+f(13)=6 f(10)=mind(10,12)+f(12

40、),d(10,13)+f(13)=8 8.8 动态规划：动态规划：最优路径最优路径前面求得前面求得f(8)=7,f(9)=6,f(10)=8,则则:f(4)=mind(4,8)+f(8),d(4,9)+f(9)=13f(5)=mind(5,8)+f(8),d(5,9)+f(9)=10f(6)=mind(6,9)+f(9),d(6,10)+f(10)=9f(7)=mind(7,9)+f(9),d(7,10)+f(10)=12f(2)=mind(2,4)+f(4),d(2,5)+f(5),d(2,6)+f(6)=13f(3)=mind(3,5)+f(5),d(3,6)+f(6),d(3,7)+f(7)=16f(1)=mind(1,2)+f(2),d(1,3)+f(3)=18 即从即从1到到16的最短路径是：的最短路径是：1258121516