第九讲-搜索之BFS课件

搜索之BFS广度优先搜索搜索之BFS广度优先搜索1广度优先搜索基本思想：

从初始状态S开始，利用规则，生成所有可能的状态。构成树的下一层节点，检查是否出现目标状态G，若未出现，就对该层所有状态节点，分别顺序利用规则。生成再下一层的所有状态节点，对这一层的所有状态节点检查是否出现G，若未出现，继续按上面思想生成再下一层的所有状态节点，这样一层一层往下展开。直到出现目标状态为止。广度优先搜索基本思想：2BFS算法（1）把起始节点S线放到OPEN表中（2）如果OPEN是空表，则失败退出，否则继续。（3）在OPEN表中取最前面的节点node移到CLOSED表中。（4）扩展node节点。若没有后继（即叶节点），则转向（2）循环。（5）把node的所有后继节点放在OPEN表的末端。各后继结点指针指向node节点。（6）若后继节点中某一个是目标节点，则找到一个解，成功退出。否则转向（2）循环。BFS算法（1）把起始节点S线放到OPEN表中3BFS–广度优先搜索BFS在访问了起始顶点A之后,由A出发,依次访问A的各个未被访问过的邻接顶点B,D,…,C,然后再顺序访问B,D,…,C的所有还未被访问过的邻接顶点。再从这些访问过的顶点出发，再访问它们的所有还未被访问过的邻接顶点，…如此做下去，直到图中所有顶点都被访问到为止。广度优先搜索是一种分层的搜索过程,每向前走一步可能访问一批顶点。ACDEGBFIH123456789BFS–广度优先搜索BFS在访问了起始顶点A之后,4BFS的代码分析voidBFS(){ queue<point>q;//队列

q.push(st);//初始点入队列 while(!q.empty())//队列中还有要处理的点

{

从队列中取出下一个处理的点p；

for(p的所有邻接点)

if(该邻接点满足搜索条件) { q.push(邻接点);

标记该邻接点为已访问； } }

}BFS的代码分析voidBFS()5BFS广度优先搜索过程ACDEGBFIH123456789FEDCABGHI队列变化情况指针箭头表示当前访问节点搜索完成BFS广度优先搜索过程ACDEGBFIH1234567896BFS的另一种应用假设图的每条边的权值都是1，因为BFS是分层进行的，所以，从起点到达同一层点的路经距离应该是相同的，如果在图中标记一个起点和一个终点，从起点出发，用BFS逐层向终点靠近，那么当到达终点时，会形成一条路径，那么这条路径必定是这两点的最短路经。ACDEGBFIH123456789BFS的另一种应用假设图的每条边的权值都是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>

基本函数： 建立队列：queue<元素类型>队列名;

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

去掉队列头元素：队列名.pop();

队列头元素：队列名.front();

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

判断是否为空：队列名.empty();

队列大小：队列名.size();BFS与队列STL中队列基本用法：9FindTheMultiple

/JudgeOnline/problem?id=1426题意：给出一个整数n，(1<=n<=200)。求出任意一个它的倍数m，要求m必须只由十进制的'0'或'1'组成。

SampleInput

26190

SampleOutput

10100100100100100100111111111111111111

FindTheMultiple

http://acm.10思路：化为bfs求最短路径问题，关键有几点：

1.懂得用模拟除法运算的过程去做。

2.余数为m(1~n-1)的情况若出现多次，则第一次出现时所构造路径肯定比后面的情况短，根据鸽巢原理，对余数重复出现的情况进行剪枝，否则会MemoryLimitExceeded，队列的长度只限制在Max=200。

3.构造答案的输出过程有点费心思，现在为止没想到什么好方法，只能构造出一颗二叉树，找到最后的目标节点后，再递归到根部进行输出。思路：化为bfs求最短路径问题，关键有几点：11这等同于构造一颗二叉树，然后按层次去遍历这颗树；11011100101110111………这等同于构造一颗二叉树，然后按层次去遍历这颗树；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题意：从一个四位素数到另一个四位素数，每次变换一个数字，变换之后仍为素数，最少的步骤。比如：1033

8179变换过程：1033

1733

3733

3739

3779

8779

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

15SampleInput

3103381791373801710331033

SampleOutput

670

SampleInput16从起始素数开始进行广搜，每轮将所有可行的改变（个位至千位，每个位置进行一次改变）放入搜寻队列一次进行素数判断。用数组来记载转变路径，每个结点指向其父结点。达到纲标之后向上寻找到先人，即可求出转变了多少次。第九讲-搜索之BFSppt课件17STL：queue#include<queue>

定义一个queue的变量

queue<Type>M

查看是否为空队列

M.empty()

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

从已有元素后面增加元素

M.push()

输出现有元素的个数

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跳马规则

abcdefgh12345678在2×3的矩形里：跳马规则abcdefgh24例如：从a1到e4当目标出现在所扩展出的结点里，结果就找到了。Togetfroma1toe4takes3knightmoves.

abcdefgh1234567803321322312332233323333333233332例如：从a1到e4当目标出现在所扩展出的结点里，结果就找到了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个整数，N个整数可列出若干加减运算式；若存在一个算式，它的值能被K整除,输出“Divisible”，否则输出“Notdivisible”.输入：247

175-211545

175-2115输出：Divisible

Notdivisible例2Divisibility输入N、K,然后输入N个整数，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层，结点总数210000-1。不可能枚举所有表达式本题的目标：判断叶子结点上是否有值能被k

整除=>判断是否有值，除以k的余数为零。计算中间值取余，不影响结果。

(a+b)%k=(a%k+b%k)%k因此只需记录对k的余数。2<=k<=100，每层结点最多100个，不是指数级增加。最坏情况N=10000，二叉树有10000层，结点总数2103147175-2115每层最多7个结点(定义数组)：首先加入起点，17%7=3扩展第2层结点(3+5)%7=1(3–5+7)%7=51234560+-扩展第3层结点(1+-21)%7