搜索算法---广度优先搜索
2021/6/17 1:23:42
本文主要是介绍搜索算法---广度优先搜索,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
一、通过迷宫问题总结广度优先搜索算法
假设有一个迷宫,用二维矩阵表示,矩阵中标记为0的地方表示可以通过,标记为1的地方表示有障碍物不能通过。现在给定迷宫大小为10*10,入口位置在(1,1)位置出口在(8,10)位置,判断从入口进来,是否可以走出迷宫,每次可以任意方向走。
尝试深度优先搜索是否可以解决:
- 从入口进来,朝着一个方向走到尽头。
- 如果没有找到出口,则折返换一个方向继续。
- 直到找到出口或者所有方向都尝试完也没找到出口结束。
#include<iostream> #include<vector> #include<stdlib.h> #include<time.h> using namespace std; struct Node { int x; int y; }; void DepthFirstSearch(vector<vector<int>>& maze,int sr,int sc,vector<struct Node>& ret) { //终止条件:位置非法;有障碍物;已经走出 if (sr < 0 || sr >= 10 || sc < 0 || sc >= 10) { //ret.pop_back(); return; } if (maze[sr][sc] != 0) { //ret.pop_back(); return; } if (sr == 8 && sc == 9) { struct Node newNode = {8,9}; ret.push_back(newNode); return; } //没有找到出口且还可以继续走,则将该位置存入ret,继续往四个方向走 struct Node newNode = { sr,sc }; ret.push_back(newNode); //将该位置标记为-1,表示已经走过 maze[sr][sc] = -1; DepthFirstSearch(maze,sr,sc-1,ret); DepthFirstSearch(maze, sr, sc + 1, ret); DepthFirstSearch(maze, sr-1, sc, ret); DepthFirstSearch(maze, sr+1, sc, ret); //某一个位置四个方向走完都没有出去,则折返 int x = ret.back().x; int y = ret.back().y; if (x == sr && y == sc) ret.pop_back(); } int main() { //随机数种子 srand((unsigned)time(NULL)); //给定迷宫 vector<vector<int>> maze(10,vector<int>(10,0)); //第一行最后一行全为1,第一列和最后一列有一个出口和入口 for (int i = 0; i < 10; i++) { for (int j = 0; j < 10; j++) { if (i == 0 || i == 9 || j == 0 || j == 9) maze[i][j] = 1; else { //生成一个随机数,这个随机数要么是0要么是1 maze[i][j] = rand()%2; } } } //入口(1,0)出口(8,9) maze[1][0] = maze[8][9] = 0; /*maze = { {1,1,1,1,1,1,1,1,1,1}, {0,0,0,1,0,0,1,1,1,1}, {1,1,0,0,0,0,0,0,0,1}, {1,0,1,0,1,1,1,1,0,1}, {1,1,0,0,0,0,0,1,1,1}, {1,0,1,0,0,0,1,1,0,1}, {1,1,0,0,1,1,0,1,0,1}, {1,0,0,1,0,0,0,1,0,1}, {1,0,0,0,0,0,0,0,0,0}, { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 } };*/ //打印迷宫 for (int i = 0; i < 10; i++) { for (int j = 0; j < 10; j++) { cout << maze[i][j] << " "; } cout << endl; } //深度优先搜索打印出路径 vector<struct Node> path; DepthFirstSearch(maze,1,0,path); //打印路径 if (path.empty()) cout << "没有能够出去的路径" << endl; for (auto e : path) { cout << '(' << e.x << ',' << e.y << ')' << " "; } cout << endl; return 0; }
广度优先该如何解决这个问题呢?
- 深度优先搜索是指一条路走到黑,没有成功找另一条路,成功直接返回。
- 广度优先搜索,顾名思义先判断该节点的四个方向,如果有一个是出口,则找到了。
- 否则,在从这四个方向分别出发,判断它们的四个方向是否有出口
#include<iostream> #include<vector> #include<stdlib.h> #include<time.h> using namespace std; struct Node { int x; int y; }; int BreadthFirstSearch(vector<vector<int>>& maze,int sr,int sc,int dr,int dc,vector<struct Node>& path) { //入口(sr,sc)出口(dr,dc) //注意:maze中1表示障碍物,-1表示该位置已经走过了,0表示该位置可以走 //思路:从当前路径带出四个方向,四个方向在依次带出各自的四个方向 //初始化path struct Node newNode = {sr,sc}; path.push_back(newNode); maze[sr][sc] = -1; //标记是否为出口 int flag = 0; //四个行走的方向,上下左右 int next[4][2] = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } }; //标记起始和结束位置,注意的是每有一个位置入数组,tail++ int head = 0; int tail = 1; while (head < tail) { //从head带出它的四个方向 for (int i = 0; i < 4; i++) { //新位置的坐标 int nx = path[head].x + next[i][0]; int ny = path[head].y + next[i][1]; //新位置非法,继续下一个方向 if (nx < 0 || nx >= 10 || ny < 0 || ny >= 10) continue; //如果该位置没被走过 if (maze[nx][ny] == 0) { newNode = {nx,ny}; path.push_back(newNode); maze[nx][ny] = -1; tail++; } //新位置为出口,结束 if (nx == dr && ny == dc) { flag = 1; break; } } if (flag) break; head++; } return flag; } int main() { //随机数种子 srand((unsigned)time(NULL)); //给定迷宫 vector<vector<int>> maze(10, vector<int>(10, 0)); //第一行最后一行全为1,第一列和最后一列有一个出口和入口 //for (int i = 0; i < 10; i++) //{ // for (int j = 0; j < 10; j++) // { // if (i == 0 || i == 9 || j == 0 || j == 9) // maze[i][j] = 1; // else // { // //生成一个随机数,这个随机数要么是0要么是1 // maze[i][j] = rand() % 2; // } // } //} 入口(1,0)出口(8,9) //maze[1][0] = maze[8][9] = 0; maze = { {1,1,1,1,1,1,1,1,1,1}, {0,0,0,1,0,0,1,1,1,1}, {1,1,0,0,0,0,0,0,0,1}, {1,0,1,0,1,1,1,1,0,1}, {1,1,0,0,0,0,0,1,1,1}, {1,0,1,0,0,0,1,1,0,1}, {1,1,0,0,1,1,0,1,0,1}, {1,0,0,1,0,0,0,1,0,1}, {1,0,0,0,0,0,0,0,0,0}, { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 } }; //打印迷宫 for (int i = 0; i < 10; i++) { for (int j = 0; j < 10; j++) { cout << maze[i][j] << " "; } cout << endl; } //深度优先搜索打印出路径 vector<struct Node> path; if (BreadthFirstSearch(maze, 1, 0, 8, 9, path)) cout << "找到了" << endl; else cout << "没找到" << endl; return 0; }
观察上面两种方法,它们有什么区别?
1、广度优先搜索的一般过程
Bfs() { 1. 建立起始步骤,队列初始化 2. 遍历队列中的每一种可能,whlie(队列不为空) { 通过队头元素带出下一步的所有可能,并且依次入队 { 判断当前情况是否达成目标:按照目标要求处理逻辑 } 继续遍历队列中的剩余情况 } }
2、广度优先搜索的特点
- 通过上面一个题,可以看出深度优先搜索是在探寻一跳路径
- 广度优先搜索是找到所有路径
- 因此,广度优先搜索一定可以寻找最优解。而深度优先搜索找到的不一定是最优解。
- 广度优先搜索一般使用循环+队列进行搜索
二、例题分析
1、员工的重要性
思路:将一个员工的所有直系下属的重要性之和计算完,在计算它们的下属的下属。即,定义一个队里用广度优先搜索的思路进行计算,首先将id元素找到并入队,队头元素出队前先将其直系下属带入队列。
class Solution { public: int _getImportance(vector<Employee*>& employees,int id) { //定义并初始化队列 queue<Employee*> qu; //找到id员工在数组中的下标,保存到队列中 int index = 0; for(int i = 0;i < employees.size();i++) { if(employees[i]->id == id) { qu.push(employees[i]); break; } } //遍历队列,每一个队头节点将自己的直系下属带入队列在,直到队列为空 int sumImportance = qu.front()->importance; while(!qu.empty()) { //如果队头节点有直系下属 //计算队头元素的直系下属的重要性之和 for(int i = 0;i < qu.front()->subordinates.size();i++) { int subId = qu.front()->subordinates[i]; //在employees中找到该员工并保存到队列中 for(int j = 0;j < employees.size();j++) { if(employees[j]->id == subId) { sumImportance += employees[j]->importance; qu.push(employees[j]); break; } } } //队头节点将其所有直系下属节点带入队列后,队头节点出队 qu.pop(); } return sumImportance; } int getImportance(vector<Employee*> employees, int id) { //|广度优先搜索 return _getImportance(employees,id); } };
2、N叉树的层序遍历
思路:层序遍历,需要注意的是这里要求一层一层的输出。因此,层序遍历时还要记录当前层节点的个数和下一层的节点个数。
class Solution { public: void _levelOrder(vector<vector<int>>& ret,Node* root) { //定义队列并初始化 queue<Node*> qu; qu.push(root); //记录当前层和下一层的节点个数 int cur = 1;//第一层,只有一个节点 int next = 0;//下一层,初始化为0 vector<int> tmp; //遍历队列,用队列的头结点将其所有孩子节点带入队列 while(!qu.empty()) { if(qu.front() != nullptr) { if(cur == 0) { //当前层遍历完了,遍历下一层 cur = next; next = 0; ret.push_back(tmp); tmp.resize(0); } //带入孩子节点 for(int i = 0;i < qu.front()->children.size();i++) { qu.push(qu.front()->children[i]); next++; } //所有孩子节点带入后,出队 tmp.push_back(qu.front()->val); } qu.pop(); cur--; } ret.push_back(tmp); } vector<vector<int>> levelOrder(Node* root) { //广度优先搜索 vector<vector<int>> ret; if(root == nullptr) return ret; _levelOrder(ret,root); return ret; } };
3、腐烂的橘子
这个题需要注意的是,刚开始可能就有多个橘子腐烂,所以开始时队列中可能会有多个节点。同时,每个节点带入的新节点的num应该是在该节点的基础上+1的。还有一点就是,如果没有橘子输出的结果是0.
public: struct Node { int x; int y; int num; }; int _orangesRotting(vector<vector<int>>&grid) { int ret = 0; //定义并初始化队列 queue<Node> qu; //找出所有腐烂的橘子加入队列中 for(int i = 0;i < grid.size();i++) { for(int j = 0;j < grid[0].size();j++) { if(grid[i][j] == 2) { Node newNode = {i,j,0}; qu.push(newNode); } } } //四个方向 int direction[4][2] = {{-1,0},{1,0},{0,-1},{0,1}}; while(!qu.empty()) { //带入四个方向 for(int i = 0;i < 4;i++) { int nx = qu.front().x + direction[i][0]; int ny = qu.front().y + direction[i][1]; //判断新的位置是否合法 if(nx < 0 || nx >= grid.size() || ny < 0 || ny >= grid[0].size()) continue; //该位置是新鲜橘子 if(grid[nx][ny] == 1) { Node newNode = {nx,ny,qu.front().num+1}; grid[nx][ny] = 2; qu.push(newNode); ret = qu.back().num; } } qu.pop(); } return ret; } int orangesRotting(vector<vector<int>>& grid) { if(grid.empty()) return -1; //判断是否有腐烂的橘子 int sr = -1,sc = -1; for(int i = 0;i < grid.size();i++) { for(int j = 0;j < grid[0].size();j++) { if(grid[i][j] == 2) { sr = i; sc = j; break; } } } if(sr == -1 && sc == -1) { //如果没有橘子返回0,否则返回-1 for(int i = 0;i < grid.size();i++) { for(int j = 0;j < grid[0].size();j++) { if(grid[i][j] != 0) return -1; } } return 0; } //广度优先搜索找最优解 int ret = _orangesRotting(grid); //判断是否没有好橘子 for(int i = 0;i < grid.size();i++) { for(int j = 0;j < grid[0].size();j++) { if(grid[i][j] == 1) return -1; } } return ret; } };
4、单词接龙
思路:为了查找快速,建立unorder_map将字符串序列保存,并且记录该字符串是否访问过。用26个英文小写字符替换单词中的每一个字母,并且查找替换后会不会出现序列中相同的单词,如果出现则保存在队列中。直到找到endWord
class Solution { public: struct Node { string str; int count; }; int ladderLength(string beginWord, string endWord, vector<string>& wordList) { //保存在hashmap中,查找速度快,同时可以记录是否被访问过 unordered_map<string,int> hashMap; for(auto e:wordList) hashMap[e] = 0; //定义并初始化队列 queue<struct Node> qu; struct Node newNode = {beginWord,1}; qu.push(newNode); //遍历队列 int flag = 1; while(!qu.empty() && flag) { string& str = qu.front().str; for(int i = 0;i < str.size() && flag;i++) { //对单词第i位用26个字母进行替换 for(int j = 0;j < 26;j++) { if(str[i] != 'a'+j) { string tmp = str; tmp[i] = 'a'+j; if(hashMap.find(tmp) != hashMap.end() && hashMap.find(tmp)->second == 0) { //存在这么一个单词 newNode = {tmp,qu.front().count+1}; qu.push(newNode); hashMap[tmp] = 1; if(tmp == endWord) { flag = 0; break; } } } } } qu.pop(); } if(flag == 1) return 0; return qu.back().count; } };
5、最小基因变化
注意:和上一个题是同类型,思路完全相同
class Solution { public: struct Node { string str; int count; }; int minMutation(string start, string end, vector<string>& bank) { //将基因库保存在unordered_map中,方便快速查找 unordered_map<string,int> hashMap; for(auto e:bank) hashMap[e] = 0; //定义并初始化队列 queue<struct Node> qu; struct Node newNode = {start,0}; qu.push(newNode); //遍历队列 int flag = 1;//表示是否找到,为0表示找到 char list[4] = {'A','C','G','T'}; int ret; while(!qu.empty() && flag) { //对队头的基因序列进行改变 string str = qu.front().str; for(int i = 0;i < 8;i++) { //将str的第i位变成ACGT中的任意一个,在基因库中查看是否存在 for(int j = 0;j < 4;j++) { if(str[i] != list[j]) { string tmp = str; tmp[i] = list[j]; //基因库中存在这个基因 if(hashMap.find(tmp) != hashMap.end() &&hashMap.find(tmp)->second == 0) { newNode = {tmp,qu.front().count+1}; qu.push(newNode); hashMap[tmp] = 1; if(tmp == end) { ret = qu.back().count; flag = 0; break; } } } } } qu.pop(); } if(flag == 1) return -1; return ret; } };
6、打开转盘锁
思路:对锁中的每一个+1或-1,并将结构保存在set中用于下次判断是否已经使用过。对队列进行遍历,直到找到target.需要注意的是,存在两种特殊情况“0000”就是死锁或者是target,因此需要对这两种情况进行单独判断。
class Solution { public: struct Node { string str; int count; }; int openLock(vector<string>& deadends, string target) { //将死亡数字保存在unordered_Set中 unordered_set<string> hashSet; for(auto e:deadends) hashSet.insert(e); //判断“0000”是否为死锁 if(hashSet.find("0000") != hashSet.end()) return -1; if(target == "0000") return 0; //使用hashmap保存所有的中间节点 unordered_map<string,int> hashMap; //定义并初始化队列 queue<struct Node> qu; struct Node newNode = {"0000",0}; qu.push(newNode); int flag = 1; int ret = -1; int list[2] = {1,-1}; while(!qu.empty() && flag) { //每一个字符串的四位替换成0~9进行查找,判断是否会出现target string str = qu.front().str; for(int i = 0;i < 4 && flag;i++) { for(int j = 0;j < 2;j++) { string tmp = str; int n = (tmp[i]-'0'+10+list[j])%10; tmp[i] = n+'0'; if(hashSet.find(tmp) != hashSet.end()) { //死锁 continue; } else if(hashMap.find(tmp) == hashMap.end()) { //这个没有被使用过 hashMap[tmp] = 0; newNode = {tmp,qu.front().count+1}; qu.push(newNode); if(tmp == target) { flag = 0; ret = qu.back().count; break; } } } } qu.pop(); } return ret; } };
这篇关于搜索算法---广度优先搜索的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)