浅谈搜索算法在信息学竞赛中的应用汇编

1、浅谈搜索算法在信息学竞赛中的应用Search Algorithm in Informatics【前言】在信息学竞赛日渐普及，信息技术越来越重要的今天，搜索算法，一种充分利用计算机计算速度遍历所有可能解的算法，被认为非常基础也非常重要。让我们走近这听起 来非常高端的算法，一窥其真面目。【摘要】本文对搜索算法的两个分支一一深度优先搜索（dfs）和广度优先搜索（bfs）展开了研究，并通过在例题中的各种应用分析两种搜索方法的优化，对这一类的算法进行了 通用总结。【关键词】搜索算法信息学深度优先搜索广度优先搜索DFS BFSJ枝【研究过程】主要算法（一）深度优先搜索（dfs ）深度优先搜索属于图算法的一

2、种，英文缩写为DFS即Depth First Search.其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次。主要用于图的搜索，但是在许多别的领域也有广泛应用。举例说明之：下图是一个无向图，如果我们从 A点发起深度优先搜索（以下 的访问次序并不是唯一的，第二个点既可以是 B也可以是C,D）,则我们可能得 到如下的一个访问过程：A->B->E （没有路了！回溯到A）->C->F->H->G->D （没 有路，最终回溯到A,A也没有未访问的相邻节点，本次搜索结束）.让我们先看一道经典例题。【深度搜索基础】迷宫路径（深搜）

3、Description这是实验心理学中的一个经典问题，心理学家把一只老鼠从一个无顶盖的大 盒子的入口处赶进迷宫。迷宫中设置很多隔壁，对前进方向形成了多处障碍，心理学家在迷宫的唯一出口处放置了一块奶酪， 吸引老鼠在迷宫中寻找通路以到达 出口。迷宫以一个01矩阵表示，0表示通路，1表示不通，入口在座标（1,1）, 出口在（m,n） , m表示行，n表示列。老鼠在某一格子时，可以向周围 8个格 子移动（只要目的格子不为1或没有超出边界）。现求解出到达出口的最少移动 步数，注：站在（m,n）即表示已经抵达出口，起始时老鼠站在（1,1）处。入口（1）（6,8）图2. 4用niaz巳叫n表示的迷宫迷宫的定

4、义如下：const m=6 /迷宫的实际行n=8 迷宫的实际列maze:array L .1. . n of integer; 表示通路.1表示不通这道题的基本思路是以（1,1）即起点为起始点，不断地通过递归来拓展每一个可能节点，直到找到终点或无路可走为止。在遍历所有可能路径的同时统计 最短的一条路，输出答案即可。实际 C+代码如下：#include<iostream>#include<string.h>using namespace std;int g5252,n,m,xmin=10000;struct int x;int y;xx8;void x(int nn,in

5、t mm,int c);main()(int s,ss;xx0.x=0;xx0.y=1;xx1.x=1;xx1.y=1;xx2.x=1;xx2.y=0;xx3.x=1;xx3.y=-1;xx4.x=0;xx4.y=-1;xx5.x=-1;xx5.y=-1;xx6.x=-1;xx6.y=0;xx7.x=-1;xx7.y=1;cin>>n>>m;for(s=0;s<=n+1;s+)gs0=1;gsm+1=1;for(s=0;s<=m+1;s+)g0s=1;gn+1s=1;for(s=1;s<=n;s+)for(ss=1;ss<=m;ss+)cin&g

6、t;>gsss;x(1,1,0);if(xmin=10000)cout<<"no"else cout<<xmin;void x(int nn,int mm,int c)int s;if(nn=n&&mm=m)&&(c<xmin)xmin=c;else if(c<xmin)for(s=0;s<=7;s+)if(gnn+xxs.xmm+xxs.y=0) gnn+xxs.xmm+xxs.y=2;x(nn+xxs.x,mm+xxs.y,c+1);gnn+xxs刈mm+xxs.y=0; 这段代码中应用了标

7、志数组的小技巧，使程序更加简洁明了。同时，我们可 以发现这种算法在最不利情况下的时间效率其实非常低，所以在这里加了非常有效的可行性剪枝，使效率大大提高。关于一些剪枝方法，我会在后文谈到。（二）广度优先搜索（bfs ）宽度优先搜索算法（又称广度优先搜索）是最简便的图的搜索算法之一，这 一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最 小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫 BFS属于一种 盲目搜寻法，目的是系统地展开并检查图中的所有节点， 以找寻结果。换句话说， 它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。在bfs中，通常使用先

8、进先出队列（一种数据结构）来维护，并通过判重使 搜索规模得到控制，避免做无用功，重复搜索同样的状态。如图所示：以1为起点，8为终点，路径长度为1。在图中，我们可以通过路径段数把 整个图划分成三层，其中，2, 3, 4是由1直接拓展出的节点，先把他们加入队 列。接下来取出2,通过2拓展出5, 6两个节点并加入队列。下一步取出 3,通 过3拓展出6, 7。需要注意的是，此时6已经在队列中了，所以不需要再次入 队，以后如果再遇到6也不需要入队，而且该情况仅对路径长度为1时适用。依此类推，当取出的节点为终点时就可以结束搜索了。我们再来看看例题。【宽度搜索基础】奇怪的电梯(宽搜)Description呵

9、呵，有一天我做了一个梦,梦见了一种很奇怪的电梯。大楼的每一层楼都 可以停电梯，而且第i层楼(1 <= i <= N)上有一个数字Ki(0 <= Ki <= N)。电梯只 有四个按钮：开，关，上，下。上下的层数等于当前楼层上的那个数字。当然， 如果不能满足要求，相应的按钮就会失灵。例如： 3 3 1 25代表了 Ki(K1=3,K2=3,)从一楼开始。在一楼，按 上”可以到4楼，按 下”是不起 作用的，因为没有-2楼。那么，从A楼到B楼至少要按几次按钮呢？这道题的思路和上面的最短路径其实有异曲同工之妙。 按一次按钮相当于走 过路径长度为一的路，到达的每层楼则相当于上图中的

10、节点， 但是哪两条节点问 有通路呢？这就要看每层楼上的 Ki值了，如果某层楼楼层数+/-Ki=另一楼层数， 那么这两个节点间就有长度为1的边相连。具体代码如下： #include<iostream> #include<string.h> using namespace std; void lift(int x,int c,int z); int g100,N,A,B,front,rear,step201,ss=0; bool boo201,arrive=false; int ki201;int s;memset(boo,true,sizeof(boo);cin>&

11、gt;N>>A>>B;for(s=1;s<=N;s+)cin>>kis;if(A!=B)booA=false;g0=A；front=0;stepgfront=0；rear=1;while(front!=rear)lift(gfront,stepgfront,1);lift(gfront,stepgfront,2);if(arrive)break;front+;front=front%100;if(ss=0)cout<<-1<<endl;else cout<<ss<<endl;else cout<&l

12、t;0<<endl;return 0;void lift(int x,int c,int z)if(z=1)x=x+kigfront;if(boox&&(x>0)&&(x<=N)boox=false;stepx=c+1;grear=x;rear+;rear=rear%100;if(x=B)arrive=true;ss=stepx;else x=x-kigfront;if(boox&&(x>0)&&(x<=N)boox=false;stepx=c+1;grear=x;rear+;rear=rear

13、%100;if(x=B)arrive=true;ss=stepx;一、优化方法：剪枝（一）剪枝的原则原则之一：正确性。因为它能够“剪去”搜索树中的一些“枝条”。 然而，如果在剪枝的时 候，将“长有”我们所需要的解的枝条也剪掉了， 那么，一切优化也就都失 去了意义。所以，对剪枝的第一个要求就是正确性， 即必须保证不丢失正确 的结果，这是剪枝优化的前提。我们利用“必要条件”来进行剪枝判断。 也 就是说，通过解所必须具备的特征、必须满足的条件等方面来考察待判断的 枝条能否被剪枝。这样，就可以保证所剪掉的枝条一定不是正解所在的枝条。 原则之二：准确性。即能够尽可能多的剪去不能通向正解的枝条。 准确性可

14、以说是剪枝优化 的生命。原则之三：高效性。经常还需要提高判断操作本身的时间效率。综上所述，我们可以把剪枝优化的主要原则归结为六个字：正确、准确、高效。（二）剪枝方法1、可行性剪枝搜索过程可以看作是对一棵树的遍历。 在很多情况下，并不是搜索树中的所有枝条都能通向我们需要的结果，很多的枝条实际上只是一些死胡同。如果我们能够在刚刚进入这样的死胡同的时候，就能够判断出来并立即剪枝，程序的效率往往会得到提高。而所谓可行性剪枝，正是基于这样一种考虑。2、最优性剪枝在我们平时遇到的问题中，有一大类是所谓最优化问题，即所要求 的结果是最优解。此时就可以利用最优性剪枝来简化搜索复杂度。在搜索的过程中，一般情况下，我们需要保存一个“当前最优解”， 实际上就是保存解的优度的一个下界。 在遍历到搜索树的叶子节点的时候， 我们就能得到一个新的解，当然也就得到了它的评价函数值，如果新解更 优则更新优值下限。搜索结束后，所保存的解就是最优解。那么，最优性剪枝又是如何进行的呢？当我们处在搜索树的枝条上时，可以通过某种 方法估算出该枝条上的所有解的评价函数的上界，即所谓估价函数。显然， 大于当前保存的优度的下界，是该枝条上存在最优解的必要条件，否则就 一定可以剪枝。所以，最优性剪枝也可以称为“上下界剪枝”。同时，我 们也可以看到，最优性