《2022年c语言技巧之搜索剪枝 .pdf》由会员分享，可在线阅读，更多相关《2022年c语言技巧之搜索剪枝 .pdf（29页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、搜索问题计算机学院2006 级师范班程文华搜索被称为“通用的解题法”，在算法和人工智能方面占有非常重要的低位，特别是在各类 ACM程序设计比赛中非常常见，在题目中一般位于中间位置，作为中等难度的题目出现。因此我们需要着重掌握各类的搜索算法，才能面对各类即将到来的ACM 大赛。 “只要功夫深，铁棒磨成针” ， “冰冻三尺，非一日之寒”，要能熟练的掌握和AC 比赛中的题目，必须在熟练掌握各类搜索算法的基础上勤加练题，也是唯一的好方法。本次讲解中，首先给出有关搜索的基本概念，然后针对各类专题，讲解具体的几个例题并加于分析（注：题目全部选自poj 中的题目）。一 概念介绍状态（ state ） 问题在
2、某一时刻的进展情况的数学描述。算符（ operator ） / 状态转移问题从一种状态变换成另一种( 或几种 ) 状态的操作。解答树搜索的过程实际是在遍历一个图，它的结点就是所有的状态，有向边对应于算符，而一个可行解就是一条从起始节点出发到目标状态集中任意一个结点的路径。特个图称为状态空间（ state space） ，这样的搜索称为状态空间搜索（Single-Agent Search） ，得到的遍历树称为解答数。基本搜索法：枚举枚举法的基本思想是根据提出的问题枚举所有可能状态，并用问题给定的条件检验哪些是需要的，哪些是不需要的。能使命题成立，即为其解。枚举算法的特点比较单纯，往往容易写出程序
3、，也容易证明算法的正确性和分析算法的时间复杂度，可以解决一些很小的问题。它的缺点是效率特别低，往往很多题目不能用枚举方法，用了只会超时。所以它适应于容易找到状态并且状态较少的题目。没有信心确定其状态较少，请勿立即动手写程序！深度优先搜索DFS （有时称为回溯法）遵循的搜索策略是尽可能深地搜索图，在深度优先搜索中，对于最新发现的顶点，如果它还有以此为起点而未探索到的边，就沿此边继续搜索下去。当结点V的所有边都已被探寻过时，搜索将回溯到发现结点V有那条边的始结点。这一过程一直进行到已发现从源结点可达的所有结点为止。如果还存在未被发现的结点，则选择另一个未发现的结点作为新的源结点重新上面的过程，直至
4、所有的结点都搜索到。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 29 页 - - - - - - - - - 宽度优先搜索 BFS 遵循的搜索策略是从源结点开始，把所有该结点的子结点都搜索完，在搜索每个结点的时候都把其子结点都放入一个队列的后面等待以后搜索，当把此层结点全部搜索完时，所有的下层结点也就进入了队列，继续这样的过程。当仍然没有找到解并且还有没有搜索到的结点时，以没有搜索的结点作为源结点继续上述的搜索过程，直至找到解。剪枝在搜索的过程中，在还没到达叶结点之前
5、就可以判断以此结点为根的子树不可能包含可行解或者最优解，因此不需要扩展这颗树，就像拿一把剪刀把这颗子树剪去，称为剪枝。还有一些搜索算法的概念没有给出如分支限界搜索，迭代加深搜索，迭代加宽搜索，A*算法等。他们都各种有适应的范围，也是较为复杂的搜索。专题 1：深度优先搜索DFS 深度优先搜索有很多呈现形式，一般用递归解决，但也可循环等解决，不管用什么实现，其都会遵循深度优先思想。下面是递归实现的程序框架，供初始学习者参考：Procedure DepthFirstSearch(State:Statetype;depth:integer); Begin For Operand:=1 to Opera
6、ndcount(State) do Begin NewState:=DoOperand(State,Operand); If Answer then PrintAnswer Else if depthn) Output(x); else for(int i=f(n,t);i=g(n,t);i+) xt=hi; if (Constraint(t)& Bound(t) Backtrack(t+1); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 29 页 - - - - -
7、 - - - - （1）循环解决的深搜（此题又像枚举）1166 The ClocksDescription There are nine clocks in a 3*3 array (figure 1). The goal is to return all the dials to 12 oclock with as few moves as possible. There are nine different allowed ways to turn the dials on the clocks. Each such way is called a move. Select for eac
8、h move a number 1 to 9. That number will turn the dials 90 (degrees) clockwise on those clocks which are affected according to figure 2 below. 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 29 页 - - - - - - - - - Input Your program is to read from standard inpu
9、t. Nine numbers give the start positions of the dials. 0=12 oclock, 1=3 oclock, 2=6 oclock, 3=9 oclock. Output Your program is to write to standard output. Output a shortest sorted sequence of moves (numbers), which returns all the dials to 12 oclock. You are convinced that the answer is unique. Sam
10、ple Input 3 3 0 2 2 2 2 1 2 Sample Output 4 5 8 9 大概题意：有九个时钟，每个时钟只有4 种状态： 12 ：00，3：00 ，6：00，9：00。分别用0，1，2，3 代替。现在有9 种操作，如表2 所示，每种操作能使对应的钟顺时针旋转90 度。现在给出9 个时钟的初始状态，问怎么用最少的操作使得这9 个时钟都指向12 ：00 。输入给出9 个数字，用1，2，3，4 代表每个时钟的初始状态。输出要求给出操作代号，此操作代号按升序排列。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - -
11、名师精心整理 - - - - - - - 第 4 页，共 29 页 - - - - - - - - - 4 种状态 9 种操作解题思想：可以观察到这九个时钟都是按顺时针旋转，由于求最少的操作数，我们知道一个时钟如果旋转 4 次，那么它就回到了初始位置，相当于没有操作，那么上面的4 次操作是多余的，不可能成为解，因此可以得出结论，每个操作，如操作1 ABDE 最多只需要操作3 次，最少是不操作。 那么 9 个时钟的有49 种方法，此数字并不是很大， 完全可以在有限的1000ms运行出结果。因此可以用最笨的方法解决。本题如果先不对程序加以分析和解剖，洞察问题的本质和寻找规律，那么将是非常严重的问题
12、，不但效率低，甚至严重超时。参考代码：#include using namespace std; int temp9;/存储每一列时钟的状态int main() int move99= /操作表，对对应有操作为1 1,1,0,1,1,0,0,0,0, 1,1,1,0,0,0,0,0,0, 0,1,1,0,1,1,0,0,0, 1,0,0,1,0,0,1,0,0, 0,1,0,1,1,1,0,1,0, 0,0,1,0,0,1,0,0,1, 0,0,0,1,1,0,1,1,0, 0,0,0,0,0,0,1,1,1, 0,0,0,0,1,1,0,1,1 ; int ways9; /各操作的遍数boo
13、l find; int clock9; /时钟的初始状态int i,j; for (i=0;iclocki; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 29 页 - - - - - - - - - / 下面 9 层循环遍历了所有可能的出现的情况for (ways0=0;ways04;ways0+) for (ways1=0;ways14;ways1+) for (ways2=0;ways24;ways2+) for (ways3=0;ways34;ways3+) f
14、or (ways4=0;ways44;ways4+) for (ways5=0;ways54;ways5+) for (ways6=0;ways64;ways6+) for (ways7=0;ways74;ways7+) for (ways8=0;ways84;ways8+) find=true; for (i=0;i9;i+) /对每个时钟旋转 tempi=clocki; for (j=0;j9;j+) tempi+=waysj*moveji; tempi%=4; if(tempi!=0) find=false; break; if(find) for (i=0;i9;i+) for (j=
15、0;jwaysi;j+) couti+1 ; coutendl; return 0; return 0; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 29 页 - - - - - - - - - （2） 递归解决的简单搜索1562 Oil Deposits Description The GeoSurvComp geologic survey company is responsible for detecting underground oil deposits.
16、GeoSurvComp works with one large rectangular region of land at a time, and creates a grid that divides the land into numerous square plots. It then analyzes each plot separately, using sensing equipment to determine whether or not the plot contains oil. A plot containing oil is called a pocket. If t
17、wo pockets are adjacent, then they are part of the same oil deposit. Oil deposits can be quite large and may contain numerous pockets. Your job is to determine how many different oil deposits are contained in a grid. Input The input contains one or more grids. Each grid begins with a line containing
18、 m and n, the number of rows and columns in the grid, separated by a single space. If m = 0 it signals the end of the input; otherwise 1 = m = 100 and 1 = n = 100. Following this are m lines of n characters each (not counting the end-of-line characters). Each character corresponds to one plot, and i
19、s either *, representing the absence of oil, or , representing an oil pocket. Output are adjacent horizontally, vertically, or diagonally. An oil deposit will not contain more than 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 29 页 - - - - - - - - - 100 pocket
20、s. Sample Input 1 1 * 3 5 * * * 1 8 * 5 5 * * * * * 0 0 Sample Output 0 1 2 2 大概题意：有一个 GeoSurvComp地质勘探公司正在负责探测地底下的石油块。这个公司在一个时刻调查一个矩形区域，并且创建成一个个的格子用来表示众多正方形块。它然后使用测定设备单个的分析每块区域，决定是否有石油。一块有石油小区域被称为一个pocket，假设两个 pocket是相邻的，然后他们就是相同石油块的一部分，石油块可能非常的大并且包涵很多的pocket。你的任务就是在一个网格中存在多少个石油块。输入首先给出图的大小，然后给出这个图。
21、*代表没有石油， 代表存在石油。输出每种情况下石油块的个数。解题思想：对于个给出的图，用一个整型的二维数组代表有无石油，然后循环这个二维数组，如发现存在石油，则以这个方格为起始结点进行深搜，如发现石油就标记为 -1，然后继续遍历这个二维数组，直至找到下一个有石油的方格，找到一个计数加 1。最后的计数即为所求的石油的方块数。参考代码：#include using namespace std; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 29 页 - - - - - -
22、- - - void seach(int x,int y); char oil100100; bool visit100100; int m,n; int go82=-1,-1,0,-1,1,-1,1,0,1,1,0,1,-1,1,-1,0;/算符存入一个二维数组里void seach(int x,int y) int i; visitxy=true; for (i=0;i=0&(x+goi0)=0&(y+goi1)mn&(m|n) for (int i=0;im;i+) for (j=0;joilij; visitij=false; int count=0;/计数值for (i=0;im;i
23、+) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 29 页 - - - - - - - - - for (j=0;jn;j+) if(oilij=&!visitij) seach(i,j); count+; coutcountendl; return 0; （3） 递归解决的带剪枝的深搜2248 Addition Chains Description An addition chain for n is an integer sequence with the fol
24、lowing four properties: a0 = 1 am = n a0 a1 a2 . am-1 am For each k (1=k=m) there exist two (not necessarily different) integers i and j (0=i, j=k-1) with ak=ai+aj You are given an integer n. Your job is to construct an addition chain for n with minimal length. If there is more than one such sequenc
25、e, any one is acceptable. For example, and are both valid solutions when you are asked for an addition chain for 5. Input The input will contain one or more test cases. Each test case consists of one line containing one integer n (1=n=100). Input is terminated by a value of zero (0) for n. 名师资料总结 -
26、- -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 29 页 - - - - - - - - - Output For each test case, print one line containing the required integer sequence. Separate the numbers by one blank. Hint: The problem is a little time-critical, so use proper break conditions wher
27、e necessary to reduce the search space. Sample Input 5 7 12 15 77 0 Sample Output 1 2 4 5 1 2 4 6 7 1 2 4 8 12 1 2 4 5 10 15 1 2 4 8 9 17 34 68 77 大概题意：一个整数 n 的加法链就是一个满足下面性质的序列：a0 = 1 am = n a0 a1 a2 . am-1 am 对于每个 k (1=k=m) 存在两个整数(不一定不同 ) i 和 j (0=i, j=k-1) 有ak=ai+aj 你被给定一个n，你的工作是构造一个最短长度的加法链，假设这样的
28、序列超过一个，任何一个合适的序列均可。输入包括很多种测试实例，每个测试实例由一行组成，即就是n，然后输出这个加法链的数字序列。解题思想：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 29 页 - - - - - - - - - 由于每个数字都是由前面的两个数字之和。并且要使这个数字链最短。那么我们可以深搜一下，假设后面的数是由前面的两个数字的和,前面的两个数是我们可以逐渐往前扫描，那么算符就是前面的两个数相加，得到后面的数，这样深搜下去，并且记录找到解后这个数据链的长
29、度。当数据长度最短时即为所求的解，这里为了加快寻找速度，对于一些不必要搜索的我们不需要去搜索，于是就把它剪去。参考代码：#include #include using namespace std; int n,page, ans, a100, r100, d202; void dfs(int); void print(); void init(); int main() while(scanf(%d, &n) & n) init(); page=0; dfs(0); print(); return 0; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - -
30、- - - - - - 名师精心整理 - - - - - - - 第 12 页，共 29 页 - - - - - - - - - void init() int i; ans = n; a0 = 1; for(i = n; i 0; i -) di = di + i + 1; /di中存放到给定数字的最短的距离数 void print() int i; for(i = 0; i = ans) /剪枝，当搜索到的长度加上从此数到给定的数最短/的距离的值比已搜到的最短的距离还要长时，则不需要深搜下去，直接跳出，继续相邻结/点的搜素 return; if(al = n) ans = l; for(i
31、 = 0; i = 0; i -) /此两层循环即为循环所有算符，以找到新的状态 for(k = i; k = 0; k -) al + 1 = ai + ak; /后一个数由前两个个值之和得到if(al + 1 al & al + 1 = n) /排除不符合的情况dfs(l + 1); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 29 页 - - - - - - - - - 专题 2：宽度优先搜索BFS （1）从结点 V 开始，给 V 标上已到达（或访问）标记此时
32、称结点V 还没有被检测，而当算法访问了邻接于某结点的所有结点时，称该结点被检测了。（2）访问邻接于V 且尚未被访问的所有结点这些结点是新的未被访问的结点。将这些结点依次放置到一个未检测结点表（队列Q）中（末端插入）。（3）标记 V 已被检测。（4）若未检测结点表为空，则算法终止；否则从未检查结点表的表头取一结点作为下一个待检测结点。按照广度优先的顺序遍历状态空间，一般用 open ，close表来实现。 不要用循环队列，因为需要保存已出列的结点。算法框架如下：Procedure BreadthFirstSearch（InitialState:StateType）; Begin Enqueue(
33、InitialState)；While Not EmptyQueue do Begin Dequeue （State）；For Operand：=1 to OperandCount（ State） do Begin NewState：=DoOperand（State， Operand ）；If Answer（NewState） then PrintAnswer；Else Enqueue（NewState）；End ；End ；End ；说明：函数名为BreadthFirstSearch，只有一个形参InitialState表示初始状态。函数体内开始是一个进队列函数，把初始状态进队列，然后就是一
34、个循环语句，如果队列不为空则循环，循环体内是首先把队列的头结点取出，然后循环算符，产生此结点的所有后继结点，若出现解，者打印输出，若还没出现解则如队列。（1） 常见求最少步数宽搜2243 Knight Moves Description A friend of you is doing research on the Traveling Knight Problem (TKP) where you are to find the shortest closed tour of knight moves that visits each square of a given set of n sq
35、uares on a chessboard exactly once. He thinks that the most difficult part of the problem is determining the smallest number of knight moves between two given squares and that, once you have accomplished this, finding the tour would be easy. Of course you know that it is vice versa. So you offer him
36、 to write a program that solves the difficult part. 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 29 页 - - - - - - - - - Your job is to write a program that takes two squares a and b as input and then determines the number of knight moves on a shortest route
37、from a to b. Input The input will contain one or more test cases. Each test case consists of one line containing two squares separated by one space. A square is a string consisting of a letter (a-h) representing the column and a digit (1-8) representing the row on the chessboard. Output For each tes
38、t case, print one line saying To get from xx to yy takes n knight moves. Sample Input e2 e4 a1 b2 b2 c3 a1 h8 a1 h7 h8 a1 b1 c3 f6 f6 Sample Output To get from e2 to e4 takes 2 knight moves. To get from a1 to b2 takes 4 knight moves. To get from b2 to c3 takes 2 knight moves. 名师资料总结 - - -精品资料欢迎下载 -
39、- - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 29 页 - - - - - - - - - To get from a1 to h8 takes 6 knight moves. To get from a1 to h7 takes 5 knight moves. To get from h8 to a1 takes 6 knight moves. To get from b1 to c3 takes 1 knight moves. To get from f6 to f6 takes 0 knight moves
40、. 大概题意：一个 8 行 8 列的棋谱，任意给出knight的两个位子，问按照knight的走法，从其中的一个位子出发，问至少需要经过几步到达另外一个位子。行用 1-8表示，列用a-h表示。输出格式见上。解题思想：起始位子作为初始结点进入队列，然后取出第一个结点，把knight能走的位子依次全部进入队列，在进入队列前判断是否为终结点。开辟一个二维数组记录步数。参考代码：#include #include using namespace std; struct point int x,y; ; int chessboard88;/记录步数vector v; point p; bool find
41、; int index; int start_x,start_y,end_x,end_y; void deal(int x,int y,int time) if(x=end_x&y=end_y) find=true; return; if(x-2=0&y-1=0&chessboardx-2y-1=-1) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 17 页，共 29 页 - - - - - - - - - chessboardx-2y-1=time+1; p.x=x-2; p.y
42、=y-1; v.push_back(p); if(x-2=0&y+18&chessboardx-2y+1=-1) chessboardx-2y+1=time+1; p.x=x-2; p.y=y+1; v.push_back(p); if(x+28&y+18&chessboardx+2y+1=-1) chessboardx+2y+1=time+1; p.x=x+2; p.y=y+1; v.push_back(p); if(x+2=0&chessboardx+2y-1=-1) chessboardx+2y-1=time+1; p.x=x+2; p.y=y-1; v.push_back(p); if
43、(x-1=0&y+2=0&y-2=0&chessboardx-1y-2=-1) chessboardx-1y-2=time+1; p.x=x-1; p.y=y-2; v.push_back(p); if(x+18&y+28&chessboardx+1y+2=-1) chessboardx+1y+2=time+1; p.x=x+1; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 18 页，共 29 页 - - - - - - - - - p.y=y+2; v.push_back(p)
44、; if(x+1=0&chessboardx+1y-2=-1) chessboardx+1y-2=time+1; p.x=x+1; p.y=y-2; v.push_back(p); int main() char _s,_e; int s,e; while (cin_ss_ee) start_x=(int)(_s-a); start_y=s-1; end_x=(int)(_e-a); end_y=e-1; memset(chessboard,-1,sizeof(chessboard); chessboardstart_xstart_y=0; p.x=start_x; p.y=start_y;
45、v.clear(); v.push_back(p); find=false; index=0; while (!find) deal(vindex.x,vindex.y,chessboardvindex.xvindex.y); index+; coutTo get from _ss to _ee takes chessboardend_xend_y knight moves.endl; return 0; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 19 页，共 29 页 - -
46、 - - - - - - - （2） 宽搜经典3278 Catch That Cow Description Farmer John has been informed of the location of a fugitive cow and wants to catch her immediately. He starts at a point N (0 N 100,000) on a number line and the cow is at a point K (0 K 100,000) on the same number line. Farmer John has two mode
47、s of transportation: walking and teleporting. * Walking: FJ can move from any point X to the points X - 1 or X + 1 in a single minute * Teleporting: FJ can move from any point X to the point 2 X in a single minute. If the cow, unaware of its pursuit, does not move at all, how long does it take for F
48、armer John to retrieve it? Input Line 1: Two space-separated integers: N and KOutput Line 1: The least amount of time, in minutes, it takes for Farmer John to catch the fugitive cow. Sample Input 5 17 Sample Output 4 Hint 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - -
49、第 20 页，共 29 页 - - - - - - - - - The fastest way for Farmer John to reach the fugitive cow is to move along the following path: 5-10-9-18-17, which takes 4 minutes. 大概题意：Farmer John 想抓到一头牛， Farmer John 在一个数轴的一个位子， 牛在数轴的另一个位子。但Farmer John 这个人在一个单位时间内可以有三种走的方式，一是走到数轴的下一格，或是前一格，或是他的数轴的两倍的格子上，为此人最快抓到牛的时间
50、。解题思想：其实是上面的一个变形，棋子变成了一个人和一头牛，然后走的规则变了一下，问的步数变成了时间。所以模板还是基本和上面的一样。参考代码：#include #include using namespace std; int digit200001; int start,end; int index; bool find; vectorvc; void deal(int x,int time) if (x=end) find=true; return; if (x+1=0&digitx-1=-1) digitx-1=time+1; vc.push_back(x-1); if (x*2star