2024年-搜索之BFS課件

SEARCHINGSTRATEGIESACM/ICPC之搜索篇

2搜索概論搜索被稱為“通用解題法”，在算法和人工智能中占據(jù)重要地位。但由于它巨大的局限性和自身靈活性，也被認(rèn)為是最難學(xué)難用的算法之一。本節(jié)目標(biāo)：希望同學(xué)們對于任意一個問題， 1.很快建立狀態(tài)空間 2.提出一個合理算法 3.簡單估計時空性能ACM/ICPCTRAINING2007SUMMER

3搜索分類盲目搜索：按預(yù)定的控制策略進(jìn)行搜索，在搜索過程中獲得的中間信息不用來改進(jìn)控制策略。啟發(fā)式搜索：在搜索中加入了與問題有關(guān)的啟發(fā)性信息，用以指導(dǎo)搜索朝著最有希望的方向發(fā)展，加速問題的求解過程并找到最優(yōu)解。ACM/ICPCTRAINING2007SUMMER

4搜索算法盲目搜索：1.廣度優(yōu)先搜索（BreadthFirstSearch）2.深度優(yōu)先搜索（DepthFirstSearch）3.純隨機(jī)搜索、重復(fù)式搜索、迭代加深搜索、迭代加寬搜索、柱型搜索啟發(fā)式搜索：1.A*算法2.IDA*算法ACM/ICPCTRAINING2007SUMMER

5狀態(tài)空間明確以下概念：狀態(tài)：問題在某一時刻進(jìn)展?fàn)顩r的數(shù)學(xué)描述。狀態(tài)轉(zhuǎn)移：問題從一種狀態(tài)到另一種或幾種狀態(tài)的操作。狀態(tài)空間：一個“圖”，圖結(jié)點對應(yīng)于狀態(tài)，點之間的邊對應(yīng)于狀態(tài)轉(zhuǎn)移。搜索：尋找一種可行的操作序列，從起始狀態(tài)經(jīng)過一系列狀態(tài)轉(zhuǎn)移，達(dá)到目標(biāo)狀態(tài)。ACM/ICPCTRAINING2007SUMMER

6過河問題某人要帶一條狗、一只雞、一籮米過河，但小船除需要人劃外，最多只能載一物過河，而當(dāng)人不在場時，狗要咬雞、雞要吃米。問此人應(yīng)如何過河?ACM/ICPCTRAINING2007SUMMER

7過河問題（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時b≠c；當(dāng)a≠c時c≠dACM/ICPCTRAINING2007SUMMER

8過河問題（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)ACM/ICPCTRAINING2007SUMMER

9過河問題（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)ACM/ICPCTRAINING2007SUMMER

10過河問題（con4）搜索在“圖”中進(jìn)行，但圖不需要事先建立（“隱式圖”）。搜索過程就是對圖的遍歷過程，可以得到一棵“搜索樹”。搜索樹的結(jié)點個數(shù)、分枝數(shù)、深度，決定著搜索的效率。ACM/ICPCTRAINING2007SUMMER

11過河問題（con5）ACM/ICPCTRAINING2007SUMMER

12過河問題（con6）普通狀態(tài)可以用4個整數(shù)表示壓縮狀態(tài)用4個bit表示(char型有8個bit，足夠用)。用廣度優(yōu)先(BFS,BreathFirstSearch)或用深度優(yōu)先(DFS,DepthFirstSearch)ACM/ICPCTRAINING2007SUMMER

13BFS+DFS入門顧名思義，廣搜就是“往廣了搜”，深搜就是“往深了搜”。廣搜例子:你的眼鏡掉在地上以后，你趴在地板上找。你總是先摸最接近你的地方，如果沒有，再摸遠(yuǎn)一點的地方……深搜例子：走迷宮，你沒有辦法用分身術(shù)來站在每個走過的位置。不撞南山不回頭。ACM/ICPCTRAINING2007SUMMER

14BFS思想1.從圖中某頂點v0出發(fā)，在訪問了v0之后，搜索v0的(所有未被訪問的)鄰接頂點v1.v2…2.依次從這些鄰接頂點出發(fā)，廣搜圖中其它頂點，直至圖中所有已被訪問的頂點的鄰接頂點都被訪問到。3.若此時圖中還有未被訪問到的頂點，則再選擇其中之一作為v0重復(fù)上述過程。直到圖中所有頂點均被訪問到。//搜索過程沒有回溯，是一種犧牲空間換取時間的方法。時間復(fù)雜度：O(V+E)ACM/ICPCTRAINING2007SUMMER

15BFS思想（cont.）樹、圖的BFS演示0123485967100214536ACM/ICPCTRAINING2007SUMMER

16BFS程序基本結(jié)構(gòu)定義一個隊列;起始點加入隊列;while(隊列不空){取出隊頭結(jié)點;若它是所求的目標(biāo)狀態(tài),跳出循環(huán);否則，從它擴(kuò)展出子結(jié)點,全都添到隊尾;}若循環(huán)中找到目標(biāo),輸出結(jié)果;否則輸出無解;這個結(jié)構(gòu)是普遍適用的。任何非遞歸的BFS程序都能套進(jìn)去ACM/ICPCTRAINING2007SUMMER

17BFS演示無向圖如下，邊權(quán)均為1，求V1到V3的最短路徑V3V2V4V1V6V5ACM/ICPCTRAINING2007SUMMER

18定義一個隊列;起始點加入隊列;while(隊列不空){取出隊頭結(jié)點;若它是所求的目標(biāo)狀態(tài),跳出循環(huán);否則，從它擴(kuò)展出子結(jié)點,全都添到隊尾;}若循環(huán)中找到目標(biāo),輸出結(jié)果;否則輸出無解;v10V1隊列結(jié)點記錄兩個信息1：頂點編號2：步數(shù)ACM/ICPCTRAINING2007SUMMER

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

20定義一個隊列;起始點加入隊列;while(隊列不空){

取出隊頭結(jié)點;若它是所求的目標(biāo)狀態(tài),跳出循環(huán);否則，從它擴(kuò)展出子結(jié)點,全都添到隊尾;}若循環(huán)中找到目標(biāo),輸出結(jié)果;否則輸出無解;v10V1v10ACM/ICPCTRAINING2007SUMMER

21定義一個隊列;起始點加入隊列;while(隊列不空){取出隊頭結(jié)點;

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

否則，從它擴(kuò)展出子結(jié)點,全都添到隊尾;}若循環(huán)中找到目標(biāo),輸出結(jié)果;否則輸出無解;v10V1v10V1不是終點ACM/ICPCTRAINING2007SUMMER

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

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

24定義一個隊列;起始點加入隊列;while(隊列不空){

取出隊頭結(jié)點;若它是所求的目標(biāo)狀態(tài),跳出循環(huán);否則，從它擴(kuò)展出子結(jié)點,全都添到隊尾;}若循環(huán)中找到目標(biāo),輸出結(jié)果;否則輸出無解;v10V2V4V1V6V5v21v41v51v61v21ACM/ICPCTRAINING2007SUMMER

25定義一個隊列;起始點加入隊列;while(隊列不空){取出隊頭結(jié)點;

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

否則，從它擴(kuò)展出子結(jié)點,全都添到隊尾;}若循環(huán)中找到目標(biāo),輸出結(jié)果;否則輸出無解;v10V2V4V1V6V5v21v41v51v61V2不是終點v21ACM/ICPCTRAINING2007SUMMER

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

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

28定義一個隊列;起始點加入隊列;while(隊列不空){

取出隊頭結(jié)點;若它是所求的目標(biāo)狀態(tài),跳出循環(huán);否則，從它擴(kuò)展出子結(jié)點,全都添到隊尾;}若循環(huán)中找到目標(biāo),輸出結(jié)果;否則輸出無解;v10V2V4V1V6V5v21v41v51v61V3v32v41ACM/ICPCTRAINING2007SUMMER

29定義一個隊列;起始點加入隊列;while(隊列不空){取出隊頭結(jié)點;

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

否則，從它擴(kuò)展出子結(jié)點,全都添到隊尾;}若循環(huán)中找到目標(biāo),輸出結(jié)果;否則輸出無解;v10V2V4V1V6V5v21v41v51v61V3v32v41V4不是終點ACM/ICPCTRAINING2007SUMMER

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

31定義一個隊列;起始點加入隊列;while(隊列不空){

取出隊頭結(jié)點;若它是所求的目標(biāo)狀態(tài),跳出循環(huán);否則，從它擴(kuò)展出子結(jié)點,全都添到隊尾;}若循環(huán)中找到目標(biāo),輸出結(jié)果;否則輸出無解;v10V2V4V1V6V5v21v41v51v61V3v32v51ACM/ICPCTRAINING2007SUMMER

32定義一個隊列;起始點加入隊列;while(隊列不空){

取出隊頭結(jié)點;若它是所求的目標(biāo)狀態(tài),跳出循環(huán);否則，從它擴(kuò)展出子結(jié)點,全都添到隊尾;}若循環(huán)中找到目標(biāo),輸出結(jié)果;否則輸出無解;v10V2V4V1V6V5v21v41v51v61V3v32v61ACM/ICPCTRAINING2007SUMMER

33定義一個隊列;起始點加入隊列;while(隊列不空){

取出隊頭結(jié)點;若它是所求的目標(biāo)狀態(tài),跳出循環(huán);否則，從它擴(kuò)展出子結(jié)點,全都添到隊尾;}若循環(huán)中找到目標(biāo),輸出結(jié)果;否則輸出無解;v10V2V4V1V6V5v21v41v51v61V3v32v32ACM/ICPCTRAINING2007SUMMER

34定義一個隊列;起始點加入隊列;while(隊列不空){取出隊頭結(jié)點;

若它是所求的目標(biāo)狀態(tài),跳出循環(huán);否則，從它擴(kuò)展出子結(jié)點,全都添到隊尾;}若循環(huán)中找到目標(biāo),輸出結(jié)果;否則輸出無解;v10V2V4V1V6V5v21v41v51v61V3v32v32V3是終點，結(jié)束搜索，輸出2ACM/ICPCTRAINING2007SUMMER

35休息一下happy2ACM/ICPCTRAINING2007SUMMER

36例1KnightMoves

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

abcdefgh12345678h8a1ACM/ICPCTRAINING2007SUMMER

37跳馬規(guī)則abcdefgh12345678在2×3的矩形里：ACM/ICPCTRAINING2007SUMMER

38例如：從a1到e4當(dāng)目標(biāo)出現(xiàn)在所擴(kuò)展出的結(jié)點里，結(jié)果就找到了。Togetfroma1toe4takes3knightmoves.

abcdefgh1234567803321322312332233323333333233332ACM/ICPCTRAINING2007SUMMER

39boolin(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; } } }}#include<iostream>#include<queue>usingnamespacestd;structxxx{ intx,y;};xxxdir[8]={{-2,1},{-2,-1},{-1,-2},{1,-2},{2,-1},{2,1},{1,2},{-1,2}};charc[6];inta[6];queue<int>qq;boolmp[9][9];intans;ACM/ICPCTRAINING2007SUMMER

40intmain(){ 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;}ACM/ICPCTRAINING2007SUMMER

41雙向BFSabcdefgh123456780212212122211112012從起點、終點同時開始雙向BFS,有效地提高了時空效率。從起點找2步能跳到的點從終點找1步能跳到的點ACM/ICPCTRAINING2007SUMMER

42例2Divisibility輸入N、K,然后輸入N個整數(shù)，N個整數(shù)可列出若干加減運算式；若存在一個算式，它的值能被K整除,輸出“Divisible”，否則輸出“Notdivisible”.輸入：247

175-211545

175-2115輸出：Divisible

NotdivisibleACM/ICPCTRAINING2007SUMMER

43{17，5，-21，15}1755-21-21-21-211515151515151515+++17+5+-21+15++++-------17-5+-21-15ACM/ICPCTRAINING2007SUMMER

44最壞情況N=10000，二叉樹有10000層，結(jié)點總數(shù)210000-1。不可能枚舉所有表達(dá)式本題的目標(biāo)：判斷葉子結(jié)點上是否有值能被k整除=>判斷是否有值，除以k的余數(shù)為零。計算中間值取余，不影響結(jié)果。

(a+b)%k=(a%k+b%k)%k因此只需記錄對k的余數(shù)。2<=k<=100，每層結(jié)點最多100個，不是指數(shù)級增加。ACM/ICPCTRAINING2007SUMMER

4547175-2115每層最多7個結(jié)點(定義數(shù)組)：首先加入起點，17%7=3擴(kuò)展第2層結(jié)點(3+5)%7=1(3–5+7)%7=51234560+-擴(kuò)展第3層結(jié)點(1+-21)%7=1(1–-21)%7=1(5+-21)%7=5(5–

-21)%7=51234560擴(kuò)展第4層結(jié)點(1+15)%7=2(1–15)%7=0(5+15)%7=6(5–

15)%7