搜索相關(guān)算法

1、搜索DFS&BFS王豪ACMContents目錄遞歸思想遞歸思想DFS棧與隊列棧與隊列BFSPart One神奇的遞歸神奇的遞歸01011-1 函數(shù)自身調(diào)用函數(shù)自身調(diào)用程序調(diào)用自身的編程技巧稱為遞歸（ recursion）For exampleint f(int a) if (a=1) return 1; return (f(a-1)*a); f(5)=f(4)*5 f(4)=f(3)*4 f(3)=f(2)*3 f(2)=f(1)*2 f(1)=1 大梵天創(chuàng)造世界的時候做了三根金剛石柱子，在一根柱子上從下往上按照大小順序摞著64片黃金圓盤。大梵天命令婆羅門把圓盤從下面開始按大小順序重

2、新擺放在另一根柱子上。并且規(guī)定，在小圓盤上不能放大圓盤，在三根柱子之間一次只能移動一個圓盤。這里我們考慮同樣的問題，只是數(shù)據(jù)量要小的多（不然根本算不完）。然后是這個問題：1-2 漢諾塔漢諾塔假定我們要從A柱子把盤子移到C柱子，借助B1.對于n=1個盤子，很簡單，直接從A移到C2.對于n1，我們開始遞歸： a.將最上面的n-1個盤子借助C柱子移動到B b.將最底下的盤子移動到C c.再將在B柱子上的n-1個盤子借助A移動到C不理解的同學(xué)肯定要問，那n-1個盤子怎么移?當(dāng)然是用同樣的方法，把n-1個盤子分解成n-2個盤子，和1個盤子。同時我們注意到對于n-1個盤子而言，是完全可以借助柱子A的，因為

3、柱子A上的那個盤子比n-1個盤子都要大talk is cheap show the code#includeusing namespace std;void hanoi(int n,char a,char b,char c) if(n=1) coutn a cendl; else hanoi(n-1,a,c,b); coutn a cendl; hanoi(n-1,b,a,c); int main() int n; cout輸入正整數(shù):n; hanoi(n,A,B,C); return 0;Part Two直接上直接上DFS02022-1 DFSDFS（Depth-First-Search）深

4、度優(yōu)先搜索算法ADBEFC正如算法名稱那樣，深度優(yōu)先搜索所遵循的搜索策略是盡可能“深”地搜索圖。那么這個策略就可以用遞歸來實現(xiàn)：函數(shù) DFS（V）1）訪問起始點V2）對于每個能從V到達的點W做以下工作： 如果W未被訪問，將W作為起始點，應(yīng)用DFS（W）可以看到在實現(xiàn)DFS這個函數(shù)的過程中，函數(shù)調(diào)用了自身注意點：回溯。2-2-1 Example某石油勘探公司正在按計劃勘探地下油田資源，工作在一片長方形的地域中。他們首先將該地域劃分為許多小正方形區(qū)域，然后使用探測設(shè)備分別探測每一塊小正方形區(qū)域內(nèi)是否有油。若在一塊小正方形區(qū)域中探測到有油，則標記為，否則標記為*。如果兩個相鄰區(qū)域都為，那么它們同屬于

5、一個石油帶，一個石油帶可能包含很多小正方形區(qū)域，而你的任務(wù)是要確定在一片長方形地域中有多少個石油帶。 所謂相鄰，是指兩個小正方形區(qū)域上下、左右、左上右下或左下右上同為。3 5 * * *Cpp problem 1012這題的思路其實很簡單，把每一個格子當(dāng)作一個結(jié)點，與它相鄰的格子就是和當(dāng)前結(jié)點相鄰的結(jié)點，把訪問過的結(jié)點標記后遞歸。2-2-2 CodeCpp problem 1012void dfs(int x,int y) if (x,y) 超出地圖的范圍 return if (x,y) 已經(jīng)被訪問過return 標記(x,y)已經(jīng)被訪問過 八個方向遞歸： dfs(x+1,y); dfs(x-

6、1,y); dfs(x,y+1); dfs(x,y-1); . . .2-3-1 Example在88格的國際象棋上擺放八個皇后，使其不能互相攻擊，即任意兩個皇后都不能處于同一行、同一列或同一斜線上，問有多少種擺法。 高斯認為有76種方案（然而高斯居然錯了?。Ｆ鋵嵵灰杜e每種排法，判斷一下當(dāng)前排法下坐標為（i,j）的位置上能否放皇后就可以得到全部解了。所以我們要解決的問題就來了：一是怎么枚舉所有排法，二是怎么判斷當(dāng)前點能否放置皇后。2-3-2 Example直觀的枚舉：八個for循環(huán)嵌套（其實dfs也差不多，就是代碼更短）當(dāng)然是不可能的，寫起來太麻煩了而且如果題目改成N皇后就要跪。我們先考慮

7、已知的事情：一行一定只能放一個皇后，而放在哪一列有八種可能，但這八種可能并不是全部符合條件的。那么如果把行號作為dfs中的結(jié)點是否可行？（當(dāng)然是可以的啦，不然我怎么會這么問）然后在每個dfs里面寫一個for循環(huán)枚舉列號。當(dāng)找到一個位置可行的時候，標記好這個位置后調(diào)用自身dfs（當(dāng)前行號+1）。判斷：首先判斷當(dāng)前列上有沒有其他皇后，再判斷這個點擴展開去的兩條斜線上有沒有皇后就可以了。因此上面提到的標記是十分重要的。注意點：在每次遞歸回溯后，都應(yīng)該把標記復(fù)原。因為遞歸回溯后代表將要把當(dāng)前行的皇后放到下一列去了，那么原來占有的點所影響到的列與斜線上又可以放皇后了。2-4 Code#include#i

8、ncludeint col10,sla1100,sla2100,ans;void dfs(int step) if (step=9) ans+; for (int i=1;i=8;i+) int x=7-step+i,y=step+i-2; if (coli=0&sla1x=0&sla2y=0) coli=1; sla1x=1; sla2y=1; dfs(step+1); coli=0; sla1x=0; sla2y=0; int main() ans=0; dfs(1); printf(%dn,ans);2-5 DFS 作為搜索算法的一種，DFS對于尋找一個解的NP（包括NP

9、C）問題作用很大。但是，搜索算法畢竟是時間復(fù)雜度是O(n!)的階乘級算法，它的效率比較低，在數(shù)據(jù)規(guī)模變大時，這種算法就顯得力不從心了。 關(guān)于深度優(yōu)先搜索的效率問題，有多種解決方法。最具有通用性的是剪枝，也就是去除沒有用的搜索分支。有可行性剪枝和最優(yōu)性剪枝兩種。此外，對于很多問題，可以把搜索與動態(tài)規(guī)劃、完備匹配（匈牙利算法）等高效算法結(jié)合。From 度娘 雖然DFS的效率不高，然而在搜索的問題上還是經(jīng)常會遇到的，而且相對來說DFS的遞歸寫法會比非遞歸寫法更易于理解。所以必須要學(xué)會并靈活運用。From 我Part Three來看看大二才學(xué)的東西來看看大二才學(xué)的東西03033-1 棧和隊列棧和隊列

10、雖然棧和隊列是大二數(shù)據(jù)結(jié)構(gòu)課程上才學(xué)的東西，但其實并不難，也不需要什么預(yù)備知識。（還有江老板數(shù)據(jù)結(jié)構(gòu)明明比我六，但他上節(jié)課就是不肯講，STL里面明明也是有的啊。哦對，江老板說他棧和隊列從來都是自己手打，不用STL。）棧和隊列都屬于邏輯數(shù)據(jù)結(jié)構(gòu)，什么叫邏輯數(shù)據(jù)結(jié)構(gòu)？就是人開腦洞想出的。比如，你可以把棧想象成一個細小有底的圓筒，數(shù)據(jù)是一個個與圓筒直徑相等的珠子，那么當(dāng)你把數(shù)據(jù)都放進這個圓筒再拿出來時，先放進去的珠子后出來。這就是棧了。棧的原理非常簡單，那么怎么實現(xiàn)它？其實用數(shù)組就可以簡單的實現(xiàn)（江老板手打棧的時候大概都是用數(shù)組的吧）。不過我們這里介紹一下STL里面棧的模版。頭文件：#include

11、定義：stacka;操作：壓棧（也叫入棧）：a.push(b); 取棧頂?shù)脑兀篴.top(); 出棧：a.pop();3-2 Struct在使用stack和queue這樣的模版之前，還有一點需要講的是結(jié)構(gòu)體struct。比如在使用stack定義一個隊列Q的時候，如果定義成：stackQ。那么棧中的元素就會是一個int類型的整數(shù)，但結(jié)點不一定就是int值，它可能包含很多值，這些值的類型也可能完全不同，這個時候就應(yīng)該用到結(jié)構(gòu)體。定義如下：struct node int a,b,c. char x,y,z . . . ;這個時候node就相當(dāng)于是你自己定義的一個數(shù)據(jù)類型，你可以用node去定義變量

12、。比如 node J；那么變量J中就會包含你在定義node時所定義的那些變量。使用那些變量也很簡單，只要J.a就可以直接使用左邊式子中定義的一個int類型的名為a 的變量。3-3 棧棧那為什么棧要放在遞歸后面講？因為從本質(zhì)上來講，遞歸的過程就是一個壓棧和出棧的過程。任何一個遞歸程序都可以用stack實現(xiàn)。只不過遞歸中的出棧過程，程序自己會完成。但是stack的出棧還要編程的人自己確定。下面是我寫的八皇后的stack版本，真的有些麻煩。while(!Q.empty() a=Q.top(); node d; for (int i=a.x+1;i=8;i+) int fla=0; for (int

13、j=1;j=8;j+) int xx=7-i+j,yy=j+i-2; if (collij=1) colj=0; sla1xx=0; sla2yy=0; collij=0; continue; if (colj=0&sla1xx=0&sla2yy=0) fla=1; colj=1; sla1xx=1; sla2yy=1; collij=1; d.x=i; d.y=j; Q.push(d); break; if (fla=0) break; if (!Q.empty() d=Q.top(); if (d.x=8) ans+; Q.pop(); 3-4 隊列隊列如果說棧是個有底的圓

14、筒，那么隊列就是沒有底的圓筒。因此先進入隊列的數(shù)據(jù)先從隊列中出來同樣的，在STL中也有已經(jīng)封裝好的隊列模版頭文件：#include定義 ： queuea;操作：放入隊列：a.push(b); 取隊列首部元素：a.front(); 首部元素彈出隊列：a.pop();隊列是實現(xiàn)BFS的基礎(chǔ)，所以接下來我們就可以來看看最后一項內(nèi)容BFS到底是個什么鬼了。Part FourBFS04044-1 BFSAFBCED寬度優(yōu)先搜索算法（又稱廣度優(yōu)先搜索）上面這個閃電的擴展方式就跟寬搜很像那么用隊列實現(xiàn)BFS的規(guī)則就該是這樣：1）訪問起始點2）初始化一個隊列為僅包含一個初始點3）當(dāng)這個隊列非空時，做以下工作：

15、 a.從隊列中拿出一個頂點v并將其從隊列中刪除 b.對于所有鄰接于v的定點w，如果w未被訪問過，那么將w標記為訪問過，然后放入隊列中4-2 Example假如給你一張地圖，o代表可以行走的道路，#代表墻壁。問你從a走到r最短的路的長度為多少？7 8 #o#o#oa#ooro #oo#oooooo#oo#o# #ooo#ooo#oooooooooooooo如果使用DFS，那么我們就需要遍歷出所有可能從a到r的路徑，并找出最小的值，但如果是使用BFS，我們只要直接輸出找到的第一條符合條件的路徑長度就可以了。為什么？4-3 Example很明顯我們可以把地圖上的每個點都作為一個結(jié)點，可以定義一個結(jié)構(gòu)

16、體nodeint x，y，length；x為點的橫坐標，y為點的縱坐標，那么length就代表從起點到這個點的路徑長度然后我們遍歷這張圖，找到并記錄起點和終點所在的坐標將起點放入隊列中當(dāng)隊列不為空的時候，我們拿出隊列首部的結(jié)點，注意是拿出。也就是一個front（）加一個pop（）；然后對拿出的結(jié)點進行判斷，如果它是終點，那么直接輸出答案，并終止。如果不是那么對它標記后，往四個方向擴展。那么由當(dāng)前點擴展出的四個點的length值將是當(dāng)前點length值+1；4-4 Codenode a;a.x=i;a.y=j;a.length=0;Q.push(a);While(!Q.empty() a=Q.front(); Q.pop(); if (mpa.xa.y=r) couta.lengthendl; break; if (a.x=n|a.y=m) continue; if (mpa.xa.y=#) continue; for (int i=0;i4;i+) node d; d.x=a.x+dri; d.y=a.y+dci; d.length=a.length+1; Q.push(d); Int dc=0,1,0,-1;Int dr=1,0,-1,0;4-5 小結(jié)小結(jié)對于遞歸來說最重要的有三點，一個是這個問題能否通過解決更小的相同的問題來解