信息學(xué)奧賽寬搜及應(yīng)用課件

寬搜及應(yīng)用寬搜及應(yīng)用本講要點(diǎn)寬搜及其算法思想寬搜的算法實(shí)現(xiàn)寬搜應(yīng)用初步本講要點(diǎn)寬搜及其算法思想引言搜索算法是基于計(jì)算機(jī)高速運(yùn)算的特點(diǎn)而使用的求解方法。它從問題的初始狀態(tài)出發(fā)，根據(jù)約束條件，按照一定的策略，有序推進(jìn)，不斷深入，最終到達(dá)所有符合條件的目標(biāo)狀態(tài)（或無解），或者找出所有可行解中的最優(yōu)解。

按照推進(jìn)的控制策略，搜索一般分為寬度優(yōu)先搜索和深度優(yōu)先搜索。引言搜索算法是基于計(jì)算機(jī)高速運(yùn)算的特白色表示未訪問的節(jié)點(diǎn)，黑色表示已經(jīng)訪問的節(jié)點(diǎn)，灰色表示：DFS中為正在訪問的節(jié)點(diǎn)，BFS中為已入隊(duì)等待訪問的節(jié)點(diǎn)。深度優(yōu)先搜索（DFS）與寬度優(yōu)先搜索（BFS)的比較DFSBFS白色表示未訪問的節(jié)點(diǎn)，黑色表示已經(jīng)訪問的節(jié)點(diǎn)，灰色表一、寬度優(yōu)先搜索的算法思想寬度優(yōu)先搜索（BreadthFirstSearch,BFS)，簡稱寬搜，又稱為廣度優(yōu)先搜索。它是從初始結(jié)點(diǎn)開始，應(yīng)用產(chǎn)生式規(guī)則和控制策略生成第一層結(jié)點(diǎn)，同時(shí)檢查目標(biāo)結(jié)點(diǎn)是否在這些生成的結(jié)點(diǎn)中。若沒有，再用產(chǎn)生式規(guī)則將所有第一層結(jié)點(diǎn)逐一拓展，得到第二層結(jié)點(diǎn)，并逐一檢查第二層結(jié)點(diǎn)是否包含目標(biāo)結(jié)點(diǎn)。若沒有，再用產(chǎn)生式規(guī)則拓展第二層結(jié)點(diǎn)。如此依次拓展，檢查下去，直到發(fā)現(xiàn)目標(biāo)結(jié)點(diǎn)為止。如果拓展完所有結(jié)點(diǎn)，都沒有發(fā)現(xiàn)目標(biāo)結(jié)點(diǎn)，則問題無解。對于同一層結(jié)點(diǎn)來說，它們對于問題的解的價(jià)值是相同的，所以第一個(gè)找到的目標(biāo)結(jié)點(diǎn)一定是應(yīng)用產(chǎn)生式規(guī)則最少的，因此，寬搜適合求最少步驟或最短解序列這類最優(yōu)解問題。

一、寬度優(yōu)先搜索的算法思想寬度優(yōu)先搜索（Breadth一、寬度優(yōu)先搜索的算法思想abcdehfg第0層第1層第2層第3層逐層遍歷一、寬度優(yōu)先搜索的算法思想abcdehfg第0層第1層第2層二、寬度優(yōu)先搜索的算法分析BFS問題解決的關(guān)鍵狀態(tài)表示：狀態(tài)一般是指現(xiàn)場信息的描述，通常用T表示。一般用T0表示初始狀態(tài)，Tn表示目標(biāo)狀態(tài)。狀態(tài)轉(zhuǎn)移：根據(jù)產(chǎn)生式規(guī)則和約束條件控制從當(dāng)前狀態(tài)轉(zhuǎn)移到下一個(gè)狀態(tài)。狀態(tài)判重：大多數(shù)情況下，出現(xiàn)重復(fù)狀態(tài)會造成死循環(huán)或空間的浪費(fèi)?，F(xiàn)在在哪兒？下一步去哪兒？去過的就別再去了！二、寬度優(yōu)先搜索的算法分析BFS問題解決的關(guān)鍵現(xiàn)在在哪兒三、寬度優(yōu)先搜索的算法實(shí)現(xiàn)

為保證“先生成的結(jié)點(diǎn)先擴(kuò)展”，寬搜需用到符合“先進(jìn)先出”特點(diǎn)的這種重要的數(shù)據(jù)結(jié)構(gòu)。隊(duì)列三、寬度優(yōu)先搜索的算法實(shí)現(xiàn)為保證“先生成的隊(duì)列的概念隊(duì)列：限定僅在一端進(jìn)行插入，而在另一端進(jìn)行刪除操作的線性表。允許刪除的一端稱為隊(duì)頭(front)，允許插入的一端稱為隊(duì)尾(rear)。當(dāng)隊(duì)列中沒有元素時(shí)稱為空隊(duì)列。在空隊(duì)列中依次加入元素a1,a2,…an之后，a1是隊(duì)頭元素，an是隊(duì)尾元素。

隊(duì)列(Queues)是生活中“排隊(duì)”的抽象。隊(duì)列的概念隊(duì)列：限定僅在一端進(jìn)行插入，而在另一端進(jìn)行刪除操作三、寬度優(yōu)先搜索的算法實(shí)現(xiàn)隊(duì)列(Queue)允許用戶從表的一端(隊(duì)尾)入隊(duì)，從表的另一端(隊(duì)頭)出隊(duì)。因此，隊(duì)列也被稱作先進(jìn)先出線性表(FIFO-FirstInFirstOut)。三、寬度優(yōu)先搜索的算法實(shí)現(xiàn)隊(duì)列(Queue)允許用戶從表三、寬度優(yōu)先搜索的算法實(shí)現(xiàn)隊(duì)列實(shí)現(xiàn)：數(shù)組模擬、STL（queue）用數(shù)組模擬隊(duì)列頭指針front、尾指針rear

入隊(duì)與出隊(duì)隊(duì)空三、寬度優(yōu)先搜索的算法實(shí)現(xiàn)隊(duì)列實(shí)現(xiàn)：數(shù)組模擬、STL（que三、寬度優(yōu)先搜索的算法實(shí)現(xiàn)constintMAXN=1010;//隊(duì)列的容量上限intq[MAXN];//隊(duì)列的元素類型intfront,rear;//頭指針、尾指針rearfront

隊(duì)列定義（數(shù)組）三、寬度優(yōu)先搜索的算法實(shí)現(xiàn)constintMAXN三、寬度優(yōu)先搜索的算法實(shí)現(xiàn)隊(duì)列初始化，初始狀態(tài)入隊(duì)front=0;rear=1;q[1]=1;//q[rear]=1;rearfront11約定：從1號結(jié)點(diǎn)開始存放隊(duì)列元素三、寬度優(yōu)先搜索的算法實(shí)現(xiàn)隊(duì)列初始化，初始狀態(tài)入隊(duì)fron三、寬度優(yōu)先搜索的算法實(shí)現(xiàn)取隊(duì)首元素，準(zhǔn)備擴(kuò)展front++;x=q[front];rearfront11三、寬度優(yōu)先搜索的算法實(shí)現(xiàn)取隊(duì)首元素，準(zhǔn)備擴(kuò)展front++三、寬度優(yōu)先搜索的算法實(shí)現(xiàn)擴(kuò)展隊(duì)首結(jié)點(diǎn)，新狀態(tài)入隊(duì)rear++;q[rear]=x;rearfront123123三、寬度優(yōu)先搜索的算法實(shí)現(xiàn)擴(kuò)展隊(duì)首結(jié)點(diǎn)，新狀態(tài)入隊(duì)rear+三、寬度優(yōu)先搜索的算法實(shí)現(xiàn)隊(duì)首結(jié)點(diǎn)擴(kuò)展完畢，出隊(duì)front++;x=q[front];指針后移一位，指向待擴(kuò)展節(jié)點(diǎn)。rearfront123123三、寬度優(yōu)先搜索的算法實(shí)現(xiàn)隊(duì)首結(jié)點(diǎn)擴(kuò)展完畢，出隊(duì)front+三、寬度優(yōu)先搜索的算法實(shí)現(xiàn)判斷隊(duì)列是否為空隊(duì)列不空：front<rearrearfront123隊(duì)列空：front>=rear三、寬度優(yōu)先搜索的算法實(shí)現(xiàn)判斷隊(duì)列是否為空隊(duì)列不空：fron三、寬度優(yōu)先搜索的算法實(shí)現(xiàn)隊(duì)列基本操作constintMAXN=101;intq[MAXN];intfront,rear;intmain(){front=0;rear=1;q[1]=1;rear++;q[rear]=2;rear++;q[rear]=3; while(front<rear)//隊(duì)列非空{(diào) front++;

//隊(duì)首出隊(duì)intx=q[front];

cout<<x<<"";}return0;}123三、寬度優(yōu)先搜索的算法實(shí)現(xiàn)隊(duì)列基本操作constintM三、寬度優(yōu)先搜索的算法實(shí)現(xiàn)BFS算法模板（數(shù)組模擬）front

0;rear

1;初始狀態(tài)入隊(duì);while(front<rear)//當(dāng)隊(duì)列不為空{(diào) 取隊(duì)首元素進(jìn)行擴(kuò)展; for(對所有可能的拓展?fàn)顟B(tài)) { if(新狀態(tài)合法)入隊(duì);

if(當(dāng)前狀態(tài)是目標(biāo)狀態(tài))

處理(輸出解或比較解的優(yōu)劣); }}三、寬度優(yōu)先搜索的算法實(shí)現(xiàn)BFS算法模板（數(shù)組模擬）fron1.將隊(duì)列中的所有元素均向低地址區(qū)移動(dòng)，顯然這種方法是很浪費(fèi)時(shí)間的；用循環(huán)隊(duì)列節(jié)約存儲空間2.將數(shù)組存儲區(qū)看成是一個(gè)首尾相接的環(huán)形區(qū)域。當(dāng)存放到n地址后，下一個(gè)地址就"翻轉(zhuǎn)"為１。在結(jié)構(gòu)上采用這種技巧來存儲的隊(duì)列稱為循環(huán)隊(duì)列。1.將隊(duì)列中的所有元素均向低地址區(qū)移動(dòng)，顯然這種方法是很浪費(fèi)STL中隊(duì)列queue的常用函數(shù)介紹q.pop()刪除queue的隊(duì)首元素q.front()返回隊(duì)列的隊(duì)首元素，但不刪除該元素q.back()返回隊(duì)列的隊(duì)尾元素，但不刪除該元素q.push(tmp)將元素tmp插入到隊(duì)列的隊(duì)尾q.size()

返回隊(duì)列中元素的個(gè)數(shù)q.empty()當(dāng)隊(duì)列為空時(shí)返回true，否則返回falsewhile(!q.empty())

q.pop();清空隊(duì)列三、寬度優(yōu)先搜索的算法實(shí)現(xiàn)STL中隊(duì)列queue的常用函數(shù)介紹q.pop()隊(duì)列queue的定義和使用queue<int>q;intmain(){for(inti=0;i<6;i++)q.push(i);//入隊(duì)列q.push(20);cout<<q.size()<<endl;//隊(duì)列元素個(gè)數(shù)while(!q.empty())//隊(duì)列不空時(shí)循環(huán){ cout<<q.front()<<‘’;//輸出隊(duì)首元素 q.pop();//刪除隊(duì)首元素}return0;}三、寬度優(yōu)先搜索的算法實(shí)現(xiàn)隊(duì)列queue的定義和使用queue<int>q;三、寬度三、寬度優(yōu)先搜索的算法實(shí)現(xiàn)BFS算法模板（queue）queue<類型>q;

//定義一個(gè)名為q的隊(duì)列q.push(初始狀態(tài));while(!q.empty())//當(dāng)隊(duì)列不為空{(diào) 取隊(duì)首元素進(jìn)行擴(kuò)展; for(對所有可能的拓展?fàn)顟B(tài)) { if(新狀態(tài)合法)q.push(新狀態(tài));

if(當(dāng)前狀態(tài)是目標(biāo)狀態(tài))

處理(輸出解或比較解的優(yōu)劣); }q.pop();//出隊(duì)}三、寬度優(yōu)先搜索的算法實(shí)現(xiàn)BFS算法模板（queue）que四、寬度優(yōu)先搜索的算法應(yīng)用（入門）求最優(yōu)解問題求連通塊問題四、寬度優(yōu)先搜索的算法應(yīng)用（入門）求最優(yōu)解問題四、寬度優(yōu)先搜索的算法應(yīng)用第一類應(yīng)用：求最優(yōu)解問題四、寬度優(yōu)先搜索的算法應(yīng)用第一類應(yīng)用：求最優(yōu)解問題四、寬度優(yōu)先搜索的算法應(yīng)用[例1]抓住那頭牛

農(nóng)夫知道一頭牛的位置，想要抓住它。農(nóng)夫和牛都位于數(shù)軸上，農(nóng)夫起始位于點(diǎn)N(0<=N<=100000)，牛位于點(diǎn)K(0<=K<=100000)。

農(nóng)夫有兩種移動(dòng)方式：

1、從X移動(dòng)到X-1或X+1，每次移動(dòng)花費(fèi)一分鐘

2、從X移動(dòng)到2*X，每次移動(dòng)花費(fèi)一分鐘假設(shè)牛沒有意識到農(nóng)夫的行動(dòng)，站在原地不動(dòng)。問：農(nóng)夫最少需要花多少時(shí)間才能抓住那頭牛？四、寬度優(yōu)先搜索的算法應(yīng)用[例1]抓住那頭牛四、寬度優(yōu)先搜索的算法應(yīng)用[例1]抓住那頭?！緲永斎搿?5{農(nóng)夫起始位置牛起始位置}【樣例輸出】

2{農(nóng)夫抓到牛所要花費(fèi)的最小分鐘數(shù)}四、寬度優(yōu)先搜索的算法應(yīng)用[例1]抓住那頭牛四、寬度優(yōu)先搜索的算法應(yīng)用[問題分析-抓住那頭牛]初始狀態(tài)N目標(biāo)狀態(tài)K狀態(tài)轉(zhuǎn)移規(guī)則1：XX-1規(guī)則2：X

X+1規(guī)則3：X2*X

約束條件：0<=X<=100000狀態(tài)表示位置四、寬度優(yōu)先搜索的算法應(yīng)用[問題分析-抓住那頭牛]初始狀態(tài)四、寬度優(yōu)先搜索的算法應(yīng)用[問題分析-抓住那頭牛]12345678910303246當(dāng)前位置最少時(shí)間15rearfront2141611252找到目標(biāo)狀態(tài)四、寬度優(yōu)先搜索的算法應(yīng)用[問題分析-抓住那頭牛]12345四、寬度優(yōu)先搜索的算法應(yīng)用【思考】為什么BFS找到的第一個(gè)目標(biāo)結(jié)點(diǎn)一定是最優(yōu)解？在搜索的過程中，BFS對于結(jié)點(diǎn)總是沿著深度的斷層逐層擴(kuò)展的，即要擴(kuò)展第n+1層結(jié)點(diǎn)，必須先將第n層結(jié)點(diǎn)全部擴(kuò)展完畢。且對于同一層結(jié)點(diǎn)而言，它們對于問題解的價(jià)值是相同的。所以BFS一定能保證：第一個(gè)找到的目標(biāo)結(jié)點(diǎn)，一定是應(yīng)用產(chǎn)生式規(guī)則最少的。因此，寬度優(yōu)先搜索較適合求最優(yōu)解的問題。四、寬度優(yōu)先搜索的算法應(yīng)用【思考】為什么BFS找到的第一個(gè)目四、寬度優(yōu)先搜索的算法應(yīng)用[例2]小明抄答案有一次上數(shù)學(xué)課，老師布置了課堂作業(yè)。小明在寫作業(yè)時(shí)睡著了。他夢見自己站在一個(gè)迷宮里，一個(gè)圣人給了他迷宮的地圖，說：“你現(xiàn)在位于迷宮的左上角，迷宮的右下角有數(shù)學(xué)作業(yè)的答案。你只能上下左右走，但你放心，我沒有耍你，迷宮是一定能走得通的?！毙∶骱芟肽玫酱鸢?，但他太笨了，所以找來了會編程的你，叫你幫他找到答案。他需要知道找到答案的最少步數(shù)。四、寬度優(yōu)先搜索的算法應(yīng)用[例2]小明抄答案四、寬度優(yōu)先搜索的算法應(yīng)用[例2]小明抄答案

【輸入】

第一行是兩個(gè)整數(shù)，Ｒ和Ｃ，代表迷宮的行數(shù)和列數(shù)（2<=R,C<=100）。接下來的Ｒ行，每行Ｃ個(gè)字符，代表整個(gè)迷宮?？盏馗褡佑?.'表示，有障礙物的格子用'#'表示。迷宮左上角和右下角都是'.'?！据敵觥?/p>

一行包含一個(gè)整數(shù)，輸出從左上角走到右下角至少要經(jīng)過多少步（即至少要經(jīng)過多少個(gè)空地格子）。注：計(jì)算步數(shù)要包括起點(diǎn)和終點(diǎn)。四、寬度優(yōu)先搜索的算法應(yīng)用[例2]小明抄答案四、寬度優(yōu)先搜索的算法應(yīng)用[問題分析-小明抄答案]

狀態(tài)表示：

初始狀態(tài)：

目標(biāo)狀態(tài)：

(1,1)(r,c)11StartEndrc當(dāng)前所在迷宮的位置（行號,列號）左上角右下角四、寬度優(yōu)先搜索的算法應(yīng)用[問題分析-小明抄答案]四、寬度優(yōu)先搜索的算法應(yīng)用[問題分析-小明抄答案]

狀態(tài)轉(zhuǎn)移：

轉(zhuǎn)移規(guī)則：

約束條件：1<=x<=r1<=y<=c④③(x,y)①

②①(x,y+1)②(x+1,y)③(x,y-1)④(x-1,y)四、寬度優(yōu)先搜索的算法應(yīng)用[問題分析-小明抄答案]四、寬度優(yōu)先搜索的算法應(yīng)用[問題分析-小明抄答案]

123456789111行號最少步數(shù)12341●●##2#●●#3#●#●4#●●●列號(1,1)(1,2)(2,2)(2,3)(3,2)(4,2)(4,3)(4,4)122223234324425436447找到目標(biāo)狀態(tài)四、寬度優(yōu)先搜索的算法應(yīng)用[問題分析-小明抄答案]四、寬度優(yōu)先搜索的算法應(yīng)用[問題分析-小明抄答案]思考：如果要輸出其中一條最短路徑，怎么辦？1234567811223444122322341234456701233567行號最少步數(shù)列號前驅(qū)節(jié)點(diǎn)(1,1)(1,2)(2,2)(3,2)(4,2)(4,3)(4,4)12341●●##2#●●#3#●#●4#●●●四、寬度優(yōu)先搜索的算法應(yīng)用[問題分析-小明抄答案]12345四、寬度優(yōu)先搜索的算法應(yīng)用第二類應(yīng)用：求連通塊問題四、寬度優(yōu)先搜索的算法應(yīng)用第二類應(yīng)用：求連通塊問題四、寬度優(yōu)先搜索的算法應(yīng)用[例3]寶島探險(xiǎn)【題目描述】某海域航拍圖由一個(gè)R行C列的數(shù)字矩陣組成，圖中數(shù)字表示海拔，0表示海洋，1~9表示陸地。求該海域共有多少島嶼，最大的島嶼面積多大（即包含多少格子）。我們把上下左右相鄰接的陸地視為同一島嶼。四、寬度優(yōu)先搜索的算法應(yīng)用[例3]寶島探險(xiǎn)四、寬度優(yōu)先搜索的算法應(yīng)用[例3]寶島探險(xiǎn)【樣例輸入】【樣例輸出】4104110234500067103456050020456006710000000089【數(shù)據(jù)范圍】1<=R，C<=20四、寬度優(yōu)先搜索的算法應(yīng)用[例3]寶島探險(xiǎn)四、寬度優(yōu)先搜索的算法應(yīng)用[問題分析-寶島探險(xiǎn)]求連通塊問題的基本思路是：從某關(guān)鍵點(diǎn)（不是海洋的點(diǎn)）開始BFS，形成的連通區(qū)域即為一連通塊。四、寬度優(yōu)先搜索的算法應(yīng)用[問題分析-寶島探險(xiǎn)]四、寬度優(yōu)先搜索的算法應(yīng)用[問題分析-寶島探險(xiǎn)]1234567891010234500067210345605003204560067140000000089每找到一個(gè)島嶼，個(gè)數(shù)就+1四、寬度優(yōu)先搜索的算法應(yīng)用[問題分析-寶島探險(xiǎn)]123456四、寬度優(yōu)先搜索的算法應(yīng)用[問題分析-寶島探險(xiǎn)]123456789101112123456789101023450006721034560500320456006714000000008913142315243325342635rear即為當(dāng)前島嶼大小ij四、寬度優(yōu)先搜索的算法應(yīng)用[問題分析-寶島探險(xiǎn)]123456for(inti=1;i<=n;i++)for(intj=0;j<m;j++){ if(s[i][j]!='0') {ans++;//島嶼個(gè)數(shù)tot=1;

//島嶼大小 s[i][j]='0'; tmp.x=i; tmp.y=j; q.push(tmp); bfs(); if(tot>imax)imax=tot; }}voidbfs(){while(!q.empty()){

for(inti=0;i<4;i++){ tmp.x=q.front().x+dx[i]; tmp.y=q.front().y+dy[i]; if(tmp.x>=1&&tmp.x<=n&&tmp.y>=0&&tmp.y<m&&s[tmp.x][tmp.y]!='0') { q.push(tmp); s[tmp.x][tmp.y]='0'; tot++; }

}q.pop();}}輸出什么?for(inti=1;i<=n;i++)voidbfs([例4]分油問題

有三個(gè)容量分別是10升、7升、3升的桶，開始時(shí)只有10升的桶都是滿的，而7升和3升桶是空的。我們可以把油從一個(gè)桶倒到另一個(gè)桶中，每一次的倒油過程都以原始桶空或目標(biāo)桶滿為結(jié)束，且倒油過程中不會產(chǎn)生任何的浪費(fèi)。那么最少需要幾步可在10升桶和7升桶中各裝入5升的油？五、課后討論[例4]分油問題五、課后討論[問題分析-倒油問題]狀態(tài)的表示

初始狀態(tài)：

目標(biāo)狀態(tài)：

用一個(gè)三元組T（x10,x7,x3）表示狀態(tài)，其中x10，x7，x3分別表示三個(gè)瓶子中的當(dāng)前油量。（10,0,0）（5,5,0）五、課后討論[問題分析-倒油問題]用一個(gè)三元組T（x10,x7,x3）表[問題分析-倒油問題]狀態(tài)的轉(zhuǎn)移（規(guī)則）

三個(gè)瓶子（x10,x7,x3）有6種倒油規(guī)則：10升瓶

7升瓶10升瓶

3升瓶7升瓶

10升瓶7升瓶

3升瓶3升瓶

10升瓶3升瓶

7升瓶五、課后討論[問題分析-倒油問題]10升瓶7升瓶10升瓶3升瓶7升瓶[問題分析-倒油問題]狀態(tài)的轉(zhuǎn)移（約束條件）

當(dāng)

且

時(shí)：如果

,那么

倒?jié)M7升瓶新狀態(tài)T’(

)入隊(duì)否則

倒空10升瓶新狀態(tài)T’(

)入隊(duì)10升瓶

7