搜索之BFS（課堂PPT）

1、SEARCHING STRATEGIES3/5/20222.l搜索被稱為“通用解題法”，在算法和人工智能中占據重要地位。l但由于它巨大的局限性和自身靈活性，也被認為是最難學難用的算法之一。l本節(jié)目標：希望同學們對于任意一個問題， 1.很快建立狀態(tài)空間 2.提出一個合理算法 3.簡單估計時空性能3/5/20223.l盲目搜索盲目搜索：按預定的控制策略進行搜索，在搜索過程中獲得的中間信息不用來改進控制策略。l啟發(fā)式搜索啟發(fā)式搜索：在搜索中加入了與問題有關的啟發(fā)性信息，用以指導搜索朝著最有希望的方向發(fā)展，加速問題的求解過程并找到最優(yōu)解。3/5/20224.l盲目搜索： 1. 廣度優(yōu)先搜索（Bread

2、th First Search） 2. 深度優(yōu)先搜索（Depth First Search） 3. 純隨機搜索、重復式搜索、迭代加深搜索、 迭代加寬搜索、柱型搜索l啟發(fā)式搜索： 1. A*算法 2. IDA*算法3/5/20225.明確以下概念：明確以下概念：l狀態(tài)：問題在某一時刻進展狀況的數學描述。l狀態(tài)轉移：問題從一種狀態(tài)到另一種或幾種狀態(tài)的操作。l狀態(tài)空間：一個“圖”，圖結點對應于狀態(tài)，點之間的邊對應于狀態(tài)轉移。l搜索：尋找一種可行的操作序列，從起始狀態(tài)經過一系列狀態(tài)轉移，達到目標狀態(tài)。3/5/20226.l某人要帶一條狗、一只雞、一籮米過河，但小船除需要人劃外，最多只能載一物過河，而當

3、人不在場時，狗要咬雞、雞要吃米。問此人應如何過河?3/5/20227.l狀態(tài)：建立四元組（人，狗，雞，米）。用0表示在左岸，1表示在右岸。l起始狀態(tài)(0,0,0,0)，終止狀態(tài)(1,1,1,1)l狀態(tài)轉移規(guī)則： (a,b,c,d) (1-a,1-b,c,d)（當a=b） (1-a,b,1-c,d)（當a=c） (1-a,b,c,1-d)（當a=d） (1-a,b,c,d)l約束：(a,b,c,d)中，當ab時bc；當ac時cd3/5/20228.v搜索：(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) (

4、1,0,0,0)3/5/20229.v搜索：(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)3/5/202210.l搜索在“圖”中進行，但圖不需要事先建立（“隱式圖”）。l搜索過程就是對圖的遍歷過程，可以得到一棵“搜索樹”。l搜索樹的結點個數、分枝數、深度，決定著搜索的效率。3/5/202211.3

5、/5/202212.l普通狀態(tài)可以用4個整數表示l壓縮狀態(tài)用4個bit表示(char型有8個bit，足夠用)。l用廣度優(yōu)先(BFS, Breath First Search) 或 用深度優(yōu)先(DFS, Depth First Search)3/5/202213.l顧名思義，廣搜就是“往廣了搜”，深搜就是“往深了搜”。l廣搜例子:你的眼鏡掉在地上以后，你趴在地板上找。你總是先摸最接近你的地方，如果沒有，再摸遠一點的地方l深搜例子：走迷宮，你沒有辦法用分身術來站在每個走過的位置。不撞南山不回頭。3/5/202214.l1.從圖中某頂點v0出發(fā)，在訪問了v0之后，搜索v0的(所有未被訪問的)鄰接頂點

6、v1.v2l2.依次從這些鄰接頂點出發(fā)，廣搜圖中其它頂點，直至圖中所有已被訪問的頂點的鄰接頂點都被訪問到。l3.若此時圖中還有未被訪問到的頂點，則再選擇其中之一作為v0重復上述過程。直到圖中所有頂點均被訪問到。/搜索過程沒有回溯，是一種犧牲空間換取時間的方法。時間復雜度：O(V+E)3/5/202215.l樹、圖的BFS演示01234859671002145363/5/202216.定義一個隊列;起始點加入隊列;while(隊列不空) 取出隊頭結點; 若它是所求的目標狀態(tài),跳出循環(huán); 否則，從它擴展出子結點,全都添到隊尾;若循環(huán)中找到目標,輸出結果;否則輸出無解;這個結構是普遍適用的。任何非遞

7、歸非遞歸的BFS程序都能套進去3/5/202217.l無向圖如下，邊權均為無向圖如下，邊權均為1，求，求V1到到V3的最短路徑的最短路徑V3V2V4V1V6V53/5/202218.定義一個隊列;起始點加入隊列;while(隊列不空) 取出隊頭結點; 若它是所求的目標狀態(tài),跳出循環(huán); 否則，從它擴展出子結點,全都添到隊尾;若循環(huán)中找到目標,輸出結果;否則輸出無解;v10V1隊列結點記錄兩個信息1：頂點編號2：步數3/5/202219.定義一個隊列;起始點加入隊列;while(隊列不空) 取出隊頭結點; 若它是所求的目標狀態(tài),跳出循環(huán); 否則，從它擴展出子結點,全都添到隊尾;若循環(huán)中找到目標,輸

8、出結果;否則輸出無解;v10V13/5/202220.定義一個隊列;起始點加入隊列;while(隊列不空) 取出隊頭結點; 若它是所求的目標狀態(tài),跳出循環(huán); 否則，從它擴展出子結點,全都添到隊尾;若循環(huán)中找到目標,輸出結果;否則輸出無解;v10V1v103/5/202221.定義一個隊列;起始點加入隊列;while(隊列不空) 取出隊頭結點; 若它是所求的目標狀態(tài),跳出循環(huán); 否則，從它擴展出子結點,全都添到隊尾;若循環(huán)中找到目標,輸出結果;否則輸出無解;v10V1v10V1不是終點3/5/202222.定義一個隊列;起始點加入隊列;while(隊列不空) 取出隊頭結點; 若它是所求的目標狀態(tài)

9、,跳出循環(huán); 否則，從它擴展出子結點,全都添到隊尾;若循環(huán)中找到目標,輸出結果;否則輸出無解;v10V2V4V1V6V5v21v41v51v61v103/5/202223.定義一個隊列;起始點加入隊列;while(隊列不空) 取出隊頭結點; 若它是所求的目標狀態(tài),跳出循環(huán); 否則，從它擴展出子結點,全都添到隊尾;若循環(huán)中找到目標,輸出結果;否則輸出無解;v10V2V4V1V6V5v21v41v51v613/5/202224.定義一個隊列;起始點加入隊列;while(隊列不空) 取出隊頭結點; 若它是所求的目標狀態(tài),跳出循環(huán); 否則，從它擴展出子結點,全都添到隊尾;若循環(huán)中找到目標,輸出結果;否

10、則輸出無解;v10V2V4V1V6V5v21v41v51v61v213/5/202225.定義一個隊列;起始點加入隊列;while(隊列不空) 取出隊頭結點; 若它是所求的目標狀態(tài),跳出循環(huán); 否則，從它擴展出子結點,全都添到隊尾;若循環(huán)中找到目標,輸出結果;否則輸出無解;v10V2V4V1V6V5v21v41v51v61V2不是終點v213/5/202226.定義一個隊列;起始點加入隊列;while(隊列不空) 取出隊頭結點; 若它是所求的目標狀態(tài),跳出循環(huán); 否則，從它擴展出子結點,全都添到隊尾;若循環(huán)中找到目標,輸出結果;否則輸出無解;v10V2V4V1V6V5v21v41v51v61V

11、3v32v213/5/202227.定義一個隊列;起始點加入隊列;while(隊列不空) 取出隊頭結點; 若它是所求的目標狀態(tài),跳出循環(huán); 否則，從它擴展出子結點,全都添到隊尾;若循環(huán)中找到目標,輸出結果;否則輸出無解;v10V2V4V1V6V5v21v41v51v61V3v323/5/202228.定義一個隊列;起始點加入隊列;while(隊列不空) 取出隊頭結點; 若它是所求的目標狀態(tài),跳出循環(huán); 否則，從它擴展出子結點,全都添到隊尾;若循環(huán)中找到目標,輸出結果;否則輸出無解;v10V2V4V1V6V5v21v41v51v61V3v32v413/5/202229.定義一個隊列;起始點加入隊

12、列;while(隊列不空) 取出隊頭結點; 若它是所求的目標狀態(tài),跳出循環(huán); 否則，從它擴展出子結點,全都添到隊尾;若循環(huán)中找到目標,輸出結果;否則輸出無解;v10V2V4V1V6V5v21v41v51v61V3v32v41V4不是終點3/5/202230.定義一個隊列;起始點加入隊列;while(隊列不空) 取出隊頭結點; 若它是所求的目標狀態(tài),跳出循環(huán); 否則，從它擴展出子結點,全都添到隊尾;若循環(huán)中找到目標,輸出結果;否則輸出無解;v10V2V4V1V6V5v21v41v51v61V3v32v413/5/202231.定義一個隊列;起始點加入隊列;while(隊列不空) 取出隊頭結點;

13、若它是所求的目標狀態(tài),跳出循環(huán); 否則，從它擴展出子結點,全都添到隊尾;若循環(huán)中找到目標,輸出結果;否則輸出無解;v10V2V4V1V6V5v21v41v51v61V3v32v513/5/202232.定義一個隊列;起始點加入隊列;while(隊列不空) 取出隊頭結點; 若它是所求的目標狀態(tài),跳出循環(huán); 否則，從它擴展出子結點,全都添到隊尾;若循環(huán)中找到目標,輸出結果;否則輸出無解;v10V2V4V1V6V5v21v41v51v61V3v32v613/5/202233.定義一個隊列;起始點加入隊列;while(隊列不空) 取出隊頭結點; 若它是所求的目標狀態(tài),跳出循環(huán); 否則，從它擴展出子結點

14、,全都添到隊尾;若循環(huán)中找到目標,輸出結果;否則輸出無解;v10V2V4V1V6V5v21v41v51v61V3v32v323/5/202234.定義一個隊列;起始點加入隊列;while(隊列不空) 取出隊頭結點; 若它是所求的目標狀態(tài),跳出循環(huán); 否則，從它擴展出子結點,全都添到隊尾;若循環(huán)中找到目標,輸出結果;否則輸出無解;v10V2V4V1V6V5v21v41v51v61V3v32v32V3是終點，結束搜索，輸出23/5/202235.happy23/5/202236.l國際象棋棋盤上有一個馬，要從起點跳到指定目標，最少跳幾步？輸入：輸入：a1 h8輸出：輸出：To get from a

15、1 to h8 takes 6 knight moves. a b c d e f g h12345678h8a13/5/202237. a b c d e f g h12345678在23的矩形里：3/5/202238.l例如：從a1到e4當目標出現在所擴展出的結點里，結果就找到了。To get from a1 to e4 takes 3 knight moves. a b c d e f g h123456780 332 13 22 31 233 22 3332 33333332 333323/5/202239.lbool in(int a,int b)llif(a0&a0&

16、;b=8)lreturn true;lreturn false;llint bfs()llint col,row,i;lwhile(!qq.empty()llcol=qq.front();lqq.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+d

17、iri.x);lqq.push(ans+1);lmprow+diri.xcol+diri.y=true;llll3/5/202240.lint 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;/start rowla2=c3-a+1;/end colla3=c4-0;/end rowlans=0;lqq.push(a0);lqq.push(a1);lqq.

18、push(ans);lmpa1a0=true;lans=bfs();lcoutTo get from c0c1 to c3c4 takes ans knight moves.判斷是否有值，除以k的余數為零。 計算中間值取余，不影響結果。 (a + b) % k = ( a % k + b % k) % kn因此只需記錄對k的余數。2=k=100，每層結點最多100個，不是指數級增加。3/5/202245.4 717 5 -21 15每層最多7個結點 (定義數組)：首先加入起點，17 % 7 = 3擴展第2層結點(3+5) % 7 = 1(3 5 + 7) % 7 =51 2 3 4 5 60+

19、-擴展第3層結點(1+ -21) % 7 = 1(1 -21) % 7 = 1(5+ -21) % 7 = 5(5 -21) % 7 = 51 2 3 4 5 60擴展第4層結點(1+ 15) % 7 = 2(1 15) % 7 = 0(5 + 15) % 7 = 6(5 15) % 7 = 41 2 3 4 5 601 2 3 4 5 603/5/202246.v一條長度為L“貪吃蛇”在n*m的迷宮中，求它走到出口（1，1）的最少步數。 (2L 8;1n,m 20)輸入：輸入：5 6 44 14 23 23 132 33 33 40 0 0輸出：輸出：Case 1: 93/5/202247.l蛇頭在上、下、左、右四方向上的探索過程l注意：l蛇不能出界，l不能撞自己，l不能撞石頭。3/5/202248.l八數碼游戲3/5/202249.22