第4章 算法设计战略v4.1 分治战略 v4.2 回溯战略v4.3 贪婪战略v4.4 分枝界定战略v4.5 动态规划算法设计战略4.1 分治战略分治战略 任何一个可以用计算机求解的问题所需的计算时间都与其任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。直接求解一个规模较大的问题，往往是相当困难的。规模有关。直接求解一个规模较大的问题，往往是相当困难的。但是当问题的规模减少到一定程度时，一个量变到量变的景象但是当问题的规模减少到一定程度时，一个量变到量变的景象就能够发生，问题的求解变得比较容易。这时，假设能找到小就能够发生，问题的求解变得比较容易。这时，假设能找到小规模的该类问题与大规模的该类问题之间的关系，就可以运用规模的该类问题与大规模的该类问题之间的关系，就可以运用分治战略对大规模的问题进展求解了。分治战略对大规模的问题进展求解了。 分治法所能处理的问题普通具有以下几个特征：分治法所能处理的问题普通具有以下几个特征：1该问题可以分解为假设干个规模较小的一样问题。该问题可以分解为假设干个规模较小的一样问题。 2各个子问题相互独立，子问题之间不包含公共的各个子问题相互独立，子问题之间不包含公共的子子问题。子子问题。3该问题的规模减少到一定的程度可以容易地求解。该问题的规模减少到一定的程度可以容易地求解。4利用该问题分解出的子问题的解可以合并为该问利用该问题分解出的子问题的解可以合并为该问题的解。题的解。v4.1.1 二分查找二分查找v4.1.2 快速排序快速排序v4.1.3 自行车带人问题自行车带人问题分治法往往要依托分治法往往要依托递归过程，并且大致有如下三个步程，并且大致有如下三个步骤： 分解：将原分解：将原问题分解分解为假假设干个干个规模模较小、相互独立，与原小、相互独立，与原问题方式一方式一样的子的子问题。 处理：假理：假设子子问题规模模较小而容易被小而容易被处理那么直接理那么直接处理，否那理，否那么么递归地地处理各个子理各个子问题。 合并：将各个子合并：将各个子问题的解合并的解合并为原原问题的解。的解。 这一一节，引，引见几种运用分治几种运用分治战略的例子。略的例子。4.1.1 二分查找二分查找一、一、问题描画描画在在N个已排序个已排序设为从小到大的数据从小到大的数据数或字符串，数或字符串，查询某一个数据：假某一个数据：假设找找到了，就指出其在到了，就指出其在N个数据中的位置；否个数据中的位置；否那么那么给出无出无该数据的信息，如数据的信息，如给出出“-1。查询是在一个数据集中，查找给定数据的过程。查询是在一个数据集中，查找给定数据的过程。查询的结果有两种情形：找到给定的数据，并给出其查询的结果有两种情形：找到给定的数据，并给出其位置；找不到给定数据。位置；找不到给定数据。二、算法分析二、算法分析采用二分法求解本采用二分法求解本问题的根本思的根本思绪是：如是：如图4.1所示，所示，设数列数列为a1、a2、an，被，被查找的数据找的数据为x，那么，那么查找首先找首先对am(m=(1+n)/2)进展，于是得到展，于是得到如下如下3种情形：种情形： 假假设xam，那么，那么x能能够在区在区间 am+1,an中。中。 假假设x=r) 打印找不到信息,终了程序执行;else if(xam) 调用函数binsrchm+1,r,x;else 调用函数binsrchs,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; /* 数组声明及初始化，外部数组 */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);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; 定义在一切函数的外部，即不在任何一个函数内。这定义在一切函数的外部，即不在任何一个函数内。这种定义在函数外部的数组，称为外部数组。普通来说，种定义在函数外部的数组，称为外部数组。普通来说，定义在外部的变量称为外部变量。外部变量是在每一定义在外部的变量称为外部变量。外部变量是在每一个函数中都可以运用的变量。相对而言，前面运用过个函数中都可以运用的变量。相对而言，前面运用过的、定义在某一个函数内部的变量称为部分变量，它的、定义在某一个函数内部的变量称为部分变量，它只能在所定义的部分运用。只能在所定义的部分运用。五、编程练习五、编程练习1. 用二分法求一元方程式的根提示：用二分迭代法。用二分法求一元方程式的根提示：用二分迭代法。2. 用二分法计算用二分法计算xn的值提示：当的值提示：当n为偶数时，运用为偶数时，运用xn=xp*xp；当；当n为奇数时，运用为奇数时，运用xn=x*xp*xp。3. 用二分法找出一个数组中的最大值和最小值。用二分法找出一个数组中的最大值和最小值。4.1.2 快速排序快速排序一、快速排序的根本思想：一、快速排序的根本思想：快速排序快速排序quick sort是由著名是由著名计算机科学算机科学家家C.A.R.Hoare根据分治根据分治战略略给出的一种高效率的出的一种高效率的排序方法。排序方法。它的根本思想是：在待排序序列中它的根本思想是：在待排序序列中选定一个元定一个元素素X(可以任可以任选，也可以，也可以选第一个元素第一个元素)，称，称为划分元划分元素，用它将原序列整理素，用它将原序列整理划分划分partitioning为两个子序列，使其左两个子序列，使其左边的元素不比它大，使其右的元素不比它大，使其右边的元素不比它小；然后再的元素不比它小；然后再对两个子序列两个子序列进展上述划展上述划分；分；经过不断划分，直至将原序列整理不断划分，直至将原序列整理终了了为止，止，如如图4.2所示。所示。 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,n,i);递归调用qksort(m,i-1);递归调用qksort(i+1,m);else 输出排序终了信息return;下面进一步思索如何描画函数part()。根本思绪如下：根本思绪根本思绪步步骤1：预备： 步步骤1.1：设置两个指置两个指针i和和j，分，分别指向待划分序列的首指向待划分序列的首尾元素尾元素am和和an； 步步骤1.2：选取划分元素取划分元素p=akk属于属于m,n，将，将am移至移至k，即令，即令ak=am。步步骤2：划分：当：划分：当ip,那么那么令令j-j左移一个数据位左移一个数据位;否那么，令否那么，令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 = ajajp, 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 part(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,int 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=0;i=N-1;i+)printf(%5.1f,ai);四、运转结果四、运转结果sorted sequenc is:1.1, 1.3, 1.5, 1.7, 1.9, 2.1, 2.3, 2.5, 2.7, 2.9五、编程练习五、编程练习1. 归并排序并排序Merging sort：“归并的含并的含义是将两个或两个以上的是将两个或两个以上的有序表列合并有序表列合并为一个新的有序表列。一个新的有序表列。归并排序就是把一个具有并排序就是把一个具有n 个数据的序个数据的序列看作列看作n个有序的子序列，不断两两个有序的子序列，不断两两归并，最后构成一个有序序列。并，最后构成一个有序序列。显然然这是一种分治是一种分治战略。略。归并排序的关并排序的关键是是归并。下面引并。下面引见一种一种归并算法：并算法：设序列序列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. 根本思绪根本思绪假设要三人尽快到达假设要三人尽快到达B，就要思索当一个人骑，就要思索当一个人骑自行车带一个人走的同时，另一个人也同时开场步自行车带一个人走的同时，另一个人也同时开场步行，并且自行车不是到达行，并且自行车不是到达B后再前往去接步行的人，后再前往去接步行的人，而是在中途前往去接步行的人，让原来带的人步行而是在中途前往去接步行的人，让原来带的人步行到终点。选择适宜的自行车前往点，使自行车接上到终点。选择适宜的自行车前往点，使自行车接上原来步行的人后，与中途下车的人同时到达。这样原来步行的人后，与中途下车的人同时到达。这样用的时间最短。用的时间最短。图图4.4为一个根本的解题思绪。为一个根本的解题思绪。A AD DE 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用的时间相等，所以：用的时间相等，所以：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 CB BL LS S图图4.4 自行车带人问题自行车带人问题2. 用二分法试探确定用二分法试探确定C下面用下面用试探方法来确定探方法来确定L即即C的位置。的位置。首先思索用二分法，首先思索用二分法，进展展试探。即先以中点作探。即先以中点作为想象的想象的C，后分，后分别计算算t1与与t2： 假假设t1=t2，该点即点即为C； 假假设t1t2，阐明甲坐自行明甲坐自行车少了少了ba，即，即C的的实践位置践位置该当在当在该C点与点与B之之间，该当当继续在在CB之之间找下一个找下一个C； 假假设t1t2，阐明甲坐自行明甲坐自行车多了，即多了，即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 =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)/2,pt);if(t1 t2) putLen(pf,(pf+pt)/2);3. 运用优选法替代二分法运用优选法替代二分法优选法比二分法具有较快的收敛性。用优选法优选法比二分法具有较快的收敛性。用优选法替代二分法，就是用替代二分法，就是用0.618替代替代0.5。三、程序三、程序#include #include #define 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 =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上探求，不达出口时，反复进展搜索上探求，不达出口时，反复进展搜索 */*处置死点处置死点*/ 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. 程序续程序续/* 按顺时针顺序先走没有走过的点按顺时针顺序先走没有走过的点 */ 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; 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 count=19结果矩果矩阵中的中的“1为搜索后，找到的穿搜索后，找到的穿过迷迷宫的道的道路；路；“0为未搜索未搜索过的的节点。点。三、运用堆栈组织搜索过程三、运用堆栈组织搜索过程1. 基于堆栈的回溯基于堆栈的回溯求解此求解此题的根本算法是回溯，而基于堆的根本算法是回溯，而基于堆栈的回溯可以使人思的回溯可以使人思绪更更为明晰。其根本思明晰。其根本思绪如如图4.8所示，把所示，把对迷迷宫的搜索，看成一棵搜索的搜索，看成一棵搜索树的的生成生成过程：程：1首先将根首先将根节点入口点入口处压入堆入堆栈；2 按照下面的按照下面的规那么那么调查栈顶节点点图中灰色中灰色节点的可点的可扩展性即前面展性即前面还有路可走，直到找到一个解或得出无解堆有路可走，直到找到一个解或得出无解堆栈空空即前往到入口的即前往到入口的结论为止：止： 可可扩展，那么将下一展，那么将下一层的各个能的各个能够的的节点按照某种点按照某种顺序如序如顺时针压入堆入堆栈； 不可不可扩展，那么将展，那么将栈顶节点点弹出出图中黑色的中黑色的节点，点，继续调查下一个下一个节点。点。这下一个下一个节点能点能够是同是同层的兄弟的兄弟节点，也能点，也能够是一个上是一个上层节点回溯。点回溯。(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) 扩展节点扩展节点(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,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将栈顶节点弹出，阐明该节点是死节点，相当于将栈顶节点弹出，阐明该节点是死节点，相当于铺了第铺了第2条线。为了未来能在迷宫矩阵中阐明该点曾经条线。为了未来能在迷宫矩阵中阐明该点曾经被探求过，将其置一个特殊的数被探求过，将其置一个特殊的数3。2. 定义数据构造定义数据构造基于基于栈的迷的迷宫探求，需求建立两种根本的数据构造：探求，需求建立两种根本的数据构造： 表示迷表示迷宫的数据构造的数据构造这在前面曾在前面曾经引引见过了，就是用矩了，就是用矩阵二二维数数组表示。表示。 用于回溯控制的数据构造用于回溯控制的数据构造堆堆栈。这里首先思索如何建立基于数里首先思索如何建立基于数组的堆的堆栈。1模模拟迷迷宫的数据构造的数据构造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迷宫中某个节点的表示和探求栈迷宫中某个节点的表示和探求栈/*在在type.h函数中表示函数中表示*/#define N 100typedef struct Node int x,y; /* 节点位置节点位置 */ int nodeState; /* 节点形状节点形状 */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(“探察探察终了，探察了，探察过程如下：程如下：“)；return;elseif(死点死点)置以死点置以死点标志志,重新重新获取取栈顶节点点进展拓展；展拓展；else 先将此先将此节点点压栈;将此将此节点周点周围值为0不是不是墙以及未以及未压过栈的的节点点压栈，同，同时将它将它们的置的置1；重新重新获取取栈顶节点点进展拓展；展拓展；程序框架程序框架2程序框架程序框架定义迷宫矩阵为静态数组定义迷宫矩阵为静态数组定义入口、出口坐标定义入口、出口坐标定义探求栈定义探求栈定义栈的压入函数定义栈的压入函数定义栈的弹出函数定义栈的弹出函数定义栈顶节点扩展函数定义栈顶节点扩展函数定义迷宫矩阵打印函数定义迷宫矩阵打印函数void main()从入口节点开场调用栈顶节点扩展函数；从入口节点开场调用栈顶节点扩展函数；调用迷宫矩阵打印函数；调用迷宫矩阵打印函数；4. 程序设计程序设计1push操作和操作和pop操作操作/*在在stack.h函数中函数中*/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; 1push操作和操作和pop操作续操作续/*在在stack.h函数中函数中*/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栈顶节点扩展函数设计栈顶节点扩展函数设计/*在在expand.h函数中函数中*/int Ei=5,Ej=5; /* 判别是为出口判别是为出口*/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=end.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(mazeij+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栈顶节点扩展函数设计续栈顶节点扩展函数设计续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栈顶节点扩展函数设计续栈顶节点扩展函数设计续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输出函数输出函数/*在在print.h函数中函数中*/prnt() int i,j; printf(n); for(i=0;i=6;i+) for(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 *start;main() (*start).x=Si; (*start).y=Sj; /* 入口的初始化入口的初始化*/ (*start).nodeState=1; mazeSiSj=1; push(start); mazeExpand(start); /* 从入口节点开场调用栈顶节点扩展函数从入口节点开场调用栈顶节点扩展函数*/ prnt(); /*调用迷宫矩阵打印函数调用迷宫矩阵打印函数*/五、编程练习五、编程练习1. 三个猎人杂技团的三位训兽师带着三只猴子过河，只需一条最多三个猎人杂技团的三位训兽师带着三只猴子过河，只需一条最多只能乘二人的船，人猴体重相当，且猴子也会划船。在穿越过河的过程中，只能乘二人的船，人猴体重相当，且猴子也会划船。在穿越过河的过程中，假设留在岸上的猴子数多于人数，猴子就会逃跑。请为三位训兽师设计一假设留在岸上的猴子数多于人数，猴子就会逃跑。请为三位训兽师设计一个平安的渡河方案。个平安的渡河方案。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看成同一种拆分看成同一种拆分5=2+3请设计一个对恣意自然数，找出一切拆分方法的程序。请设计一个对恣意自然数，找出一切拆分方法的程序。五、编程练习续五、编程练习续3. 机器设计问题：某机器由机器设计问题：某机器由n 个部件组成，每一个部件可从个部件组成，每一个部件可从3个投资个投资者那里获得。令者那里获得。令wij 是从投资者是从投资者j 那里得到的零件那里得到的零件i 的分量，的分量，cij 那么为该零那么为该零件的耗费。编写一个回溯算法，找出耗费不超越件的耗费。编写一个回溯算法，找出耗费不超越c的机器构成方案，使其的机器构成方案，使其分量最少。分量最少。4. 邮票问题：想象一个国家发行的几种面值不同的邮票。假设每个邮票问题：想象一个国家发行的几种面值不同的邮票。假设每个信封上至多只允许贴信封上至多只允许贴m枚邮票。当邮资从枚邮票。当邮资从1开场，在增量为开场，在增量为1的情况下，请的情况下，请给出能够获得的邮资值的最大延续区及获得此区域的各种面值的集合。如，给出能够获得的邮资值的最大延续区及获得此区域的各种面值的集合。如，对于对于n=4，m=5，有面值，有面值(1，4，12，21)四种邮票。用回溯法求解此题。四种邮票。用回溯法求解此题。5. 控制方格棋控制方格棋盘游游戏：如：如图4.9所示的所示的55的方格棋的方格棋盘，假，假设在某一方格内放入一在某一方格内放入一个黑子，那么与个黑子，那么与该方格相方格相邻的上、下、左、的上、下、左、右右4各方格中都不可再放黑子。于是，在棋各方格中都不可再放黑子。于是，在棋盘的的X个位置各放一个黑子，就可以控制整个位置各放一个黑子，就可以控制整个棋个棋盘。请设计在棋在棋盘上放上放7个黑子就可以个黑子就可以控制整个棋控制整个棋盘的一切方案。的一切方案。图图4.9 控制方格棋盘游戏控制方格棋盘游戏五、编程练习续五、编程练习续6. 魔板问题：魔板问题：Rubik先生发明了一种玩具，称为魔板。它由先生发明了一种玩具，称为魔板。它由8块同样大小块同样大小的方块组成，这的方块组成，这8个方块分别涂以不同的颜色或编号。它有个方块分别涂以不同的颜色或编号。它有3种根本玩法，种根本玩法，以图以图4.10a为初始形状这为初始形状这3种玩法分别如图种玩法分别如图4.10b、c、d所示。运用三种根本操作，可以由一种形状到达另一种形状。所示。运用三种根本操作，可以由一种形状到达另一种形状。12348765a魔板的一个初始形状魔板的一个初始形状12348765b上下行互换上下行互换12348765c两行同时循环右移一格两行同时循环右移一格12348765d中间中间4块顺时针旋转一格块顺时针旋转一格图图4.10 4.10 魔板魔板 请编写一个程序，经过一系列根本操作，可以将魔板从原始形状请编写一个程序，经过一系列根本操作，可以将魔板从原始形状变为一个输入的目的形状。变为一个输入的目的形状。五、编程练习续五、编程练习续7. 四色问题：在彩色地图中，相邻区块要用不同的颜色表示。那么四色问题：在彩色地图中，相邻区块要用不同的颜色表示。那么印制地图时，最少需求预备几种颜色就能到达相邻区块要用不同的颜色表印制地图时，最少需求预备几种颜色就能到达相邻区块要用不同的颜色表示的要求呢？一百多年前，英国的格色离提出了最少色数为示的要求呢？一百多年前，英国的格色离提出了最少色数为4的猜测的猜测4-colours conjecture。为了证明这一猜测，许多科学家付出了艰巨的劳。为了证明这一猜测，许多科学家付出了艰巨的劳动，但不断没有胜利。直到动，但不断没有胜利。直到1976年，美国数学家年，美国数学家K.Appl和和M.Haken借助借助电子计算机才证明了这一猜测，并称之为四色定理。电子计算机才证明了这一猜测，并称之为四色定理。请按四色定理为图请按四色定理为图4.11所示地图进展着色。所示地图进展着色。AKHBFCDEGJI图图4.11 4.11 一张地图一张地图4.3 贪婪战略贪婪战略v贪婪婪战略略greedy method是一种企是一种企图经过部分最部分最优到达到达全局最全局最优的的战略，犹如登山，并非一开略，犹如登山，并非一开场就就选择出一条到达出一条到达山山顶的最正确道路，而是首先在的最正确道路，而是首先在视力能及的范力能及的范围内，看中一内，看中一个高个高处目的，目的，选择一条最正确途径；然后在新的起点上，再一条最正确途径；然后在新的起点上，再选择一条往上爬的最正确途径；一条往上爬的最正确途径；企；企图经过每一每一阶段的段的最正确途径，构造全局的最正确途径。也就是最正确途径，构造全局的最正确途径。也就是说，贪婪婪战略略总是不断地将原是不断地将原问题变成一个成一个类似、而似、而规模更小的模更小的问题，然，然后做出当前看似最好的后做出当前看似最好的部分意部分意义上的最上的最优选择。v显然，然，贪婪婪战略不能保略不能保证对一切的一切的问题求得的最后解都是最求得的最后解都是最优的，特的，特别是不能用来求最大或最小解是不能用来求最大或最小解问题。但是。但是许多情况多情况下，用下，用贪婪婪战略可以得到最略可以得到最优解的接近解的接近结果。因此，初学者果。因此，初学者该当当经过分析和分析和阅历积累，了解哪些累，了解哪些问题适宜用适宜用贪婪婪战略，略，并掌握如何并掌握如何选择适宜的适宜的贪婪婪战略。略。4.3.1 游览费用问题游览费用问题一、问题描画一、问题描画一个游客要到如图一个游客要到如图4.124.12a a所示的所示的A A、B B、C C、D D、E E五五个景点游览。图中标出了五个景点之间的交通费用。试问，个景点游览。图中标出了五个景点之间的交通费用。试问，该游客从该游客从A A出发，如何以最小费用走过每一个景点最后前往出发，如何以最小费用走过每一个景点最后前往A A？ AEDCB50308030201243103621图图4.12 a游览费用拓扑游览费用拓扑二、解题战略二、解题战略 按照贪婪战略，在部分寻优的过程可以用图按照贪婪战略，在部分寻优的过程可以用图4.12b表示，得到的途径表示，得到的途径为为A-B-E-C-D-A，总费用为，总费用为10+30+20+12+80=152。显然，这一结果并非最优。显然，这一结果并非最优。由于，最优途径为。由于，最优途径为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 Da游览费用拓扑游览费用拓扑b贪婪法求解问题贪婪法求解问题图图4.12 游览费用问题游览费用问题程序框架程序框架1. 数据构造数据构造1费用网用网络描画描画(用用图的的邻接矩接矩阵的描画的描画)：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 expense13 43expenseae expense14 302. 贪婪过程贪婪过程初始化一切节点的费用标志；初始化一切节点的费用标志；设置出发节点设置出发节点V；for( i =1; i= n-1; i + +) s = 从从V至一切未曾到过的景点中费用最少的景点；至一切未曾到过的景点中费用最少的景点；累加费用；累加费用；V = s；/* 新的起点新的起点 */设置设置V的已访问标志；的已访问标志；最后一个景点前往第一个景点，累加费用；最后一个景点前往第一个景点，累加费用；三、程序的实现三、程序的实现#define N 5/*节点个数节点个数*/main() int expenseNN =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-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+i)=0;return(strcat(str,str+i+1);四、阐明四、阐明普通来普通来说，适宜，适宜贪婪婪战略的略的问题大多数具有两个特征：大多数具有两个特征：1贪婪婪选择性性质贪婪婪选择性性质就是可以就是可以经过部分最部分最优选择到达全局最到达全局最优。这种部分种部分选择能能够依依赖于曾于曾经作出的一切作出的一切选择，但不依，但不依赖有待有待于做的于做的选择或子或子问题的解。例如此的解。例如此题中，当前要中，当前要删除的数不依除的数不依赖于未来要于未来要删除的数，只思索当前最除的数，只思索当前最优。2最最优子构造子构造问题的最的最优解包含了子解包含了子问题的最的最优解，称解，称为最最优子构造。子构造。例如此例如此题中的数中的数27685923，要，要删去去4个数字，一定要个数字，一定要删去去768和和9。而采用。而采用贪婪婪战略略时，要依次，要依次删去去7、8、6、9。即。即问题的最的最优解包含了解包含了4个子个子问题的解。的解。五、程序及其测试五、程序及其测试1. 程序程序#include #include char *striDel(char *str,int i);void getMinInteger(char * digitStr,int 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;/* 删除最后数字删除最后数字 */程序续程序续/*删除第删除第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请输入一个数字串：请输入一个数字串：897654请输入需删除数字个数：请输入需删除数字个数：36542测试测试2请输入一个数字串：请输入一个数字串：456789请输入需删除数字个数：请输入需删除数字个数：24567六、编程练习六、编程练习1. 输入一个数字串位数小于输入一个数字串位数小于200，在其中添入，在其中添入mm小于小于20个加个加号，使其值最小。号，使其值最小。2. 汽车加油问题：某汽车加满一次油后可以行驶汽车加油问题：某汽车加满一次油后可以行驶n公里路程。某次游览公里路程。某次游览的总路程为的总路程为s公里，并且该路程中共有公里，并且该路程中共有m个加油站。个加油站。要求：沿途加油次数最少。要求：沿途加油次数最少。输入：每个加油站距出发点的间隔。输入：每个加油站距出发点的间隔。输出：汽车加油的加油站序列号。输出：汽车加油的加油站序列号。六、编程练习续六、编程练习续3. 机器调度问题：现有机器调度问题：现有N项义务和无限多台机器。义务可以在机器上处项义务和无限多台机器。义务可以在机器上处置。每件义务开场时间和完成时间如表置。每件义务开场时间和完成时间如表4.1所示。所示。在可行分配中每台机器在任何时辰最多处置一个义务。最优分配是在可行分配中每台机器在任何时辰最多处置一个义务。最优分配是指运用的机器最少的可行分配方案。请就此题给出的条件，求出最优分配。指运用的机器最少的可行分配方案。请就此题给出的条件，求出最优分配。提示：一种获得最优分配的贪婪方法是逐渐分配义务。每步分配一提示：一种获得最优分配的贪婪方法是逐渐分配义务。每步分配一件义务，且按义务开场时间的非递减次序进展分配。假设曾经至少有一件义件义务，且按义务开场时间的非递减次序进展分配。假设曾经至少有一件义务分配给某台机器，那么称这台机器是旧的；假设机器非旧，那么它是新的。务分配给某台机器，那么称这台机器是旧的；假设机器非旧，那么它是新的。在选择机器时，采用以下贪婪准那么：根据欲分配义务的开场时间，假设此在选择机器时，采用以下贪婪准那么：根据欲分配义务的开场时间，假设此时有旧的机器可用，那么将义务分给旧的机器。否那么，将义务分配给一台时有旧的机器可用，那么将义务分给旧的机器。否那么，将义务分配给一台新的机器。新的机器。如图如图4.14所示，根据此题中的数据，贪婪算法共分为所示，根据此题中的数据，贪婪算法共分为n = 7步，义务步，义务分配的顺序为分配的顺序为a、f、b、c、g、e、d。第一步没有旧机器，因此将。第一步没有旧机器，因此将a 分配给分配给一台新机器比如一台新机器比如M1。这台机器在。这台机器在0到到2时辰处于忙形状。在第二步，思时辰处于忙形状。在第二步，思索义务索义务f。由于当。由于当f 启动时旧机器仍处于忙形状，因此将启动时旧机器仍处于忙形状，因此将f 分配给一台新机器分配给一台新机器(设为设为M2 )。第三步思索义务。第三步思索义务b， 由于旧机器由于旧机器M1在在Sb = 3时辰已处于闲形状，时辰已处于闲形状，因此将因此将b分配给分配给M1执行，执行，M1下一次可用时辰变成下一次可用时辰变成fb = 7，M2的可用时辰变成的可用时辰变成ff = 5。第四步，思索义务。第四步，思索义务c。由于没有旧机器在。由于没有旧机器在Sc = 4时辰可用，因此将时辰可用，因此将c 分配给一台新机器分配给一台新机器M3，这台机器下一次可用时间为，这台机器下一次可用时间为fc = 7。第五步思索。第五步思索义务义务g，将其分配给机器，将其分配给机器M2，第六步将义务，第六步将义务e 分配给机器分配给机器M1, 最后在第七步，最后在第七步，义务义务2分配给机器分配给机器M3。留意：义务。留意：义务d 也可分配给机器也可分配给机器M2。义务义务abcdefg开场开场(si)(si)0349716完成完成(fi)(fi)277111058表表4.1 机器调度问题的一组数据机器调度问题的一组数据图图4.14 机器调度问题的一组解机器调度问题的一组解4.4 分枝界定战略分枝界定战略v分枝定界branch and bound是一种减少搜索解空间、加速搜索进程的方法。在搜索问题的解空间树时，它给每一个活节点只需一次时机成为扩展节点。活节点一旦成为扩展节点就一次性产生其一切的儿子节点。但是，并不把一切儿子节点都参与活节点表中，要把导致不可行解或非最优解的儿子节点舍弃剪枝，把剩下的儿子节点参与活节点表中。然后，从活节点表中取下一个节点进展上述扩展操作。如此继续，直到找到要求的解或活节点表为空。v运用分枝定界法的关键点运用分枝定界法的关键点1扩展一个活展一个活节点点时，如何决，如何决议将哪些儿子将哪些儿子节点舍弃。方法是在每一点舍弃。方法是在每一个活个活节点点处，计算一个函数算一个函数值界限，并根据函数界限，并根据函数值来来选择导致不可致不可行或非最行或非最优解的儿子解的儿子节点舍弃。点舍弃。2如何从活如何从活节点表中点表中选择下一个下一个扩展展节点。最常点。最常见的方法有两种：的方法有两种： 将活将活节点点组织成一个成一个队列，按照列，按照FIFO先先进先出的原那么先出的原那么选取下一个取下一个扩展展节点。点。这种方法称种方法称为队列式列式FIFO分枝定界法。分枝定界法。 将活将活节点点组织成一个成一个优先先队列，按照列，按照优先先顺序序选取下一个取下一个扩展展节点。点。这种方法称种方法称为优先先队列式分枝定界法或列式分枝定界法或LC分枝定界法。分枝定界法。FIFO分枝定界法采用分枝定界法采用队列列组织活活节点点进展广度展广度优先搜索，同先搜索，同时剪剪除不可行除不可行节点点为根的子根的子树。LC分枝定界法常用一个与分枝定界法常用一个与节点相关的数点相关的数值p表表示示节点的点的优先先级，并采用堆，并采用堆组织优先先队列。列。4.4.1 最小耗费问题最小耗费问题一、问题一、问题如图如图4.15所示的城市间交通道路图。图中的有向边所示的城市间交通道路图。图中的有向边上的数字表示从起点城市到终止点城市的交通费用。求上的数字表示从起点城市到终止点城市的交通费用。求A到到E的最小耗费。的最小耗费。B3AB1C1C2C3D1D2E5836792576423图图4.15 最小耗费问题最小耗费问题二、二、FIFO分枝定界算法框架分枝定界算法框架miniCost() /* 用用FIFO分枝定界法进展搜索分枝定界法进展搜索 */取出队列头节点取出队列头节点;for( ; ; ) /* 搜索问题的解空间搜索问题的解空间 */if(两节点可达两节点可达) if(满足控制约束满足控制约束) 更新此节点的形状，参与各点形状队列更新此节点的形状，参与各点形状队列else舍弃当前扩展途径舍弃当前扩展途径 if ( 到达终点到达终点)return;else miniCost(); /* 递归搜索子问题的解空间递归搜索子问题的解空间*/三、程序描画三、程序描画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;2. 节点的数据构造节点的数据构造/*在在type.h中中*/typedef struct Node int x; /* 节点的当前位置节点的当前位置 */ int length;/* 节点到始点的长度费用节点到始点的长度费用 */COST_NODE;COST_NODE path100;3. pop操作和操作和push操作操作/*在在stack_do.h中中*/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中中*/miniCost() 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 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 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 限定限定总分量分量为0时，所，所选物品的物品的总值为0F1(y)=y/w1v1 Fk(y)=maxvjxj (0kN)kj=1wjxj =y (0yB)kj=13. 递推关系递推关系Fky= maxFk-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 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;算法续算法续 /*maxFk-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 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);printf(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 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阶段的划分是动态规划的关键，必需根据题意分析，寻求合理的划阶段的划分是动态规划的关键，必需根据题意分析，寻求合理的划分阶段分阶段(子问题子问题)方法。方法。2在动态规划程序设计中，主要利用了问题的两个性质：最优子构造在动态规划程序设计中，主要利用了问题的两个性质：最优子构造和子问题重叠。和子问题重叠。3变量不可太多，否那么会使问题无法求解。变量不可太多，否那么会使问题无法求解。4最优化原理应在子问题求解中表达。最优化原理应在子问题求解中表达。5有些问题也允许顺推。有些问题也允许顺推。6动态规划是一个非常高效的算法，但是对于一些问题它并不是一个动态规划是一个非常高效的算法，但是对于一些问题它并不是一个理想的算法，其缘由很多。理想的算法，其缘由很多。六、编程练习六、编程练习v用动态规划方法求解以下问题。用动态规划方法求解以下问题。1. 交通交通费用用问题：图4-18表示城市之表示城市之间的交通路网，的交通路网，线段上的数字表示段上的数字表示费用。用。试用用动态规划的最划的最优化原理求出化原理求出单向通行由向通行由AE的最省的最省费用。用。图中，有向中，有向边上的数字，表示从前一个城市到后一个城市的上的数字，表示从前一个城市到后一个城市的费用决策；用决策；B1、B2、B3，C1、C2、C3，D1、D2分分别为由由A到到B，B到到C，C到到D几几种不同决策种不同决策结果。果。B3AB1B2C1C2C3D1D2EABCDE第第4阶段阶段第第3阶段阶段第第2阶段阶段第第1阶段阶段9733461655710324536图图4-18 最小费用问题最小费用问题v提示提示这个个问题是一个多是一个多阶段决策段决策问题：从：从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就是就是第二第二阶段的段的终点，同点，同时又是第三又是第三阶段的始点。同理段的始点。同理递推下去，可看到各推下去，可看到各个个阶段的决策不同，段的决策不同，线路就不同，路就不同，费用也不同。很明用也不同。很明显，当某，当某阶段的起段的起点点给定定时，它直接影响着后面各，它直接影响着后面各阶段的行段的行进道路和整个道路的道路和整个道路的长短，而短，而后面各后面各阶段的道路的开展不受段的道路的开展不受这点以前各点以前各阶段的影响。故此段的影响。故此问题的要求的要求是：在各个是：在各个阶段段选取一个恰当的决策，使由取一个恰当的决策，使由这些决策些决策组成的一个决策序成的一个决策序列所决列所决议的一条道路，其的一条道路，其总路程最短。路程最短。此此题是一个最是一个最优问题，要求由，要求由AE的最的最优决策。根据最决策。根据最优化原化原理，在多理，在多阶段决策中，无段决策中，无论过程的初始形状和初始决策是什么，其他的程的初始形状和初始决策是什么，其他的决策必需相决策必需相对于初始决策所于初始决策所产生的形状搞成一个最生的形状搞成一个最优决策序列。决策序列。对于此于此题来来说，要求，要求AE的最的最优包含包含BE的最的最优，BE的最的最优包含包含CE的最的最优，CE的最的最优包含包含DE的最的最优。因此，解。因此，解题的决策的决策过程程该当从当从E开开场倒推，并分成四个倒推，并分成四个阶段，即四个子段，即四个子问题。战略是每个略是每个阶段到段到E的最省的最省费用用为本本阶段的决策途径。段的决策途径。v决策过程决策过程1第第1阶段阶段输人节点输人节点D1、D2。它们到。它们到E都只需一种费用，分别为都只需一种费用，分别为5、2。但这时髦无法确定它们之中哪一个将在全程最优战略的途径上，但这时髦无法确定它们之中哪一个将在全程最优战略的途径上，因此第因此第2阶段计算中，阶段计算中，5、2都应分别参与计算。都应分别参与计算。2第第2阶段阶段输人节点输人节点C1、C2、C3。它们到。它们到D1、D2各有两种费用。此各有两种费用。此时应计算时应计算C1、C2、C3分别到分别到E的最少费用。的最少费用。C1的决策是：的决策是：minC1D1，C1D2= min (7+5,10+3)=12；途径：；途径：C1+D1+E。C2的决策是：的决策是：minC2D1，C2D2= min (4+5,2+3)=5；途径：；途径：C2+D2+E。C3的决策是：的决策是：minC3D1，C3D2= min (6+5,3+3)=6；途径：；途径：C3+D2+E。此时也无法定下第一、二阶段的城市那二个将在整体的最此时也无法定下第一、二阶段的城市那二个将在整体的最优决策途径上。优决策途径上。3第第3阶段阶段输人节点输人节点B1、B2、B3。决策输出节点能够为。决策输出节点能够为C1、C2、C3。仿前计。仿前计算可得算可得Bl、B2、B3的决策途径为如下情况。的决策途径为如下情况。Bl的决策是：的决策是：minB1C1,B1C2,B1C3= min (6+12,5+5,1+6)=7；途径途径:B1+C3+D2+E。B2的决策是：的决策是：minB2C1,B2C2= min (4+12,3+5)=8；途径；途径:B2+C2+D2+E。B3的决策是：的决策是：minB3C2,B3C3= min (5+5,6+6)=10；途径；途径:B3+C2+D2+E。此时也无法定下第一、二、三阶段的城市那三个将在整体的最优决策途径上。此时也无法定下第一、二、三阶段的城市那三个将在整体的最优决策途径上。4第第4阶段阶段输人节点输人节点A，决策输出节点能够为，决策输出节点能够为B1、B2、B3。同理可得决策途径。同理可得决策途径为：为：minAB1,AB2,AB3= min (9+7,7+8,3+10)=13；途径；途径:A+B3+C2+D2+E。此时才最终确定每个子问题的节点中，那一个节点被包含在最优费用此时才最终确定每个子问题的节点中，那一个节点被包含在最优费用的途径上，并得到最小费用的途径上，并得到最小费用13。按照上述解题战略，子问题的决策中，只对同一城市节点比较优按照上述解题战略，子问题的决策中，只对同一城市节点比较优劣。而同一阶段的城市节点的优劣要由下一个阶段去决议。劣。而同一阶段的城市节点的优劣要由下一个阶段去决议。六、编程练习续六、编程练习续2. 数的拆分数的拆分问题：计算将整数算将整数n6n200拆分成拆分成k2k6份的份的方案数，要求：方案数，要求：1每种拆分方案不能每种拆分方案不能为空。空。2恣意两种拆分方案不能一恣意两种拆分方案不能一样不思索不思索顺序序1,1,5; 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=3，可以称出，可以称出 1g、2g、3g三种不同的分量。三种不同的分量。六、编程练习续六、编程练习续4. 电路板的路板的设计：如：如图4.19所示，一所示，一块电路板的上、下两端各有路板的上、下两端各有n个接个接线柱，柱，在制造在制造电路板路板时要用要用n条条连线将上排接将上排接线柱与下排的一个接柱与下排的一个接线柱柱衔接。接。在制造在制造电路板路板时，要遵照如下原那么：，要遵照如下原那么： 将将n条条连线分布到假分布到假设干干层绝缘层上，使同一上，使同一层中的中的连线不相交。不相交。 要确定哪些要确定哪些连线安排在第安排在第1层，使，使该层布置尽能布置尽能够多的多的连线。提示：提示：1可以将可以将导线按照上端的接按照上端的接线柱命名，如柱命名，如导线i，(i)称称为该电路板路板上的第上的第i条条连线，用于，用于衔接上端的接接上端的接线柱柱i和下端的接和下端的接线柱柱(i)1in。2对于任何两条于任何两条连线i和和j1 (j)。1234567891012345678910图图4.19 电路板接线柱的衔接电路板接线柱的衔接