BFS提高效率的一点建议
2024-09-01 00:18:57
BFS有两种常见的形式:
形式1:
把初始点加入队列;
while (队列非空) {
取出队头;
操作取出的点;
寻找周围符合条件的点加入队列;
}
形式2:
操作初始点
把初始点加入队列;
while (队列非空) {
取出队头;
寻找周围符合条件的点,操作找到的点,然后加入队列;
}
这两种形式的差别就是新找到的点先插入队列还是先操作,看似没什么差别,其实有的时候效率差别非常大;
举个栗子:
//BFS示例1:先操作后插入队列 void bfs(int x, int y, int n, int m, vector<vector<char>> &board) {
static int dx[] = {-1, 1, 0, 0};
static int dy[] = {0, 0, -1, 1};
static queue<pair<int, int> > Q;
Q.push(make_pair(x, y));
board[x][y] = 'Y';
while (!Q.empty()) {
auto e = Q.front();
Q.pop();
for (int i = 0; i < 4; ++i) {
if (check(e.first + dx[i], e.second + dy[i], n, m) && board[e.first + dx[i]][e.second + dy[i]] == 'O') {
board[e.first + dx[i]][e.second + dy[i]] = 'Y';
Q.push(make_pair(e.first + dx[i], e.second + dy[i]));
}
}
}
}
//BFS示例2: 先插入队列后操作
void bfs(int x, int y, int n, int m, vector<vector<char>> &board) {
static int dx[] = {-1, 1, 0, 0};
static int dy[] = {0, 0, -1, 1};
static queue<pair<int, int> > Q;
Q.push(make_pair(x, y));
while (!Q.empty()) {
auto e = Q.front();
Q.pop();
board[e.first][e.second] = 'Y';
for (int i = 0; i < 4; ++i) {
if (check(e.first + dx[i], e.second + dy[i], n, m) && board[e.first + dx[i]][e.second + dy[i]] == 'O') {
Q.push(make_pair(e.first + dx[i], e.second + dy[i]));
}
}
}
}
每次操作为对节点赋值为‘Y’
如果输入20 x 20的字符矩阵,则代码1的运行时间为0.003s, 代码2的运行时间为1.126s,是不是感到大吃一惊???
原因在哪里呢?
如果输出中间过程的队列长度就可以发现代码2的队列长度非常大,因为未处理就加入队列,以后被重复加入的几率很大,大量点被重复的加入队列,导致冗余,造成不必要的开张,效率低下。
而先处理再加入队列,因此节点已经改变,则不会再被加入队列,因此队列内不会出现重复。
因此,最好使用BFS的第一种形式。
最新文章
- Maven使用第三方jar文件的两种方法
- Oracle数据库SQL优化
- css3 怎么实现像书籍装订线的效果
- matlab中 hold on 与hold off的用法
- iOS iOS9下修改回HTTP模式进行网络请求
- 关于类似于自动填充搜索框的DEMO
- PHP:class static
- Android控件状态依赖框架
- WPF中的RichTextBox
- MySQL数据同步,出现Slave_SQL_Running:no和slave_io_running:no问题的解决方法
- 第一个用eclipse打包APK时报错一个错误怎么解决
- python3 输出系统信息
- 新建一个self hosted Owin+ SignalR Project(1)
- org.apache.commons.dbcp.SQLNestedException: Cannot load JDBC driver class &#39;com.microsoft.sqlserver.jdbc.SQLServerDriver &#39;
- Tinyos学习笔记(二)
- SSM项目的数据库密码加密方案
- mybatis 对象关系映射例子
- TypeError: to_categorical() got an unexpected keyword argument &#39;nb_classes&#39;
- PHP后台处理jQuery Ajax跨域请求问题 — xx was not called解决办法
- Ios国际化翻译工具