5-搜索之BFSppt課件

1、SEARCHING STRATEGIES2021-12-132l搜索被稱為“通用解題法”，在算法和人工智能中占據(jù)重要地位。l但由于它巨大的局限性和自身靈活性，也被認(rèn)為是最難學(xué)難用的算法之一。l本節(jié)目標(biāo)：希望同學(xué)們對(duì)于任意一個(gè)問(wèn)題， 1.很快建立狀態(tài)空間 2.提出一個(gè)合理算法 3.簡(jiǎn)單估計(jì)時(shí)空性能ACM/ICPC TRAINING 2007 SUMMER2021-12-133l盲目搜索盲目搜索：按預(yù)定的控制策略進(jìn)行搜索，在搜索過(guò)程中獲得的中間信息不用來(lái)改進(jìn)控制策略。l啟發(fā)式搜索啟發(fā)式搜索：在搜索中加入了與問(wèn)題有關(guān)的啟發(fā)性信息，用以指導(dǎo)搜索朝著最有希望的方向發(fā)展，加速問(wèn)題的求解過(guò)程并找到最優(yōu)解。A

2、CM/ICPC TRAINING 2007 SUMMER2021-12-134l盲目搜索： 1. 廣度優(yōu)先搜索（Breadth First Search） 2. 深度優(yōu)先搜索（Depth First Search） 3. 純隨機(jī)搜索、重復(fù)式搜索、迭代加深搜索、 迭代加寬搜索、柱型搜索l啟發(fā)式搜索： 1. A*算法 2. IDA*算法ACM/ICPC TRAINING 2007 SUMMER2021-12-135明確以下概念：明確以下概念：l狀態(tài)：?jiǎn)栴}在某一時(shí)刻進(jìn)展?fàn)顩r的數(shù)學(xué)描述。l狀態(tài)轉(zhuǎn)移：?jiǎn)栴}從一種狀態(tài)到另一種或幾種狀態(tài)的操作。l狀態(tài)空間：一個(gè)“圖”，圖結(jié)點(diǎn)對(duì)應(yīng)于狀態(tài)，點(diǎn)之間的邊對(duì)應(yīng)于狀態(tài)轉(zhuǎn)

3、移。l搜索：尋找一種可行的操作序列，從起始狀態(tài)經(jīng)過(guò)一系列狀態(tài)轉(zhuǎn)移，達(dá)到目標(biāo)狀態(tài)。ACM/ICPC TRAINING 2007 SUMMER2021-12-136l某人要帶一條狗、一只雞、一籮米過(guò)河，但小船除需要人劃外，最多只能載一物過(guò)河，而當(dāng)人不在場(chǎng)時(shí)，狗要咬雞、雞要吃米。問(wèn)此人應(yīng)如何過(guò)河?ACM/ICPC TRAINING 2007 SUMMER2021-12-137l狀態(tài)：建立四元組（人，狗，雞，米）。用0表示在左岸，1表示在右岸。l起始狀態(tài)(0,0,0,0)，終止?fàn)顟B(tài)(1,1,1,1)l狀態(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)

4、（當(dāng)a=c） (1-a,b,c,1-d)（當(dāng)a=d） (1-a,b,c,d)l約束：(a,b,c,d)中，當(dāng)ab時(shí)bc；當(dāng)ac時(shí)cdACM/ICPC TRAINING 2007 SUMMER2021-12-138v搜索：(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/ICPC TRAINING 2007 SUMMER2021-12-139v搜索：(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

5、)(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/ICPC TRAINING 2007 SUMMER2021-12-1310l搜索在“圖”中進(jìn)行，但圖不需要事先建立（“隱式圖”）。l搜索過(guò)程就是對(duì)圖的遍歷過(guò)程，可以得到一棵“搜索樹(shù)”。l搜索樹(shù)的結(jié)點(diǎn)個(gè)數(shù)、分枝數(shù)、深度，決定著搜索的效率。ACM/ICPC TRAINING 2007 SUMMER2021-12-1311ACM/ICPC TRAINING 2007 SUMMER2

6、021-12-1312l普通狀態(tài)可以用4個(gè)整數(shù)表示l壓縮狀態(tài)用4個(gè)bit表示(char型有8個(gè)bit，足夠用)。l用廣度優(yōu)先(BFS, Breath First Search) 或 用深度優(yōu)先(DFS, Depth First Search)ACM/ICPC TRAINING 2007 SUMMER2021-12-1313l顧名思義，廣搜就是“往廣了搜”，深搜就是“往深了搜”。l廣搜例子:你的眼鏡掉在地上以后，你趴在地板上找。你總是先摸最接近你的地方，如果沒(méi)有，再摸遠(yuǎn)一點(diǎn)的地方l深搜例子：走迷宮，你沒(méi)有辦法用分身術(shù)來(lái)站在每個(gè)走過(guò)的位置。不撞南山不回頭。ACM/ICPC TRAINING 200

7、7 SUMMER2021-12-1314l1.從圖中某頂點(diǎn)v0出發(fā)，在訪問(wèn)了v0之后，搜索v0的(所有未被訪問(wèn)的)鄰接頂點(diǎn)v1.v2l2.依次從這些鄰接頂點(diǎn)出發(fā)，廣搜圖中其它頂點(diǎn)，直至圖中所有已被訪問(wèn)的頂點(diǎn)的鄰接頂點(diǎn)都被訪問(wèn)到。l3.若此時(shí)圖中還有未被訪問(wèn)到的頂點(diǎn)，則再選擇其中之一作為v0重復(fù)上述過(guò)程。直到圖中所有頂點(diǎn)均被訪問(wèn)到。/搜索過(guò)程沒(méi)有回溯，是一種犧牲空間換取時(shí)間的方法。時(shí)間復(fù)雜度：O(V+E)ACM/ICPC TRAINING 2007 SUMMER2021-12-1315l樹(shù)、圖的BFS演示0123485967100214536ACM/ICPC TRAINING 2007 SUMM

8、ER2021-12-1316定義一個(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)去ACM/ICPC TRAINING 2007 SUMMER2021-12-1317l無(wú)向圖如下，邊權(quán)均為無(wú)向圖如下，邊權(quán)均為1，求，求V1到到V3的最短路徑的最短路徑V3V2V4V1V6V5ACM/ICPC TRAINING 2007 SUMMER2021-12-1318定義一個(gè)隊(duì)列;起始點(diǎn)加入隊(duì)列;while(隊(duì)列不空) 取

9、出隊(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ù)ACM/ICPC TRAINING 2007 SUMMER2021-12-1319定義一個(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ú)解;v10V1ACM/ICPC TRAINING 2007 SUMMER2021-12-1320定義一個(gè)隊(duì)列;起始點(diǎn)加入隊(duì)列;while(隊(duì)列不空) 取出隊(duì)頭結(jié)

10、點(diǎn); 若它是所求的目標(biāo)狀態(tài),跳出循環(huán); 否則，從它擴(kuò)展出子結(jié)點(diǎn),全都添到隊(duì)尾;若循環(huán)中找到目標(biāo),輸出結(jié)果;否則輸出無(wú)解;v10V1v10ACM/ICPC TRAINING 2007 SUMMER2021-12-1321定義一個(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)ACM/ICPC TRAINING 2007 SUMMER2021-12-1322定義一個(gè)隊(duì)列;起始點(diǎn)加入隊(duì)列;while(隊(duì)列不空) 取出隊(duì)頭結(jié)點(diǎn); 若它是所求的目標(biāo)狀

11、態(tài),跳出循環(huán); 否則，從它擴(kuò)展出子結(jié)點(diǎn),全都添到隊(duì)尾;若循環(huán)中找到目標(biāo),輸出結(jié)果;否則輸出無(wú)解;v10V2V4V1V6V5v21v41v51v61v10ACM/ICPC TRAINING 2007 SUMMER2021-12-1323定義一個(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ú)解;v10V2V4V1V6V5v21v41v51v61ACM/ICPC TRAINING 2007 SUMMER2021-12-1324定義一個(gè)隊(duì)列;起始點(diǎn)加入隊(duì)列;while(隊(duì)列不空

12、) 取出隊(duì)頭結(jié)點(diǎn); 若它是所求的目標(biāo)狀態(tài),跳出循環(huán); 否則，從它擴(kuò)展出子結(jié)點(diǎn),全都添到隊(duì)尾;若循環(huán)中找到目標(biāo),輸出結(jié)果;否則輸出無(wú)解;v10V2V4V1V6V5v21v41v51v61v21ACM/ICPC TRAINING 2007 SUMMER2021-12-1325定義一個(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)v21ACM/ICPC TRAINING 2007 SUMMER2021-12-1

13、326定義一個(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ú)解;v10V2V4V1V6V5v21v41v51v61V3v32v21ACM/ICPC TRAINING 2007 SUMMER2021-12-1327定義一個(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ú)解;v10V2V4V1V6V5v21v41v51v61V3v32ACM/ICPC

14、TRAINING 2007 SUMMER2021-12-1328定義一個(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ú)解;v10V2V4V1V6V5v21v41v51v61V3v32v41ACM/ICPC TRAINING 2007 SUMMER2021-12-1329定義一個(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ú)解;v10V2V4V1V

15、6V5v21v41v51v61V3v32v41V4不是終點(diǎn)ACM/ICPC TRAINING 2007 SUMMER2021-12-1330定義一個(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ú)解;v10V2V4V1V6V5v21v41v51v61V3v32v41ACM/ICPC TRAINING 2007 SUMMER2021-12-1331定義一個(gè)隊(duì)列;起始點(diǎn)加入隊(duì)列;while(隊(duì)列不空) 取出隊(duì)頭結(jié)點(diǎn); 若它是所求的目標(biāo)狀態(tài),跳出循環(huán); 否則，從它擴(kuò)展出子結(jié)點(diǎn),

16、全都添到隊(duì)尾;若循環(huán)中找到目標(biāo),輸出結(jié)果;否則輸出無(wú)解;v10V2V4V1V6V5v21v41v51v61V3v32v51ACM/ICPC TRAINING 2007 SUMMER2021-12-1332定義一個(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ú)解;v10V2V4V1V6V5v21v41v51v61V3v32v61ACM/ICPC TRAINING 2007 SUMMER2021-12-1333定義一個(gè)隊(duì)列;起始點(diǎn)加入隊(duì)列;while(隊(duì)列不空) 取出隊(duì)頭結(jié)

17、點(diǎn); 若它是所求的目標(biāo)狀態(tài),跳出循環(huán); 否則，從它擴(kuò)展出子結(jié)點(diǎn),全都添到隊(duì)尾;若循環(huán)中找到目標(biāo),輸出結(jié)果;否則輸出無(wú)解;v10V2V4V1V6V5v21v41v51v61V3v32v32ACM/ICPC TRAINING 2007 SUMMER2021-12-1334定義一個(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é)束搜索，輸出2ACM/ICPC TRAINING 2007 SUMM

18、ER2021-12-1335happy2ACM/ICPC TRAINING 2007 SUMMER2021-12-1336l國(guó)際象棋棋盤(pán)上有一個(gè)馬，要從起點(diǎn)跳到指定目標(biāo)，最少跳幾步？輸入：輸入：a1 h8輸出：輸出：To get from a1 to h8 takes 6 knight moves. a b c d e f g h12345678h8a1ACM/ICPC TRAINING 2007 SUMMER2021-12-1337 a b c d e f g h12345678在23的矩形里：ACM/ICPC TRAINING 2007 SUMMER2021-12-1338l例如：從a1到

19、e4當(dāng)目標(biāo)出現(xiàn)在所擴(kuò)展出的結(jié)點(diǎn)里，結(jié)果就找到了。To get from a1 to e4 takes 3 knight moves. a b c d e f g h1234567803321322312332233323333333233332ACM/ICPC TRAINING 2007 SUMMER2021-12-1339lbool in(int a,int b)llif(a0&a0&b=8)lreturn true;lreturn false;llint bfs()llint col,row,i;lwhile(!qq.empty()llcol=qq.front();lqq.

20、pop();lrow=qq.front();lqq.pop();lans=qq.front();lqq.pop();lif(col=a2&row=a3)lreturn ans;lfor(i=0;i8;i+)llif(in(row+diri.x,col+diri.y)&!mprow+diri.xcol+diri.y)llqq.push(col+diri.y);lqq.push(row+diri.x);lqq.push(ans+1);lmprow+diri.xcol+diri.y=true;llll#include #include using namespace std;stru

21、ct xxxint x,y;xxx dir8=-2,1,-2,-1,-1,-2,1,-2,2,-1,2,1,1,2,-1,2;char c6;int a6;queue qq;bool mp99;int ans;ACM/ICPC TRAINING 2007 SUMMER2021-12-1340lint main()llregister int i,j;ll while(gets(c)llwhile(!qq.empty()lqq.pop();lfor(i=0;i=8;i+)lfor(j=0;j=8;j+)lmpij=false;la0=c0-a+1;/ start colla1=c1-0;/sta

22、rt rowla2=c3-a+1;/end colla3=c4-0;/end rowlans=0;lqq.push(a0);lqq.push(a1);lqq.push(ans);lmpa1a0=true;lans=bfs();lcoutTo get from c0c1 to c3c4 takes ans knight moves.判斷是否有值，除以k的余數(shù)為零。 計(jì)算中間值取余，不影響結(jié)果。 (a + b) % k = ( a % k + b % k) % kn因此只需記錄對(duì)k的余數(shù)。2=k=100，每層結(jié)點(diǎn)最多100個(gè)，不是指數(shù)級(jí)增加。ACM/ICPC TRAINING 2007 SUMME

23、R2021-12-13454 717 5 -21 15每層最多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 = 5(5 -21) % 7 = 51234560擴(kuò)展第4層結(jié)點(diǎn)(1+ 15) % 7 = 2(1 15) % 7 = 0(5 + 15) % 7 = 6(5 15) % 7 = 412345601234560ACM/ICPC TRAINING 2007 SUMMER2021-12-1346v一條長(zhǎng)度為L(zhǎng)“貪吃蛇”在n*m的迷宮中，求它走到出口（1，1）的最少步數(shù)。 (2L 8;1n,m 20)輸入：輸入：5 6 44 14 23 23 132 33 33 40 0 0輸出：輸出：Case 1: 9ACM/ICPC TRAINING 2007 SUMMER2021-12-1347l蛇頭在上、下、左、右四方向上的探索過(guò)程l注意：l蛇不能出界，l不能撞自己，l不能撞石頭。ACM/ICPC TRAINING 2007 SUMMER2021-12-1348l八數(shù)碼游戲Input: 2 3 4 1 5 x 7 6 8 Outpu