搜索 广度优先搜索 BFS
教程导读
学研发网的这篇信息学奥赛技术教程文章主要介绍了搜索 广度优先搜索 BFS,现在分享给大家,供学习和参考。文章包含2076字,纯文字阅读大概需要6分钟。
教程信息
(一)核心思想
1、广度优先
广度优先的思想从起始节点开始搜索,逐层向外遍历图形,直到找到目标节点或所有节点都被遍历。
在搜索算法中,指通过维护队列的方法,不断同时在解空间中层层向外,并且判断当前延伸到“可能解”是否是一个“正确解”。
2、泛洪
广度优先遍历从起点出发,扩展相同层更多的可能性以拓宽广度,类似于泼水一般,让水流顺着多个方向同时蔓延,有利于弥补深搜的不足。
但是广度优先的路径可能是有重复点的,因此每一条水路总是带着一副自己是否访问过的标记数组,如果使用共用的标记数组可能产生混乱。
(二)实现框架
queue Q; Q.push(初始状态); // 将初始状态入队 while (Q.empty() == false) { State u = Q.front(); // 取出队首 Q.pop(); //出队 for (枚举所有可扩展状态) if (是合法的) { // 如未访问过、未在队内等 维护某些必要信息 Q.push(v); // 入队 } else if (达到终点) 输出解 }
(三)走迷宫代码
实现代码:
#include<bits/stdc++.h> using namespace std; int G[6][6]; //迷宫图 int d[4][2] = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } }; //每一行表示一个方向偏移量{0,1}往上,{0,-1}往下,{1,0}往右,{-1,0}往左 int n, m, t, nx, ny, ex, ey, zx, zy; //迷宫的长和宽,障碍数,起点终点,障碍坐标 int countt = 0; //存储答案 struct nod { int x, y, g[6][6]; //g用来存储到当前点位置走过的路,防止不同路径干涉在G上干涉,导致答案缺失 }; int main() { cin >> n >> m >> t >> nx >> ny >> ex >> ey; G[nx][ny] = 1; for (int i = 0; i < t; i++) { cin >> zx >> zy; if (zx == ex && zy == ey) { //坑,终点可能是障碍 cout << 0; return 0; } G[zx][zy] = 1; } queue < nod > Q; nod node = { nx, ny }; node.g[nx][ny] = 1; Q.push(node); while (Q.empty() == false) { node = Q.front(); //队头元素 Q.pop(); //出队 for (int i = 0; i < 4; i++) { nod node1 = { node.x + d[i][0], node.y + d[i][1] }; memcpy(node1.g, node.g, sizeof(node.g)); if (node1.x == ex && node1.y == ey) countt++; else if (node1.x >= 1 && node1.y >= 1 && node1.x <= n && node1.y <= m && G[node1.x][node1.y] == 0 && node1.g[node1.x][node1.y] == 0) { //不超边界,不是障碍,没有走过 node1.g[node1.x][node1.y] = 1; //该点标记走过。 Q.push(node1); } } } cout << countt; return 0; }
执行结果:
教程咨询
如果章节内容看不懂,可以联系作者。
教程总结
以上是学研发网为您提供搜索 广度优先搜索 BFS的全部内容,希望教程文章能够帮你了解学习搜索 广度优先搜索 BFS,解决所遇到的问题。 如果觉得学研发网信息学奥赛教程内容还不错,欢迎将学研发网网站推荐给身边需要的人。
教程备注
版权声明:教程内容为学研发网整理和编写,如需转载请联系站长并附上文章原始链接和原始作者信息。
手机阅读
扫描二维码推送至手机访问。
本文链接:http://www.xueyanfa.com/xinaojiaocheng/xinaogaoji-285.html