搜索之BFS優(yōu)秀課件

SEARCHINGSTRATEGIESACM/ICPC之搜索篇搜索概論搜索被稱為“通用解題法”，在算法和人工智能中占據(jù)重要地位。但由于它巨大的局限性和自身靈活性，也被認(rèn)為是最難學(xué)難用的算法之一。本節(jié)目標(biāo)：希望同學(xué)們對(duì)于任意一個(gè)問(wèn)題， 1.很快建立狀態(tài)空間 2.提出一個(gè)合理算法 3.簡(jiǎn)單估計(jì)時(shí)空性能4/23/20232搜索分類盲目搜索：按預(yù)定的控制策略進(jìn)行搜索，在搜索過(guò)程中獲得的中間信息不用來(lái)改進(jìn)控制策略。啟發(fā)式搜索：在搜索中加入了與問(wèn)題有關(guān)的啟發(fā)性信息，用以指導(dǎo)搜索朝著最有希望的方向發(fā)展，加速問(wèn)題的求解過(guò)程并找到最優(yōu)解。4/23/20233搜索算法盲目搜索：1.廣度優(yōu)先搜索（BreadthFirstSearch）2.深度優(yōu)先搜索（DepthFirstSearch）3.純隨機(jī)搜索、重復(fù)式搜索、迭代加深搜索、迭代加寬搜索、柱型搜索啟發(fā)式搜索：1.A*算法2.IDA*算法4/23/20234狀態(tài)空間明確以下概念：狀態(tài)：?jiǎn)栴}在某一時(shí)刻進(jìn)展?fàn)顩r的數(shù)學(xué)描述。狀態(tài)轉(zhuǎn)移：?jiǎn)栴}從一種狀態(tài)到另一種或幾種狀態(tài)的操作。狀態(tài)空間：一個(gè)“圖”，圖結(jié)點(diǎn)對(duì)應(yīng)于狀態(tài)，點(diǎn)之間的邊對(duì)應(yīng)于狀態(tài)轉(zhuǎn)移。搜索：尋找一種可行的操作序列，從起始狀態(tài)經(jīng)過(guò)一系列狀態(tài)轉(zhuǎn)移，達(dá)到目標(biāo)狀態(tài)。4/23/20235過(guò)河問(wèn)題某人要帶一條狗、一只雞、一籮米過(guò)河，但小船除需要人劃外，最多只能載一物過(guò)河，而當(dāng)人不在場(chǎng)時(shí)，狗要咬雞、雞要吃米。問(wèn)此人應(yīng)如何過(guò)河?4/23/20236過(guò)河問(wèn)題（con1）狀態(tài)：建立四元組（人，狗，雞，米）。用0表示在左岸，1表示在右岸。起始狀態(tài)(0,0,0,0)，終止?fàn)顟B(tài)(1,1,1,1)狀態(tài)轉(zhuǎn)移規(guī)則：(a,b,c,d)→(1-a,1-b,c,d)（當(dāng)a=b）→(1-a,b,1-c,d)（當(dāng)a=c）→(1-a,b,c,1-d)（當(dāng)a=d）→(1-a,b,c,d)約束：(a,b,c,d)中，當(dāng)a≠b時(shí)b≠c；當(dāng)a≠c時(shí)c≠d4/23/20237過(guò)河問(wèn)題（con2）搜索：(0,0,0,0)→(1,1,0,0)→(1,0,1,0)→(0,0,1,0)→(1,0,1,1)→(1,0,0,1)→(1,1,1,0)→(1,0,0,0)4/23/20238過(guò)河問(wèn)題（con3）搜索：→(1,0,1,1)→(0,0,0,1)→(1,1,0,1)→(0,1,0,1)→(1,1,1,1)ok→(0,0,1,0)→(1,0,1,1)→(0,0,1,1)→(0,0,1,1)→(1,1,1,0)→(0,0,1,0)→(1,0,1,1)→(0,0,1,1)→(0,1,0,0)→(1,1,0,1)→(0,1,0,1)→(1,1,1,1)ok→(0,1,1,0)4/23/20239過(guò)河問(wèn)題（con4）搜索在“圖”中進(jìn)行，但圖不需要事先建立（“隱式圖”）。搜索過(guò)程就是對(duì)圖的遍歷過(guò)程，可以得到一棵“搜索樹”。搜索樹的結(jié)點(diǎn)個(gè)數(shù)、分枝數(shù)、深度，決定著搜索的效率。4/23/202310過(guò)河問(wèn)題（con5）4/23/202311過(guò)河問(wèn)題（con6）普通狀態(tài)可以用4個(gè)整數(shù)表示壓縮狀態(tài)用4個(gè)bit表示(char型有8個(gè)bit，足夠用)。用廣度優(yōu)先(BFS,BreathFirstSearch)或用深度優(yōu)先(DFS,DepthFirstSearch)4/23/202312BFS+DFS入門顧名思義，廣搜就是“往廣了搜”，深搜就是“往深了搜”。廣搜例子:你的眼鏡掉在地上以后，你趴在地板上找。你總是先摸最接近你的地方，如果沒(méi)有，再摸遠(yuǎn)一點(diǎn)的地方……深搜例子：走迷宮，你沒(méi)有辦法用分身術(shù)來(lái)站在每個(gè)走過(guò)的位置。不撞南山不回頭。4/23/202313BFS思想1.從圖中某頂點(diǎn)v0出發(fā)，在訪問(wèn)了v0之后，搜索v0的(所有未被訪問(wèn)的)鄰接頂點(diǎn)v1.v2…2.依次從這些鄰接頂點(diǎn)出發(fā)，廣搜圖中其它頂點(diǎn)，直至圖中所有已被訪問(wèn)的頂點(diǎn)的鄰接頂點(diǎn)都被訪問(wèn)到。3.若此時(shí)圖中還有未被訪問(wèn)到的頂點(diǎn)，則再選擇其中之一作為v0重復(fù)上述過(guò)程。直到圖中所有頂點(diǎn)均被訪問(wèn)到。//搜索過(guò)程沒(méi)有回溯，是一種犧牲空間換取時(shí)間的方法。時(shí)間復(fù)雜度：O(V+E)4/23/202314BFS思想（cont.）樹、圖的BFS演示01234859671002145364/23/202315BFS程序基本結(jié)構(gòu)定義一個(gè)隊(duì)列;起始點(diǎn)加入隊(duì)列;while(隊(duì)列不空){取出隊(duì)頭結(jié)點(diǎn);若它是所求的目標(biāo)狀態(tài),跳出循環(huán);否則，從它擴(kuò)展出子結(jié)點(diǎn),全都添到隊(duì)尾;}若循環(huán)中找到目標(biāo),輸出結(jié)果;否則輸出無(wú)解;這個(gè)結(jié)構(gòu)是普遍適用的。任何非遞歸的BFS程序都能套進(jìn)去4/23/202316BFS演示無(wú)向圖如下，邊權(quán)均為1，求V1到V3的最短路徑V3V2V4V1V6V54/23/202317定義一個(gè)隊(duì)列;起始點(diǎn)加入隊(duì)列;while(隊(duì)列不空){取出隊(duì)頭結(jié)點(diǎn);若它是所求的目標(biāo)狀態(tài),跳出循環(huán);否則，從它擴(kuò)展出子結(jié)點(diǎn),全都添到隊(duì)尾;}若循環(huán)中找到目標(biāo),輸出結(jié)果;否則輸出無(wú)解;v10V1隊(duì)列結(jié)點(diǎn)記錄兩個(gè)信息1：頂點(diǎn)編號(hào)2：步數(shù)4/23/202318定義一個(gè)隊(duì)列;起始點(diǎn)加入隊(duì)列;while(隊(duì)列不空){取出隊(duì)頭結(jié)點(diǎn);若它是所求的目標(biāo)狀態(tài),跳出循環(huán);否則，從它擴(kuò)展出子結(jié)點(diǎn),全都添到隊(duì)尾;}若循環(huán)中找到目標(biāo),輸出結(jié)果;否則輸出無(wú)解;v10V14/23/202319定義一個(gè)隊(duì)列;起始點(diǎn)加入隊(duì)列;while(隊(duì)列不空){

取出隊(duì)頭結(jié)點(diǎn);若它是所求的目標(biāo)狀態(tài),跳出循環(huán);否則，從它擴(kuò)展出子結(jié)點(diǎn),全都添到隊(duì)尾;}若循環(huán)中找到目標(biāo),輸出結(jié)果;否則輸出無(wú)解;v10V1v104/23/202320定義一個(gè)隊(duì)列;起始點(diǎn)加入隊(duì)列;while(隊(duì)列不空){取出隊(duì)頭結(jié)點(diǎn);

若它是所求的目標(biāo)狀態(tài),跳出循環(huán);

否則，從它擴(kuò)展出子結(jié)點(diǎn),全都添到隊(duì)尾;}若循環(huán)中找到目標(biāo),輸出結(jié)果;否則輸出無(wú)解;v10V1v10V1不是終點(diǎn)4/23/202321定義一個(gè)隊(duì)列;起始點(diǎn)加入隊(duì)列;while(隊(duì)列不空){取出隊(duì)頭結(jié)點(diǎn);若它是所求的目標(biāo)狀態(tài),跳出循環(huán);否則，從它擴(kuò)展出子結(jié)點(diǎn),全都添到隊(duì)尾;}若循環(huán)中找到目標(biāo),輸出結(jié)果;否則輸出無(wú)解;v10V2V4V1V6V5v21v41v51v61v104/23/202322定義一個(gè)隊(duì)列;起始點(diǎn)加入隊(duì)列;while(隊(duì)列不空){取出隊(duì)頭結(jié)點(diǎn);若它是所求的目標(biāo)狀態(tài),跳出循環(huán);否則，從它擴(kuò)展出子結(jié)點(diǎn),全都添到隊(duì)尾;}若循環(huán)中找到目標(biāo),輸出結(jié)果;否則輸出無(wú)解;v10V2V4V1V6V5v21v41v51v614/23/202323定義一個(gè)隊(duì)列;起始點(diǎn)加入隊(duì)列;while(隊(duì)列不空){

取出隊(duì)頭結(jié)點(diǎn);若它是所求的目標(biāo)狀態(tài),跳出循環(huán);否則，從它擴(kuò)展出子結(jié)點(diǎn),全都添到隊(duì)尾;}若循環(huán)中找到目標(biāo),輸出結(jié)果;否則輸出無(wú)解;v10V2V4V1V6V5v21v41v51v61v214/23/202324定義一個(gè)隊(duì)列;起始點(diǎn)加入隊(duì)列;while(隊(duì)列不空){取出隊(duì)頭結(jié)點(diǎn);

若它是所求的目標(biāo)狀態(tài),跳出循環(huán);

否則，從它擴(kuò)展出子結(jié)點(diǎn),全都添到隊(duì)尾;}若循環(huán)中找到目標(biāo),輸出結(jié)果;否則輸出無(wú)解;v10V2V4V1V6V5v21v41v51v61V2不是終點(diǎn)v214/23/202325定義一個(gè)隊(duì)列;起始點(diǎn)加入隊(duì)列;while(隊(duì)列不空){取出隊(duì)頭結(jié)點(diǎn);若它是所求的目標(biāo)狀態(tài),跳出循環(huán);否則，從它擴(kuò)展出子結(jié)點(diǎn),全都添到隊(duì)尾;}若循環(huán)中找到目標(biāo),輸出結(jié)果;否則輸出無(wú)解;v10V2V4V1V6V5v21v41v51v61V3v32v214/23/202326定義一個(gè)隊(duì)列;起始點(diǎn)加入隊(duì)列;while(隊(duì)列不空){取出隊(duì)頭結(jié)點(diǎn);若它是所求的目標(biāo)狀態(tài),跳出循環(huán);否則，從它擴(kuò)展出子結(jié)點(diǎn),全都添到隊(duì)尾;}若循環(huán)中找到目標(biāo),輸出結(jié)果;否則輸出無(wú)解;v10V2V4V1V6V5v21v41v51v61V3v324/23/202327定義一個(gè)隊(duì)列;起始點(diǎn)加入隊(duì)列;while(隊(duì)列不空){

取出隊(duì)頭結(jié)點(diǎn);若它是所求的目標(biāo)狀態(tài),跳出循環(huán);否則，從它擴(kuò)展出子結(jié)點(diǎn),全都添到隊(duì)尾;}若循環(huán)中找到目標(biāo),輸出結(jié)果;否則輸出無(wú)解;v10V2V4V1V6V5v21v41v51v61V3v32v414/23/202328定義一個(gè)隊(duì)列;起始點(diǎn)加入隊(duì)列;while(隊(duì)列不空){取出隊(duì)頭結(jié)點(diǎn);

若它是所求的目標(biāo)狀態(tài),跳出循環(huán);

否則，從它擴(kuò)展出子結(jié)點(diǎn),全都添到隊(duì)尾;}若循環(huán)中找到目標(biāo),輸出結(jié)果;否則輸出無(wú)解;v10V2V4V1V6V5v21v41v51v61V3v32v41V4不是終點(diǎn)4/23/202329定義一個(gè)隊(duì)列;起始點(diǎn)加入隊(duì)列;while(隊(duì)列不空){取出隊(duì)頭結(jié)點(diǎn);若它是所求的目標(biāo)狀態(tài),跳出循環(huán);否則，從它擴(kuò)展出子結(jié)點(diǎn),全都添到隊(duì)尾;}若循環(huán)中找到目標(biāo),輸出結(jié)果;否則輸出無(wú)解;v10V2V4V1V6V5v21v41v51v61V3v32v414/23/202330定義一個(gè)隊(duì)列;起始點(diǎn)加入隊(duì)列;while(隊(duì)列不空){

取出隊(duì)頭結(jié)點(diǎn);若它是所求的目標(biāo)狀態(tài),跳出循環(huán);否則，從它擴(kuò)展出子結(jié)點(diǎn),全都添到隊(duì)尾;}若循環(huán)中找到目標(biāo),輸出結(jié)果;否則輸出無(wú)解;v10V2V4V1V6V5v21v41v51v61V3v32v514/23/202331定義一個(gè)隊(duì)列;起始點(diǎn)加入隊(duì)列;while(隊(duì)列不空){

取出隊(duì)頭結(jié)點(diǎn);若它是所求的目標(biāo)狀態(tài),跳出循環(huán);否則，從它擴(kuò)展出子結(jié)點(diǎn),全都添到隊(duì)尾;}若循環(huán)中找到目標(biāo),輸出結(jié)果;否則輸出無(wú)解;v10V2V4V1V6V5v21v41v51v61V3v32v614/23/202332定義一個(gè)隊(duì)列;起始點(diǎn)加入隊(duì)列;while(隊(duì)列不空){

取出隊(duì)頭結(jié)點(diǎn);若它是所求的目標(biāo)狀態(tài),跳出循環(huán);否則，從它擴(kuò)展出子結(jié)點(diǎn),全都添到隊(duì)尾;}若循環(huán)中找到目標(biāo),輸出結(jié)果;否則輸出無(wú)解;v10V2V4V1V6V5v21v41v51v61V3v32v324/23/202333定義一個(gè)隊(duì)列;起始點(diǎn)加入隊(duì)列;while(隊(duì)列不空){取出隊(duì)頭結(jié)點(diǎn);

若它是所求的目標(biāo)狀態(tài),跳出循環(huán);否則，從它擴(kuò)展出子結(jié)點(diǎn),全都添到隊(duì)尾;}若循環(huán)中找到目標(biāo),輸出結(jié)果;否則輸出無(wú)解;v10V2V4V1V6V5v21v41v51v61V3v32v32V3是終點(diǎn)，結(jié)束搜索，輸出24/23/202334休息一下happy24/23/202335例1KnightMoves

國(guó)際象棋棋盤上有一個(gè)馬，要從起點(diǎn)跳到指定目標(biāo)，最少跳幾步？輸入：a1h8輸出：Togetfroma1toh8takes6knightmoves.

abcdefgh12345678h8a14/23/202336跳馬規(guī)則abcdefgh12345678在2×3的矩形里：4/23/202337例如：從a1到e4當(dāng)目標(biāo)出現(xiàn)在所擴(kuò)展出的結(jié)點(diǎn)里，結(jié)果就找到了。Togetfroma1toe4takes3knightmoves.

abcdefgh12345678033213223123322333233333332333324/23/202338boolin(inta,intb){ if(a>0&&a<=8&&b>0&&b<=8) returntrue; returnfalse;}intbfs(){ intcol,row,i; while(!qq.empty()) { col=qq.front(); qq.pop(); row=qq.front(); qq.pop(); ans=qq.front(); qq.pop(); if(col==a[2]&&row==a[3]) returnans; for(i=0;i<8;i++) { if(in(row+dir[i].x,col+dir[i].y)&&!mp[row+dir[i].x][col+dir[i].y]) { qq.push(col+dir[i].y); qq.push(row+dir[i].x); qq.push(ans+1); mp[row+dir[i].x][col+dir[i].y]=true; } } }}4/23/202339intmain(){ registerinti,j;

while(gets(c)) { while(!qq.empty()) qq.pop(); for(i=0;i<=8;i++) for(j=0;j<=8;j++) mp[i][j]=false; a[0]=c[0]-'a'+1;//startcol a[1]=c[1]-'0';//startrow a[2]=c[3]-'a'+1;//endcol a[3]=c[4]-'0';//endrow ans=0; qq.push(a[0]); qq.push(a[1]); qq.push(ans); mp[a[1]][a[0]]=true; ans=bfs(); cout<<"Togetfrom"<<c[0]<<c[1]<<"to"<<c[3]<<c[4]<<"takes"<<ans<<"knightmoves."<<endl; } return0;}4/23/202340雙向BFSabcdefgh123456780212212122211112012從起點(diǎn)、終點(diǎn)同時(shí)開(kāi)始雙向BFS,有效地提高了時(shí)空效率。從起點(diǎn)找2步能跳到的點(diǎn)從終點(diǎn)找1步能跳到的點(diǎn)4/23/202341例2Divisibility輸入N、K,然后輸入N個(gè)整數(shù)，N個(gè)整數(shù)可列出若干加減運(yùn)算式；若存在一個(gè)算式，它的值能被K整除,輸出“Divisible”，否則輸出“Notdivisible”.輸入：247

175-211545

175-2115輸出：Divisible

Notdivisible4/23/202342{17，5，-21，15}1755-21-21-21-211515151515151515+++17+5+-21+15++++-------17-5+-21-154/23/202343最壞情況N=10000，二叉樹有10000層，結(jié)點(diǎn)總數(shù)210000-1。不可能枚舉所有表達(dá)式本題的目標(biāo)：判斷葉子結(jié)點(diǎn)上是否有值能被k整除=>判斷是否有值，除以k的余數(shù)為零。計(jì)算中間值取余，不影響結(jié)果。

(a+b)%k=(a%k+b%k)%k因此只需記錄對(duì)k的余數(shù)。2<=k<=100，每層結(jié)點(diǎn)最多100個(gè)，不是指數(shù)級(jí)增加。4/23/20234447175-2115每層最多7個(gè)結(jié)點(diǎn)(定義數(shù)組)：首先加入起點(diǎn)，17%7=3擴(kuò)展第2層結(jié)點(diǎn)(3+5)%7=1(3–5+7)%7=51234560+-擴(kuò)展第3層結(jié)點(diǎn)(1+-21)%7=1(1–-21)%7=1(5+-21)%7=