寬度優(yōu)先搜索(BFS)

寬度優(yōu)先搜索引例1,12,33,21,54,41,32,45,32,53,44,55,5(1,1)(1,3)(1,5)(2,3)(2,4)(2,5)(3,2)(3,4)(3,5)(4,4)(4,5)(5,3)(5,5)11233215351324445325344555跳馬搜索樹（解答樹）法3——BFS(寬度優(yōu)先搜索)需引入數(shù)據(jù)結(jié)構(gòu)——隊(duì)列寬度優(yōu)先搜索隊(duì)列基本概念(queue)隊(duì)列是限定在一端進(jìn)行插入，在另一端進(jìn)行刪除的特殊的線性表。像食堂排隊(duì)買飯，后來的人排在隊(duì)尾（插入），隊(duì)頭上的人買完飯后出隊(duì)（刪除）。所有需要進(jìn)隊(duì)的數(shù)據(jù)項(xiàng)只能從隊(duì)尾進(jìn)入；所有需要出隊(duì)的數(shù)據(jù)項(xiàng)只能從隊(duì)頭離開。先入隊(duì)的元素先出隊(duì)，這種表又稱為先進(jìn)先出表（FIFO表---firstinfirstout）。隊(duì)列可用數(shù)組表示，在隊(duì)列運(yùn)算中要設(shè)兩個(gè)指針：隊(duì)頭指針--------head

隊(duì)尾指針--------tail假設(shè)我們約定:(1)head指向隊(duì)列第一個(gè)元素的前一個(gè)單元;(2)tail指向隊(duì)列最后一個(gè)元素;如下圖狀態(tài)：head=0;tail=5;顯然，隊(duì)列元素個(gè)數(shù)：n=tail-head;0123456123345671、初始化：head=tail=02、元素入隊(duì)：tail++;q[tail]=data;01234560123456123、元素出隊(duì)：head++;data=q[head];012345613124、判斷隊(duì)列空否：head>=tail?或元素個(gè)數(shù)為0否：tail-head==0?非空：head<tail012345612131617BFS框架1（僅供參考）int

bfs(){

隊(duì)列初始化;

初始狀態(tài)入隊(duì); while(隊(duì)列不空) {

獲取隊(duì)頭狀態(tài)s;彈出隊(duì)頭狀態(tài)s;

if(s是目標(biāo)狀態(tài))

處理目標(biāo)狀態(tài);

for(k=1;k<=擴(kuò)展規(guī)則總數(shù);k++)

{

利用擴(kuò)展規(guī)則k擴(kuò)展出s的子狀態(tài)s’;

if(狀態(tài)s’合法)

子狀態(tài)s’入隊(duì);

} } return0;}BFS框架2（僅供參考）隊(duì)列實(shí)現(xiàn)方法（1）用數(shù)組模擬隊(duì)列，如上面的演示（2）使用C++標(biāo)準(zhǔn)模板庫(kù)中的容器queue，詳細(xì)用法見如下程序段：（見下頁(yè)）#include<queue>………………structnode{ intx,y;//行列號(hào)}start,h,s;//聲明三個(gè)狀態(tài)對(duì)象queue<node>

q;//聲明隊(duì)列,<node>用來聲明隊(duì)列元素的類型intt[5][3]={{0,0,0},{0,-2,1},{0,-1,2},{0,1,2},{0,2,1}};//跳馬規(guī)則,下一行是規(guī)則另外一種表示方式//inttx[5]={0,-2,-1,1,2};intty[5]={0,1,2,2,1};inthorse_bfs(){

start.x=1;start.y=1;//起始狀態(tài)

q.push(start);//初始狀態(tài)入隊(duì)

while(!q.empty())//隊(duì)列不空

{ h=q.front();q.pop();//獲得隊(duì)頭狀態(tài)后,讓其出隊(duì)

for(intk=1;k<=4;k++)

{

利用跳馬規(guī)則k擴(kuò)展出h的子狀態(tài)s;

if(狀態(tài)s合法)

if(s是目標(biāo)狀態(tài))

處理目標(biāo)狀態(tài);

else

q.push(s);//s狀態(tài)入隊(duì);

} } return0;}練習(xí)

BFS基礎(chǔ)練習(xí)1：跳馬問題、騎士集結(jié)

跳馬問題基礎(chǔ)版：跳馬跳數(shù)基礎(chǔ)版跳馬問題分析該問題遍歷過程可以按照馬前進(jìn)的步數(shù)劃分成若干階段，每一個(gè)階段的各個(gè)狀態(tài)構(gòu)成遍歷樹的某一層。某層某狀態(tài)的最優(yōu)值只與上一層的某些狀體有關(guān)，無后效性體現(xiàn)的很明顯。所以考慮用動(dòng)態(tài)規(guī)劃。由于只允許馬向右跳，在二維數(shù)組中，某個(gè)狀態(tài)所依賴的上一個(gè)階段的那些狀態(tài)都在該狀態(tài)的左邊兩列，所以我們從左到右更新每一列即可保證每個(gè)狀態(tài)的最優(yōu)。跳馬問題：法2——?jiǎng)討B(tài)規(guī)劃階段x：馬跳x步的可達(dá)狀態(tài)，即解答樹中第x層的狀態(tài)；狀態(tài)：f(i,j)表示（起點(diǎn)）到（i,j）的路徑數(shù)；狀態(tài)轉(zhuǎn)移方程：f[i][j]+=f[i-2][j-1]+f[i-1][j-2]+f[i+1][j-2]+f[i+2][j-1];(