第九講-搜索之BFS課件

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

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

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

{

從隊列中取出下一個處理的點p；

for(p的所有鄰接點)

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

標記該鄰接點為已訪問； } }

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

nodest={sx,sy,0};

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

{

從隊列中取出下一個處理的點p；

for(p的所有鄰接點)

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

標記該鄰接點為已訪問； } }

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

#include<queue>

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

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

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

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

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

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

隊列大?。宏犃忻?size();BFS與隊列STL中隊列基本用法：9FindTheMultiple

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

SampleInput

26190

SampleOutput

10100100100100100100111111111111111111

FindTheMultiple

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

1.懂得用模擬除法運算的過程去做。

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

3.構(gòu)造答案的輸出過程有點費心思，現(xiàn)在為止沒想到什么好方法，只能構(gòu)造出一顆二叉樹，找到最后的目標節(jié)點后，再遞歸到根部進行輸出。思路：化為bfs求最短路徑問題，關(guā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題意：從一個四位素數(shù)到另一個四位素數(shù)，每次變換一個數(shù)字，變換之后仍為素數(shù)，最少的步驟。比如：1033

8179變換過程：1033

1733

3733

3739

3779

8779

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

15SampleInput

3103381791373801710331033

SampleOutput

670

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

定義一個queue的變量

queue<Type>M

查看是否為空隊列

M.empty()

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

從已有元素后面增加元素

M.push()

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

M.size()

顯示第一個元素

M.front()

顯示最后一個元素

M.back()

清除第一個元素

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國際象棋棋盤上有一個馬，要從起點跳到指定目標，最少跳幾步？輸入：a1h8輸出：Togetfroma1toh8takes6knightmoves.

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

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

abcdefgh1234567803321322312332233323333333233332例如：從a1到e4當(dāng)目標出現(xiàn)在所擴展出的結(jié)點里，結(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從起點、終點同時開始雙向BFS,有效地提高了時空效率。從起點找2步能跳到的點從終點找1步能跳到的點雙向BFSabcdefg28例2Divisibility輸入N、K,然后輸入N個整數(shù)，N個整數(shù)可列出若干加減運算式；若存在一個算式，它的值能被K整除,輸出“Divisible”，否則輸出“Notdivisible”.輸入：247

175-211545

175-2115輸出：Divisible

Notdivisible例2Divisibility輸入N、K,然后輸入N個整數(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é)點總數(shù)210000-1。不可能枚舉所有表達式本題的目標：判斷葉子結(jié)點上是否有值能被k

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

(a+b)%k=(a%k+b%k)%k因此只需記錄對k的余數(shù)。2<=k<=100，每層結(jié)點最多100個，不是指數(shù)級增加。最壞情況N=10000，二叉樹有10000層，結(jié)點總數(shù)2103147175-2115每層最多7個結(jié)點(定義數(shù)組)：首先加入起點，17%7=3擴展第2層結(jié)點(3+5)%7=1(3–5+7)%7=51234560+-擴展第3層結(jié)點(1+-21)%7