搜索基本算法20128

1、搜索基本算法搜索是人工智能中的一种基本方法，利用计算机的高性能来有目的、有方法的穷举一个问题的部分或所有的可能情况，从而求出问题的解的一种方法。在建立搜索算法时，首先需要关注的问题是，以什么作为状态？这些状态之间又有什么样的关系？其实，在这样的思考过程中，我们已经不知不觉地将一个具体的问题抽象成了一个图论的模型树（如图所示）。即搜索算法的使用第一步在于搜索树的建立。根结点一个成功的解目标结点第0层第1层第2层第3层由上图可以知道，这样形成的一棵树叫搜索树（图）。初始状态对应着根结点，目标状态对应着目标结点。排在前的结点叫父结点，其后的结点叫子结点，同一层中的结点是兄弟结点，由父结点产生子结点叫

2、扩展。完成搜索的过程就是找到一条从根结点到目标结点的路径，找出一个最优的解。这种搜索算法的实现类似于图或树的遍历，通常可以有两种不同的实现方法：深度优先搜索（epth First search）和宽度优先搜索（First Search），下文对这两种方法分别进行讨论。 深度优先搜索一深度搜索如算法名称那样，深度优先搜索所遵循的搜索策略是尽可能“深”地搜索树。它的基本思想是：为了求得问题的解，先选择某一种可能情况向前（子结点）探索，在探索过程中，一旦发现原来的选择不符合要求，就回溯至父亲结点重新选择另一结点，继续向前探索，如此反复进行，直至求得最优解。如迷宫问题（可以理解为遍历图的问题）：进入迷

3、宫后，先随意选择一个前进方向，一步步向前试探前进，如果碰到死胡同，说明前进方向已无路可走，这时，回到上一步，改变前进方向是否有路可走，如果有路可走，则沿该方向再向前试探；如果已无路可走，则再返回一步，再看其它方向是否还有路可走；如果有路可走，则沿该方向再向前试探。按此原则不断搜索回溯再搜索，直到找到新的出路或从原路返回入口处无解为止。深度优先搜索在树（图）的遍历中也称作树（图）的先序遍历。对于树而言，深度优先搜索的思路可以描述为：（） 将根结点置为出发结点。（） 访问该出发结点。（） 依次将出发结点的子结点置为新的出发结点，进行深度优先遍历回溯（执行（）。（） 回溯上一层的出发结点。深度优先搜

4、索的具体编程可用递归过程或模拟梯归来实现。他们各有各有优缺点。通常情况下采用递归方式实现搜索算法，因为递归形式的程序符合思维习惯，编写起来较容易。下面是深度优先搜索的用递归方式实现的程序框架：Procedure dfs（i:integer）;Var k:integer;Begin If 所有阶段都已求解 then Begin 比较最优解并保存； endelse beginfor k:=1 to i（同一深度可能决策的范围）do begin 穷举当前阶段所有可能的决策（方案、结点）k if k方案可行 then begin 记录状态变化；DFS(i+1); / 将子结点作为新的出发结点状态恢复（

5、现场恢复）； endend; end;End.二例 题1. 选择最短路径【问题描述】有如下所示的交通路线图，边上数值表示该道路的长度，现要求出从1号地点到达7号地点的最短的路径长度是多少，并输出该长度。 1 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 75317912 6 7 5 4 3 2 1 1 6 7 5 4 3 2 1 6 7 5 4 3 2 1 6 7 5 4 3 2 1 6 7 5 4 3 2 1第1层第2层第3层第4层第5层522233154812119 1 2 3 4 5 7 2 1 3

6、 5 7 6 410图1 图2【问题分析】首先需要把图1转化成搜索树模式。在建立搜索树之前，各节点之间的状态，结点与结点之间的关系。结点状态：现有结点号，每个结点存在两种状态，即已进入搜素路径或者未进入搜素路径，初始状态都是未进入搜索路径，两种状态可以用“1”和“0”表示。结点之间关系：存在路劲或者不存在路径。存在路径有具体的数值表示，不存在路径可以用“-1”来代替。在明确以上两点的基础上建立如图2所示的搜索树。求最短路径就是遍历该搜索树的过程。首先从号结点开始，在遍历过程中，搜索到与结点时存在路径，首先把结点纳入路径，然后累加路径的长度同时判断该结点是否为结点。继续调用以为起点的搜索，开始继

7、续遍历中的结点，发现结点、已在路径中，结点不存在连接，判断与结点的连接，存在连接，同样把结点纳入路径，累加路径的长度，同时判断该结点是否为结点，依次类推，形成一颗搜索树，一条完整的搜索路径：-。完成第一条路径的搜索以后，即完成了第5层面的搜素，但是前面的4个层面还没有完成，这时回溯至第4层完成结点和结点的搜索，不存在连接，继续回溯至第3层，遍历至结点，遍历结点，发现结点、结点已经存在路径中，与结点存在连接，同样把结点纳入路径，累加路径的长度，同时判断该结点是否为结点，然后以结点为起点，遍历搜索结点，发现无连接，这样宣布这条路径失败，回溯至第4层，继续遍历结点-，结点已在连接中，结点本身，结点不

8、存在连接，继续遍历结点，发现与该结点存在连接，同样把结点纳入路径，累加路径的长度，同时发现该结点为终结点。完成又一路经的的深度搜索：-。所得路径长度与前一次比较，保留小的数值。依次类推完成所有的路径搜索，求出最短路径。现设定邻接矩阵表示图的连接和权值：ai,j=x,或者ai,j=-1（表示两者之间不存在距离）。bi=1表示结点i是否已经遍历过。用变量min来保存最优解，而用total变量保存求解过程中临时解（当前路径总长度）。该过程深度搜索子程序框架结构如下：procedure dfs(I:integer);var k:integer;begin if 到达了终点n then begin 保存

9、较优解；endn else beginn for 穷举决策范围内I的值 don if I到k点有直接联边并且k点没有遍历过 then beginn 把aI,K累加入路径长度total；k标记为已遍历；dfs(k)；n 现场恢复（还原加入的结点的状态和和减去加入的路径长度）；n end;n end; End;【程序代码】Var i,n,total,min:longint; a:array1.100,1.100 of integer; b:array1.100 0f boolean;procedure dfs(i:integer);var k：integer;beginif i=n then be

10、gin if total<min then min:=total;end else begin for k:=1 to n do if (bk=false) and (i<>k) and (ai,k>0) then begin bk:=true; total:=total+ai,k;if total>min then begin bk:=false; total:=total-ai,k;continue； /剪 枝 end;dfs(k); /搜索遍历 bk:=false; total:=total-ai,k; /现场恢复end; end;end;begin /主程

11、序read(n);Fillchar(b,sizeof(b),false); /置初值,作为是否加入路径标志total:=0;b1:=true;min:=maxlongint; /置初值for i:=1 to 7 do /读入所有点与点之间的距离（不存在路径用-1代替） for j:= 1 to 7 do read(ai,j)；dfs(1); writeln('total=',min);end.三算法优化在例题中有一个值得思考的问题，每次寻找到一条完成的路径后，需要与前一次的所求的的最短路径值相比较，以获取最短路径。这样的比较是否可以考虑把他放置在把结点纳入路径的过程中，一旦发现

12、现有的路径值大于现保留的最短路径值，就立即终止当前路径搜索，回溯，搜索另一条路径，这样可以大大减少了搜索的次数，这就是搜索优化方式之一剪枝。所谓剪枝就是通过某种判断，避免一些不必要的遍历过程，形象地说，就是剪彩去了搜索树中的某些不符合要求的“枝条”，减少搜索时间和空间。剪枝算法按照其判断思路可大致分成三类：可行性剪枝、最优化剪枝和判重剪枝。显而易见，应用剪枝优化的核心问题是设计剪枝判断方法，即确定哪些枝条应当舍弃，哪能些枝条应当保留的方法。在设计一个优秀的设计剪枝判断方法的过程中，一般需要考虑以下三个方面的问题。1 正确性 剪枝方法之所以能够优化程序的执行效率，正如前文所述是因为它能够“剪枝”

13、过程中剪掉没有价值的枝叶，这些枝叶的“值”不存在对最优解的准确性产生影响，为此必须在考虑剪枝方法的正确性。当然，由必要条件的定义，我们知道，没有被剪的枝不意味着其中一定有正解，否则就不必搜索了。2 力 度剪枝的力度是指搜索中剪去的枝与所有枝的比值。搜索的效率很大程序上取决于剪枝的力度，因为力度对搜索效率的贡献并不仅仅是成正比的，而是呈几何级数上升的，强有力的剪枝可以省去一大半的时间或空间。剪枝方法只有在具有了较强的力度的时候，才能真正收到优化的效果，因此，剪枝的力度可以说是剪枝优化的生命。3 代 价剪枝的代价是指剪枝本身所花费的时间与空间。一般说来，设计好剪枝判断方法之后，需对搜索树的每个枝条

14、都要执行一次判断操作。但是判断操作无疑带来的是时间代价开销的递增，如果剪枝判断的时间消耗过多，就就可能减小、甚至完全抵消提高判断力度所能带来的优化效果，这就变成得不偿失。很多情况下，能否较好的处理这个矛盾，往往成为搜索算法优化的关健。剪枝条件的获取，并不是盲目的，恰恰相反，剪枝有一些逻辑性与规律性的方法。剪枝条件的获取主要要有两个方法：直觉法和推理法。在引题“选择最短路径”中，剪枝的条件获取比较直觉。在每次纳入结点的过程中，加入路径的长度，随之与当前最短路径值比较，大于当前最优路径的值即剪枝。四经典例题1数字排列(number.pas)【问题描述】列出所有从数字1到数字n的连续自然数的排列，要

15、求所产生的任一数字序列中不允许出现重复的数字。【输入格式】 单独一行N（1<=N<=9）【输出格式】 由1n组成的所有不重复的数字序列，每行一个序列。【样例输入】 3【样例输出】1 2 3 1 3 2 2 1 3 2 3 13 1 2 3 2 1 【问题分析】采用方法：可以采用全排的手段，也可以采用回溯+去重剪枝。本题实质就是对n个数进行排列组合，并打印出所有的组合。现以n=3为例建立一棵如下图所示的搜索树，每一条路径代表一个组合。但是根据题意在对n个数值进行组合的过程中，不允许出现相同的数字，为此在对搜索树搜索的过程中可以进行适当的剪枝，这样可以大大提高搜索效率。图中用“”实现对

16、n=3数值的剪枝。 在程序实现的过程中定义一个函数确定该数是否被使用，没有则递归处理下一位数，否则剪枝回溯，直到k>n。 13 13 12 11 11 13 12 11 12 13 12 11 13 10 13 13 12 11 11 13 12 11 12 13 12 11 12 13 13 12 11 11 13 12 11 12 13 12 11 11【程序代码】program number;var a:array 1.100 of integer; i,n:integer;function pd(k,i:integer):boolean; /判断需排列的数字是否重复；var m:

17、integer;begin m:=1; while (m<k)and(i<>am) do m:=m+1;/与排列的数字比较判重； if m=k then pd:=true else pd:=false;end;procedure try(k:integer); /回溯搜索全排组合；var i:integer;begin if k>n then begin /完成一次数字排列后打印 for i:=1 to n do write(ai:5); writeln end else for i:=1 to n do /从1-n完成按次序实现全排 if pd(k,i) then b

18、egin /判重，逐个按序选出需排列的数字 ak:=i /选出的数字放入数组a中； try(k+1); /回溯调用排列下一位数字; end;end;begin assign(input,'number.in');reset(input); assign(output,'number.out');rewrite(output); readln(n); try(1);end. 2特殊的质数（USACO练习题 spnumber.pas）【问题描述】农民约翰的母牛总是生产出最好的肋骨。你能通过农民约翰和美国农业部标记在每根肋骨上的数字认出它们。农民约翰确定他卖给买方的是

19、真正的质数肋骨，是因为从右边开始切下肋骨,每次还剩下的肋骨上的数字都组成一个质数，举例来说：7 3 3 1全部肋骨上的数字7331是质数，三根肋骨733是质数，二根肋骨 73 是质数，当然，最后一根肋骨7也是质数。7331 被叫做长度 4 的特殊质数。 写一个程序对给定的肋骨的数目 N (1<=N<=8)，求出所有的特殊质数。数字1不被看作一个质数。【输入格式】单独的一行包含N。 【输出格式】按顺序输出长度为 N 的特殊质数，每行一个。 【样例输入】4【样例输出】233323392393239929393119313737333739379337975939719373317333

20、7393【问题分析】采用方法：深度优先搜索+条件剪枝。问题的本质就是寻找一个n位的质数，然后逐位去掉末尾，要求该形成的新数也是质数。根据样例数据分析可以采用末尾补奇数的方式，然后判断该数是否为质数。即逐步深搜添加的数值为1、3、5、7、9，同时对该数进行判断是不是质数（素数），是则递归处理下一位数，不是则剪枝回溯，直到depth>n。 或者直接深搜19，然后条件判断是不是质数（素数），是则递归处理下一位数，不是则剪枝回溯，直到depth>n。当然在处理完该4位数是质数后需要记录该数。【程序代码】program spnumber;var s:longint; n,b:longint;

21、function pd(x:longint):boolean; /判断所获得的数值是否为素数var flag:boolean; i:longint;begin flag:=true; if x=1 then flag:=flase; else begin for i:=2 to trunc(sqrt(x) do if x mod i=0 then begin flag:=false; break; end; end;end;procedure dfs(s:longint);var k:longint;begin if s>n then begin writeln(b) exit end;

22、 /完成符合位数要求素数搜索后，输出该素数 for k:=1 to 9 do begin if (k=2)or(k mod 2 =1) then begin /要求末尾加入k值为2或者为奇数 b:=b*10+k; /累加位数，并把k值加入末尾，形成新的b值if pd(b)then dfs(s+1); /判断新形成的数值是否是素数，是深度搜索下1位数值； s:=s-1;b:=b div 10; /恢复现场，为继续加入下一个数值初始化； end; end; end;begin assign(input,'spnumber.in');reset(input); assign(outp

23、ut,'spnumber.out');rewrite(output); readln(n); /读入数值的位数 s:=1; /统计位数 dfs(1); /搜索数值 close(input);close(output);end.3.砝码称重（NOIP 1996 提高组weight.pas）【问题描述】设有1g、2g、3g、5g、10g、20g的砝码各若干枚（其总重<=1000），求：用这些砝码能称出的不同重量的个数，但不包括一个砝码也不用的情况。【输入格式】输入文件中只有一行以空格分隔的6个数字，a1 a2 a3 a4 a5 a6。表示1g砝码有a1个，2g砝码有a2个，3

24、g砝码有a3个，5g砝码有a4个，10g砝码有a5个20g砝码有a6个。【输出格式】 输出文件中只有一行数据：Total=N。表示用这些砝码能称出的不同重量的个数，但不包括一个砝码也不用的情况。【输入样例】 1 1 0 0 0 0【输出样例】Total=3【问题分析】采用方法：深度优先搜索。问题的实质就是完成对不同的数值的组合，求能够形成多少种不同的组合。首先建一棵搜索树，如下图所示，然后对该搜索树做一次深度遍历。 b 0 d 0 d 0 0 d d h 0 0 b 0 a 0 第1个砝码第2个砝码第3个砝码第6个砝码由上图可以知道每1种砝码都存在多种情况，可以取0n个，同样当第1种砝码取0个

25、的时候，同样第二种砝码存在多种取法，依次类推，即建立了如上图所示的搜索树。直接深搜16，直到depth>6，然后直接用一维数组，记录能够称重的砝码，统计该数组的值，得出能够称重的种类。【程序代码】program weight;var f:array0.1000of longint; /用于记录能够称重的不同重量 a,w:array1.6of longint; 数组a存放砝码的个数，数组w存放砝码的重量 s,i:longint;procedure dfs(i:longint);var j:longint;begin if i>6 then begin /完成1次6个砝码的组合，并记录

26、能够称重的重量 fs:=1;exit; end; for j:=0 to ai do begin /按不同种类的砝码数量搜索能够称重的重量 s:=s+j*wi; dfs(i+1); / 进入下一类别砝码重量的搜索 s:=s-j*wi; /恢复现场，为搜索下一个重量做准备 end;end;begin/ assign(input,'weight.in');reset(input);/ assign(output,'weight.out');rewrite(output); for i:=1 to 6 do read(ai); /分别读入砝码的个数 w1:=1;w2:

27、=2;w3:=3; w4:=5;w5:=10;w6:=20;/定义砝码的重量 fillchar(f,sizeof(f),0); /初始化数组f； s:=0; /初始化初值s， dfs(1); /深度搜索调用过程 s:=0; for i:=1 to 1000 do s:=s+fi; writeln('Total=',s); / close(output);close(input);end.4.导游（2007年宁波市中小学程序设计比赛决赛题 guide.pas）【问题描述】宁波市的中小学生们在镇海中学参加程序设计比赛之余，热情的主办方邀请同学们参观镇海中学内的各处景点，已知镇海中学

28、内共有n处景点。现在有n位该校的学生志愿承担导游和讲解任务。每个学生志愿者对各个景点的熟悉程度是不同的，如何将n位导游分配至n处景点，使得总的熟悉程度最大呢？要求每个景点处都有一个学生导游。【输 入】输入文件中有若干行：第一行只有一个正整数n，表示有n个景点和n个学生导游。第二行至第n+1行共n行，每行有n个以空格分隔的正整数。第i+1行的第j个数k(1k1000)，表示第i个学生导游对景点j的熟悉程度为k。【输 出】输出文件只有一行，该行只有一个正整数，表示求得的熟悉程度之和的最大值。【样例输入】【样例输出】3 2410 6 89 2 31 7 2【样例说明】第1个学生负责第3个景点，第2个

29、学生负责第1个景点，第3个学生负责第2个景点时，熟悉程度总和为24，达到最大值。【数据限制】50%的数据，1n9；100%的数据，1n17。【问题分析】 8 6 10 3 2 9 2 7 1采用方法：深度搜索+调整剪枝。问题的实质就是在搜索二维数组中的值，要求每行每列中只能取一个值，然后求该数值的和，找出其中最大的和。根据样例，首先建立一棵搜索树，如下图所示。根据以样例建立的搜索树可以看出，可以采用深搜遍历搜索树的方法求的该问题的解，但是根据数据限制“100%的数据，1n17”，采用遍历全部的方式肯定存在超时。变通思维方式，题意中最大景点的值是1000，转换二维数组的值，用1000减去该值，变

30、求二维数组中最大的值为求最小值，然后在深度遍历的过程中，比较所获取的和值，比当前已获取的最小值比较，小则递归处理下一个数值，大或者等于则剪枝回溯，直到depth>n。【程序代码】program guide;const maxn=50;var a:array1.maxn,1.maxnof longint; f:array1.maxnof boolean; /用于标识景点、导游是否被分配过； n,i,j,ans:longint;procedure dfs(i,s:longint); var j:longint;begin if i>n then begin / 当完成一次导游搜索组合，

31、得出当前最佳的得的熟悉程度值 if ans>s then ans:=s;exit; end; if s>=ans then exit; /当前得到的熟悉程度值大于先前最佳熟悉程度值时则剪枝 for j:=1 to n do /按导游对各景点的熟悉程度搜索 if fj then begin /假如该景点未被分配过导游 fj:=false; /标识景点使用标识 dfs(i+1,s+ai,j); /累加景点熟悉程度值，并进入下一层景点熟悉程度的搜索 fj:=true; / 完成以该近点为前提的搜索，恢复现场，为同层下一景点搜索做准备 end;end;begin assign(input,

32、'guide.in');reset(input); assign(output,'guide.out');rewrite(output); read(n); for i:=1 to n do for j:=1 to n do beginread(ai,j); /读入各导游对各景点的熟悉程度ai,j:=1000-ai,j; /变求最大值为最小值 end;fillchar(f,sizeof(f),true); /初始化布尔数组为“true” ans:=maxlongint; dfs(1,0); /深度搜索调用 writeln(n*1000-ans); /求的最大熟悉

33、程度的值 close(output);close(input);end.5.外星生命（live.pas）【问题描述】在外太空航行的飞船拍到了某种外星生命的图像。科学家在研究该图像时，把该图像分为n行m列,共n*m个格子，每格给出了一个以整数表示的相似度的值。现在请你帮助统计该图像可以分成几部分？给定一个正整数的灵敏度值x, 如果某格与某相邻格子的相似度值的差值小于或等于x时，该格与该相邻格子属于同一个部件（所谓相邻，是指上、下、左、右之一）。如下图所示，当灵敏度值分别为10和5时，可以分为3个部件和5个部件。1015132522502352825102502452401001051112918

34、999104102100908810151325225023528251025024524010010511129189991041021009088【输 入】输入文件live.in中有若干行：第一行有三个整数n、m和x,表示图像有n行m列,设定的灵敏度为x。第二行起至第n+1行，每行有m个整数，互相间以一个空格分隔。第k+1行的第j个整数，表示图像中第k行第j列的相似度值。【输 出】 输出文件live.out中只有一行，该行只有一个整数，表示可以划分出的部件数。【样例输入1】 【样例输入2】4 6 10 4 6 5 10 15 13 252 250 235 10 15 13 252 250

35、23528 25 10 250 245 240 28 25 10 250 245 240 100 105 11 12 91 89 100 105 11 12 91 8999 104 102 100 90 88 99 104 102 100 90 88【样例输出1】 【样例输出2】3 5【数据限制】1n,m1000【问题分析】采用方法：深度搜索。本问题的实质就是对一个二维数组的搜索，要求在搜索的过程中求出相邻的两个数的差值小于等于x的连续最大区域单元格的个数以样例1为例，以中心点10为例，可以向4个不同方向查询。在同一行向左搜索不得小于1，向右搜索不得小于n，在同一列的搜索过程中，向上不得小于1

36、，向下搜索不得大于m，同时在搜索的必须保证连续相邻两数的绝对值差值不得大于灵敏度值x,完成对二维数组的搜索，计算出符合灵敏度的区块数量。在深度遍历的过程中，分别按照四个方向深度遍历，在搜索遍历过程中同时满足三个条件：在规定的二维数组行列中搜索、该结点数据内有被纳入其他区域中和相邻连续区域的绝对差值小于等于比当前已获取的最小值灵敏度值x，符合要求则递归处理下一个数值，不符合回溯，遍历完所有二维数组结点。【程序代码】program live;var f:array1.1000,1.1000of integer; /用于存放二维数组的值； visited:array1.1000,1.1000of b

37、oolean;/标识二维数组是否被访问过； n,m,x,i,j,re:longint;procedure dfs(i,j:longint);/开展以某点为中心，敏感度为x的上下左右搜索； begin visitedi,j:=false; if (i>1) and visitedi-1,j and (abs(fi-1,j-fi,j)<=x) then dfs(i-1,j); if (i<n) and visitedi+1,j and (abs(fi+1,j-fi,j)<=x) then dfs(i+1,j); if (j>1) and visitedi,j-1 an

38、d (abs(fi,j-1-fi,j)<=x) then dfs(i,j-1); if (j<m) and visitedi,j+1 and (abs(fi,j+1-fi,j)<=x) then dfs(i,j+1); end;begin assign(input,'live.in');reset(input); assign(output,'live.out');rewrite(output); read(n,m,x); /读入n、m和敏感程度x的值； for i:=1 to n do for j:=1 to m do read(fi,j);

39、/读入二维数组值 re:=0;fillchar(visited,sizeof(visited),true);/初始化标识数组 for i:=1 to n do for j:=1 to m do /按列、行逐个搜索 if visitedi,j then begin inc(re);dfs(i,j);end;/假如该值没有被访问过，则作为一个区域，并开展敏感度 x的搜索； writeln(re); close(input);close(output);end.6数的拆分（snumber.pas）【问题描述】对于正整数 n ，输出其和等于 n 且满足以下限制条件的所有正整数的和式，以及和式的总数。组

40、成和式的数字自左至右构成一个非递增的序列。如n=4，程序输出为：4=44=3+14=2+24=2+1+14=1+1+1+15【输入文件】输入文件snumber.in仅一行，该行只有一个正整数n(1n50)。【输出文件】输出文件snumber.out包含若干行，最后一行输出和式的数目，除此之外，前面每一行输出一个和式，组成和式的数字自左至右构成一个非递增的序列，不同行的和式先按照等号右边的第一个数字降序排列，若第一个数字相同，则按第二个数字降序排列，依此类推，直到输出所有和式为止。【输入样例】5【输出样例】5=55=4+15=3+25=3+1+15=2+2+15=2+1+1+15=1+1+1+1

41、+17【问题分析】解决方法：深度搜索+调整剪枝。问题的实质就是对输入的n进行拆分。根据样例建立的一颗如图所示的搜索树。 5 50 41 32 22 10 20 10 10 10 11 21 11 11 10 11 11 11 11第一层第二层第三层由样例图可知，每一组数据存在两个数字，前一个数字为依次需要拆分的数字，另一个为下一拆分起点最大数值（该数值在取值过程中需要进行适当的调整，与先前所拆分的数值进行比较，取两者较小数值为再次拆分对象，即为下一层搜索对象的起始值，目的避免重复拆分数值，进行适度调整剪枝），然后对该数值进行递归处理，判断剩余的数值是否为0，是则打印，并回溯至上一层，继续该层中

42、其他数值的拆分。不是则按序穷举当前层的所有取值，并递归深搜下一层剩余数值的拆分。以上图拆分5=2+2+1和5=2+1+1+1为例。首先在完成前一组数值拆分恢复现场，回溯穷举至2（第一层），得第一个拆分数值2，余下的数值5-2，即为3，剩下数值3与已拆分前一个所得数值比较取较小值2（避免5再次拆分成2和3），获得拆分数值穷举范围即2-1，进入第二层搜索，首先是穷举2，获得第二个拆分数值2，计算剩余数值得1，然后递归调拆分余下的数值1，首先判断剩下的数值是否为0（完成拆分），不是，该数值与前一个拆分所得的数值2比较取小数值得1，获得该数的数值拆分范围为1-1，进入第三层搜索，取第三个拆分数值1，同

43、时剩下的数值减去该数值得0，递归调用，拆分余下的数值0，在递归调用过程中，发现剩余数值为0，递归调用结束，即打印该拆分数即4=2+2+1，恢复现场至上一层，得剩余数值为1，再次恢复现场至上一层（第二层），得剩余数值为3，穷举下一个拆分数值1，据悉完成5=1+1+1+1+1的拆分。【程序代码】program snumber;const maxn=50;var a:array0.maxnof integer; /用于存放拆分的数值； left,n:integer;变量left用于存放n拆分以后所剩下的值 total:longint;procedure dfs(k:integer);var i,mi

44、n:integer;begin if left=0 then begin 当剩下的的值为“0”时，完成一组拆分，累加 write(n,'=',a1);total:=total+1; for i:=2 to k-1 do write('+',ai);writeln; end else begin if left<ak-1 then min:=left else min:=ak-1; for i:=min downto 1 do begin ak:=i;left:=left-i; dfs(k+1); left:=left+i; end; end;end;beg

45、in assign(input,'snumber.in');reset(input); assign(output,'snumber.out');rewrite(output); readln(n);a0:=n;left:=n;total:=0; dfs(1);writeln(total); close(input);close(output);end.7.棋 盘（USACO练习题checker.pas）【问题描述】检查一个如下的6×6的跳棋棋盘，有六个棋子被放置在棋盘上，使得每行、每列只有一个，每条对角线(包括两条主对角线的所有平行线)上至多有一个棋

46、子，如下图所示。上面的布局可以用序列2 4 6 1 3 5来描述，第i个数字表示在第i行的相应位置有一个棋子，如下： 行号 1 2 3 4 5 6 列号 2 4 6 1 3 5 这只是跳棋放置的一个解。请编一个程序找出所有跳棋放置的解。并以上面的序列方法输出解（按字典顺序排列）。请输出前3个解，最后一行是解的总个数。 【输入格式】 一个数字N (6 <= N <= 13) 表示棋盘是N × N大小的。 【输出格式】 前三行为前三个解，每个解的两个数字之间用一个空格隔开，第四行只有一个数字，表示解的总数。 【输入样例】6 【输出样例】2 4 6 1 3 5 3 6 2 5

47、1 4 4 1 5 2 6 3 4【问题分析】解决方法：深搜+优化。问题的实质就是类似八皇后问题。首先建立一颗搜索树，如下图所示以6×6的跳棋棋盘建立的一颗搜索树，在深度搜索解的过程中最为主要的是检查判断，即检查同一列、对角线是否有其他棋子存在，为此可以通过建立标志数组bi、ci-k和dk+i。数组bi控制同一列只能有一个棋子存在；ci-k控制“”对角线是否有棋子存在，在同一“”对角线上其行列坐标之差是相等的；dk+i控制“/”对角线是否有棋子存在，在同一“”对角线上其行列坐标之和是相等的。这样在放置下一个棋子的时候，判断需要放置棋子位置的所在的列、对角线上是否有棋子，即该棋子的列、

48、对角线标志值是否为初始值（“0”），是则可以放置该棋子，然后递归调用，直到depth>n,回溯；反之枚举同一行中的其他列放置位置。继续判断，一旦发现该行不存在合适的棋子放置位置时，同样，回溯，修改上一行中棋子放置位置，直到遍历棋盘中的所有的位置。问题优化：但是这样的搜索对于该题最后一个数据测试数据无法通过。为此可以优化该算法。可以通过考虑对称方法。如果n是偶数，第一行枚举前一半的数，这样每搜索出一种方案后，沿中线对称过来又是一种方案，并且因为第一行的数小于一半，对称过来的方案总大于原方案，即在搜索树中后被搜索到，不会出现重复的情况。 如果n是奇数，先在中间行和中间列放之，并且位置都不超过

49、半数(<n div 2)，且中间行大于中间列，这样每搜索出一种方案，把它对称旋转后一共有8种方案，因为中间行和中间列的的不出现重复，所以8种方案不重复。这样只需枚举原来的1/8即可。 1 2 1 1 1 1 1 1 1 1 1 2 1 1 1 2 1 1 1 1 2 1 1 1 2 1 1 1 1 1 1 1 2 11 2 3 4 5 6123456 1 1【程序代码】var a:array-50.50 of longint; b,c,d：array-50.50 of boolean；n,t:longint;procedure dfs(k:longint);var j,i:longint;beginif k>n then begin if t<3 then begin write(a1); for j:=2 to n do write(' ',aj);writeln;end;t:=t+1;exit;end;for i:=1 to n doif (bi=0) and (ci-k=0) and (dk+i=0) then begin ak:=i;bi:=1;ci-k:=1;di+k:=1;dfs(k+1);bi:=0;ci-k:=0;di+k:=0;end;end;beginassign(input,'