淺談搜索算法在信息學(xué)競賽中的應(yīng)用

1、淺談搜索算法在信息學(xué)競賽中的應(yīng)用 Search Algorithm in Informatics【前言】在信息學(xué)競賽日漸普及，信息技術(shù)越來越重要的今天，搜索算法，一種充分利用計算機計算速度遍歷所有可能解的算法，被認為非?；A(chǔ)也非常重要。讓我們走近這聽起來非常高端的算法，一窺其真面目。【摘要】本文對搜索算法的兩個分支深度優(yōu)先搜索（dfs）和廣度優(yōu)先搜索（bfs）展開了研究，并通過在例題中的各種應(yīng)用分析兩種搜索方法的優(yōu)化，對這一類的算法進行了通用總結(jié)?！娟P(guān)鍵詞】搜索算法 信息學(xué) 深度優(yōu)先搜索 廣度優(yōu)先搜索 DFS BFS剪枝【研究過程】主要算法（1） 深度優(yōu)先搜索（dfs）深度優(yōu)先搜索屬于圖算法的

2、一種，英文縮寫為DFS即Depth First Search.其過程簡要來說是對每一個可能的分支路徑深入到不能再深入為止，而且每個節(jié)點只能訪問一次。 主要用于圖的搜索，但是在許多別的領(lǐng)域也有廣泛應(yīng)用。舉例說明之：下圖是一個無向圖，如果我們從A點發(fā)起深度優(yōu)先搜索（以下的訪問次序并不是唯一的，第二個點既可以是B也可以是C,D），則我們可能得到如下的一個訪問過程：A->B->E（沒有路了！回溯到A)->C->F->H->G->D（沒有路，最終回溯到A,A也沒有未訪問的相鄰節(jié)點，本次搜索結(jié)束）. 讓我們先看一道經(jīng)典例題?！旧疃人阉骰A(chǔ)】迷宮路徑（深搜）Desc

3、ription 這是實驗心理學(xué)中的一個經(jīng)典問題，心理學(xué)家把一只老鼠從一個無頂蓋的大盒子的入口處趕進迷宮。迷宮中設(shè)置很多隔壁，對前進方向形成了多處障礙，心理學(xué)家在迷宮的唯一出口處放置了一塊奶酪，吸引老鼠在迷宮中尋找通路以到達出口。 迷宮以一個01矩陣表示，0表示通路，1表示不通，入口在座標（1,1），出口在（m,n），m表示行，n表示列。老鼠在某一格子時，可以向周圍8個格子移動（只要目的格子不為1或沒有超出邊界）。現(xiàn)求解出到達出口的最少移動步數(shù)，注：站在（m,n）即表示已經(jīng)抵達出口，起始時老鼠站在（1,1）處。 這道題的基本思路是以（1，1）即起點為起始點，不斷地通過遞歸來拓展每一個可能節(jié)點，直

4、到找到終點或無路可走為止。在遍歷所有可能路徑的同時統(tǒng)計最短的一條路，輸出答案即可。實際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,int mm,int c);· main()· · int s,ss;·

5、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+)·

6、; for(ss=1;ss<=m;ss+)· cin>>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)

7、3; 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.xmm+xxs.y=0;· · · ·這段代碼中應(yīng)用了標志數(shù)組的小技巧，使程序更加簡潔明了。同時，我們可以發(fā)現(xiàn)這種算法在最不利情況下的時間效率其實非常低，所以在這里加了非常有效的可行性剪枝，使效率大大提高。關(guān)于一些剪枝方法，我會在后文談到。（2） 廣度優(yōu)先搜索（bfs）寬度優(yōu)先搜索算法（又稱廣度優(yōu)先搜索）是

8、最簡便的圖的搜索算法之一，這一算法也是很多重要的圖的算法的原型。Dijkstra單源最短路徑算法和Prim最小生成樹算法都采用了和寬度優(yōu)先搜索類似的思想。其別名又叫BFS，屬于一種盲目搜尋法，目的是系統(tǒng)地展開并檢查圖中的所有節(jié)點，以找尋結(jié)果。換句話說，它并不考慮結(jié)果的可能位置，徹底地搜索整張圖，直到找到結(jié)果為止。在bfs中，通常使用先進先出隊列（一種數(shù)據(jù)結(jié)構(gòu)）來維護，并通過判重使搜索規(guī)模得到控制，避免做無用功，重復(fù)搜索同樣的狀態(tài)。如圖所示：以1為起點，8為終點，路徑長度為1。在圖中，我們可以通過路徑段數(shù)把整個圖劃分成三層，其中，2，3，4是由1直接拓展出的節(jié)點，先把他們加入隊列。接下來取出2，

9、通過2拓展出5，6兩個節(jié)點并加入隊列。下一步取出3，通過3拓展出6，7。需要注意的是，此時6已經(jīng)在隊列中了，所以不需要再次入隊，以后如果再遇到6也不需要入隊，而且該情況僅對路徑長度為1時適用。依此類推，當取出的節(jié)點為終點時就可以結(jié)束搜索了。我們再來看看例題?！緦挾人阉骰A(chǔ)】奇怪的電梯（寬搜） Description 呵呵，有一天我做了一個夢，夢見了一種很奇怪的電梯。大樓的每一層樓都可以停電梯，而且第i層樓(1 <= i <= N)上有一個數(shù)字Ki(0 <= Ki <= N)。電梯只有四個按鈕：開，關(guān)，上，下。上下的層數(shù)等于當前樓層上的那個數(shù)字。當然，如果不能滿足要求，相

10、應(yīng)的按鈕就會失靈。例如：3 3 1 2 5代表了Ki(K1=3,K2=3,)，從一樓開始。在一樓，按“上”可以到4樓，按“下”是不起作用的，因為沒有-2樓。那么，從A樓到B樓至少要按幾次按鈕呢？ 這道題的思路和上面的最短路徑其實有異曲同工之妙。按一次按鈕相當于走過路徑長度為一的路，到達的每層樓則相當于上圖中的節(jié)點，但是哪兩條節(jié)點間有通路呢？這就要看每層樓上的Ki值了，如果某層樓樓層數(shù)+/-Ki=另一樓層數(shù)，那么這兩個節(jié)點間就有長度為1的邊相連。具體代碼如下：· #include<iostream>· #include<string.h>·

11、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 main()· · int s;· memset(boo,true,sizeof(boo);· cin>>N>>A>>B;· for(s=1;s<=N;s+)cin>>ki

12、s;· 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;

13、3; else cout<<ss<<endl;· · else cout<<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+;·

14、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%100;· · if(x=B)arrive=true;ss=stepx;· · 1、 優(yōu)化方法:剪枝（一）

15、剪枝的原則原則之一：正確性。    因為它能夠“剪去”搜索樹中的一些“枝條”。然而，如果在剪枝的時候，將“長有”我們所需要的解的枝條也剪掉了，那么，一切優(yōu)化也就都失去了意義。所以，對剪枝的第一個要求就是正確性，即必須保證不丟失正確的結(jié)果，這是剪枝優(yōu)化的前提。我們利用“必要條件”來進行剪枝判斷。也就是說，通過解所必須具備的特征、必須滿足的條件等方面來考察待判斷的枝條能否被剪枝。這樣，就可以保證所剪掉的枝條一定不是正解所在的枝條。 原則之二：準確性。即能夠盡可能多的剪去不能通向正解的枝條。準確性可以說是剪枝優(yōu)化的生命。原則之三：高效性。 經(jīng)常還需要提高判斷操

16、作本身的時間效率。 綜上所述，我們可以把剪枝優(yōu)化的主要原則歸結(jié)為六個字：正確、準確、高效。（二） 剪枝方法 1、可行性剪枝 搜索過程可以看作是對一棵樹的遍歷。在很多情況下，并不是搜索樹中 的所有枝條都能通向我們需要的結(jié)果，很多的枝條實際上只是一些死胡同。如果我們能夠在剛剛進入這樣的死胡同的時候，就能夠判斷出來并立即剪枝，程序的效率往往會得到提高。而所謂可行性剪枝，正是基于這樣一種考慮。2、 最優(yōu)性剪枝 在我們平時遇到的問題中，有一大類是所謂最優(yōu)化問題，即所要求的結(jié)果是最優(yōu)解。此時就可以利用最優(yōu)性剪枝來簡化搜索復(fù)雜度。    在搜索的過程中，一般情況下，我們需要保存一個“當前最優(yōu)解”，實際上就是保存解的優(yōu)度的一個下界。在遍歷到搜索樹的葉子節(jié)點的時候，我們就能得到一個新的解，當然也就得到了它的評價函數(shù)值，如果新解更優(yōu)則更新優(yōu)值下限。搜索結(jié)束后，所保存的解就是最優(yōu)解。 那么，最優(yōu)性剪枝又是如何進行的呢？當我們處在搜索樹的枝條上時，可以通過某種方法估算出該枝條上的所有解的評價函數(shù)的上界，即所謂估價函數(shù)。顯然，大于當前保存的優(yōu)度的下界，是該枝條上存在最優(yōu)解的必要條件，否則就一定可以剪枝。