例题：P1397 八数码难题
###双向BFS
普通BFS
双向BFS
所谓双向广度优先搜索指的是搜索沿两个方向同时进行
正向搜索：从初始点向目标点搜索；
逆向搜索：从目标点向初始点搜索；
从正反两个方向搜索，理论上可以节省二分之一的搜索量，从而提高搜索速度，节约内存空间。
从初始状态和目标状态向两个方向同时进行扩展，如果两颗解答树在某个节点发生一次重合，即可终止此搜索过程，则该节点所连接的两条路径所拼成的路径就是最优解
●双向广度优先搜索通常有两种搜索方法:
①、两个方向交替扩展;
②、选择结点个数较少的那个方向先扩展;
●实现方法:
建立两个队列分别拓展两个方向出发的状态。
每次while循环时只扩展正反两个方向中节点数目较少的一个，可以使两边的发展速度保持一定的平衡，从而减少总扩展节点的个数,加快搜索速度。
例题代码
#include<iostream>
#include<map>
#include<queue>
#include<cstring>
using namespace std;
map<string, int> ma,mb;
struct nod
{
string a;
int x, y;
};
queue<nod> qa,qb;
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
int main()
{
string aim = "123804765",a;
cin >> a;
if(a==aim)
{
cout << "0";
return 0;
}
for (int i = 0; i < 9;i++)
{
if(a[i]=='0')
qa.push({a, i / 3, i % 3});
}
qb.push({aim, 1, 1});
ma[a] = mb[aim] = 0;
while(!qa.empty()||!qb.empty())
{
if(qa.size()<qb.size())
{
string temp = qa.front().a;
int x1 = qa.front().x;
int y1 = qa.front().y;
qa.pop();
for (int i = 0; i < 4;i++)
{
if(x1+dx[i]<0||x1+dx[i]>2||y1+dy[i]<0||y1+dy[i]>2)
continue;
string b = temp;
swap(b[x1 * 3 + y1], b[(x1 + dx[i]) * 3 + y1+dy[i]]);
if(ma[b]!=0)
continue;
if(mb[b]!=0)
{
cout << ma[temp] + mb[b] + 1;
return 0;
}
ma[b] = ma[temp] + 1;
qa.push({b, x1 + dx[i], y1 + dy[i]});
}
}
else
{
string temp = qb.front().a;
int x1 = qb.front().x;
int y1 = qb.front().y;
qb.pop();
for (int i = 0; i < 4;i++)
{
if(x1+dx[i]<0||x1+dx[i]>2||y1+dy[i]<0||y1+dy[i]>2)
continue;
string b = temp;
swap(b[x1 * 3 + y1], b[(x1 + dx[i]) * 3 + y1+dy[i]]);
if(mb[b]!=0)
continue;
if(ma[b]!=0)
{
cout << ma[b] + mb[temp] + 1;
return 0;
}
mb[b] = mb[temp] + 1;
qb.push({b, x1 + dx[i], y1 + dy[i]});
}
}
}
return 0;
}
|
###双端队列BFS
P4667 [BalticOI 2011 Day1]Switch the Lamp On
类似优先队列优化的d j最短路，每次用未被标记最小的值去更新其他点。
边权只有0、1，可用双端队列代替优先队列
边权为0，插到队头；边权为1，插入队尾，这样就省去了排序操作，保证队首最小
例题代码
#include<deque>
#include<cstring>
#include<iostream>
using namespace std;
struct nod
{
int x, y;
};
char sq[505][505];
deque<nod> q;
int dx[4] = {1, 1, -1, -1};
int dy[4] = {1, -1, 1, -1};
int rx[4] = {0, 0, -1, -1};
int ry[4] = {0, -1, 0, -1};
char ch[5] = "\\//\\";
bool vis[505][505];
int dist[505][505];
int n, m;
void bfs()
{
memset(vis, 0, sizeof(vis));
memset(dist, 0x3f, sizeof(dist));
q.push_front({0, 0});
dist[0][0] = 0;
while(!q.empty())
{
int x1 = q.front().x;
int y1 = q.front().y;
q.pop_front();
if(vis[x1][y1])
continue;
vis[x1][y1] = 1;
for (int i = 0; i < 4;i++)
{
int x2 = x1 + dx[i];
int y2 = y1 + dy[i];
if(x2<0||x2>n||y2<0||y2>m)
continue;
int xs = x1 + rx[i];
int ys = y1 + ry[i];
int d = dist[x1][y1];
if(sq[xs][ys]!=ch[i])
d++;
if(d<dist[x2][y2])
{
dist[x2][y2] = d;
if(sq[xs][ys]!=ch[i])
q.push_back({x2, y2});
else
q.push_front({x2, y2});
}
}
}
}
int main()
{
cin >> n >> m;
for (int i = 0; i < n;i++)
{
for (int j = 0; j < m;j++)
cin >> sq[i][j];
}
bfs();
if(dist[n][m]==0x3f3f3f3f)
cout << "NO SOLUTION"<<endl;
else
cout << dist[n][m]<<endl;
return 0;
}
|
