东北师范大学信息学选论第四章搜索法.ppt

1、第四章、搜索法,下面介绍3种最常用的搜索策略 (1)枚举法 (2)回溯法(深度优先法) (3)分支限界法（广度优先搜索）,无论什么类型的试题，只要能归纳出数学模型，就尽量用解析方法求解。因为一个好的数学模型建立了客观事物间准确的运算关系，运用这个数学模型直接求解是再合适不过的了。当然，这仅是一种可能性，因为并非所有选手都能在竞赛的“一瞬间”把问题分析得如此透彻，并非所有给定的问题都能建立数学模型，即便有了数学模型，解该模型的准确方法也不一定能套用现成算法。因此在某些情况下，还需要通过搜索（列举所有可能情况）来寻求问题的解。,第一节 枚举法,枚举法的基本思想是根据提出的问题枚举所有可能状态，并用

2、问题给定的条件检验哪些是需要的，哪些是不需要的。能使命题成立，即为其解。虽然枚举法本质上属于搜索策略，但是它与后面讲的回溯法有所不同，因为适用枚举法求解的问题必须满足两个条件：,(1)可预先确定每个状态的元素个数 n ; (2)状态元素 a1, a2,an的可能值为一个连续的值域。 设:ai1 状态元素 ai的最小值； aik一状态元素ai的最大值(1=i=n)， 即 a11=a1=a1k; a21=a2=a2k; ai1=ai=aik, an1=an=ank,我们称状态元素为枚举变量。例如某问题的枚举变量有3个： a1 , a2 , a3 。其中： 1=a1=2， 2=a2=4, 5=a3=

3、7 则问题的可能状态集为： (a1,a2,a3)=(1,2,5),(1,2,6),(1,2,7), (1,3,5),(1,3,6),(1,3,7), (1,4,5),(1,4,6),(1,4,7), (2,2,5),(2,2,6),(2,2,7), (2,3,5),(2,3,6),(2,3,7), (2,4,5),(2,4,6),(2,4,7) 在上述 18 个可能的状态集中，满足问题给定的检验条件的状态即为问题的解。,般来说，如果确定了枚举变量的个数及其值域，我们则可以利用for语句和条件判断语句逐步求解或证明：,for(a1=a11;a1=a1k;a1+) for(a2=a21;a2=a2

4、k;a2+) for(ai=ai1;ai=aik;ai+) for(an=an1;an=ank;an+) if 状态(a1,a2 ai,an)满足检验条件 输出问题的解； 由此可见，枚举的次数为,枚举法的优点： (1)由于枚举算法一般是现实生活中问题的“直译”，因此比较直观，易于理解； (2)由于枚举算法建立在考察大量状态、甚至是穷举所有状态的基础上，所以算法的正确性比较容易证明。 枚举法的缺点：枚举算法的效率取决于枚举状态的数量及单个状态枚举的代价，因此效率比较低。 当然，由于模型建立的不同，信息提取量的不同，同一个问题可以有多个枚举算法，效率也可能有所不同，甚至可能有很大的差异。,一、“直

5、译”的枚举算法,将自然语言描述的问题“翻译”成算法的过程，即为“直译”。现实生活中的许多问题可以“直译”成枚举算法。 例如古代著名的“百鸡百钱”(公鸡一只5文钱，母鸡一只3文钱，小鸡3只一文钱。要求计算一百钱可买3种鸡一百只的数量。)问题就是一个典型的枚举问题。,状态： 3 种鸡的数量 x , y , z 每个状态元素的取值范围： 约束条件： 5x +3y+ z /3 = 100 由此“直译”成如下枚举算法,for(int x=1; x18;x+) for(int y=1;y31;y+) int z=100-x-y; if(5*x+3*y+z/3.0=0) coutxyzendl; ,从上例可

6、以看出，能够被“直译”的问题一般具有下列特征： (1)建立在离散模型上； (2)状态的数量和枚举单个状态的代价确定； (3)枚举算法的时间复杂度为一个多项式。,【例1 】跳远,在水平面上整齐地放着n个正三角形，相邻两个三角形的底边之间无空隙，如图所示。 一个小孩想站在某个三角形i的顶端，跳到三角形j的顶端上（ij）。他总是朝着斜向45度的方向起跳，且初始水平速度v不超过一个给定值v0。,在跳跃过程中，由于受到重力作用（忽略空气阻力)，小孩将沿着抛物线行进， 水平运动方程为 x=x0vt ， 竖直运动方程为 y=y0+vt-0.5gt2， 运动轨迹是一条上凸的抛物线。取g=10.0, (x0,y

7、0)是起跳点坐标。 请编程求出他从每个位置起跳能到达的最远三角形的编号。注意：跳跃过程中不许碰到非起点和终点的其他三角形。,输入： 第1行为两个正整数n,v0 (3=n=20,1=v0= 100) ,表示三角形的个数和最大水平初速度。 第2行有n个正整数li(1=li=20)，表示从左到右各个三角形的边长。 输出： 输出仅一行，包括n-1个数，表示从三角形1,2,3,n-1 的顶点出发能到达的最右边的三角形编号。如果从某三角形出发无法达到任何三角形，相应的数为0 。,分析：本题的基本思想是枚举。对于每一个起跳点i，依次判断点i+1,i+2，n能否跳到。 状态：起跳点i和i点后的点j ，每个状态

8、元素的取值范围： 1=i=n-1, i+1=j=n 约束条件的分析：判断小孩能否从i点跳到j点的方法如下：设起点和终点间的水平距离为l、垂直距离为h，则由物理知识有：,因此: 当然，这个v不一定符合要求，它应满足两个条件 (1)它不能大于极限速度v0，即必须有v=v0 ; (2)跳跃过程中不得碰到其他三角形。,条件2的判断要复杂一些。好在题目中提示：轨迹是一条上凸的曲线，因此只要顶点在抛物线下方，则整条线段都在抛物线下方。这样，我们依次判断起点和终点之间的各个三角形顶点k，看它是否在抛物线下方。 如何判断顶点k是否在抛物线下方呢？我们可以算出到达时间t0=dx/v （其中dx为起点到顶点k的水

9、平坐标增量)，然后算出该时刻的垂直坐标增量，vt0-5t02 。如果此增量大于起点到顶点k的垂直坐标增量，则抛物线在上方。只需起点和终点之间任何一个三角形的顶点不在抛物线下方，则跳远不能完成。我们在枚举过程中不断将小孩所能跳到的点j调整为best。枚举结束后，best 即为试题要求的最远点。,#include #include using namespace std; int main() int len20; /存放三角形的边长 double x20; /存放三角形的顶点x坐标 double y20; /存放三角形的顶点y坐标 /输入三角形的个数和最大水平初速度 int n; double

10、v0; cinnv0; for(int i=0;ileni;,/计算每个三角形的顶点坐标 x0=len0/2; y0=len0*sqrt(3)/2; for(i=1;in;i+) xi=xi-1+leni-1/2+leni/2; yi=leni*sqrt(3)/2; /依次计算每个三角形所能达到的最远点。 for(i=1;in;i+) int best=0; /所能达到的最右的三角形的编号 coutfrom i ;,for(int j=i+1;jv0) break; /大于最大初速度 bool ok=true; /判断是否碰到其他三角形 for(int k=i+1;kj;k+) double

11、t=(xk-xi)/v; if (v*t-5*t*t)-(yk-yi)0.0) ok=false; break; if (ok) best=j; elsebreak; coutbestendl; return 0; ,二、枚举算法的优化,枚举算法的时间复杂度可以用状态总数乘以考察单个状态的耗时来表示，因此优化主要是： 减少状态总数（即减少枚举变量和枚举变量的值域）; 降低单个状态的考察代价。,优化过程从几个方面考虑。具体为： (1)提取有效信息，即在枚举问题给出的浩瀚信息中，取其对解题有直接帮助的精华，弃其无用的糟粕。这样做，会对减少状态总数有很大作用。 (2)减少重复计算。虽然从表面上看，各

12、个状态是独立的，但是不同状态在考察过程中可能有一部分相同的内容。如果让互相联系的状态共同“分担”考察费用，可以降低时间复杂度。,(3)有的枚举问题的状态是复合型的，由多个子状态组成。这时可以考虑将原问题化为更小的问题。表面上看是一个量的变化，但如果充分利用问题的信息，可能使算法产生质的变化。 (4)根据问题的性质进行截肢，特别是最优化枚举问题，往往可以根据问题性质抖除一些“显然”不可能的状态，从而达到减少状态总数的效果。 (5)引进其他算法。一个可“直译”成枚举算法的问题,其解题思路可以从枚举开始，并不一定非得以枚举结束,很多枚举问题可以通过引进其他高效算法达到解题目的。,信息数字化，表面上看

13、是非数值的问题，但经过数字化处理后，就可以方便地进行算法设计了。 【例2】警察抓小偷。警察局抓了a,b,c,d四名偷窃嫌疑犯，其中只有一人是小偷，审问结果如下: a说：“我不是小偷。” b说：“c是小偷。” c说：“小偷肯定是d。” d说：“c是在冤枉人。” 现在已知4个人3人说的是真话，一人说的是假话，问到底谁是小偷？,问题分析：将a,b,c,d对四个人进行编号。则问题可用枚举法来解决。 算法设计：用变量x存放小偷的编号，则x的取值范围a取到d，就假设了他们中的某人是小偷的所有情况。4个人所说的话就可以分别写成： a说的话：x!=a或!(x=a) b说的话：x=c c说的话：x=d d说的话

14、：x!=d或!(x=d) 已知4个人3人说的是真话，一人说的是假话可以表示为当这4个逻辑式的值相加等于3。,#include using namespace std; void main() for(char x=a;x=d;x+) if(x!=a)+(x=c)+(x=d)+(x!=d)=3) coutx is a thief.endl; ,例 3位老师对某次数学竞赛进行了预测，他们的预测结果如下： 甲说：学生A得第一名，学生B得第三名。 乙说：学生C得第一名，学生D得第四名。 丙说：学生D得第二名，学生A得第三名。 竞赛结果表明，他们都说对了一半，说错了一半，并且无并列名次，试求出A、B、C

15、、D各自的名次。 问题分析：用数1，2，3，4分别代表学生A、B、C、D获得的名次，问题就可以利用三重循环把所有的情况枚举出来。,算法设计： 用a、b、c、d代表4个同学，其存储的值代表名次。 设置第一层计数循环a的范围从1到4。 设置第二层计数循环b的范围从1到4. 设置内层计数循环c的范围从1到4 由于无并列名次，名次的和1+2+3+4=10，故d的名次为10-a-b-c; 问题的已知内容可以表示成以下几个条件式。 (a=1)+(b=3)=1 (c=1)+(d=4)=1 (d=2)+(a=3)=1 若三个条件均满足，则输出结果，否则继续循环，直到循环正常结果。,#include using

16、 namespace std; void main() for(int a=1;a=4;a+) for(int b=1;b=4;b+) if (a!=b) for(int c=1;c=4;c+) if (c!=a ,第二节、回溯法,回溯法也是搜索算法中的一种控制策略，但与枚举法不同的是，它是从初始状态出发，运用题目给出的条件、规则，按照深度优先搜索的顺序扩展所有可能情况，从中找出满足题意要求的解答。回溯法是求解特殊型计数题或较复杂的枚举题中使用频率最高的一种算法。,一、回溯法的基本思路,【例3 】n皇后问题 一个 n*n(1=n=100)的国际象棋棋盘上放置n个皇后，使其不能相互攻击，即任何两

17、个皇后都不能处在棋盘的同一行、同一列、同一条斜线上，试问共有多少种摆法？ 输入：n 输出：所有方案。每个方案为n+1行，格式： 方案序号 以下n行。其中第 i 行(1=i=n)为棋盘i行中皇后的列位置。,在分析算法思路之前，先介绍几个常用的概念： (1)状态(state) 状态是指问题求解过程中每一步的状况。在n皇后问题中，皇后所在的行位置i(1=i=n)即为当时皇后问题的状态。 (2)算符(operator) 算符是把问题从一种状态变换到另一种状态的方法代号。算符通常采用合适的数据来表示，设为局部变量。n皇后的一种摆法对应1,n排列方案(a1,an)。排列中的每个元素aj对应j行上皇后的列位

18、置（1=j=n)。由此想到，在n皇后问题中，采用当前行的列位置i(1=i=n)作为算符是再合适不过了。,(3）解答树（analytic tree) 现在让我们先来观察一个简单的n皇后问题。设n=4，初始状态显然是一个空棋盘，见图。 此时第1个皇后开始从第1行第1列位置试放，试放的顺序是从左至右、自上而下。 每个棋盘由4个数据表征相应的状态信息（X, X, X, X）其中第i(1=i=4)个数据指明当前方案中第i个皇后置放在第i行的列位置。若该数据为0，表明所在行尚未放置皇后。,从初始的空棋盘出发，第1个皇后可以分别试放第1行的4个列位置，扩展出4个子结点。 在图中，结点右上方给出按回溯法扩展顺

19、序定义,4皇后的解答树,4皇后的解答树是度为4的树。 某结点所拥有的子结点的个数称作该结点的度。 树中各结点度的最大值，称作该树的度 算符的个数即为解答树的度。,一棵树中的某个分支结点也可视为“子根”，以此结点为根的树则称作该结点的“子树”。由以上讨论可以看出解答树的结构： 初始状态构成(主)树的根结点。对应于n皇后来说，初始时的空棋盘即为根结点。 除根结点以外，每个结点都具有一个且只有一个父结点。对应于n皇后问题来说，置放i行皇后的子结点，只有在置放了前i-1行皇后的一个父结点基础上才能产生。, 每个非根结点都有一条路径通往根结点，其路径长度（代价）定义为这条路径的边数。对应于n皇后来说，当

20、前行序号即为路径代价。当路径代价为n+1时，说明n个皇后已置放完毕，一种成功的摆法产生。,有了以上的基础知识和对n皇后问题的初步分析，已经清楚地看到，求解n皇后问题，无非就是做两件事： 从左至右逐条树枝地构造和检查解答树t 检查t的结点是否对应问题的目标状态。 上述两件事同时进行。,为了加快检查速度，一般规定： 在扩展一个分支结点前进行检查，只要它不满足约束条件，则不再构造以它为根的子树。 已处理过的结点若以后不会再用，则不必保留。即回溯过程中经过的结点不再保留。一般来说，当求出一条路径后，必须从叶子结点开始，沿所在路径回溯，回溯至第1个还剩有适用算符的分支点(亦称为尚未使用过的通向右边方向的

21、结点)，从那里换上一个新算符，继续求下一条路径,由上述扩展过程引出回溯法的基本思想：从左至右逐条树枝地构造和查找解答树，已处理过的结点若以后不会再使用则不必保留（一般说来，检查长度为n的树枝，只要保留n个结点就够了）。若按这种方式得到一条到达树叶的树枝t，实际上就得到了一条路径。然后沿树枝t回溯到第1个尚未使用过通往右边路径方向上的分支点，并由此分支点向右走一步，然后再从左至右地逐个进行构造和检查，直至达到叶子为止，这时又得到一条路径。按这种方法搜索下去，直至求出所有路径。显然用这种方法检查，在树枝左边的一切结点都已检查过，树枝右边的一切结点尚未产生出来。我们把这种不断“回溯”查找解答树中目标

22、结点的方法，称作“回溯法”。,由上述算法思想，我们很容易想到，应选择怎样一种数据结构来存放当前路径上各结点的状态和算符？它应具有“后进先出”的特征，就像一叠盘子，每次只许一个一个地往顶上堆，一个一个地从顶上往下取。这就是我们通常所说的栈。,#include #include using namespace std; int total=0; /方案数 const int MAX=100; /最多皇后数 int stackMAX+1; /stacki为i行皇后的列位置 int n; /实际皇后数 /检查前l-1行,产生攻击则返回true,否则返回false bool att(int l,int

23、i) for(int j=1;jl;j+) if (fabs(j-l)=fabs(stackj-i)|(i=stackj) return true; return false; ,void run(int l) /处理n皇后第l行 if (l=n+1) coutn; run(1); ,我们在应用回溯法求所有路径的算法框架时，应考虑如下几个重要因素： (1)定义状态：即如何描述问题求解过程中每一步的状况。在n皇后问题中，将行位置L作为状态。如果扩展结点时参与运算的变量有多个，为了精简程序，增加可读性，我们一般将参与子结点扩展运算的变量组合成当前状态列入值参，以便回溯时能恢复递归前的状态，重新计算

24、下一条路径。,(2)边界条件：即在什么情况下程序不再递归下去。在n皇后问题中，将 L=n+1（产生一种成功摆法)作为边界条件。如果是求满足某个特定条件的一条最佳路径，则当前状态到达边界时并不一定意味着此时就是最佳目标状态。因此还须增加判别最优目标状态的条件。,(3)搜索范围：在当前状态不满足边界条件的情况下，应如何设计算符值的范围。换句话说，如何设定for语句中循环变量的初值和终值。在n皇后问题中，L行的列位置i作为搜索范围，即 1=i=n 。,(4)约束条件和最优性要求：所谓约束条件是指，当前扩展出一个子结点后应满足什么条件方可继续递归下去；如果是求满足某个特定条件的一条最佳路径，那么在扩展

25、出某个子状态后是否继续递归搜索下去，不仅取决于子状态是否满足约束条件，而且还取决于子状态是否满足最优性要求。在n皇后问题中，将（L,i)置放皇后不产生攻击 (att=false)作为约束条件。,(5)参与递归运算的参数：将参与递归运算的参数设为递归子程序的值参或局部变量。若这些参数的存储量大（例如数组）且初始值需由主程序传入，为避免内存溢出，则必须将其设为全局变量，且回溯前需恢复其递归前的值。在n皇后问题中，将皇后的行位置L和列位置i作为参与递归运算的参数。,二、回溯法的应用实例,回溯法有“通用的解题法”之称，它实际是应用穷举法的一种方式。许多涉及搜索问题的求解过程都要利用回溯策略。它主要应用

26、在解决一些过程完成中要经过若干个步骤，而每个步骤都有若干种可能的分支，为了完成这一过程，又须遵守一些规则，但这些规则又无法精确地用数学公式或语言来描述的一类问题中。,回溯法的基本思想是：在含问题所有解的一棵状态树中，按照深度优先的策略，从根结点开始搜索，每到达一个结点就判断以该结点为根的子树是否可能包含问题的解，如果可以肯定没有，则放弃对该子系统结点的搜索，而向上一层结点回溯，寻找未被搜索过的子结点，对新的一棵树进行同样的判断，可能有解就进入继续搜索，直到找到解或所有结点均被搜索。,从搜索过程可以看出，回溯法体现了“穷举”的方式，但它很好地利用了条件对解状况的约束，免去了不必要的搜索，起到了截

27、枝的作用，使得用回溯法找解的效率要远远高于穷举法。,在组成状态的各个元素中，如果有元素需要采用存储量大（例如数组、字符串）的数据类型，则应该避免将这些元素列为值参或局部变量。因为系统栈区的容量极其有限，每次递归都要将这些大存储量的数据压入栈区，很容易产生内存溢出。不妨将它们设为全局变量来参与递归运算，但回溯前需要恢复其递归前的值。,用回溯法解题通常包含以下3个步骤 （1）针对所给问题，定义问题的解空间 （2）确定易于搜索的解空间结构 （3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索,递归回溯,void Backtrack(int t) if(tn) Output(x); e

28、lse for(int i=f(n,t);i=g(n,t);i+) xt=h(i); if (Constraint(t) 在主函数中调用一次Backtrack(1)即可完成整个回溯搜索过程,说明,形参t表示递归深度，即当前扩展结点在解空间树中的深度。 n用于控制递归深度，当tn时，算法已搜索到叶结点。 output(x)记录或输出得到的可行解。 f(n,t)和g(n,t)表示当前扩展结点未搜索过的子树的起始编号和终止编号 h(i)表示当前扩展结点xt的第i个可选值 Constraint(t)表示当前扩展结点处的约束函数，若不满足可剪去相应子树 Bound(t)表示当前结点处的限界函数。为了避免

29、生成不可能产生最佳解的问题状态，要不断地利用限界函数来处死那些实际上不可能产生所需解的活结点，以减少问题的计算量。Backtrack(t+1)对其相应的子树做进一步搜索。,迭代回溯,采用树的非递归深度优先遍历算法 void IterativeBacktrack(void) int t=1; while(t0) if(f(n,t)=g(n,t) for(int i=f(n,t);ig(n,t);i+) xt=h(i); if (Constraint(t) ,用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间中从根结点到叶结

30、点的最长路径的长度为h(n),则回溯法所需的计算空间通常为O(h(n)，而显式地存储整个解空间则需要O(2h(n)或O(h(n)！)内存空间。,子集树和排列树,子集树和排列树是回溯法解题时常遇到的两类典型的解空间树 当所给问题是从n个元素的集合S中找到满足某种性质的子集时，相应的解空间树称为子集树。 当所给问题是确定n个元素满足某种性质的排列时，相应的解空间称为排列树。,子集树与排列树,遍历子集树需O(2n)计算时间,遍历排列树需要O(n!)计算时间,void backtrack (int t) if (tn) output(x); else for (int i=0;i=1;i+) xt=i

31、; if (legal(t) backtrack(t+1); ,void backtrack (int t) if (tn) output(x); else for (int i=t;i=n;i+) swap(xt, xi); if (legal(t) backtrack(t+1); swap(xt, xi); ,【例 4】 构造字符串,生成长度为n的字符串，其字符从26个英文字母的前p(p=26）个字母中选取，使得没有相邻的子序列相等。例如 p=3,n=5时： “abcba”满足条件； abcbc”不满足条件。 输入：n, p 输出：所有满足条件的字串,分析： (1)回溯搜素满足条件的所有字

32、符串 我们从空串出发，逐个字符地延长字符串。若当前字符添入后使得字符串保持合理的性质，则添入该字符，否则改变字符串。 状态：待扩展的字母序号at。实际上字符串s亦参与了递归运算，但是由于该变量的存储量太大，因此我们将s设为全局变量。 边界条件和目标状态：产生了一个满足条件的字符串，即 at=n。 搜索范围：在at位置可填的字母集a.a+p-1。 约束条件：当前字符串没有相邻子串相等的情况。,(2)检查当前字符串是否符合条件 设当前串s=s1sm-1sm且s1 sm-1合理。按照下述方法判断是否仍然保持其合理性质： 分别判断s的后缀中长度为1的两个相邻子串sm-1 与sm是否相等；长度为2的两个

33、相邻子串是否相等，直到长度为m/2的两个相邻子串是否相等。若经过m/2次判断未出现不合理情况，则说明s=s1sm-1sm满足条件。,#include #include using namespace std; string s; /字符串 int n,p; int tl=0; /字符串数 void main() cinnp; solve(0); couttlendl; ,void solve(int at) if (at=n) cout(at+1)/2) solve(at+1); s=s.substr(0,at); /恢复填前的字符串 ,【例】四色问题,著名的四色定理指出任何平面区域图均可用四

34、种颜色着色,使相邻区域着不同的颜色。 设有下列形状的图形，有n个区域(1=n =100) ,各区域的相邻关系用0(不相邻)、1(相邻)表示。对给定的区域图找出所有可能的不超过四种颜色的着色方案。,例如有如下图形及相邻关系。,将上面图形的每一部分涂上红(1)、黄(2)、蓝(3)、绿(4)四种颜色之一，要求相邻部分的颜色不同。 输入：n 区域数 n*n的0、1矩阵 输出：全部颜色方案，格式如下： 1 1的颜色码 n n的颜色码,输入输出示例 对于上例，一种可能的输出为： 1 1 2 2 3 1 4 2 5 1 6 3 7 4 8 2,分析：程序中用 14 表示四种颜色。 要着色的N个区域用0N-1

35、编号。 区域相邻关系用adj矩阵表示。 数组 color用来存储着色结果,其中 colori 的值为区域i所着颜色。在计算过程中，我们总是对最近涂色的区域进行颜色调整，即所谓的“后进先出”,#include using namespace std; const int N=8; int adjNN = 0,1,0,0,0,0,1,1, 1,0,1,0,0,1,1,0, 0,1,0,1,0,1,0,0, 0,0,1,0,1,1,0,0, 0,0,0,1,0,1,0,0, 0,1,1,1,1,0,1,0, 1,1,0,0,0,1,0,1, 1,0,0,0,0,0,1,0; static int c

36、olorN+1; int sum=0; void main() backtrack(1); coutsum;,bool ok(int k) for(int j=1;jN) sum+; for(int i=1;i=N;i+) coutcolori ; coutendl; else for(int i=1;i=4;i+) colort=i; if(ok(t) backtrack(t+1); colort=0; ,三、回溯法的优化,回溯法亦有其致命的弱点一一时间效率比数学解析法低。为了改善其时效，要尽可能减少分支（减少解答树的度）和增加约束条件（使其在保证出解的前提下尽可能“苛刻”）。另外，还可以从

37、下述两个方面考虑优化：,(1)递归前对尚待搜索的信息进行预处理 如果搜索对象是通过某种运算直接得出其结果的，那么搜索前一般需进行预处理 通过相应运算将所有搜索对象的计算结果置入常量表，搜索过程中只要将当前搜索对象的结果值从常量表中取出即可，这样可以显著改善搜索效率，否则，在搜索过程中每遇到这些对象都要计算，就会产生大量的重复运算。,(2)记忆化搜索 如果解答树中存在一些性质相同的子树，那么，只要我们知道了其中一棵子树的性质，就可以根据这个信息，导出其他子树的性质。这就是自顶向下记忆化搜索的基本思想。,【例6】 序关系计数问题,用关系“”和“=”将3个数a，b和c依次排列，有13种不同的关系：

38、abc, ab=c, acb, a=bc, a=b=c, a=cb, bac, ba=c, bca, b=ca, cab, ca=b, cba。 输入： n 。 输出： n 个数依序排列时有多少种关系。,(1)枚举所有序关系表达式 我们可以采用回溯法枚举出所有的序关系表达式.n个数的序关系表达式，是由n个字母和连接各字母的n-1个关系符号构成的。依次枚举每个位置上的字母和关系符号，直到确定一个序关系表达式为止。 由于类似“a=b”和“b=a”的序关系表达式是等价的，为此，规定等号前面的字母在ASCII 表中的序号必须比等号后面的字母序号小。基于这个思想，我们很容易写出解这道题目的回溯算法。,状

39、态(step，first，can)：其中step表示当前确定的第step个关系符号;first表示当前字母中最小字母的序号；can是一个集合，集合中的元素是还可以使用的字母序号。 边界条件(step=n)：即确定了最后关系符号。 搜索范围(first=i=n)：枚举当前字母的序号。 约束条件（i in Can)：序号为i的大写字母可以使用。 算法 1 :,#include #include #include using namespace std; set can; int n; long total=0; void main() cinn; for(int i=0;in;i+) can.in

40、sert(a+i); count(1,a); couttotal; ,void count(int step,int first) if (step=n) /确定了最后一个关系符号 for(int i=first;i=a+n;i+) if(find(can.begin(),can.end(),i)!=can.end() total+; return; for(int i=first;i=a+n;i+) if (find(can.begin(),can.end(),i)!=can.end() can.erase(i); count(step+1,i+1); /添加= count(step+1,a

41、); /添加 can.insert(i); ,(2)粗略利用信息,算法1中存在大量的冗余运算。如图所示的n=3时的解答树,3个方框内子树的形态完全一样。一旦知道了其中某一个方框内所产生的序关系数，就可以利用这个信息，直接得到另外两个方框内将要产生的序关系数。显然，在枚举的过程中，若已经确定了前k个数，并且下一个关系符号是小于号，这时所能产生的序关系数就是剩下的n-k个数所能产生的序关系数。,设i个数共有Fi种不同的序关系，那么，由上面的讨论可知，在算法1中，调用一次 count(step+1,a)之后，total的增量应该是Fn-step。这个值可以在第1次调用count(step+1,a)时

42、求出。而一旦知道了Fn-step的值，就可以用total= total+Fn-step代替调用count(step+1,a)。这样，可以得到改进后的算法2。开始时将F0,F1,Fn-1初始化为-1。,#include #include #include using namespace std; set can; const int MAXN=1000; long fMAXN; int n; long total=0; void main() cinn; for(int mn=0;mnMAXN;mn+) fmn=-1; for(int i=0;in;i+) can.insert(a+i); co

43、unt(1,a); couttotal; ,void count(int step,int first) if (step=n) for(int i=first;i=a+n;i+) if (find(can.begin(),can.end(),i)!=can.end() total+;return; for(int i=first;i=a+n;i+) if (find(can.begin(),can.end(),i)!=can.end() can.erase(i);count(step+1,i+1);can.insert(i); if(fn-step=-1) /第一次调用 fn-step=to

44、tal; can.erase(i); count(step+1,a); /添加 can.insert(i); fn-step=total-fn-step; /增量 elsetotal=total+fn-step; ,算法2就是利用了F0, F1， ，Fn-1的值，使得在确定添小于号以后，能够避免多余的搜索，尽快地求出所需要的方案数。该算法实质上就是自顶向下记忆化方式的搜索，它的时间复杂度为W(2n）。同算法1相比，效率虽然有所提高，但仍不够理想。,( 3 ）充分利用信息,在搜索的过程中，如果确定在第 k个字母之后添加第1个小于号，则可得到下面两条信息： 第1条信息：前k个字母都是用等号连接的。

45、 第2条信息：在此基础上继续搜索，将产生Fn-k个序关系表达式。,如图所示，序关系表达式中第一个小于号将整个表达式分成了两个部分。由乘法原理知，图示的序关系表达式的总数，就是图中前半部分所能产生的序关系数，乘以后半部分所能产生的序关系数。算法2实质上利用了第2条信息，直接得到图中后半部分将产生的 Fn-k个序关系数，并通过搜索得到前半部分将产生的序关系数。,如果我们利用第1条信息，就可以推知图中前半部分将产生的序关系数，就是n个物体中取k个的组合数，即 Cnk。这样，我们可以得到Fn的递推关系式： 采用上述公式计算 Fn的算法记为算法3，它的时间复杂度是W(n2)。,#include usin

46、g namespace std; const int MAXN=1000; void main() long fMAXN=1,0; int n; cinn; for(int i=1;i=n;i+) fi=0; long x=1; for(int j=1;j=i;j+) x=x*(i-j+1)/j; fi=fi+x*fi-j; coutfnendl; ,在优化算法1的过程中，我们通过利用 F0，F1， ，Fn-1的信息，得到算法2, 时间复杂度也从W(n!)降到W(2n)。在算法2中，进一步消除冗余运算，就得到了时间复杂度为W(n2)的算法3。算法3充分利用信息，通过两重循环的递推计算Fn，将时

47、间复杂度降到W(n2)，实现了程序的最优性要求。,通过搜索状态空间树的方法求解问题答案的方法可以分为两类：深度优先搜索和广度优先搜索。如果在运用搜索算法时使用剪枝函数，便成为分支限界法。 分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。,第三节 分支限界法,采用广度优先产生状态空间树的结点，并使用剪枝函数的方法称为分支限界法。 按照广度优先的原则，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。 此后，从活结点表中取下一结点成为当前扩

48、展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。,分支限界法与回溯法 （1）求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。 （2）搜索方式的不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。,常见的两种分支限界法,(1)队列式(FIFO)分支限界法 按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。 (2)优先队列式分支限界法 按照优先队列中规定的优先级选取优先级最高的节点成为当前

49、扩展节点。,广度优先搜索,初始化visited数组，将所有点的值设为false； /visited数组用来保存所有点的访问情况 visitedstart=true;/start为起始点 queue search;/用来保存待搜索点的队列 search.push(start)； while(!search.empty() v=search.front(); search.pop(); /弹出一个点处理，用v表示 for(每一个v的相邻点) if(!visitedv) visitedv=true; search.push(v); ,用分支限界法求解背包问题（0/1背包） 1.问题描述：已知有N个物

50、品和一个可以容纳TOT重量的背包，每种物品的重量为Weight，价值为Value。一个物品只能全放入或者不放入，求解如何放入物品，可以使背包里的物品的总价值最大。 2.设计思想与分析：对物品的选取与否构成一棵解树，左子树表示装入，右表示不装入，通过检索问题的解树得出最优解，并用结点上界杀死不符合要求的结点。,方法1（队列式分支限界法） #include #include #include using namespace std; struct goods int no; /物品标号 int weight;/物品重量 int value; /物品价值 ; struct node int flag

51、; /装入标记 int curv; /当前价值 int curw; /当前重量 int level; /结点层次 bool operator curv; ;,int number; /物品数量 int TOT; /背包最大可承载重量 int bestv; /最大收益 vector bag; queue t; priority_queue result; void addnode(int flag,int curv,int curw,int level) node* b=new node ; b-flag=flag; b-curv=curv; b-curw=curw; b-level=level

52、; t.push(*b); ,void bound()/遍历结点并选择装入的结点 int i=0; addnode(0,0,0,0); while(inumber) do if(t.front().curw+bagi.weight=TOT) /左子树结点可行 addnode(1,t.front().curv+bagi.value, t.front().curw+bagi.weight,i+1); /右子树结点一定可行 addnode(0,t.front().curv,t.front().curw,i+1); t.pop(); while(t.front().level=i);i+; while

53、(!t.empty() result.push(t.front();t.pop(); return; ,void main() cinnumber; cinTOT; for(int i=0; ib.weightb.value; b.no=i+1; bag.push_back(b); bound(); coutresult.top().curvendl; ,方法2（LC（最小成本）检索） #include using namespace std; struct goods int weight;/物品重量 int value;/物品价值 int flag;/是否装入标记 ; goods *bag=NULL; int number;/物品数量 int TOT; /背包最大可承载重量 int upb