第10章 算法设计 本章主要介绍下列内容（教材第二章） 1. 回溯法 2. 动态规划法 3. 贪婪法 4. 分而治之法 5. 分支界限法 6. 局部搜索法 课时分配：第1-5节每节讲授三个学时、上机三个学时，第6节根据时间多少而选讲 重点、难点：各节方法介绍、具体问题的算法设计思想 第一节 回溯法 一、思路：见p41 二、哪些问题可用回溯法解 1．迷宫问题 详见《数据结构》C语言版p50 3.2.4 或题集p183 2．排列问题、组合问题、皇后问题、砝码问题。详见补充材料（师院学报理科版论文： 几个典型问题的回溯算法）。 对于砝码问题，有简单的非回溯算法——穷举砝码个数位二进制法，类似于最长有序 子序列的非动态规则法。 3．集和问题 见cp139 n个正数，找出满足条件的一切组合：每个组合中的数之和等于给定的某个正数M。 算法类似于砝码问题。例子：M=30,W=(5,10,12,13,15,18) 解：5 10 0 0 15 0，5 0 12 13 0 0 ，0 0 12 0 0 18 4． 性判定问题，cp141 5．哈密顿回路，cp144 6．稳定婚姻问题，p32 7．马步问题，p41 …… 三、以排列组合或N后问题为例引入回溯思想。 补充： （一）马步问题 1．先演示41页5阶阵人工走法技巧 2．再演示下图（逆时针均匀转大圈法） 21 4 9 14 19 10 15 20 3 8 5 22 1 18 13 16 11 24 7 2 23 6 17 12 25 边上最困难，走法最少，先解决。绕中心转。 计算机程序实现比较困难，且有偶然性。 3．再演示下图（随机转小圈） ×18 ×13 ×12 7 10 3 ×14 ×17 4 1 6 9 ×11 8 ×15 2 ×16 5 4．回溯法介绍（程序实现方便） （二）图的可着色性（cp142） 1．算法 const maxn=100; var g:array[1…maxn,1…maxn]of integer; x:array[1…maxn]of integer; m，n:integer; procedure mcoloring（k:integer）; Lable mexti; Begin for i：=1 To n do [for j:=1 To k-1 do if g[j,k]=1 and x[j]=i then goto mexti; x[k]:=i; if k=n then print(x) else mcoloring(k+1) mexti:] end; Begin 输入m,n,g; mcoloring(1) End。 2．例子 a b a b c d m=3 n=4 着色方案： 1 2 1 2 2 1 2 1 3 1 2 1 c d 1 2 1 3 2 1 2 3 3 1 3 1 1 2 3 2 2 1 3 1 3 1 3 2 1 3 1 2 2 3 1 3 3 2 1 2 1 3 1 3 2 3 2 1 3 2 3 1 1 3 2 3 2 3 2 3 3 2 3 2 三、哈密顿回路（cp145） 1. 算法 const maxn=100; var g:array[1…maxn,1…maxn]of integer; a:array[1…maxn]of integer; m，n:integer; procedure H(k:integer); Lable mexti; Begin for i：=1 To n do [for j:=1 To k-1 do if a[j]=i then goto mexti; if g[a[k-1],i]<>1 then goto mexti; a[k]:=i; if k=n then [if g[a[1],a[n]]=1 then 打印a] else H(k+1)； mexti:] end; Begin{main} 输入n,g; for m:=1 To n do [a[1]:=m;H[2];] END 2. 例子： 1 2 3 4 5 结果：128765431 8 7 6 1 2 3 结果：无 5 4 第二节 动态规则法 ——为求优化问题最优解的“顾全大局、全面考虑”的一种算法设计方法 1. 矩阵乘法问题——按乘法结合律安排连乘积顺序P23 2. 特殊有向图的最短路径问题 p29 类似于《数据结构》中求关键路径，区别是这里求min，那里求max. 特殊的含义是：具有层次性的有向无环图。 多级图的单源最短路径问题，请同学们按《数据结构》理解。 根据学生接受力和课时多少适当补充以下内容。 3. 求给定有限序列中最长有序子序列及其长度——有向图、动态规划。 问题：任给一个序列a1,a2,…,an，请提出方法，计算其最长有序子序列的长度（元素 个数）。注：子序列中元素可以从原序列中跳跃取出，不要求连续。例如，9，2，7，3，4， 10，则2，3，4，10是最长的有序子序列，其长度为4。 方法1 穷举法 从1循环至2n-1( 即n位二进制，见下 图)，对其中的每一个整数i, 化成n位二进 0 1 1 … 0 1 2 3 n 制，判别其为1的位置上原序列中的相应数是 否构成有序子序列，是则统计出 1 的个数 ci. 所有ci的最大者即为题目所求。 方法2 动态规划法 第一步：根据原序列的大小关系建立一个类似于AOE的网（见右上图）： 令每个结点的长度初值为1，边权为1，路径序列初值开始时是本身，以后按类似 于最短路径的求法进行逐步替换。 1 10 长度 路径 1 1 1 1 1 1 1 1 1 10 2 7 4 3 9 第二步：按逆拓扑顺序求从每个顶点出发可能构成的最长有序子序列及其长度（按如 下公式）： ?? ??? ><+= = }i { }j,i(dut)j(Vl{max)i(Vl }0n{ 1)n(Vl j 为其它点 的点，可能不唯一为出度为 <i,j>∈s, 1≤i≤n-1 其中，s是所有以i为尾的弧的集合。 该步的算法实现可仿《数据结构》算法7.13，7.14。 第三步： ni≤≤1 max {Vl(i)}为所求解。 如果还需求出对应的最长子序列元素，则可仿最短路径一节。 教材p29图2.1对应的有向无环图： 要求同学以动态规划观点复习《数据结构》的关键路径一节。 4．最佳旅行路线（详见《pcworld China 1997.4》） p159，奥赛精解） 5．一个M位（1≤m≤200）数字串及N个（0≤N≤20）加号，如何添加才能使总和最 小。作为同学思考题，课外完成。 6．货郎担问题（参考CP101） （1）问题描述 货郎担问题、旅行商问题、巡回推销员问题、Travelling Salesman Problem—TSP （2）穷举法 任取一出发点V0，则剩下的n-1个点任何一个排列均可能与V0构成一条回路（因可 能是有向完全图），对每条回路计算一次长度，在这些长度中选取最小者，其对应的路径即 为所求。显然，计算量为O（（ n-1）！）。 （3）动态规划法 a. 函数g(i,s)的定义——从顶点i出发，经过s中除去顶点i之外的其它顶点各一 次并回到顶点1的一条最短路径的长（s中可能包含1，也可能不包含），则 g(1,V-{1})就 是一条最佳路线的长。 b. 按最佳原理有：g(1,V-{1})= nk≤≤2 min {c k1 + g(k,V-{1，k})} 一般地有：g(i,s)= })}{,({min jsjgcij sj ?+ ∈ 这里i?s c．按b中所给式子，对图5.9（cp102）利用树形结构直观给出解法（值和路径获取） F C K A G P O D L S B H Q E M J R T U N 2 1 3 2 3 4 3 3 2 1 3 2 2 3 2 2 1 4 2 2 3 1 1 2 1 4 3 2 2 5 4 (2,O) (1,O) (4,B) (6,E) (9,J) (10,M) (13,Q) (11,S) (6,H) (8,M) (9,P) (8,L) (6,H) (5,D) (3,B) (7,D) (8,G) (5,A) (7,C) c= ?? ? ? ? ? ? ?? ? ? ? ? ? ∞ ∞ ∞ ∞ 988 12136 1095 201510 g(1,{2,3,4}) min c12 +g(2,{3,4}) c13 + g(3,{2,4}) c14 +g(4,{2,3}) min min min c23 + g(3,{4}) c 24 + g(4,{3}) c 32 + g(2,{4}) c 34 + g(4,{2}) c 42 + g(2,{3}) c 43 + g(3,{2}) c 34 +g(4,f ) c 43 + g(3,f ) c 24 + g(4,f ) c 42 + g(2,f ) c 23 + g(3,f ) c 32 + g(2,f ) c 41 c31 c 41 c 21 c31 c 21 (计算过程为向上，推导理解过程向下) d.复杂度（对一般情形n个点） 下面部分讲课时省去！只进行简单说明（与穷举法对比） 用5个点的情形，在黑板上演示以推导复杂度：需要实际计算g(i,s)的次数（已有的 不再计算，直接取，因而只需第一次计算的次数，比如计算g(3,{2，5})和g(4,{2，5})）， 即 min{(32+g(2,{5}),(35+g(5,{2})}和min{(42+g(2,{5}),45+g(5,{2})} 都要g(2,{5})和g(5,{2}),亦即公用{2,5}。 故，一般情况下，整个过程必须要计算和存储的内容为： g(2,f )+ g(3,f )+ g(4,f )+…+ g(n,f ),此即 n-1 个 c 1i 值，i=1,2,…,n, 共 (n-1)c0 2?n 个 [g(2,{3})，g(2,{4})，…g(2,{n})，g(3,{2})，g(3,{4})，…, g(3,{n})，…, g(n,{2}), g(n,{3}),…, g(n,{n-1})],共有(n-1) *c1 2?n [g(2,{3,4}), g(2,{3,5}),…, g(2,{3,n}), g(2,{4,5}), g(2,{4,6}),…, g(2,{n-1,n}), g(3,{2,4}), g(3,{2,5}),…, g(3,{2,n}), g(3,{4,5}), g(3,{4,6}),…, g(3,{n-1,n}), g(n,{2,3}), g(n,{2,4}),…, g(n,{2,n}), g(n,{4,5}), g(n,{4,6}),…, g(n,{n-2,n-1})]，共(n-1) *c 2 2?n … [g(2,{3,4,5,…,n}), g(3,{2,4,5,…,n}),…, g(n,{2,3,4,5,…,n-1}),共(n-1) *c 2 2?n 故，除G(1,{2,3,4,…,n})外，全部必须计算并存储的G值为∑ ? = ?? 2n 0k k 2nc)1n( 个 由于每计算一个 G(i,s)值，都要进行|s|-1 次比较，故，算出最短路径 G(1,{2,3,4,…,n})所需总的比较次数为： n-1+∑ ? = ?? 2n 0k k 2nc)1n( *(k-1)<n-1+(n-1) 2 ∑ ? = ? 2 0 2 n k k nc =(n-1)+ ( n-1) 2 2 2?n 故，时间复杂度为：O(( n-1) 2 2 2?n )=O(( n 2 2 2?n )次比较（或加法） 这比穷举法O(n!)好，但仍不可行。 由于是指数算法，故算法无意义，不介绍，只了解方法。由此知，TSP是难解问题。 7.资源分配问题（cp93） 第三节 贪婪法（贪心法，Greedy method） 问题引入 到目前为止，我们已经学过了回溯法和动态规则法这两种设计算法的方法。今天我们 学习第三种方法——贪婪法（贪心法，Greedy method，板书题目） 贪婪法、动态规划法、穷举法都可以用于最优化问题的求解算法设计。但是，穷举 法只适于解决规模较小的问题，而且对某些连续的约束条件问题根本不可能穷举（比如我 们马上介绍的背包问题就是如此）；而动态规划法的技巧性太强，不是所有优化问题都能 设计出巧妙的动态规划算法。 那么，对于给定的优化问题，当其规模大，穷举法无能，动态规划算法一时很难设计出 来的时候，怎么办？请考虑使用贪婪法来设计算法。 虽然由贪婪法所得的解不一定是最优的，但总是接近最优的，而且设计算法容易，所得 算法复杂度低，运行速度快。 现实生活中的优化问题很多，大家在《数据结构》课程中熟知的有：哈夫曼树（最 有二叉树）问题、有向网络的关键路径（最长路经）问题，最短路径问题、无向网的最小 生成树问题等。 由于本节将介绍的旅行商问题的贪婪法是受kruskal算法的启发设计出来的，下面我 们先来回忆一下《数据结构》课程中的kruskal算法求无向图最小生成树的动态过程（请 一个同学到讲台上演示给大家看，无人自愿则点名）。 ① ① 6 5 ② 5 1 ④ 演示求解过程 ② 5 1 ④ 3 ③ 5 ③ 2 6 4 2 3 4 ⑤ ⑥ ⑤ ⑥ 6 从刚才的演示可知，最小生成树的求解过程是按边长递增的顺序进行的。 其实，用 kruskal算法求给定网络最小生成树，使用的方法就是贪婪法，其求解过程是： 逐步给出解的各部分，在每一点贪婪地选择最好的部分解，但不顾及这样选择对整体的影响， 因此，一般得到的不是最好的解。 不过，对最小生成树问题，kruskal贪心算法得到的碰巧是… 我们下面的任务就是通过对另外两个典型优化问题的求解来学习设计算法的贪婪法。 （背包问题，旅行商问题） 一、背包问题（knapsack problem） 1．问题描述 通俗：设某港口有 n 种不同的货物要求运往某地，每种货物的总重量为已知，各种不 同货物的运价也是确定的。 某支船队承运部分货物，其总吨位是确定的，每种货物允许分批发运。这支船队应装 运每种货物各多少，才能使它一次获得的运费最多? 形式：给定M（吨位，背包容量）>0， iw (各种货物重量)>0, pi (运完 iw 能得到的利润 或运费)>0，1 ≤ i ≤ n。要求找出一个n元向量（x1,x2,…,xn）, 0 ≤ xi ≤ 1, 1 ≤ i ≤ n，使得： ∑ = ≤ n i ii Mx 1 w 且∑ = n i ii xp 1 达到最大。 2．解背包问题的贪婪法 大家知道，满足 0 ≤ xi ≤ 1，的任何向量（x1,x2,…,xn）都是一个可能解，这样的解显然 有无穷多个，而最佳解必然使∑ = n i ii xp 1 达到最大。 对这种可能解空间是连续实数空间的优化问题，无法用穷举法求解，因此下面我们就 围绕主观上使∑ = n i ii xp 1 达到最大这个目标，通过具体例子来讨论贪心求解法。 n=3,M=40,( 321 ,, www )=(28,15,24),( 321 ,, ppp )=(35,25,24) 贪心策略 （x1,x2,x 3） ∑ = 3 1i iixw ∑ = 3 1i iixp (1)按pi 的由大至小选 iw （1，4/5，0） 40 55 (2)按 iw 的由小至大选 iw （1/28，1，1） 40 49+35*1/28=50.25 (3)按pi/ iw 有大至小选 iw （25/28，1，0） 40 25/28*35+25=56.25 可见，第三种方法所得解最优。 对于一般的背包问题，常用这个例子中第（ 3 ）种贪心策略进行求解，下面假定 ∑ iw >M （因∑ iw <=M时，无需选择，全部装运即可），并对这三种贪心策略进行直观分析。 （1）pi 大的物品先进包（xi=1），直到某物品放不完时才取其一部分（xi<1）使背包刚 好装满。这种方法的缺点是：包装满得快，加入物品的总数减少，不一定能得到最佳解。 （2）按 iw 非降顺序来选取 iw ，使背包慢慢地被装满，以便装入尽可能多种类的物品。 该法的缺点是：忽略了利润的增长，所得解也不一定最佳。 （3）综合考虑两种因素，使单位利润（收益）大的物品尽可能多地优先进包，即按pi/ iw 的递降顺序选取物品进包（xi=1），仅最后才使xi<1。 这种方法效果最好，可以证明：按这种策略得到的一定是最佳解。证明过程可参见 cp112。 3．用类C描述的求背包问题最佳解的贪心法（时间允许则在第一节课板书，否则先让 学生思考放在下节课或作为作业，完整实现见03级试题a）。 Int greedy-knapsack(int n) {float p[n],w [n],x[n],M,Cu;int i； 给p, w , Cu读入数值； 按p[i]/ w [i]的降序调整p和w中元素位置； for(i=1;i<=n;i++) x[i]=0; Cu=M; i =1; While(w [i] ≤ Cu) { x[i]=1；Cu= Cu-w [i] ；i++} x[i]= Cu/w [i]； 输出x； } 时间复杂度：若计排序时间，则为O(nlogn)，否则为O(n)。 4．小结 （1）复习一下贪心法的求解过程：逐步给出解的各部分，在每一步贪婪地选择最好的 部分解，但不顾及这样选择对整体的影响。 （2）一般来说，由贪婪法不能保证所得解为最佳解，但若贪心策略选择得好，对某些 问题也能设计出求最佳解的贪心算法。最优二叉树（哈夫曼树）问题、最小生成树问题、背 包问题就是如此。 （3）是否存在求最佳解的贪心算法，与问题本身有关。例如，旅行商问题是一个有名 的世界难题，到目前为止，除了复杂度为指数阶的穷举法之外，任何非指数阶的算法都不能 保证求出最佳解，包括各种各样的贪心法在内。如果在坐哪位能设计出一种求 TSP 问题最 佳解的非指数阶算法，必将引起世界轰动，你的名字将会比TSP问题本身更知名。 由于贪心法直观，且所得算法复杂度低，下面我们就来详细讨论TSP问题的贪心算法。 二、旅行商问题（Travelling Salesman Problem,简称TSP） 1．问题描述 通俗：某推销员要到若干城市去推销商品，已知各城市之间的路程（或旅费）。请为其 选定一条从驻地出发，经过每个城市一遍最后回到驻地的路线，使总的路程（或旅费）最少。 这个问题开始提出时不少人都认为很简单，后来人们才从实践中逐步认识到其计算复 杂性是输入的指数函数，属于相当难解的问题之一。 中译名称不统一，常见的有“旅行商问题”、“推销员问题”、“货郎担问题”等。 形式：设 G=(V,E)是一个无向图。图中各条边的耗费C ij >0。当（i,j）?E时，定义C ij = ∞。 设|V|=n>1。所谓货郎担问题就是要在G中找出一条有最小消费的周游路线。 2．穷举法思路及改进方法，见教材p44~45，O(n!) ≈ O((n/e)n) 3．由于求最佳解的穷举法复杂度太高，必须寻求近似解法以求较优解（近似解），或 称接近最优解。贪婪法就是其中之一。而贪婪法又有多种，这里先介绍最简单的一种。 按教材p45介绍文字描述及Pascal描述。 在黑板上画出图2.3进行求解过程演示，并说明所得解ABCDEFA长70，不如ABFEDCA 短，才65。 4．变形kruskal法（另一种贪心法） （1） 最小生成树求法（略） （2） 画图演示变形算法思想p46，仍以图2.3为例演示求解过程 （3） 计算机实现办法及类pascal描述p47-49 （4） 具体例子演示并改错P49 5．小结 另一个例子（略） 第四节 分而治之法 1. 引言（cp45） 2. 合并（归并）排序（cp45） a.方法 b.复杂度 3. 快速排序（cp47） a.方法 b.复杂度 4. 赛程问题 p50 5. 整数乘法 p54（自学为主） 6. strassen法（矩阵相乘）p56（自学为主） 三种语言同类型字节数对照 字节数 c pas bas 2 int integer %或defint 4 float single ！或defSNG 4 longint longinteger DefLong 8 double double DedDbL 分而治之法（简称分治法） 引言或概述 要想直接解决一个较大的问题，有时是相当困难的。 1．分而治之（divide-and-conquer）的设计思想是：把一个难以下手的大问题分割成一 些较小的子问题，再分别解决这些较小的子问题，然后由这些子问题的解构造出整个问题的 解。（思想） 2．如果能把一个规模为n的问题分割成若干个子问题，且这些子问题都可解，并且能 利用这些子问题的解求出原问题的解，那么这种分治方法便是可行的。（可行性） 因为子问题较小，一般比原问题容易处理。 3．由分治法产生的子问题往往是原问题的较小模式，为使用递归技术提供了方便。在 多种情况下，反复应用分治手段，可以使子问题与原问题类型一致而规模却越来越小，最终 使子问题缩小到勿需再分且容易求解的地步。这样便自然导致递归过程的产生。分治和递归 象一对孪生兄弟一样，经常同时应用在算法设计之中，并且产生许多高效算法。（与递归的 关系） 4．那么，根据分治法的分割原则，应把原问题分为多少个子问题才较适宜？每个子问 题是否大小一样及怎样才为适当？这些都很难肯定地予以回答。但人们从大量实践中发现： 把一个问题分成大小相等的K个子问题的处理方法是行之有效的。许多问题可以取K等于 2。这种方法对不少问题具有典型意义。子问题大小相等的做法是出自一种平衡（balancing） 子问题的思想，它几乎总是比子问题大小不等的做法要好。（子问题个数） 5．究竟一些什么问题应该使用分治法，使用这一方法时应该怎样选择子问题的个数和 大小才能产生高效算法，目前很难给出科学的回答。我们还是致力于讨论一些具体问题，以 得到一些有益的启发。（适用场合） 现实生活中用分治法来处理的问题很多，如：用分而治之的方法，将国土分成几个部分， 对每部分国土，委派一个诸侯去管理，国君自己就不直接过问这部分国土的事情了，他们的 工作就是分国土，派诸位，过问诸候工作的结果。 现今的国家和企事业单位管理机构也是借用的分而治之法：省、地、县、乡……；院、 处、科……；厅、处、科…… 在计算机算法设计领域，这种思想得到借鉴。例如，大家所熟知的河内塔问题算法、归 并排序算法、快速排序算法都是利用分治思想设计出来的。 下面我们先来讨论一个大家不太熟悉但却很有用的问题的分治解法，然后再回头去总结 讨论归并、快速排序算法所采用的分治策略。 一、赛程问题 教材P50赛程问题：采用2等分的分治法。 教材写得不好，此处按补充材料介绍。（程国忠，赛程问题分治算法，西华师范大学学 报（自然科学版）， 2004.09） 实例演示：以堆栈为辅助工具，演示4阶和8阶例子的构造过程。 时间复杂度分析： 选赋值语句为基本运算，并设 n=2 时的 4 个赋值语句需时间为常数 C1，三个二重 For 循环中的每个赋值语句所需时间为常数 C2（因为每个赋值语句右边表达式都要做两次除法 和两次加减法，运算次数相同），则由算法可得其时间复杂度的递归方程如下： ?? ??? >+ = = 2) 2(3)2( 2 )( 2 2 1 nCnnT nC nT 可利用展开法解之。 21 2 2 2 21 22 21 2 222 21 1 2 2 2 1 22 2 21 22 2 2 1 2 21 2 2 2 2 22 2 32 2 2 22 22 2 33 2 2 2 2 22 2 2 4 ]4[ ])2([ 2 11 ))21(1(21 3 ])21()21()21()21[(3 ])2()2()2()2[(32 )2(3)2(3)2(3)2(3)2( )2(3)2(3)2(3)2( )2(3)2(3)2( )2(3)2()( CCnC nCC nnCC nCC nCC nnnnCC z n CnCnCnCnnT CnnCnnT CnCnnT CnnTnT x x xx xxx xx ?+= ?+= ?+= ? ? += +++++= +++++= ??+??+??++??+= ??+?+??+= ??+??+= ??+= ? ? L L L M 令 由此知，该算法比教材所给算法复杂度表达式简单，少了一次项，不过复杂度量级仍相 同，均为O(n2)。 若将元素赋值看成基本运算，忽略计算下标和取元素的差别，则 2 221 )(1,4 nnTCCC =?== 。 实际上，直观分析也能得出这个式子：n阶方阵每个元素都被赋值一次，则共被赋值n2 次。但左上角4个元素被赋值共用时C1；而其余元素被赋值一次要用时C2，共C2n2-4C2。 故构造整个矩阵阵A要用时C2n2-4C2+C1。 二、归并排序 1．选择排序及复杂度（P45） 这是不平均划分子问题的例子 )()1(211 10 2 1 nOnnTnnT nT n n n =?=??? ? >?+ == ? 2．归并排序思想及复杂度（P46） 这是平衡（二等分）划分子问题的例子 )log(1log 21)2(2 21 2 nn zn n nOnnT nnnT n T =+?=? ?? ??? >?+ = = 三、快速排序（不一定平衡（二等分）划分的例子）（ P47） 1．排序思想及过程（举例演示） 2．平均复杂性 )log( 2nnO 、最坏复杂性 )( 2nO 本章关于算法设计的方法，我们已学习了回溯法、动态规划法、贪心法、分而治之法 等四种类型方法，今天我们学习第五种方法—— 第五节 分枝界限法（或分枝限界法） 与贪心法一样，这种方法也是用来为组合优化问题设计求解算法的，所不同的是它在问 题的整个可能解空间搜索，所设计出来的算法虽其时间复杂度比贪心法高，但它的优点是与 穷举法类似，都能保证求出问题的最佳解，而且这种方法不是盲目的穷举搜索，而是在搜索 过程中通过限界，可以中途停止对某些不可能得到最优解的子空间进一步搜索（类似于人工 智能中的剪枝），故它比穷举法效率更高。 一、基本设计思路（树型搜索法） 动态地构造一棵搜索树，树的结点对应着可能解的一个子集；估算子集中可能解约束函 数值的界限值，用这个界限值来限定搜索的方向，控制搜索的进程。 为使同学们对分枝界限法有一个感性认识，大家可以联想现实生活中这样一个例子：假 如某小孩将心爱的风筝不慎挂在了一棵枝叶茂密的大树顶上，他欲爬上树顶取风筝。可想而 知，他绝不是盲目地往上爬，而是经过肉眼和大脑的判断，从树根开始朝着最有可能取到风 筝的树枝上爬……至于小孩是否最终真正取到了风筝，是否中途从树上摔下来，这不是我们 今天要关心的问题。 我们目前要关心的问题是，为让计算机利用分枝界限法搜索最优化问题的最佳解，事先 应做哪些准备工作。 二、准备工作（以目标函数最小化问题为例） 1．确定子集合（结点）生成规则 规定如何划分可能解集合为若干子集合。 2．确定搜索过程 一般用树的结点表示各种可能解集合或子集合，并从树根开始动态地生成搜索树。 3．确定结点界值计算法 对搜索树每个结点都要用统一方法计算出可能解集合约束函数值的下界值作为控制搜 索方向和是否进一步生成和搜索该结点子结点的判据。 4．确定限界或剪枝规则 一般规定，若某结点的下界值等于或超过了当前最佳解的值，则该结点的子结点不再生 成（在人工智能中叫剪枝）。 下面我们就用这种方法来解决一个具体问题。 三、巡回售货员问题 1．问题描述（口头叙述） 该问题的英文名称是：Travelling Salesman Problem，简称TSP。其中文译名不统一，常 见的有“货郎担问题”、“旅行商问题”、“巡回售货员问题”等。 某推销员要到若干城市去推销商品，已知各城市之间的路程（或旅费）。请为其选定一 条从驻地出发，经过每个城市一遍最后回到驻地的路线，使总的路程（或旅费）最少。 画图2.17说明acbeda：19为所求网络的一条最短路径。 关于这一问题，目前能保证求出最佳解的方法只有穷举法和类似于穷举法的动态规划 法、分枝界限法，其它方法如象贪心法和下节将学习的局部搜索法都只能保证求出接近最优 的解。 美国生物物理学家Hopfield 1982年用神经网络方法研究出一种求该问题接近最优解的 方法，引起极大震惊，掀起了人工神经网络及神经计算机研究的第二次热潮，可见该问题的 重要性。在座有兴趣的同学可在这方面再作些深入研究，若能提出一种求该问题最佳解的优 秀算法，将是对算法设计领域的极大贡献。 2．准备工作 （1）子集合（结点）生成规则 按可能解一定包含某边或一定不包含某边生成结点的子结点，但： a．若包含边xy后产生叉路或中途回路（书上无回路），则不生成相应的子结点xy； b．若排斥（不包含）某边xy后，x或y只剩一边与其相连，则不能生成相应子结点 xy。 (2) 搜索过程 用树根表示所有可能解的集合，以后的每个树结点至多有两个子结点，子结点是这样 产生的：对父结点的可能解按是否含有某一特定边，将父结点的可能解划分成两个子集，由 此得到两个子结点。 （3）估算下限值的方法 对任一条回路，如图所示：若令Na=7+3 Nb=3+4 Nc=5+4 Nd=5+6 Ne=6+7 则该回路长度 ][2176543 NeNdNcNbNaCost ++++=++++= 一般地，对含有1,2,…,n共n个顶点的任一无向图（网），若令 M i 为与 i 相连的两个 最短边之和，则网中任意一条包含全部点的简单回路之长Cost均不小于 ∑ = n i iM 12 1 。 故计算树中结点（可能解子集）回路长度下限值的公式定为： ∑ = n i iM 12 1 （4）剪枝或限界规则 令 best 表示当前所求出的 最短回路长度，其初值为： }|max{ ∞≠?= eieinbest 若任何时候求出的回路长度比 best小，均更新best的值；任何时 候所产生的叶结点的下限值≥ best，均对其作限制标志，以免再 产生并搜索其子结点。 3．从具体过程演示看原理 （P60图） 板书图及树结构，时间不够则 演示几层，然后抄录教材结果，讲 清剪枝限界过程。（补充内容见下 页） 17.5 ab 17.5 ab 18.5 ac 20.5 ac 18.5 ac 18 ac 21 ad 23 ad 18 ad 19 ad 23.5 bc 23 bc 21 bc 23 bc 19 1 2 3 10 12 15 14 9 8 6 X 7 X 13 4 X 5 11 X 结点2对应的图仍为2.17，其余结点对应的图依次为（编号对应图号）： a b e c d 7 6 4 4 5 3 8 2 6 图 3 a b e c d 6 5 3 8 6 图 4 下界： 5.20 )6365443343(21 = +++++++++ 3 4 a b e c d 7 6 3 4 5 3 8 2 6 图 5 18 )6352543323(21 = +++++++++ a b e c d 7 X 6 4 5 3 8 2 6 3 图 6 18 )6352543323(21 = +++++++++ a b e c d 7 6 4 5 3 8 6 3 图 7 23 )3756543373(21 = +++++++++ a b e c d 7 6 4 5 3 8 2 6 图 8 23 23)6862484323(21 = =+++++++++ best X X X X a b e c d 7 6 4 4 5 3 8 2 6 图 10 与原来上层相同， 因为 ac本来就小。 a b e c d 5 3 8 2 3 图 9 21 2125833 = =++++ best a b e c d 7 6 4 5 3 8 2 6 图 11 21 )3752453472(21 = +++++++++ X × 4．计算机算法实现（P61教材） 5．小结（见教材P63） 补充： ①《数据结构》87年版P153搏弈树（井字棋，帮计算机设计对弈算法） ② P150例8.1 15迷问题。 第六章 局部搜索法 （局部变换法） 按教材略讲 补充： ①《数据结构》树的计数一节中的生成函数法。 ② 斐波那契数列通项公式的生成函数解法。 其递推式为： ?? ??? >+= = = ?? 1 1 0 21 1 0 nFFF F F nnn （一）待定系数法： 由 21 ?? += nnn FFF 写出特征方程有： 01221 =???+= ?? lllll nnn a b e c d 7 6 4 4 5 3 8 6 a b e c d 7 6 4 4 5 3 8 2 6 X 图13 5.23 )3756443474(21 = +++++++++ X X 图12 19)98876(21 =++++ （教材有误，因包含ad、 ac后，一定不包含dc） a b e c d × 4 3 8 2 6 图15 2363842 =++++ a b e c d × 6 4 4 3 2 图14 19 1963442 = =++++ best 2 51 2 51 21 ?=+= ll 令方程的通解为 nnnnn CCCCF )2 51()2 51( 212211 ?++=+= ll 代入初始条件得： ?=?++?? ?? ??? =?++ =+ 12 512 51 12 512 51 0 22 21 21 CC CC CC 5 5 5 5 5 1 12 =??=?= CC 故，原递归方程满足初始条件的特解为 nnnF )2 51(55)2 51(55 ??+= ，此即所求 序列的通项公式。 （二）母函数法（生成函数法） 令 LL ++++= nn xFxFxFxFxG 221100)( ① 则 LL +++++= +1322110)( nnxFxFxFxFxxG ② LL +++++= +24231202 )( nnxFxFxFxFxGx ③ ②+③: ] 2 151 2 15 1 2 151 2 15 1 [5 ] 2 15 1 2 15 1[ 5 )2 15)(2 15(1 )( )( )( )()()()()( 2 1 0 1 1 0 0 1 1 0 0 3 3 2 2 1 0 21 12 3 21 2 10 1 0 2 ++ + + ?? ? = ++?????= ++?? ?= ?+ ?=? ?= ++?++++= ++++++= ++++++++=+ ?? ?? xx x xx x xx x xx xxG xxG xFxFxFxFxFxF xFxFxFxFFFF xFFxFFxFFxFxGxx n n n n nnn n nn LL LL LL 利用关系 由公式： ∑∑ ?=+=? ∞ = nn n n x xxx )1(1 1 1 1 0 和 有： nn n n nnn n nnnn n nnnn n n nnn F x x xx xxxxG )2 51(55)2 51(55 ])2 51(55)2 15(55[ ])2 15()1()2 15[(55 ])2 15()1()2 15[(5 ]) 2 15(15 2)1() 2 15(15 2[ 5)( 0 111 0 1111 0 11 0 0 ??+=? ??+= ???+= ??++×= ++?+??= ∑ ∑ ∑ ∑ ∑ ∞ = +++ ∞ = ++++ ∞ = ++ ∞ = ∞ =