《概念c语言程序设计》由会员分享，可在线阅读，更多相关《概念c语言程序设计（125页珍藏版）》请在金锄头文库上搜索。
1、第4章 算法设计策略v4.1 分治策略 v4.2 回溯策略v4.3 贪心策略v4.4 分枝界定策略v4.5 动态规划算法设计策略4.1 分治策略分治策略 任何一个可以用计算机求解的问题所需的计算时间都与其任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。直接求解一个规模较大的问题，往往是相当困难的。规模有关。直接求解一个规模较大的问题，往往是相当困难的。但是当问题的规模缩小到一定程度时，一个量变到质变的现象但是当问题的规模缩小到一定程度时，一个量变到质变的现象就可能发生，问题的求解变得比较容易。这时，如果能找到小就可能发生，问题的求解变得比较容易。这时，如果能找到小规模的该类问题与大
2、规模的该类问题之间的关系，就可以使用规模的该类问题与大规模的该类问题之间的关系，就可以使用分治策略对大规模的问题进行求解了。分治策略对大规模的问题进行求解了。 分治法所能解决的问题一般具有以下几个特征：分治法所能解决的问题一般具有以下几个特征：（1）该问题可以分解为若干个规模较小的相同问题。）该问题可以分解为若干个规模较小的相同问题。 （2）各个子问题相互独立，子问题之间不包含公共的子子问题。）各个子问题相互独立，子问题之间不包含公共的子子问题。（3）该问题的规模缩小到一定的程度可以容易地求解。）该问题的规模缩小到一定的程度可以容易地求解。（4）利用该问题分解出的子问题的解可以合并为该问题的解
3、。）利用该问题分解出的子问题的解可以合并为该问题的解。v4.1.1 二分查找二分查找v4.1.2 快速排序快速排序v4.1.3 自行车带人问题自行车带人问题分治法往往要依靠递归过程，并且大致有如下三个步骤：分治法往往要依靠递归过程，并且大致有如下三个步骤： 分解：将原问题分解为若干个规模较小、相互独立，与原问题形式相同的子问题。分解：将原问题分解为若干个规模较小、相互独立，与原问题形式相同的子问题。 解决：若子问题规模较小而容易被解决则直接解决，否则递归地解决各个子问题。解决：若子问题规模较小而容易被解决则直接解决，否则递归地解决各个子问题。 合并：将各个子问题的解合并为原问题的解。合并：将各
4、个子问题的解合并为原问题的解。 这一节，介绍几种使用分治策略的例子。这一节，介绍几种使用分治策略的例子。4.1.1 二分查找二分查找一、问题描述一、问题描述在N个已排序（设为从小到大）的数据（数或字符串），查询某一个数据：如果找到了，就指出其在N个数据中的位置；否则给出无该数据的信息，如给出“-1”。查询是在一个数据集中，查找给定数据的过程。查询是在一个数据集中，查找给定数据的过程。查询的结果有两种情形：找到给定的数据，并给出其查询的结果有两种情形：找到给定的数据，并给出其位置；找不到给定数据。位置；找不到给定数据。二、算法分析二、算法分析采用二分法求解本问题的基本思路是：如所示，设数列为采用
5、二分法求解本问题的基本思路是：如所示，设数列为a1、a2、an，被，被查找的数据为查找的数据为x，则查找首先对，则查找首先对am(m=(1+n)/2)进行，于是得到如下进行，于是得到如下3种情形：种情形： 若若xam，则，则x可能在区间可能在区间 am+1,an中。中。 若若x=r) 打印找不到信息,结束程序执行;else if(xam) 调用函数binsrch（m+1,r,x）;else 调用函数binsrch（s,m-1,x）;三、程序三、程序include float a10=1.1,1.3,1.5,1.7,1.9, 2.1,2.3,2.5,2.7,2.9; /* 数组声明及初始化，外部
6、数组 */void main()float x=2.3;int s=0,r=9;void binsrch(int s,int r,float x); /* 函数声明 */binsrch(s,r,x); /* 函数调用 */三、程序（续）三、程序（续）void binsrch(int s,int r,float x)int m;m=(s+r)/2;if(am=x)printf(The order of %5.1f is %d in this sequence.,x,m+1);return;else if(s=r) printf(%f is not exist in the seguense.,x
7、);exit(-1);else if(xam)binsrch(m+1,r,x); /* 递归调用 */elsebinsrch(s,m-1,x); /* 递归调用 */四、说明四、说明1. 外部数组外部数组 在本例中，声明语句在本例中，声明语句 float a10=1.1,1.3,1.5,1.7,1.9,2.1,2.3,2.5,2.7,2.9; 定义在所有函数的外部，即不在任何一个函数内。这种定义在定义在所有函数的外部，即不在任何一个函数内。这种定义在函数外部的数组，称为外部数组。一般来说，定义在外部的变函数外部的数组，称为外部数组。一般来说，定义在外部的变量称为外部变量。外部变量是在每一个函数
8、中都可以使用的变量称为外部变量。外部变量是在每一个函数中都可以使用的变量。相对而言，前面使用过的、定义在某一个函数内部的变量量。相对而言，前面使用过的、定义在某一个函数内部的变量称为局部变量，它只能在所定义的局部使用。称为局部变量，它只能在所定义的局部使用。五、编程练习五、编程练习1. 用二分法求一元方程式的根（提示：用二分迭代法）。用二分法求一元方程式的根（提示：用二分迭代法）。2. 用二分法计算用二分法计算xn的值（提示：当的值（提示：当n为偶数时，使用为偶数时，使用xn=xp*xp；当当n为奇数时，使用为奇数时，使用xn=x*xp*xp）。）。3. 用二分法找出一个数组中的最大值和最小值
9、。用二分法找出一个数组中的最大值和最小值。4.1.2 快速排序快速排序一、快速排序的基本思想：一、快速排序的基本思想：快速排序（快速排序（quick sort）是由著名计算机科学）是由著名计算机科学家根据分治策略给出的一种高效率的排序方法。家根据分治策略给出的一种高效率的排序方法。它的基本思想是：在待排序序列中选定一个元它的基本思想是：在待排序序列中选定一个元素素X(可以任选，也可以选第一个元素可以任选，也可以选第一个元素)，称为划分元，称为划分元素，用它将原序列整理素，用它将原序列整理划分（划分（partitioning）为）为两个子序列，使其左边的元素不比它大，使其右边两个子序列，使其左边
10、的元素不比它大，使其右边的元素不比它小；然后再对两个子序列进行上述划的元素不比它小；然后再对两个子序列进行上述划分；经过不断划分，直至将原序列整理完毕为止，分；经过不断划分，直至将原序列整理完毕为止，如所示。如所示。 5 7 9 8 1 6 3 4 2开始：开始： 2 4 3 1 6 8 9 7p p 5 6 5 2 1 4 8 9 7 3 4p pp pp pp pp p 9 7 5 6 1 2 3 8p pp pp p结果：结果：图图4.2 快速排序示例快速排序示例二、算法框架二、算法框架qksort(int m,int n) /* 序列由m到n */if(mn)调用划分函数part(m,
11、n,i);递归调用qksort(m,i-1);递归调用qksort(i+1,m);else 输出排序结束信息return;下面进一步考虑如何描述函数下面进一步考虑如何描述函数part()。基本思路如下：。基本思路如下：基本思路基本思路步骤步骤1：准备：准备： 步骤步骤1.1：设置两个指针：设置两个指针i和和j，分别指向待划分序列的，分别指向待划分序列的首尾元素首尾元素am和和an； 步骤步骤1.2：选取划分元素：选取划分元素p=ak（k属于属于m,n），），将将am移至移至k，即令，即令ak=am。步骤步骤2：划分：当：划分：当ip,则令则令j-（j左移一个数据位）左移一个数据位）;否则，令否
12、则，令ai=aj(将将aj放在放在i位置位置); 步骤步骤2.2：逐步增加：逐步增加i：将：将ai与与p比较，若比较，若aip,则令则令i+（i右移一个数据位）右移一个数据位）;否则，令否则，令aj=ai(将将ai放在放在j位置位置)。步骤步骤3：如果：如果i=j,放置划分元素：令放置划分元素：令Ai=p。 5 7 9 8 1 6 3 4 2i ij jp = 5p = 5 2 7 9 8 1 6 3 4 2i ij jajp, ai = ajajp, aj = aiaip, aj = ai 转向减少转向减少j jj ji ij j 2 4 9 8 1 6 3 4 7ajp, ai = aja
13、jp, aj = aiaip, aj = ai 转向减少转向减少j ji ij j 2 4 3 8 1 6 3 9 7ajp, ai = ajajp, aj = aiaip, aj = ai 转向减少转向减少j ji ij j 2 4 3 8 1 6 8 9 7ajp, ajp, 继续减少继续减少j jj j 2 4 3 1 1 6 8 9 7ajp, ai = ajajp, ai = aj 转向逐步增大转向逐步增大i ii ii ji j 2 4 3 1 1 6 8 9 7i = j,i = j,放置划分元素放置划分元素 5 图图4.3 一次划分示意图一次划分示意图划分函数划分函数int p
14、art(int low,int high)int i,j;float p; i=low; j=high; /* 准备 */p=alow;while(ij)while(i=p) /* 逐步减小j */j-;ai=aj;while(ij & ai=p) /* 逐步增大i */i+;aj=ai; ai=p; /* 放置划分元素 */ return(i);三、程序三、程序 #include #define N 10 float a=2.1,1.7,1.5,2.9,2.7,2.3,1.3,2.5,1.1,1.9; void main() int m=0,n=N-1;void qksort(int m,i
15、nt n);int part(int m,int n);void prnt();qksort(m,n);prnt(); 三、程序（续）三、程序（续） void qksort(int low,int high) int i; if(lowhigh)i=part(low,high);qksort(low,i-1);qksort(i+1,high); elsereturn;三、程序（续）三、程序（续） int part(int low,int high)参见前面参见前面“划分函数划分函数”部分部分void prnt()int i;printf(nsorted sequence is:n);for(i
16、=0;i=N-1;i+)printf(%5.1f,ai);四、运行结果四、运行结果sorted sequenc is:五、编程练习五、编程练习1. 归并排序（归并排序（Merging sort）：）：“归并归并”的含义是将两个或两个以上的含义是将两个或两个以上的有序表列合并为一个新的有序表列。归并排序就是把一个具有的有序表列合并为一个新的有序表列。归并排序就是把一个具有n 个数据的个数据的序列看作序列看作n个有序的子序列，不断两两归并，最后形成一个有序序列。显然个有序的子序列，不断两两归并，最后形成一个有序序列。显然这是一种分治策略。这是一种分治策略。归并排序的关键是归并。下面介绍一种归并算法
17、：归并排序的关键是归并。下面介绍一种归并算法：设序列设序列a(low,high)由两个有序子序列组成：由两个有序子序列组成：a(low,mid)和和a(mid,high)。归并按如下步骤进行：。归并按如下步骤进行：（1）设置一个与序列）设置一个与序列a大小相等的数组大小相等的数组b，用三个指针，用三个指针i,j,k,分别指向分别指向a(low,mid)，a(mid,high)和和b的首部；的首部；（2）重复执行下列操作：）重复执行下列操作： 如果如果aia）。问如何利用自行车，）。问如何利用自行车，才能使三人尽快全部到达才能使三人尽快全部到达B？二、算法分析二、算法分析1. 基本思路基本思路若
18、要三人尽快到达若要三人尽快到达B，就要考虑当一个人骑自，就要考虑当一个人骑自行车带一个人走的同时，另一个人也同时开始步行，行车带一个人走的同时，另一个人也同时开始步行，并且自行车不是到达并且自行车不是到达B后再返回去接步行的人，而后再返回去接步行的人，而是在中途返回去接步行的人，让原来带的人步行到是在中途返回去接步行的人，让原来带的人步行到终点。选择合适的自行车返回点，使自行车接上原终点。选择合适的自行车返回点，使自行车接上原来步行的人后，与中途下车的人同时到达。这样用来步行的人后，与中途下车的人同时到达。这样用的时间最短。的时间最短。为一个基本的解题思路。为一个基本的解题思路。A AD DE
19、 EC CB BL LS S图图4.4 自行车带人问题自行车带人问题假定甲被带到假定甲被带到C点后开始步行，这时乙步行到了点后开始步行，这时乙步行到了E点，丙点，丙返回的途中在返回的途中在D遇到乙，然后带上乙到遇到乙，然后带上乙到B时，甲也正好步行到时，甲也正好步行到B。问题的关键是求问题的关键是求C的位置。设的位置。设AC=L，那么，那么:甲从甲从A到到B的时间为：的时间为：t1=AC/b + CB/a = L/b+(S-L)/a乙从乙从A到到B的时间为：的时间为：t2=AE/a+ED/a+DC/b+CB/b并且并且,并且，并且，由于甲到由于甲到C与乙到与乙到E用的时间相等，所以：用的时间相
20、等，所以：AE/a=L/b；由于当自行车返回到由于当自行车返回到D时，乙步行到时，乙步行到D，所以，所以EC/(a+b)=ED/a=DC/b，即即:ED =（L-L/b*a）/(a+b)*a /* ED=EC/(a+b)*a=(AC-EC)/(a+b)*a */DC =（L-L/b*a）/(a+b)*b /* DC=EC/(a+b)*b=(AC-EC)/(a+b)*b */这样，这样，t1和和t2都描述成了关于都描述成了关于L的函数。如果任意给定一个的函数。如果任意给定一个L，就可以通过判定，就可以通过判定t1与与t2是否相等，得知该是否相等，得知该L是否正确。是否正确。A AD DE EC
21、CB BL LS S图图4.4 自行车带人问题自行车带人问题2. 用二分法试探确定用二分法试探确定C下面用试探方法来确定下面用试探方法来确定L（即（即C的位置）。的位置）。首先考虑用二分法，进行试探。即先以中点作为设想的首先考虑用二分法，进行试探。即先以中点作为设想的C，后分别计算，后分别计算t1与与t2： 如果如果t1=t2，该点即为，该点即为C； 如果如果t1t2，说明甲坐自行车少了（，说明甲坐自行车少了（ba），即），即C的实际位置应的实际位置应当在该当在该C点与点与B之间，应当继续在之间，应当继续在CB之间找下一个之间找下一个C； 如果如果t1t2，说明甲坐自行车多了，即，说明甲坐自行
22、车多了，即C的实际位置应当在该的实际位置应当在该C点与点与A之间，应当继续在之间，应当继续在AC之间找下一个之间找下一个C。如此反复，就会越来越接近真正的如此反复，就会越来越接近真正的C点。由于，查找的点。由于，查找的区间越来越小，当上一个区间越来越小，当上一个C与新的与新的C之间的距离小于某个给定之间的距离小于某个给定的误差范围时，就可以认为找到了的误差范围时，就可以认为找到了C。函数框架函数框架#define ERR 20double putLen(double pf,double pt)double lenth,ed,dc,t1,t2;lenth = (pf+pt)/2;ed =（len
23、th-lenth/b*a）/(a+b)*a;dc =（lenth-lenth/b*a）/(a+b)*b;t1= lenth/b+(S-lenth)/a;t2=lenth/b+ed/a+dc/b+(S-lenth)/b;if(abs(t1-t2) t2) putLen(pf+pt)/2,pt);if(t1 t2) putLen(pf,(pf+pt)/2);3. 使用优选法代替二分法使用优选法代替二分法优选法比二分法具有较快的收敛性。用优选法优选法比二分法具有较快的收敛性。用优选法代替二分法，就是用代替二分法，就是用0.618代替代替0.5。三、程序三、程序#include #include #d
24、efine S 120000#define ERR 200#define a 30#define b 70double putLen(double pf,double pt)double lenth,ed,dc,t1,t2;lenth = (pf+pt)*0.618;ed =（lenth-lenth/b*a）/(a+b)*a;dc =（lenth-lenth/b*a）/(a+b)*b;t1= lenth/b+(S-lenth)/a;t2=lenth/b+ed/a+dc/b+(S-lenth)/b;if(abs(t1-t2) t2) putLen(pf+pt) *0.618,pt);if(t1
25、=Ei & j=Ej，即继续探索的条，即继续探索的条件为：件为：iEi | jEj。4. 程序程序#include void main()int maze7=2,2,2,2,2,2,2,2,0,0,0,0,0,2,2,0,2,0,2,0,2,2,0,0,2,0,2,2, 2,2,0,2,0,2,2,2,0,0,0,0,0,2,2,2,2,2,2,2,2;int Si=1,Sj=1,Ei=5,Ej=5;/* 入口与出口入口与出口 */int i=Si,j=Sj;int count=0; /* 记录搜索步数变量记录搜索步数变量 */while(jEj | iEi)/* 在点（在点（i,j）上探索，
26、不达出口时，反复进行搜索）上探索，不达出口时，反复进行搜索 */*处理死点处理死点*/ if (mazei-1j=2 & mazeij+1=2 & mazei+1j=2) mazeij=2; j-; else if(mazeij+1=2 & mazei+1j=2 & mazeij-1=2) mazeij=2; i-; else if(mazei+1j=2 & mazeij-1=2 & mazei-1j=2) mazeij=2; j+; else if(mazeij-1=2 & mazei-1j=2 & mazeij+1=2) mazeij=2; i+; else mazeij=1;4. 程序（
27、续）程序（续）/* 按顺时针顺序先走没有走过的点按顺时针顺序先走没有走过的点 */ if (mazei-1j=0) i-; mazeij=1; else if(mazeij+1=0) j+; mazeij=1; else if(mazei+1j=0) i+; mazeij=1; else if(mazeij-1=0) j-; mazeij=1; /* 按顺时针顺序走走过的点按顺时针顺序走走过的点 */ else if(mazei-1j=1) mazeij=2; i-; else if(mazeij+1=1) mazeij=2; j+; else if(mazei+1j=1) mazeij=2;
28、 i+; else if(mazeij-1=1) mazeij=2; j-;count+; /* 记录走过点数记录走过点数 */ 4. 程序（续）程序（续） /* 打印探索结果打印探索结果 */for(i=0;i=6;i+)for(j=0;j=6;j+)printf(%d,mazeij);printf(n);printf(count=%dn,count); /* 打印搜索步数打印搜索步数 */5. 执行结果执行结果2,2,2,2,2,2,22,1,2,2,2,2,22,1,2,2,2,2,22,1,1,2,2,2,22,2,1,2,2,2,22,0,1,1,1,1,22,2,2,2,2,2,2
29、 count=19结果矩阵中的结果矩阵中的“1”为搜索后，找到的穿过迷宫的路为搜索后，找到的穿过迷宫的路线；线；“0”为未搜索过的节点。为未搜索过的节点。三、使用堆栈组织搜索过程三、使用堆栈组织搜索过程1. 基于堆栈的回溯基于堆栈的回溯求解本题的基本算法是回溯，而基于堆栈的回溯可以使人思路更求解本题的基本算法是回溯，而基于堆栈的回溯可以使人思路更为清晰。其基本思路如所示，把对迷宫的搜索，看成一棵搜索树的生成为清晰。其基本思路如所示，把对迷宫的搜索，看成一棵搜索树的生成过程：过程：（1）首先将根节点（入口处）压入堆栈；）首先将根节点（入口处）压入堆栈；（2） 按照下面的规则考察栈顶节点（图中灰色
30、节点）的可扩展按照下面的规则考察栈顶节点（图中灰色节点）的可扩展性（即前面还有路可走），直到找到一个解或得出无解（堆栈空性（即前面还有路可走），直到找到一个解或得出无解（堆栈空即即返回到入口）的结论为止：返回到入口）的结论为止： 可扩展，则将下一层的各个可能的节点按照某种顺序（如顺时可扩展，则将下一层的各个可能的节点按照某种顺序（如顺时针）压入堆栈；针）压入堆栈； 不可扩展，则将栈顶节点弹出（图中黑色的节点），继续考察不可扩展，则将栈顶节点弹出（图中黑色的节点），继续考察下一个节点。这下一个节点可能是同层的兄弟节点，也可能是一个上层下一个节点。这下一个节点可能是同层的兄弟节点，也可能是一个上层
31、节点（回溯）。节点（回溯）。(f) (f) 节点节点(1,5)(1,5)，(1,4)(1,4)都不可再扩都不可再扩展，被依次弹出展，被依次弹出(2,1)(2,1)SPSP(1,1)(1,1)(1,2)(1,2)(1,3)(1,3)(2,3)(2,3)(2,3)(1,1)(1,3)(5,3)(5,3)(e) (e) 节点节点(5.1)(5.1)不可扩展，被不可扩展，被弹出弹出(a) (a) 在栈在栈中压入根中压入根节点节点(b) (b) 扩展节点扩展节点(1,1)(1,1)， 压入两压入两个节点个节点(c) (c) 扩展节点扩展节点(2,1)(2,1)， 压入一压入一个节点个节点(d) (d)
32、扩展节点扩展节点(5,2)(5,2)，压入节，压入节点点(5,3)(5,1)(5,3)(5,1)(1,2)(1,2)SPSP(1,1)(1,1)(2,1)(2,1)(1,1)(1,1)SPSP(1,2)(1,2)SPSP(1,1)(1,1)(2,1)(2,1)(3,1)(3,1)(1,2)(1,2)(5,3)(5,3)SPSP(1,1)(1,1)(2,1)(2,1)(3,1)(3,1)(3,2)(3,2)(4,2)(4,2)(5,3)(5,3)(1,2)(1,2)SPSP(1,1)(1,1)(2,1)(2,1)(5,1)(5,1)(3,1)(3,1)(3,2)(3,2)(4,2)(4,2)(5
33、,2)(5,2)(1,1)(1,1)(2,1)(1,2)(1,1)(2,1)(3,1)(1,1)(4,2)(5,2)(1,1)(4,2)(5,2)(1,5)(2,5)(1,4)图图4.8 基于堆栈的回溯算法基于堆栈的回溯算法与克里特算法相比与克里特算法相比（1）往栈中压入一个节点，就说明该节点可达，相当）往栈中压入一个节点，就说明该节点可达，相当于铺了第于铺了第1条线。为了避免以后对该点重复压入，应在条线。为了避免以后对该点重复压入，应在压入的同时，将该节点的置压入的同时，将该节点的置1，即只压入节点值为，即只压入节点值为0的节的节点。点。（2）将栈顶节点弹出，说明该节点是死节点，相当于）将栈
34、顶节点弹出，说明该节点是死节点，相当于铺了第铺了第2条线。为了将来能在迷宫矩阵中表明该点已经条线。为了将来能在迷宫矩阵中表明该点已经被探索过，将其置一个特殊的数被探索过，将其置一个特殊的数3。2. 定义数据结构定义数据结构基于栈的迷宫探索，需要建立两种基本的数据结构：基于栈的迷宫探索，需要建立两种基本的数据结构： 表示迷宫的数据结构表示迷宫的数据结构这在前面已经介绍过了，就是用矩阵（二维数这在前面已经介绍过了，就是用矩阵（二维数组）表示。组）表示。 用于回溯控制的数据结构用于回溯控制的数据结构堆栈。堆栈。这里首先考虑如何建立基于数组的堆栈。这里首先考虑如何建立基于数组的堆栈。（1）模拟迷宫的数
35、据结构）模拟迷宫的数据结构int maze7=2,2,2,2,2,2,2, 2,0,0,0,0,0,2, 2,0,2,0,2,0,2, 2,0,0,2,0,2,2, 2,2,0,2,0,2,2, 2,0,0,0,0,0,2, 2,2,2,2,2,2,2;int Si=1,Sj=1,Ei=5,Ej=5;/* 入口与出口入口与出口 */（2）迷宫中某个节点的表示和探索栈）迷宫中某个节点的表示和探索栈/*在函数中表示在函数中表示*/#define N 100typedef struct Node int x,y; /* 节点位置节点位置 */ int nodeState; /* 节点状态节点状态 *
36、/MAZE_NODE;typedef struct ExploreStack MAZE_NODE explStackN; /*数组栈数组栈*/EXP_STACK;3. 算法设计初步算法设计初步（1）扩展栈顶节点的算法）扩展栈顶节点的算法void mazeExpand(EXP_STACK *s )获取栈顶节点在迷宫中的坐标获取栈顶节点在迷宫中的坐标x,y;if(探索栈空探索栈空)printf(“此迷宫找不到出口，探索过程如下：此迷宫找不到出口，探索过程如下：)；return;else if(栈顶节点位于出口栈顶节点位于出口)printf(“探察结束，探察过程如下：探察结束，探察过程如下：“)；r
37、eturn;elseif(死点死点)置以死点标记置以死点标记,重新获取栈顶节点进行拓展；重新获取栈顶节点进行拓展；else 先将此节点压栈先将此节点压栈;将此节点周围值为将此节点周围值为0（不是墙以及未压过栈）的节点压栈，同时将它们的置（不是墙以及未压过栈）的节点压栈，同时将它们的置1；重新获取栈顶节点进行拓展；重新获取栈顶节点进行拓展；程序框架程序框架（2）程序框架）程序框架定义迷宫矩阵为静态数组定义迷宫矩阵为静态数组定义入口、出口坐标定义入口、出口坐标定义探索栈定义探索栈定义栈的压入函数定义栈的压入函数定义栈的弹出函数定义栈的弹出函数定义栈顶节点扩展函数定义栈顶节点扩展函数定义迷宫矩阵打印
38、函数定义迷宫矩阵打印函数void main()从入口节点开始调用栈顶节点扩展函数；从入口节点开始调用栈顶节点扩展函数；调用迷宫矩阵打印函数；调用迷宫矩阵打印函数；4. 程序设计程序设计（1）push操作和操作和pop操作操作/*在函数中在函数中*/int top=-1;EXP_STACK *s;MAZE_NODE *pop(EXP_STACK *s) /*pop操作操作*/ MAZE_NODE *npop; if(top =-1) printf(stack underflow!); exit(-1); else *npop=(*s).explStacktop; top = top -1; re
39、turn npop; （1）push操作和操作和pop操作（续）操作（续）/*在函数中在函数中*/int top=-1;EXP_STACK *s;MAZE_NODE *pop(EXP_STACK *s) /*pop操作操作*/ MAZE_NODE *npop; if(top =-1) printf(stack underflow!); exit(-1); else *npop=(*s).explStacktop; top = top -1; return npop; （2）栈顶节点扩展函数设计）栈顶节点扩展函数设计/*在函数中在函数中*/int Ei=5,Ej=5; /* 判断是为出口判断是为
40、出口*/void mazeExpand(MAZE_NODE *old) extern maze7; /* 引用性声明引用性声明*/ MAZE_NODE *new1; int i,j; MAZE_NODE end; end.x=Ei; /* 出口的设置出口的设置*/ end.y=Ej; end.nodeState=0; if(top =-1) /* 探索栈空探索栈空*/ printf(n此迷宫找不到出口，探索过程如下：此迷宫找不到出口，探索过程如下：n); return; （2）栈顶节点扩展函数设计（续）栈顶节点扩展函数设计（续） else if(*old).x=end.x&(*old).y=e
41、nd.y) /* 判断是否为出判断是否为出口口*/ printf(n探察结束，探察过程如下：探察结束，探察过程如下：n); return; else i=(*old).x; /* 取出其点的位置取出其点的位置*/ j=(*old).y; if(mazei-1j=2 & mazeij+1=2 & mazei+1j=2) /* 本节点为死点：状态置为本节点为死点：状态置为2，并扩展新栈顶节点，并扩展新栈顶节点 */ (*old).nodeState=2; mazeij=2;mazeExpand(pop(s);return;（2）栈顶节点扩展函数设计（续）栈顶节点扩展函数设计（续）else if(m
42、azeij+1=2 & mazei+1j=2 & mazeij-1=2) (*old).nodeState=2; mazeij=2;mazeExpand(pop(s);return; else if(mazei+1j=2 & mazeij-1=2 & mazei-1j=2) (*old).nodeState=2; mazeij=2;mazeExpand(pop(s);return; else if(mazeij-1=2 & mazei-1j=2 & mazeij+1=2) (*old).nodeState=2; mazeij=2;mazeExpand(pop(s);return;（2）栈顶节点
43、扩展函数设计（续）栈顶节点扩展函数设计（续）else mazeij=1;push(old);/* 不是死点不是死点,则压入栈则压入栈 */ /*针对不同情况，分别进行处理压栈针对不同情况，分别进行处理压栈*/if(mazei-1j=0) (*new1).x=i-1; (*new1).y=j; (*new1).nodeState=1; mazei-1j=1; push(new1);if(mazeij+1=0) (*new1).x=i; (*new1).y=j+1; (*new1).nodeState=1; mazeij+1=1; push(new1); （2）栈顶节点扩展函数设计（续）栈顶节点扩
44、展函数设计（续）if(mazei+1j=0) (*new1).x=i+1; (*new1).y=j; (*new1).nodeState=1; mazei+1j=1; push(new1); if(mazeij-1=0) (*new1).x=i; (*new1).y=j-1; (*new1).nodeState=1; mazeij-1=1; push(new1); /*else*/ mazeExpand(pop(s); /* 扩展新栈顶节点扩展新栈顶节点*/（3）输出函数）输出函数/*在函数中在函数中*/prnt() int i,j; printf(n); for(i=0;i=6;i+) fo
45、r(j=0;j=6;j+) printf(%d,mazeij); printf(n); 四、测试程序四、测试程序#include #include type.h#include stack.h#include expand.h#include print.hint maze7=2,2,2,2,2,2,2,2,0,0,0,0,0,2,2,0,2,0,2,0,2, 2,0,0,2,0,2,2,2,2,0,2,0,2,2,2,0,0,0,0,0,2,2,2,2,2,2,2,2; /* 初始化迷宫矩阵初始化迷宫矩阵 */int Si=1,Sj=1; /* 入口坐标入口坐标 */MAZE_NODE *s
46、tart;main() (*start).x=Si; (*start).y=Sj; /* 入口的初始化入口的初始化*/ (*start).nodeState=1; mazeSiSj=1; push(start); mazeExpand(start); /* 从入口节点开始调用栈顶节点扩展函数从入口节点开始调用栈顶节点扩展函数*/ prnt(); /*调用迷宫矩阵打印函数调用迷宫矩阵打印函数*/五、编程练习五、编程练习1. 三个猎人杂技团的三位训兽师带着三只猴子过河，只有一条最多三个猎人杂技团的三位训兽师带着三只猴子过河，只有一条最多只能乘二人的船，人猴体重相当，且猴子也会划船。在穿梭过河的过程
47、中，只能乘二人的船，人猴体重相当，且猴子也会划船。在穿梭过河的过程中，若留在岸上的猴子数多于人数，猴子就会逃跑。请为三位训兽师设计一个若留在岸上的猴子数多于人数，猴子就会逃跑。请为三位训兽师设计一个安全的渡河方案。安全的渡河方案。2. 自然数的拆分：任何一个大于自然数的拆分：任何一个大于1的自然数的自然数N，总可以拆分为若干个，总可以拆分为若干个自然数之和，并且有多种拆分方法。例如自然数自然数之和，并且有多种拆分方法。例如自然数5，可以有如下一些拆分，可以有如下一些拆分方法：方法：5=1+1+1+1+15=1+1+1+25=1+2+25=1+1+35=1+4（与（与5=4+1看成同一种拆分）看
48、成同一种拆分）5=2+3请设计一个对任意自然数，找出所有拆分方法的程序。请设计一个对任意自然数，找出所有拆分方法的程序。五、编程练习（续）五、编程练习（续）3. 机器设计问题：某机器由机器设计问题：某机器由n 个部件组成，每一个部件可从个部件组成，每一个部件可从3个投资个投资者那里获得。令者那里获得。令wij 是从投资者是从投资者j 那里得到的零件那里得到的零件i 的重量，的重量，cij 则为该零件则为该零件的耗费。编写一个回溯算法，找出耗费不超过的耗费。编写一个回溯算法，找出耗费不超过c的机器构成方案，使其重的机器构成方案，使其重量最少。量最少。4. 邮票问题：设想一个国家发行的几种面值不同
49、的邮票。若每个信邮票问题：设想一个国家发行的几种面值不同的邮票。若每个信封上至多只允许贴封上至多只允许贴m枚邮票。当邮资从枚邮票。当邮资从1开始，在增量为开始，在增量为1的情况下，请给的情况下，请给出可能获得的邮资值的最大连续区及获得此区域的各种面值的集合。如，出可能获得的邮资值的最大连续区及获得此区域的各种面值的集合。如，对于对于n=4，m=5，有面值，有面值(1，4，12，21)四种邮票。用回溯法求解本题。四种邮票。用回溯法求解本题。5. 控制方格棋盘游戏：如所示的控制方格棋盘游戏：如所示的55的方格棋盘，若在某一方格内放入一个黑子，的方格棋盘，若在某一方格内放入一个黑子，则与该方格相邻的
50、上、下、左、右则与该方格相邻的上、下、左、右4各方格各方格中都不可再放黑子。于是，在棋盘的中都不可再放黑子。于是，在棋盘的X个位个位置各放一个黑子，就可以控制整个棋盘。请置各放一个黑子，就可以控制整个棋盘。请设计在棋盘上放设计在棋盘上放7个黑子就可以控制整个棋个黑子就可以控制整个棋盘的所有方案。盘的所有方案。图图4.9 控制方格棋盘游戏控制方格棋盘游戏五、编程练习（续）五、编程练习（续）6. 魔板问题：魔板问题：Rubik先生发明了一种玩具，称为魔板。它由先生发明了一种玩具，称为魔板。它由8块同样大小块同样大小的方块组成，这的方块组成，这8个方块分别涂以不同的颜色或编号。它有个方块分别涂以不同
51、的颜色或编号。它有3种基本玩法，种基本玩法，以以图图4.10（a）为初始状态这为初始状态这3种玩法分别如种玩法分别如图图4.10（b）、（）、（c）、（）、（d）所示。应用三种基本操作，可以由一种状态到达另一种状态。所示。应用三种基本操作，可以由一种状态到达另一种状态。12348765（a）魔板的一个初始状态）魔板的一个初始状态12348765（b）上下行互换）上下行互换12348765（c）两行同时循环右移一格）两行同时循环右移一格12348765（d）中间）中间4块顺时针旋转一格块顺时针旋转一格图图4.10 4.10 魔板魔板 请编写一个程序，通过一系列基本操作，可以将魔板从原始状态请编写
52、一个程序，通过一系列基本操作，可以将魔板从原始状态变为一个输入的目标状态。变为一个输入的目标状态。五、编程练习（续）五、编程练习（续）7. 四色问题：在彩色地图中，相邻区块要用不同的颜色表示。那么四色问题：在彩色地图中，相邻区块要用不同的颜色表示。那么印制地图时，最少需要准备几种颜色就能达到相邻区块要用不同的颜色表印制地图时，最少需要准备几种颜色就能达到相邻区块要用不同的颜色表示的要求呢？一百多年前，英国的格色离提出了最少色数为示的要求呢？一百多年前，英国的格色离提出了最少色数为4的猜想（的猜想（4-colours conjecture）。为了证实这一猜想，许多科学家付出了艰巨的劳）。为了证实
53、这一猜想，许多科学家付出了艰巨的劳动，但一直没有成功。直到动，但一直没有成功。直到1976年，美国数学家年，美国数学家K.Appl和和M.Haken借助借助电子计算机才证明了这一猜想，并称之为四色定理。电子计算机才证明了这一猜想，并称之为四色定理。请按四色定理为所示地图进行着色。请按四色定理为所示地图进行着色。AKHBFCDEGJI图图4.11 4.11 一张地图一张地图4.3 贪心策略贪心策略v贪心策略（贪心策略（greedy method）是一种企图通过局部最优达到）是一种企图通过局部最优达到全局最优的策略，犹如登山，并非一开始就选择出一条到达全局最优的策略，犹如登山，并非一开始就选择出一
54、条到达山顶的最佳路线，而是首先在视力能及的范围内，看中一个山顶的最佳路线，而是首先在视力能及的范围内，看中一个高处目标，选择一条最佳路径；然后在新的起点上，再选择高处目标，选择一条最佳路径；然后在新的起点上，再选择一条往上爬的最佳路径；一条往上爬的最佳路径；企图通过每一阶段的最佳路；企图通过每一阶段的最佳路径，构造全局的最佳路径。也就是说，贪心策略总是不断地径，构造全局的最佳路径。也就是说，贪心策略总是不断地将原问题变成一个相似、而规模更小的问题，然后做出当前将原问题变成一个相似、而规模更小的问题，然后做出当前看似最好的看似最好的局部意义上的最优选择局部意义上的最优选择。v显然，贪心策略不能保
55、证对所有的问题求得的最后解都是最显然，贪心策略不能保证对所有的问题求得的最后解都是最优的，特别是不能用来求最大或最小解问题。但是许多情况优的，特别是不能用来求最大或最小解问题。但是许多情况下，用贪心策略可以得到最优解的接近结果。因此，初学者下，用贪心策略可以得到最优解的接近结果。因此，初学者应当通过分析和经验积累，了解哪些问题适合用贪心策略，应当通过分析和经验积累，了解哪些问题适合用贪心策略，并掌握如何选择合适的贪心策略。并掌握如何选择合适的贪心策略。4.3.1 旅行费用问题旅行费用问题一、问题描述一、问题描述一个游客要到如一个游客要到如图图4.124.12（a a）所示的所示的A A、B B
56、、C C、D D、E E五五个景点旅行。图中标出了五个景点之间的交通费用。试问，个景点旅行。图中标出了五个景点之间的交通费用。试问，该游客从该游客从A A出发，如何以最小费用走过每一个景点最后返回出发，如何以最小费用走过每一个景点最后返回A A？ AEDCB50308030201243103621图图4.12 （a）旅行费用拓扑）旅行费用拓扑二、解题策略二、解题策略 按照贪心策略，在局部寻优的过程可以用按照贪心策略，在局部寻优的过程可以用图图4.12（b）表示，得到的路径表示，得到的路径为为A-B-E-C-D-A，总费用为，总费用为10+30+20+12+80=152。显然，这一结果并非最优。
57、显然，这一结果并非最优。因为，最优路径为。因为，最优路径为A-B-E-D-C-A，总费用为，总费用为10+30+30+12+21=103。AEDCB50308030201243103621BAEDC501280302010 802130DC43E36CDDA第第1 1步，选择步，选择B B第第2 2步，选择步，选择E E第第3 3步，选择步，选择C C第第4 4步，选择步，选择D D（a）旅行费用拓扑）旅行费用拓扑（b）贪心法求解问题）贪心法求解问题图图4.12 旅行费用问题旅行费用问题程序框架程序框架1. 数据结构数据结构（1）费用网络描述）费用网络描述(用图的邻接矩阵的描述用图的邻接矩阵的
58、描述)：int expense4 = 0, 10, 21, 80, 50, 10, 0, 36, 43, 30, 21, 36, 0, 12, 20, 80, 43, 12, 0, 30 50, 30, 20, 30, 0;（2）定义枚举变量）定义枚举变量 enum scenesa,b,c,d,e;这样，就会形成如下对应关系：这样，就会形成如下对应关系：expenseab expense01 10expenseac expense02 21expensead expense03 80expensebc expense04 50expensebc expense12 36expensebd ex
59、pense13 43expenseae expense14 302. 贪心过程贪心过程初始化所有节点的费用标志；初始化所有节点的费用标志；设置出发节点设置出发节点V；for( i =1; i= n-1; i + +) s = 从从V至所有未曾到过的景点中费用最少的景点；至所有未曾到过的景点中费用最少的景点；累加费用；累加费用；V = s；/* 新的起点新的起点 */设置设置V的已访问标志；的已访问标志；最后一个景点返回第一个景点，累加费用；最后一个景点返回第一个景点，累加费用；三、程序的实现三、程序的实现#define N 5/*节点个数节点个数*/main() int expenseNN =
60、0,10,21,80,50, 10,0,36,43,30, 21,36,0,12,20, 80,43,12,0,30, 50,30,20,30,0; enum scenesa,b,c,d,e ; enum scenes v,s; enum scenes start,j; unsigned int sum=0,min; int flagN=0,0,0,0,0; int i; v=a;/*设置出发节点设置出发节点*/ start=v;三、程序的实现（续）三、程序的实现（续）for(i=1;i=N-1;i+) min=65535;/* 设置一个尽量大的值设置一个尽量大的值*/ for(j=a;j=N
61、-1;j+) if(flagj=0&expensevj!=0) if(expensevj0;j-)/* 逐一删除逐一删除n个数字个数字 */for(i=0;i*(digitStr+i+1)/* 存在递减空间存在递减空间 */striDel(digitStr,i);/* 删除第删除第i个数字个数字 */flag =1;break;if(flag= =0)/* 无递减空间无递减空间 */*（digitStr+(strlen(digitStr)-1)）=0;/* 删除最后数字删除最后数字 */删除第删除第i个数字的函数个数字的函数char *striDel(char *str,int i)*(str
62、+i)=0;return(strcat(str,str+i+1);四、说明四、说明一般来说，适合贪心策略的问题大多数具有两个特征：一般来说，适合贪心策略的问题大多数具有两个特征：（1）贪心选择性质）贪心选择性质贪心选择性质就是可以通过局部最优选择达到全局最优。贪心选择性质就是可以通过局部最优选择达到全局最优。这种局部选择可能依赖于已经作出的所有选择，但不依赖有待这种局部选择可能依赖于已经作出的所有选择，但不依赖有待于做的选择或子问题的解。例如本题中，当前要删除的数不依于做的选择或子问题的解。例如本题中，当前要删除的数不依赖于将来要删除的数，只考虑当前最优。赖于将来要删除的数，只考虑当前最优。（
63、2）最优子结构）最优子结构问题的最优解包含了子问题的最优解，称为最优子结构。问题的最优解包含了子问题的最优解，称为最优子结构。例如本题中的数例如本题中的数27685923，要删去，要删去4个数字，肯定要删去个数字，肯定要删去768和和9。而采用贪心策略时，要依次删去。而采用贪心策略时，要依次删去7、8、6、9。即问题的最优解包含了。即问题的最优解包含了4个子问题的解。个子问题的解。五、程序及其测试五、程序及其测试1. 程序程序#include #include char *striDel(char *str,int i);void getMinInteger(char * digitStr,i
64、nt n);void getMinInteger(char * digitStr,int n)int i,j,flag=0;char * strTemp;for(j=n;j0;j-)/* 逐一删除逐一删除n个数字个数字 */flag=0;for(i=0;i*(digitStr+i+1)/* 存在递减空间存在递减空间 */striDel(digitStr,i); /* 删除第删除第i个数字个数字 */flag =1;break;if(flag=0)/* 无递减空间无递减空间 */*(digitStr+(strlen(digitStr)-1)=0;/* 删除最后数字删除最后数字 */程序（续）程序
65、（续）/*删除第删除第i个数字的函数个数字的函数*/char *striDel(char *str,int i)*(str+i)=0;return(strcat(str,str+i+1);main( )char *digitStr;int n;printf(请输入一个数字串：请输入一个数字串：);scanf(%s,digitStr);printf(请输入需删除数字个数：请输入需删除数字个数：);scanf(%d,&n);getMinInteger(digitStr,n);printf(%s,digitStr);2. 测试结果测试结果（1）测试）测试1请输入一个数字串：请输入一个数字串：8976
66、54请输入需删除数字个数：请输入需删除数字个数：3654（2）测试）测试2请输入一个数字串：请输入一个数字串：456789请输入需删除数字个数：请输入需删除数字个数：24567六、编程练习六、编程练习1. 输入一个数字串（位数小于输入一个数字串（位数小于200），在其中添入），在其中添入m（m小于小于20）个加）个加号，使其值最小。号，使其值最小。2. 汽车加油问题：某汽车加满一次油后可以行驶汽车加油问题：某汽车加满一次油后可以行驶n公里路程。某次旅行公里路程。某次旅行的总路程为的总路程为s公里，并且该路程中共有公里，并且该路程中共有m个加油站。个加油站。要求：沿途加油次数最少。要求：沿途加油
67、次数最少。输入：每个加油站距出发点的距离。输入：每个加油站距出发点的距离。输出：汽车加油的加油站序列号。输出：汽车加油的加油站序列号。六、编程练习（续）六、编程练习（续）3. 机器调度问题：现有机器调度问题：现有N项任务和无限多台机器。任务可以在机器上处项任务和无限多台机器。任务可以在机器上处理。每件任务开始时间和完成时间如所示。理。每件任务开始时间和完成时间如所示。在可行分配中每台机器在任何时刻最多处理一个任务。最优分配是在可行分配中每台机器在任何时刻最多处理一个任务。最优分配是指使用的机器最少的可行分配方案。请就本题给出的条件，求出最优分配。指使用的机器最少的可行分配方案。请就本题给出的条
68、件，求出最优分配。提示：一种获得最优分配的贪婪方法是逐步分配任务。每步分配一提示：一种获得最优分配的贪婪方法是逐步分配任务。每步分配一件任务，且按任务开始时间的非递减次序进行分配。若已经至少有一件任务件任务，且按任务开始时间的非递减次序进行分配。若已经至少有一件任务分配给某台机器，则称这台机器是旧的；若机器非旧，则它是新的。在选择分配给某台机器，则称这台机器是旧的；若机器非旧，则它是新的。在选择机器时，采用以下贪婪准则：根据欲分配任务的开始时间，若此时有旧的机机器时，采用以下贪婪准则：根据欲分配任务的开始时间，若此时有旧的机器可用，则将任务分给旧的机器。否则，将任务分配给一台新的机器。器可用，
69、则将任务分给旧的机器。否则，将任务分配给一台新的机器。如所示，根据本题中的数据，贪婪算法共分为如所示，根据本题中的数据，贪婪算法共分为n = 7步，任务分配的步，任务分配的顺序为顺序为a、f、b、c、g、e、d。第一步没有旧机器，因此将。第一步没有旧机器，因此将a 分配给一台新分配给一台新机器（比如机器（比如M1）。这台机器在）。这台机器在0到到2时刻处于忙状态。在第二步，考虑任务时刻处于忙状态。在第二步，考虑任务f。由于当由于当f 启动时旧机器仍处于忙状态，因此将启动时旧机器仍处于忙状态，因此将f 分配给一台新机器分配给一台新机器(设为设为M2 )。第三步考虑任务第三步考虑任务b， 由于旧机
70、器由于旧机器M1在在Sb = 3时刻已处于闲状态，因此将时刻已处于闲状态，因此将b分分配给配给M1执行，执行，M1下一次可用时刻变成下一次可用时刻变成fb = 7，M2的可用时刻变成的可用时刻变成ff = 5。第。第四步，考虑任务四步，考虑任务c。由于没有旧机器在。由于没有旧机器在Sc = 4时刻可用，因此将时刻可用，因此将c 分配给一台分配给一台新机器（新机器（M3），这台机器下一次可用时间为），这台机器下一次可用时间为fc = 7。第五步考虑任务。第五步考虑任务g，将，将其分配给机器其分配给机器M2，第六步将任务，第六步将任务e 分配给机器分配给机器M1, 最后在第七步，任务最后在第七步，
71、任务2分分配给机器配给机器M3。（注意：任务。（注意：任务d 也可分配给机器也可分配给机器M2）。）。任务任务abcdefg开始开始(si)0349716完成完成(fi)277111058表表4.1 机器调度问题的一组数据机器调度问题的一组数据图图4.14 机器调度问题的一组解机器调度问题的一组解4.4 分枝界定策略分枝界定策略v分枝定界（branch and bound）是一种缩小搜索解空间、加速搜索进程的方法。在搜索问题的解空间树时，它给每一个活节点只有一次机会成为扩展节点。活节点一旦成为扩展节点就一次性产生其所有的儿子节点。但是，并不把所有儿子节点都加入活节点表中，要把导致不可行解或非最
72、优解的儿子节点舍弃（剪枝），把剩下的儿子节点加入活节点表中。然后，从活节点表中取下一个节点进行上述扩展操作。如此继续，直到找到要求的解或活节点表为空。v使用分枝定界法的关键点使用分枝定界法的关键点（1）扩展一个活节点时，如何决定将哪些儿子节点舍弃。方法是在每一）扩展一个活节点时，如何决定将哪些儿子节点舍弃。方法是在每一个活节点处，计算一个函数值（界限），并根据函数值来选择导致不可个活节点处，计算一个函数值（界限），并根据函数值来选择导致不可行或非最优解的儿子节点舍弃。行或非最优解的儿子节点舍弃。（2）如何从活节点表中选择下一个扩展节点。最常见的方法有两种：）如何从活节点表中选择下一个扩展节点。
73、最常见的方法有两种： 将活节点组织成一个队列，按照将活节点组织成一个队列，按照FIFO（先进先出）的原则选取（先进先出）的原则选取下一个扩展节点。这种方法称为队列式（下一个扩展节点。这种方法称为队列式（FIFO）分枝定界法。）分枝定界法。 将活节点组织成一个优先队列，按照优先顺序选取下一个扩展将活节点组织成一个优先队列，按照优先顺序选取下一个扩展节点。这种方法称为优先队列式分枝定界法或节点。这种方法称为优先队列式分枝定界法或LC分枝定界法。分枝定界法。FIFO分枝定界法采用队列组织活节点进行广度优先搜索，同时剪分枝定界法采用队列组织活节点进行广度优先搜索，同时剪除不可行节点为根的子树。除不可行
74、节点为根的子树。LC分枝定界法常用一个与节点相关的数值分枝定界法常用一个与节点相关的数值p表表示节点的优先级，并采用堆组织优先队列。示节点的优先级，并采用堆组织优先队列。4.4.1 最小耗费问题最小耗费问题一、问题一、问题如所示的城市间交通路线图。图中的有向边上的数如所示的城市间交通路线图。图中的有向边上的数字表示从起点城市到终止点城市的交通费用。求字表示从起点城市到终止点城市的交通费用。求A到到E的最的最小耗费。小耗费。B3AB1C1C2C3D1D2E5836792576423图图4.15 最小耗费问题最小耗费问题二、二、FIFO分枝定界算法框架分枝定界算法框架miniCost() /* 用
75、用FIFO分枝定界法进行搜索分枝定界法进行搜索 */取出队列头节点取出队列头节点;for( ; ; ) /* 搜索问题的解空间搜索问题的解空间 */if(两节点可达两节点可达) if(满足控制约束满足控制约束) 更新此节点的状态，加入各点状态队列更新此节点的状态，加入各点状态队列else舍弃当前扩展路径舍弃当前扩展路径 if ( 到达终点到达终点)return;else miniCost(); /* 递归搜索子问题的解空间递归搜索子问题的解空间*/三、程序描述三、程序描述1. 费用单源矩阵的描述费用单源矩阵的描述 int cost89= /* 费用数组费用数组 */0,5,8,0,0,0,0,
76、0,0,0,0,0,3,2,6,0,0,0,0,0,0,0,9,7,0,0,0,0,0,0,0,0,0,5,0,0,0,0,0,0,0,0,4,6,0,0,0,0,0,0,0,0,7,0,0,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,3;2. 节点的数据结构节点的数据结构/*在中在中*/typedef struct Node int x; /* 节点的当前位置节点的当前位置 */ int length;/* 节点到始点的长度（费用）节点到始点的长度（费用） */COST_NODE;COST_NODE path100;3. pop操作和操作和push操作操作/*在中在中*/
77、COST_NODE pop() COST_NODE enode; if(startend) printf(nstack overflow!_popn); exit(-1); else enode=pathstart; start = start+1; return enode; void push(COST_NODE enode) if(end = 10) printf(nstack overflow!_pushn); exit(-1); else end = end +1;pathend=enode; 4. 分枝限定法搜索算法分枝限定法搜索算法/*在在miniCost.h中中*/miniCo
78、st() COST_NODE node;int i,j;node=pop();i=node.x;for(j=0;j0) /*两节点是否可达两节点是否可达*/if(node.length+costij0;i-，j+)orderj=prei;i=prei+1;printf(nThe order(起点城市到终止点城市的最低的交通费用起点城市到终止点城市的最低的交通费用) is :);for(i=0;i,orderj-i-1);printf(8.n);四、程序测试四、程序测试1. 测试程序测试程序#include #define MAX 1000 /* 设定各边上的最大值设定各边上的最大值 */int
79、 dist9; /* 临时存放始点费用临时存放始点费用*/int pre9; /* 存放前向节点的变量存放前向节点的变量 */int start=-1,end=-1; /* 队列的开始与结尾队列的开始与结尾 */int cost89= /* 费用数组费用数组 */0,5,8,0,0,0,0,0,0,0,0,0,3,2,6,0,0,0,0,0,0,0,9,7,0,0,0,0,0,0,0,0,0,5,0,0,0,0,0,0,0,0,4,6,0,0,0,0,0,0,0,0,7,0,0,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,3;#include type.h#include
80、stack_do.h#include miniCost.h#include print.h1. 测试程序（续）测试程序（续）void main()int i;COST_NODE node; for(i=0;i0,Wj0, j=1,2,，N)2. 子问题划分子问题划分物品是一件一件地放入背包的。设物品是一件一件地放入背包的。设Fk(y)为放入前为放入前k件物品、总重量件物品、总重量为为y时所得到的最大价值，即有：时所得到的最大价值，即有： 于是，定义了不同于是，定义了不同k的子问题。的子问题。F0(y)=0 （没有选物品时，总价值为（没有选物品时，总价值为0） Fk(0)=0 （限定总重量为（限
81、定总重量为0时，所选物品的总值为时，所选物品的总值为0）F1(y)=y/w1v1 Fk(y)=max（vjxj ） (0kN)kj=1wjxj =y (0yB)kj=13. 递推关系递推关系Fk（y）= max（Fk-1(y), Fk(y-wk)+vk）三、动态规划算法设计三、动态规划算法设计1. 用动态规划方法装背包的算法用动态规划方法装背包的算法#define MAX_CHOICE 16#define MAX_CAPACITY 16typedef int CHOICEMAX_CHOICE;void selection_to_maxvalue(CHOICE c)/*选择物品选择物品*/int
82、 j,k,temp;int row=0,other_row=1;int v2MAX_CAPACITY,trace2MAX_CAPACITY;for(j=0;jN;j+) cj=0;/*置初值，物品均未选中置初值，物品均未选中*/for(j=0;j=B;j+)tracerowj=-1;vrowj=0;算法（续）算法（续）vother_row0=0;for(k=0;kN;k+)temp=other_row;other_row=row;row=temp;for(j=1;jweightk;j+)vrowj=vother_rowj;tracerowj=traceother_rowj;算法（续）算法（续）
83、 /*max（Fk-1(y), Fk(y-wk)+vk），找较大的价值），找较大的价值*/for(j=weightk;j=B;j+)temp=vrowj-weightk+vv1k;if(vother_rowj-1)cj=cj+1;temp=temp-weightj;if(temp0)j=tracerowtemp;elsej=-1;2. 输出函数输出函数void print_result(CHOICE c)int j;printf(nThe selections:n);for(j=0;jN;j+)printf(Item %d=%dn,j,cj);printf(The maximum total
84、value:%d,total_value);四、测试函数四、测试函数#include #define N 3/* 物品个数物品个数 */#define B 6/* 约束条件约束条件 */CHOICE vv1=1,2,5;/* 物品的价值物品的价值 */CHOICE weight=2,3,4; /* 物品的重量物品的重量 */CHOICE package;/*物品是否选中标志物品是否选中标志*/int total_value;/* 最大价值最大价值 */void main(int argc, char *argv)int i;selection_to_maxvalue(package);prin
85、tf(The capacity of knapsack:%dn,B);printf(The number of choices:%dn,N);printf(The weight of the item:n);for(i=0;iN;i+)printf(%4d,weighti);printf(nThe value of the items:n);for(i=0;iN;i+)printf(%4d,vv1i);print_result(package);测试结果测试结果The capacity of knapsack:6The number of choices:3The weight of the
86、item: 2 3 4The value of the items: 1 2 5The selections:Item 0=1Item 1=0Item 2=1The maximum total value:6五、说明五、说明v动态规划的最优化概念是在一定条件下，找到一种途径，在动态规划的最优化概念是在一定条件下，找到一种途径，在对各阶段的效益经过按问题具体性质所确定的运算以后，使对各阶段的效益经过按问题具体性质所确定的运算以后，使得全过程的总效益达到最优。应用动态规划应当注意如下一得全过程的总效益达到最优。应用动态规划应当注意如下一些事项：些事项：（1）阶段的划分是动态规划的关键，必须依据题意
87、分析，寻求合理的划）阶段的划分是动态规划的关键，必须依据题意分析，寻求合理的划分阶段分阶段(子问题子问题)方法。方法。（2）在动态规划程序设计中，主要利用了问题的两个性质：最优子结构）在动态规划程序设计中，主要利用了问题的两个性质：最优子结构和子问题重叠。和子问题重叠。（3）变量不可太多，否则会使问题无法求解。）变量不可太多，否则会使问题无法求解。（4）最优化原理应在子问题求解中体现。）最优化原理应在子问题求解中体现。（5）有些问题也允许顺推。）有些问题也允许顺推。（6）动态规划是一个非常高效的算法，但是对于一些问题它并不是一个）动态规划是一个非常高效的算法，但是对于一些问题它并不是一个理想的
88、算法，其原因很多。理想的算法，其原因很多。六、编程练习六、编程练习v用动态规划方法求解下列问题。用动态规划方法求解下列问题。1. 交通费用问题：交通费用问题：图图4-18表示城市之间的交通路网，线段上的数字表示表示城市之间的交通路网，线段上的数字表示费用。试用动态规划的最优化原理求出单向通行由费用。试用动态规划的最优化原理求出单向通行由AE的最省费用。图的最省费用。图中，有向边上的数字，表示从前一个城市到后一个城市的费用（决策）；中，有向边上的数字，表示从前一个城市到后一个城市的费用（决策）；B1、B2、B3，C1、C2、C3，D1、D2分别为由分别为由A到到B，B到到C，C到到D几几种不同决
89、策结果。种不同决策结果。B3AB1B2C1C2C3D1D2EABCDE第第4阶段阶段第第3阶段阶段第第2阶段阶段第第1阶段阶段9733461655710324536图图4-18 最小费用问题最小费用问题v提示提示这个问题是一个多阶段决策问题：从这个问题是一个多阶段决策问题：从A到到E共分为共分为4个阶段：第一个阶段：第一阶段从阶段从A到到B，第二阶段从，第二阶段从B到到C，第三阶段从，第三阶段从C到到D，第四阶段从，第四阶段从D到到E。除起点除起点A和终点和终点E外，各点既是上一阶段的终点又是下一阶段的起点。例外，各点既是上一阶段的终点又是下一阶段的起点。例如从如从A到到B的第一阶段中，的第一
90、阶段中，A为起点，终点有为起点，终点有B1、B2、B3三个，因而这三个，因而这时决策（走的路线）有三个选择：一是走到时决策（走的路线）有三个选择：一是走到B1，一是走到，一是走到B2，一是走到，一是走到B3。若选择。若选择B2的决策，的决策，B2就是第一阶段决策的结果，它既是第一阶段行就是第一阶段决策的结果，它既是第一阶段行动（走的路线）的结果，又是第二阶段决策（走的路线）的起始状态。动（走的路线）的结果，又是第二阶段决策（走的路线）的起始状态。在第二阶段，再从在第二阶段，再从B2点出发，对于点出发，对于B2点就有一个可供选择的终点集合点就有一个可供选择的终点集合(C1，C2，C3)；若选择由
91、；若选择由B2走至走至C2为第二阶段的决策，则为第二阶段的决策，则C2就是第二就是第二阶段的终点，同时又是第三阶段的始点。同理递推下去，可看到各个阶阶段的终点，同时又是第三阶段的始点。同理递推下去，可看到各个阶段的决策不同，线路就不同，费用也不同。很明显，当某阶段的起点给段的决策不同，线路就不同，费用也不同。很明显，当某阶段的起点给定时，它直接影响着后面各阶段的行进路线和整个路线的长短，而后面定时，它直接影响着后面各阶段的行进路线和整个路线的长短，而后面各阶段的路线的发展不受这点以前各阶段的影响。故此问题的要求是：各阶段的路线的发展不受这点以前各阶段的影响。故此问题的要求是：在各个阶段选取一个
92、恰当的决策，使由这些决策组成的一个决策序列所在各个阶段选取一个恰当的决策，使由这些决策组成的一个决策序列所决定的一条路线，其总路程最短。决定的一条路线，其总路程最短。本题是一个最优问题，要求由本题是一个最优问题，要求由AE的最优决策。根据最优化原的最优决策。根据最优化原理，在多阶段决策中，无论过程的初始状态和初始决策是什么，其余的理，在多阶段决策中，无论过程的初始状态和初始决策是什么，其余的决策必须相对于初始决策所产生的状态搞成一个最优决策序列。对于本决策必须相对于初始决策所产生的状态搞成一个最优决策序列。对于本题来说，要求题来说，要求AE的最优包含的最优包含BE的最优，的最优，BE的最优包含
93、的最优包含CE的最的最优，优，CE的最优包含的最优包含DE的最优。因此，解题的决策过程应当从的最优。因此，解题的决策过程应当从E开始开始倒推，并分成四个阶段，即四个子问题。策略是每个阶段到倒推，并分成四个阶段，即四个子问题。策略是每个阶段到E的最省费用的最省费用为本阶段的决策路径。为本阶段的决策路径。v决策过程决策过程（1）第）第1阶段阶段输人节点输人节点D1、D2。它们到。它们到E都只有一种费用，分别为都只有一种费用，分别为5、2。但这时尚无法确定它们之中哪一个将在全程最优策略的路径上，但这时尚无法确定它们之中哪一个将在全程最优策略的路径上，因而第因而第2阶段计算中，阶段计算中，5、2都应分
94、别参加计算。都应分别参加计算。（2）第）第2阶段阶段输人节点输人节点C1、C2、C3。它们到。它们到D1、D2各有两种费用。此各有两种费用。此时应计算时应计算C1、C2、C3分别到分别到E的最少费用。的最少费用。C1的决策是：的决策是：min（C1D1，C1D2）= min (7+5,10+3)=12；路径：；路径：C1+D1+E。C2的决策是：的决策是：min（C2D1，C2D2）= min (4+5,2+3)=5；路径：；路径：C2+D2+E。C3的决策是：的决策是：min（C3D1，C3D2）= min (6+5,3+3)=6；路径：；路径：C3+D2+E。此时也无法定下第一、二阶段的城
95、市那二个将在整体的最此时也无法定下第一、二阶段的城市那二个将在整体的最优决策路径上。优决策路径上。（3）第）第3阶段阶段输人节点输人节点B1、B2、B3。决策输出节点可能为。决策输出节点可能为C1、C2、C3。仿前计。仿前计算可得算可得Bl、B2、B3的决策路径为如下情况。的决策路径为如下情况。Bl的决策是：的决策是：min（B1C1,B1C2,B1C3）= min (6+12,5+5,1+6)=7；路径路径:B1+C3+D2+E。B2的决策是：的决策是：min（B2C1,B2C2）= min (4+12,3+5)=8；路径；路径:B2+C2+D2+E。B3的决策是：的决策是：min（B3C2
96、,B3C3）= min (5+5,6+6)=10；路径；路径:B3+C2+D2+E。此时也无法定下第一、二、三阶段的城市那三个将在整体的最优决策路径上。此时也无法定下第一、二、三阶段的城市那三个将在整体的最优决策路径上。（4）第）第4阶段阶段输人节点输人节点A，决策输出节点可能为，决策输出节点可能为B1、B2、B3。同理可得决策路径。同理可得决策路径为：为：min（AB1,AB2,AB3）= min (9+7,7+8,3+10)=13；路径；路径:A+B3+C2+D2+E。此时才最终确定每个子问题的节点中，那一个节点被包含在最优费用此时才最终确定每个子问题的节点中，那一个节点被包含在最优费用的
97、路径上，并得到最小费用的路径上，并得到最小费用13。按照上述解题策略，子问题的决策中，只对同一城市（节点）比较优按照上述解题策略，子问题的决策中，只对同一城市（节点）比较优劣。而同一阶段的城市（节点）的优劣要由下一个阶段去决定。劣。而同一阶段的城市（节点）的优劣要由下一个阶段去决定。六、编程练习（续）六、编程练习（续）2. 数的拆分问题：计算将整数数的拆分问题：计算将整数n（6n200）拆分成）拆分成k（2k6）份的）份的方案数，要求：方案数，要求：（1）每种拆分方案不能为空。）每种拆分方案不能为空。（2）任意两种拆分方案不能相同（不考虑顺序）任意两种拆分方案不能相同（不考虑顺序1,1,5;
98、1,5,1; 5,1,1被认被认为是同一方案）。为是同一方案）。例如：例如：输入：输入：7，3输出：输出：4（四种拆分为：（四种拆分为：1、1、5; 1、2、4; 1、3、3; 2、2、3）。）。3.砝码称重问题：设有砝码称重问题：设有1g、2g、3g、5g、10g、20g的砝码各有若的砝码各有若干，它们的总重不超过干，它们的总重不超过1000g。给定一组。给定一组1g、2g、3g、5g、10g、20g砝砝码的个数码的个数a1、a2、a3、a4、a5、a6，要求输出能称出的不同重量的个数。，要求输出能称出的不同重量的个数。例如：例如：输入：输入：1、1、0、0、0、0输出：输出： total=
99、3，可以称出，可以称出 1g、2g、3g三种不同的重量。三种不同的重量。六、编程练习（续）六、编程练习（续）4. 电路板的设计：如所示，一块电路板的上、下两端各有电路板的设计：如所示，一块电路板的上、下两端各有n个接线柱，在制个接线柱，在制作电路板时要用作电路板时要用n条连线将上排接线柱与下排的一个接线柱连接。条连线将上排接线柱与下排的一个接线柱连接。在制作电路板时，要遵循如下原则：在制作电路板时，要遵循如下原则： 将将n条连线分布到若干层绝缘层上，使同一层中的连线不相交。条连线分布到若干层绝缘层上，使同一层中的连线不相交。 要确定哪些连线安排在第要确定哪些连线安排在第1层，使该层布置尽可能多的连线。层，使该层布置尽可能多的连线。提示：提示：（1）可以将导线按照上端的接线柱命名，如导线（）可以将导线按照上端的接线柱命名，如导线（i，(i)）称为该电路板）称为该电路板上的第上的第i条连线，用于连接上端的接线柱条连线，用于连接上端的接线柱i和下端的接线柱和下端的接线柱(i)（1in）。）。（2）对于任何两条连线）对于任何两条连线i和和j（1 (j)。1234567891012345678910图图4.19 电路板接线柱的连接电路板接线柱的连接
