【数据结构与算法】搜索之BFS

简介:

1、目标

通过本文,希望可以达到以下目标,当遇到任意问题时,可以:

  1、很快建立状态空间;

  2、提出一个合理算法;

  3、简单估计时空性能;

2、搜索分类

2.1、盲目搜索

  按照预定的控制策略进行搜索,在搜索过程中获得的中间信息不用来改进控制策略;

  常见算法:

  1、广度优先搜索(Breadth First Search);

  2、深度优先搜索(Depth First Search);

  3、纯随机搜索、重复式搜索、迭代加深搜索、迭代加宽搜索、柱形搜索;

2.2、启发式搜索

  在搜索中加入了与问题有关的启发性信息,用以指导搜索朝着最有希望的方向发展,加速问题的求解过程并达到最优解。

  常见算法:

  1、A*算法;

  2、IDA*算法;

3、状态空间

状态

  问题在某一时刻进展状况的数学描述;

状态转移

问题从一种状态转移到另一种或几种状态的操作;

状态空间

一个“图”,图结点对应于状态,点之间的边对应于状态转移;

搜索

寻找一种可行的操作序列,从起始状态经过一系列状态转移,达到目标状态;

4、过河问题

某人带一条狗、一只鸡、一筐米过河,但小船除了需要人划动外,最多可以带一个物品,而人不在场时,狗要吃鸡,鸡要吃米。问此人应该如何过河?

4.1、问题分析

状态:建立四元组(人,狗,鸡,米)。0表示在左岸,1表示在右岸。

起始状态:(0,0,0,0)

终止状态:(1,1,1,1)

状态转移规则(操作,用1-x来表示过一次河,无论是到左岸还是到右岸都可以):

(a,b,c,d)

  →(1-a,1-b,c,d)(当a=b)【人带狗过河】

  →(1-a,b,1-c,d)(当a=c)【人带鸡过河】

  →(1-a,b,c,1-d)(当a=d)【人带米过河】

  →(1-a,b,c,d)                 【人自己过河】

约束条件:

(a,b,c,d)中,a≠b时b≠c,a≠c时c≠d

4.2、直观的搜索过程

首先从初始状态开始:

然后再对两个可能状态进行进一步搜索:

搜索在“图”中进行,但是图不需要事先建立(“隐式图”);

搜索过程就是对图的遍历过程,可以得到一课“搜索树”;

搜索树的结点个数、分支数、深度,决定着搜索的效率;

存储和算法

  普通状态可以用4个整数表示;

  压缩状态可以用4个bit表示;

  用BFS或DFS;

5、BFS基本结构

BFS搜索过程没有回溯,是一种牺牲空间换取时间的方法。时间复杂度:O(V+E)

复制代码
1 定义一个队列;
2 起始点加入队列;
3 while(队列不空){
4     取出队头结点;
5     若它是所求的目标状态,跳出循环;
6     否则,从它扩展出子节点,全都添加到队尾;
7 }
8 若循环中找到目标,输出结果;
9 否则输出无解;
复制代码

6、BFS例题

6.1 HDOJ1242 Rescue

Description:

Angel was caught by the MOLIGPY! He was put in prison by Moligpy. The prison is described as a N * M (N, M <= 200) matrix. There are WALLs, ROADs, and GUARDs in the prison.
Angel's friends want to save Angel. Their task is: approach Angel. We assume that "approach Angel" is to get to the position where Angel stays. When there's a guard in the grid, we must kill him (or her?) to move into the grid. We assume that we moving up, down, right, left takes us 1 unit time, and killing a guard takes 1 unit time, too. And we are strong enough to kill all the guards.
You have to calculate the minimal time to approach Angel. (We can move only UP, DOWN, LEFT and RIGHT, to the neighbor grid within bound, of course.)

Input:

First line contains two integers stand for N and M.
Then N lines follows, every line has M characters. "." stands for road, "a" stands for Angel, and "r" stands for each of Angel's friend. 
Process to the end of the file.

Output:

For each test case, your program should output a single integer, standing for the minimal time needed. If such a number does no exist, you should output a line containing "Poor ANGEL has to stay in the prison all his life."

Sample Input:

复制代码
1 7 8
2 #.#####.
3 #.a#..r.
4 #..#x...
5 ..#..#.#
6 #...##..
7 .#......
8 ........
复制代码

Sample Output:

1 13

Code 1:

复制代码
  1 //这是一个比较标准的bfs,没有经过任何优化,但是思路比较清晰,容易看懂。
  2 #include <iostream>
  3 #include <cstdio>
  4 #include <queue>
  5 using namespace std;
  6 //node结构体
  7 typedef struct  
  8 {
  9     int x;
 10     int y;
 11     int len;
 12 }node;
 13 //全局变量定义
 14 #define M 202
 15 char Map[M][M];//地图
 16 int mask[M][M];//访问标志
 17 queue<node> q;//队列,只在bfs中用到
 18 int bx,by,ex,ey,w,h;//起点、终点、宽、高
 19 int step[4][2] = {//四个方向
 20     //0-up
 21     0,-1,
 22     //1-right
 23     1,0,
 24     //2-down
 25     0,1,
 26     //3-left
 27     -1,0
 28 };
 29 
 30 void readMap(int m,int n);//读取地图
 31 void bfs();//bfs
 32 int tryXY(int x,int y);//尝试x、y点
 33 
 34 void main()
 35 {
 36     while (scanf("%d %d",&h,&w)==2)
 37     {
 38         readMap(h,w);
 39         bfs();
 40         cout<<mask[ex][ey]<<endl;
 41     }
 42 }
 43 
 44 void readMap(int m,int n)//m-h,n-w
 45 {
 46     int i,j;
 47     for (i=0;i<m;i++)
 48     {
 49         for (j=0;j<n;j++)
 50         {
 51             cin>>Map[i][j];
 52             mask[i][j] = -1;//标志为未访问
 53             if (Map[i][j] == 'r')
 54             {//friend为起点,且化为road
 55                 Map[i][j] = '.';
 56                 bx = i;    by = j;
 57             }
 58             if (Map[i][j] == 'a')
 59             {//angel为终点,且化为road
 60                 Map[i][j] = '.';
 61                 ex = i;    ey = j;
 62             }
 63         }
 64     }
 65 }
 66 
 67 void bfs()
 68 {
 69     node n,m;//m为队头,n为m衍生的测试点
 70     int i,ret;
 71     //起点
 72     m.x = bx;
 73     m.y = by;
 74     m.len = 0;//len
 75     mask[bx][by] = 0;//ask
 76     q.push(m);//push
 77     //处理
 78     while (q.size())
 79     {
 80         //get front
 81         m = q.front();
 82         q.pop();
 83         //test node m
 84         for (i=0 ; i<4 ; i++)
 85         {
 86             n.x = m.x+step[i][0]; n.y = m.y+step[i][1];    n.len = m.len+1;
 87             ret = tryXY(n.x,n.y);
 88             switch(ret)
 89             {
 90             case -1://
 91                 break;
 92             case 0:
 93             case 1:
 94                 n.len += ret;
 95                 //如果未访问,保存花销;如果已经访问,保存花销最少。
 96                 if (mask[n.x][n.y] == -1 || n.len<mask[n.x][n.y])
 97                 {
 98                     mask[n.x][n.y] = n.len;//已经访问且保存的是最小花销
 99                     q.push(n);
100                 }
101                 break;
102             }
103         }
104 
105     }
106 }
107 int tryXY(int x,int y)
108 {
109     int ret;
110     //越界或遇到墙
111     if (!(x>=0 && x<w && y>=0 && y<h) || (Map[x][y] == '#'))
112         ret = -1;
113     //road or angel
114     if (Map[x][y] == '.')
115         ret = 0;
116     //guard
117     if (Map[x][y] == 'x')
118         ret = 1;
119     return ret;
120 }
复制代码

然而这个代码还有一些不足~~

1、82行代码之后应该判断是否到了目标点,达到目标则return,此时就是花销最少的路径,而不需要全部遍历结束

2、96行的代码中“<”判断是多余的,因为如果之前已经访问过了,那么现在的一定比之前的路径长;

Code 2:

复制代码
  1 #include<iostream>
  2 #include<cstdio>
  3 #include<queue>
  4 using namespace std;
  5 
  6 //定义结点结构体
  7 typedef struct{
  8     int x;
  9     int y;
 10     int len;
 11 }node;
 12 //定义全局变量
 13 #define M 202
 14 char Map[M][M];     //地图
 15 int visited[M][M];     //地图访问标识
 16 queue<node> q;      //队列,在bfs中用到
 17 int bx,by,ex,ey,w,h;//起点、终点、地图宽、地图高
 18 int step[4][2] = {
 19     0,-1,   //move up
 20     1,0,    //move right
 21     0,1,    //move down
 22     -1,0    //move left
 23 };
 24 
 25 void readMap(int m,int n);  //读取地图
 26 void bfs();                 //bfs搜索路径
 27 int costXY(int x,int y);     //尝试x,y是否可行
 28 
 29 void main(){
 30     while(scanf("%d %d",&w,&h) == 2){
 31         readMap(w,h);
 32         bfs();
 33         if(visited[ex][ey]!=-1){
 34             cout<<visited[ex][ey]<<endl;
 35         }else{
 36             cout<<"Poor ANGEL has to stay in the prison all his life."<<endl;
 37         }
 38     }
 39 }
 40 void readMap(int m,int n){
 41     int i,j;
 42     for(i=0;i<m;i++){
 43         for(j=0;j<n;j++){
 44             cin>>Map[i][j];
 45             visited[i][j] = -1;//-1表示未访问
 46             if(Map[i][j] == 'r'){//store the start point
 47                 Map[i][j] = '.';
 48                 bx = i;
 49                 by = j;
 50             }
 51             if(Map[i][j] == 'a'){//store the end point
 52                 Map[i][j] = '.';
 53                 ex = i;
 54                 ey = j;
 55             }
 56         }
 57     }
 58 }
 59 
 60 void bfs(){
 61     node n,m;//m is queue head, n is a copied m for test;
 62     int ret;
 63     //save start point into the queue
 64     m.x = bx;
 65     m.y = by;
 66     m.len = 0;
 67     visited[bx][by] = 0;
 68     q.push(m);
 69     //bfs
 70     while(q.size()){
 71         //get the head point
 72         m = q.front();
 73         q.pop();
 74         //if arrive end point return
 75         if(m.x == ex && m.y == ey){
 76             visited[ex][ey] = m.len;
 77             return ;
 78         }
 79         //test node m
 80         for(int i=0;i<4;i++){
 81             n.x = m.x + step[i][0];
 82             n.y = m.y + step[i][1];
 83             n.len = m.len + 1;
 84             ret = costXY(n.x,n.y);
 85             switch(ret){
 86             case -1:
 87                 break;
 88             case 0:
 89             case 1:
 90                 n.len += ret;
 91                 //if first time visit, save the cost
 92                 //if has been visited, save the minimum cost
 93                 if(visited[n.x][n.y] == -1){
 94                     visited[n.x][n.y] = n.len;
 95                     q.push(n);
 96                 }
 97                 break;
 98             }
 99         }
100     }
101 }
102 
103 int costXY(int x,int y){
104     int ret;
105     //out of map or a wall
106     if(!(x>=0 && x<=w && y>=0 && y<=h) || Map[x][y] == '#'){
107         ret = -1;
108     }
109     //road or angel
110     if(Map[x][y] == '.'){
111         ret = 0;
112     }
113     //guard, need one more unit time
114     if(Map[x][y] == 'x'){
115         ret = 1;
116     }
117     return ret;
118 }
复制代码

 

6.2 HDOJ1372 Knight Moves

Description:

A friend of you is doing research on the Traveling Knight Problem (TKP) where you are to find the shortest closed tour of knight moves that visits each square of a given set of n squares on a chessboard exactly once. He thinks that the most difficult part of the problem is determining the smallest number of knight moves between two given squares and that, once you have accomplished this, finding the tour would be easy.
Of course you know that it is vice versa. So you offer him to write a program that solves the "difficult" part. 
Your job is to write a program that takes two squares a and b as input and then determines the number of knight moves on a shortest route from a to b.

Input:

The input file will contain one or more test cases. Each test case consists of one line containing two squares separated by one space. A square is a string consisting of a letter (a-h) representing the column and a digit (1-8) representing the row on the chessboard.

Output:

For each test case, print one line saying "To get from xx to yy takes n knight moves.".

Sample Input:

复制代码
1 e2 e4
2 a1 b2
3 b2 c3
4 a1 h8
5 a1 h7
6 h8 a1
7 b1 c3
8 f6 f6
复制代码

Sample Output:

复制代码
1 To get from e2 to e4 takes 2 knight moves.
2 To get from a1 to b2 takes 4 knight moves.
3 To get from b2 to c3 takes 2 knight moves.
4 To get from a1 to h8 takes 6 knight moves.
5 To get from a1 to h7 takes 5 knight moves.
6 To get from h8 to a1 takes 6 knight moves.
7 To get from b1 to c3 takes 1 knight moves.
8 To get from f6 to f6 takes 0 knight moves.
复制代码

Code:

复制代码
 1 #include<iostream>
 2 #include<cstdio>
 3 #include<queue>
 4 using namespace std;
 5 
 6 //定义node结构体
 7 typedef struct{
 8     int x,y,len;
 9 }node;
10 //八个方向
11 int step[8][2] = {
12     -2,-1,  //left2-up1
13     -1,-2,  //left1-up2
14     1,-2,   //right1-up2
15     2,-1,   //right2-up1
16     2,1,    //right2-down1
17     1,2,    //right2-down2
18     -1,2,   //left1-down2
19     -2,1   //left2-down1
20 };
21 #define M 10
22 int Map[M][M];//chessboard
23 int bx,by,ex,ey;//begin point,end point
24 char a[3],b[3];
25 
26 void bfs(int x,int y);
27 
28 void main(){
29     while(scanf("%s%s",a,b)!=EOF){
30         bx = a[0]-'a'+1;    //the range of index is from 1 to 8
31         by = a[1]-'0';      //the range of index is from 1 to 8
32         ex = b[0]-'a'+1;    //the range of index is from 1 to 8
33         ey = b[1]-'0';      //the range of index is from 1 to 8
34         bfs(bx,by);
35     }
36     return 0;
37 }
38 
39 void bfs(int x,int y){
40     node t,p;
41     queue<node> q;
42     //BFS Step1:push first node t into queue q
43     t.x = x;
44     t.y = y;
45     t.len = 0;
46     q.push(t);
47     //while(!q.empty())
48     while(q.size()){
49         //BFS Step2:get the head of queue
50         t = q.front();
51         q.pop();
52         //BFS Step3:arrive the end point,return. first time arriving is the minimum.
53         if(t.x == ex && t.y == ey){
54             printf("To get from %s to %s takes %d knight moves.\n",a,b,t.num);
55             return;
56         }
57         //BFS Step4:push the next steps into queue q
58         for(int i=0;i<8;i++){
59             node next;
60             next.x = t.x + step[i][0];
61             next.y = t.y + step[i][1];
62             //no out of range and not been visited
63             if(!(next.x>0 && next.x<9 && next.y>0 && next.y<9) && !Map[next.x][next.y]){
64                 next.len = t.len+1;
65                 q.push(next);
66             }
67         }
68     }
69 }
复制代码

 


本文转自ZH奶酪博客园博客,原文链接:http://www.cnblogs.com/CheeseZH/p/4550602.html,如需转载请自行联系原作者

相关文章
|
1月前
|
算法
【算法】二分算法——搜索插入位置
【算法】二分算法——搜索插入位置
|
3月前
|
存储 机器学习/深度学习 算法
第十五届蓝桥杯pb组国赛E题[马与象] (15分)BFS算法 详解
第十五届蓝桥杯pb组国赛E题[马与象] (15分)BFS算法 详解
34 3
|
30天前
|
存储 算法
BFS算法的实现
BFS算法的实现
26 1
|
1月前
|
机器学习/深度学习 算法 文件存储
【博士每天一篇文献-算法】 PNN网络启发的神经网络结构搜索算法Progressive neural architecture search
本文提出了一种名为渐进式神经架构搜索(Progressive Neural Architecture Search, PNAS)的方法,它使用顺序模型优化策略和替代模型来逐步搜索并优化卷积神经网络结构,从而提高了搜索效率并减少了训练成本。
34 9
|
1月前
|
算法
【算法】递归、搜索与回溯——汉诺塔
【算法】递归、搜索与回溯——汉诺塔
|
1月前
|
存储 算法 调度
基于和声搜索算法(Harmony Search,HS)的机器设备工作最优调度方案求解matlab仿真
通过和声搜索算法(HS)实现多机器并行工作调度,以最小化任务完成时间。在MATLAB2022a环境下,不仅输出了工作调度甘特图,还展示了算法适应度值的收敛曲线。HS算法模拟音乐家即兴创作过程,随机生成初始解(和声库),并通过选择、微调生成新解,不断迭代直至获得最优调度方案。参数包括和声库大小、记忆考虑率、音调微调率及带宽。编码策略将任务与设备分配映射为和声,目标是最小化完成时间,同时确保满足各种约束条件。
|
2月前
|
数据采集 算法 JavaScript
揭开JavaScript字符串搜索的秘密:indexOf、includes与KMP算法
JavaScript字符串搜索涵盖`indexOf`、`includes`及KMP算法。`indexOf`返回子字符串位置,`includes`检查是否包含子字符串。KMP是高效的搜索算法,尤其适合长模式匹配。示例展示了如何在数据采集(如网页爬虫)中使用这些方法,结合代理IP进行安全搜索。代码示例中,搜索百度新闻结果并检测是否含有特定字符串。学习这些技术能提升编程效率和性能。
揭开JavaScript字符串搜索的秘密:indexOf、includes与KMP算法
|
1月前
|
算法
【算法】递归、搜索与回溯——简介
【算法】递归、搜索与回溯——简介
|
2月前
|
大数据 UED 开发者
实战演练:利用Python的Trie树优化搜索算法,性能飙升不是梦!
【7月更文挑战第19天】Trie树,又称前缀树,是优化字符串搜索的高效数据结构。通过利用公共前缀,Trie树能快速插入、删除和查找字符串。
69 2
|
2月前
|
算法 Python
逆袭之路!用 Python 玩转图的 DFS 与 BFS,让数据结构难题无处遁形
【7月更文挑战第12天】图的遍历利器:DFS 和 BFS。Python 中,图可表示为邻接表或矩阵。DFS 沿路径深入,回溯时遍历所有可达顶点,适合找路径和环。BFS 层次遍历,先近后远,解决最短路径问题。两者在迷宫、网络路由等场景各显神通。通过练习,掌握这些算法,图处理将游刃有余。
46 3