第九講-搜索之BFS課件

搜索之BFS廣度優(yōu)先搜索搜索之BFS廣度優(yōu)先搜索1廣度優(yōu)先搜索基本思想：

從初始狀態(tài)S開始，利用規(guī)則，生成所有可能的狀態(tài)。構(gòu)成樹的下一層節(jié)點(diǎn)，檢查是否出現(xiàn)目標(biāo)狀態(tài)G，若未出現(xiàn)，就對(duì)該層所有狀態(tài)節(jié)點(diǎn)，分別順序利用規(guī)則。生成再下一層的所有狀態(tài)節(jié)點(diǎn)，對(duì)這一層的所有狀態(tài)節(jié)點(diǎn)檢查是否出現(xiàn)G，若未出現(xiàn)，繼續(xù)按上面思想生成再下一層的所有狀態(tài)節(jié)點(diǎn)，這樣一層一層往下展開。直到出現(xiàn)目標(biāo)狀態(tài)為止。廣度優(yōu)先搜索基本思想：2BFS算法（1）把起始節(jié)點(diǎn)S線放到OPEN表中（2）如果OPEN是空表，則失敗退出，否則繼續(xù)。（3）在OPEN表中取最前面的節(jié)點(diǎn)node移到CLOSED表中。（4）擴(kuò)展node節(jié)點(diǎn)。若沒有后繼（即葉節(jié)點(diǎn)），則轉(zhuǎn)向（2）循環(huán)。（5）把node的所有后繼節(jié)點(diǎn)放在OPEN表的末端。各后繼結(jié)點(diǎn)指針指向node節(jié)點(diǎn)。（6）若后繼節(jié)點(diǎn)中某一個(gè)是目標(biāo)節(jié)點(diǎn)，則找到一個(gè)解，成功退出。否則轉(zhuǎn)向（2）循環(huán)。BFS算法（1）把起始節(jié)點(diǎn)S線放到OPEN表中3BFS–廣度優(yōu)先搜索BFS在訪問了起始頂點(diǎn)A之后,由A出發(fā),依次訪問A的各個(gè)未被訪問過的鄰接頂點(diǎn)B,D,…,C,然后再順序訪問B,D,…,C的所有還未被訪問過的鄰接頂點(diǎn)。再從這些訪問過的頂點(diǎn)出發(fā)，再訪問它們的所有還未被訪問過的鄰接頂點(diǎn)，…如此做下去，直到圖中所有頂點(diǎn)都被訪問到為止。廣度優(yōu)先搜索是一種分層的搜索過程,每向前走一步可能訪問一批頂點(diǎn)。ACDEGBFIH123456789BFS–廣度優(yōu)先搜索BFS在訪問了起始頂點(diǎn)A之后,4BFS的代碼分析voidBFS(){ queue<point>q;//隊(duì)列

q.push(st);//初始點(diǎn)入隊(duì)列 while(!q.empty())//隊(duì)列中還有要處理的點(diǎn)

{

從隊(duì)列中取出下一個(gè)處理的點(diǎn)p；

for(p的所有鄰接點(diǎn))

if(該鄰接點(diǎn)滿足搜索條件) { q.push(鄰接點(diǎn));

標(biāo)記該鄰接點(diǎn)為已訪問； } }

}BFS的代碼分析voidBFS()5BFS廣度優(yōu)先搜索過程ACDEGBFIH123456789FEDCABGHI隊(duì)列變化情況指針箭頭表示當(dāng)前訪問節(jié)點(diǎn)搜索完成BFS廣度優(yōu)先搜索過程ACDEGBFIH1234567896BFS的另一種應(yīng)用假設(shè)圖的每條邊的權(quán)值都是1，因?yàn)锽FS是分層進(jìn)行的，所以，從起點(diǎn)到達(dá)同一層點(diǎn)的路經(jīng)距離應(yīng)該是相同的，如果在圖中標(biāo)記一個(gè)起點(diǎn)和一個(gè)終點(diǎn)，從起點(diǎn)出發(fā)，用BFS逐層向終點(diǎn)靠近，那么當(dāng)?shù)竭_(dá)終點(diǎn)時(shí)，會(huì)形成一條路徑，那么這條路徑必定是這兩點(diǎn)的最短路經(jīng)。ACDEGBFIH123456789BFS的另一種應(yīng)用假設(shè)圖的每條邊的權(quán)值都是1，因?yàn)锽FS是分7BFS求最短路徑structnode{intx,y,d;};voidBFS(){ queue<node>q;//隊(duì)列

nodest={sx,sy,0};

q.push(st);//初始點(diǎn)入隊(duì)列 while(!q.empty())//隊(duì)列中還有要處理的點(diǎn)

{

從隊(duì)列中取出下一個(gè)處理的點(diǎn)p；

for(p的所有鄰接點(diǎn))

if(該鄰接點(diǎn)滿足搜索條件) {鄰接點(diǎn).d=p.d+1; if(該鄰接點(diǎn)是目標(biāo)點(diǎn)) returnp.d+1; q.push(鄰接點(diǎn));

標(biāo)記該鄰接點(diǎn)為已訪問； } }

}BFS求最短路徑structnode{intx,y,d;8BFS與隊(duì)列STL中隊(duì)列基本用法： 頭文件：

#include<queue>

基本函數(shù)： 建立隊(duì)列：queue<元素類型>隊(duì)列名;

向隊(duì)列中(末尾)添加元素：隊(duì)列名.push(元素名);

去掉隊(duì)列頭元素：隊(duì)列名.pop();

隊(duì)列頭元素：隊(duì)列名.front();

返回隊(duì)尾元素的引用：隊(duì)列名.back();

判斷是否為空：隊(duì)列名.empty();

隊(duì)列大?。宏?duì)列名.size();BFS與隊(duì)列STL中隊(duì)列基本用法：9FindTheMultiple

/JudgeOnline/problem?id=1426題意：給出一個(gè)整數(shù)n，(1<=n<=200)。求出任意一個(gè)它的倍數(shù)m，要求m必須只由十進(jìn)制的'0'或'1'組成。

SampleInput

26190

SampleOutput

10100100100100100100111111111111111111

FindTheMultiple

http://acm.10思路：化為bfs求最短路徑問題，關(guān)鍵有幾點(diǎn)：

1.懂得用模擬除法運(yùn)算的過程去做。

2.余數(shù)為m(1~n-1)的情況若出現(xiàn)多次，則第一次出現(xiàn)時(shí)所構(gòu)造路徑肯定比后面的情況短，根據(jù)鴿巢原理，對(duì)余數(shù)重復(fù)出現(xiàn)的情況進(jìn)行剪枝，否則會(huì)MemoryLimitExceeded，隊(duì)列的長度只限制在Max=200。

3.構(gòu)造答案的輸出過程有點(diǎn)費(fèi)心思，現(xiàn)在為止沒想到什么好方法，只能構(gòu)造出一顆二叉樹，找到最后的目標(biāo)節(jié)點(diǎn)后，再遞歸到根部進(jìn)行輸出。思路：化為bfs求最短路徑問題，關(guān)鍵有幾點(diǎn)：11這等同于構(gòu)造一顆二叉樹，然后按層次去遍歷這顆樹；11011100101110111………這等同于構(gòu)造一顆二叉樹，然后按層次去遍歷這顆樹；11011112#include<iostream>usingnamespacestd;intn;longlongq[9999999];intmain(){while(scanf("%d",&n)&&n){BFS();}return0;}#include<iostream>13voidBFS(){intfront,rear;front=rear=0;q[rear]=1;rear++;longlongtop;while(rear>front){top=q[front];if(top%n==0){break;}top*=10;q[rear++]=top;q[rear++]=top+1;front++;}printf("%lld\n",top);}voidBFS()14PrimePath

/JudgeOnline/problem?id=3126題意：從一個(gè)四位素?cái)?shù)到另一個(gè)四位素?cái)?shù)，每次變換一個(gè)數(shù)字，變換之后仍為素?cái)?shù)，最少的步驟。比如：1033

8179變換過程：1033

1733

3733

3739

3779

8779

8179最少步驟一共是6步。PrimePath

15SampleInput

3103381791373801710331033

SampleOutput

670

SampleInput16從起始素?cái)?shù)開始進(jìn)行廣搜，每輪將所有可行的改變（個(gè)位至千位，每個(gè)位置進(jìn)行一次改變）放入搜尋隊(duì)列一次進(jìn)行素?cái)?shù)判斷。用數(shù)組來記載轉(zhuǎn)變路徑，每個(gè)結(jié)點(diǎn)指向其父結(jié)點(diǎn)。達(dá)到綱標(biāo)之后向上尋找到先人，即可求出轉(zhuǎn)變了多少次。第九講-搜索之BFSppt課件17STL：queue#include<queue>

定義一個(gè)queue的變量

queue<Type>M

查看是否為空隊(duì)列

M.empty()

是的話返回1，不是返回0;

從已有元素后面增加元素

M.push()

輸出現(xiàn)有元素的個(gè)數(shù)

M.size()

顯示第一個(gè)元素

M.front()

顯示最后一個(gè)元素

M.back()

清除第一個(gè)元素

M.pop()

STL：queue#include<queue>

18#include

<iostream>

#include

<queue>

#include

<math.h>

using

namespace

std;

int

a,

b;

int

p[9999]

=

{

0

};

int

visited[9999]

=

{

0

};

bool

isprime(int

x)

{

for

(int

i

=

2;

i

<=

sqrt((double)

x);

++i)

{

if

(x

%

i

==

0)

return

false;

}

return

true;

}

#include

<iostream>

#include

<19int

BFS(int

s,

int

r)

{

queue<int>

q;

q.push(s);

p[s]

=

0;

visited[s]

=

1;

while

(!q.empty())

{

int

temp

=

q.front();

q.pop();

for

(int

i

=

0;

i

<=

9;

i++)

{

int

y1

=

(temp

/

10)

*

10

+

i;

if

(isprime(y1)

&&

!visited[y1])

{

q.push(y1);

p[y1]

=

p[temp]

+

1;

visited[y1]

=

1;

}

int

y2

=

temp

%

10

+

(temp

/

100)

*

100

+

i

*

10;

if

(isprime(y2)

&&

!visited[y2])

{

q.push(y2);

p[y2]

=

p[temp]

+

1;

visited[y2]

=

1;

}int

BFS(int

s,

int

r)

{

q20int

y3

=

temp

%

100

+

(temp

/

1000)

*

1000

+

100

*

i;

if

(isprime(y3)

&&

!visited[y3])

{

q.push(y3);

p[y3]

=

p[temp]

+

1;

visited[y3]

=

1;

}

if

(i

!=

0)

{

int

y4

=

temp

%

1000

+

i

*

1000;

if

(isprime(y4)

&&

!visited[y4])

{

q.push(y4);

p[y4]

=

p[temp]

+

1;

visited[y4]

=

1;

}

}

if

(visited[r])

return

p[r];

}}

return

0;}int

y3

=

temp

%

100

+

(temp

/

21int

main()

{

int

n;

scanf("%d",&n);

while

(n--)

{

memset(visited,0,sizeof(visited));

memset(p,0,sizeof(p));

scanf("%d%d",&a,&b);

printf("%d\n",

BFS(a,

b));

}

return

0;

}

int

main()

{

int

n;

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

abcdefgh12345678h8a1例1KnightMoves國際象棋棋盤上有一個(gè)馬，要從23跳馬規(guī)則

abcdefgh12345678在2×3的矩形里：跳馬規(guī)則abcdefgh24例如：從a1到e4當(dāng)目標(biāo)出現(xiàn)在所擴(kuò)展出的結(jié)點(diǎn)里，結(jié)果就找到了。Togetfroma1toe4takes3knightmoves.

abcdefgh1234567803321322312332233323333333233332例如：從a1到e4當(dāng)目標(biāo)出現(xiàn)在所擴(kuò)展出的結(jié)點(diǎn)里，結(jié)果就找到了25boolin(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;boolin(inta,intb)#include<26intmain(){ 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;}intmain()27雙向BFS

abcdefgh123456780212212122211112012從起點(diǎn)、終點(diǎn)同時(shí)開始雙向BFS,有效地提高了時(shí)空效率。從起點(diǎn)找2步能跳到的點(diǎn)從終點(diǎn)找1步能跳到的點(diǎn)雙向BFSabcdefg28例2Divisibility輸入N、K,然后輸入N個(gè)整數(shù)，N個(gè)整數(shù)可列出若干加減運(yùn)算式；若存在一個(gè)算式，它的值能被K整除,輸出“Divisible”，否則輸出“Notdivisible”.輸入：247

175-211545

175-2115輸出：Divisible

Notdivisible例2Divisibility輸入N、K,然后輸入N個(gè)整數(shù)，29{17，5，-21，15}1755-21-21-21-211515151515151515+++17+5+-21+15++++-------17-5+-21-15{17，5，-21，15}1755-21-21-21-21130最壞情況N=10000，二叉樹有10000層，結(jié)點(diǎn)總數(shù)210000-1。不可能枚舉所有表達(dá)式本題的目標(biāo)：判斷葉子結(jié)點(diǎn)上是否有值能被k

整除=>判斷是否有值，除以k的余數(shù)為零。計(jì)算中間值取余，不影響結(jié)果。

(a+b)%k=(a%k+b%k)%k因此只需記錄對(duì)k的余數(shù)。2<=k<=100，每層結(jié)點(diǎn)最多100個(gè)，不是指數(shù)級(jí)增加。最壞情況N=10000，二叉樹有10000層，結(jié)點(diǎn)總數(shù)2103147175-2115每層最多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