双向广度优先搜索算法学习小结
LBoy
posted @ 2011年3月01日 04:55
in Algorithm Study
, 3508 阅读
文中提及的一些观点和理论，并非全部个人原创，而是自己的总结和心得， 仅供个人学习编程使用！
LBOY: 双向广度优先搜索，简单的讲就是从初始节点和目标节点两个方向向中间进行搜索，如果是按层次遍历，那么这样他们第一次相遇的时候，肯定是最优的。这里的按层次遍历，我们可以理解为一个点绕一个固定的圆心来画圆弧，每次圆弧所在圆的半径增加一，这样的一个圆弧就是广搜，两个圆弧就是双广。
下面让我们来看看问什么非得是按层次搜索。
下面给出一段伪代码：（摘抄至某ppt）
Bool DBFS();
Begin
Queue Q[2]; Map M[2];
Q[0].Push(start); M[0][start] = 1;
Q[1].Push(end); M[1][end] = 1;
Step := 0; Idx := 0;
while(!Q[0].Empty() || !Q[1].Empty());
Begin
Idx = Step & 1;
Cnt := Q[Idx].Size();
While(Cnt--);
Begin
Cur = Q[Idx].front();
Q[Idx].Pop();
if (M[Idx^1].Find(Cur) != M.End) then
return True;
for each Ext = Extend(Cur)
Begin
if (M[Idx].Find(Ext) == M.end()) then
Q[Idx].Push(Ext);
M[Idx][Ext] = True;
End;
End
Step++;
End;
Return False;
End;
上面的代码中的Step是很有用的, 不仅记录了搜索树的深度，还通过交替搜索判断是那个队列进行操作。
Solitaire
LBOY: 一个棋盘上给定4个旗子，每个棋子可以往相邻的四个方向移动一步，或者往相邻方向存在棋子的格子移动两步。给定棋子的初始状态 和 目标状态，问能否从初始状态到达目标状态。如果可以的话，给出最小的步数。
双广的题目，一般是比较明确的，可以找到给定问题的一个初始状态和一个目标状态（多目标，多初始的可以增加源点汇点）。以这个一个题目为例说一下双广的求解的大体过程。
一个棋子往某一方向最多移动两步，因此，要判断这个方向是否可行。
题目总共有8*8个格子，那么我们可以用一个64位整型来保存每个状态，这需要hash来判重或者通过set，map 也可以，我个人习惯set.
根据刘的黑书的提示，双广A*的算法的正确性未知，所以不建议增设启发函数，当然这个题目可以用A*来做，但是，可以考虑用来做毕业设计的题目。
贴一些可爱又可恶的代码吧！
#include <iostream>
#include <set>
#include <queue>
using namespace std;
#define u64 unsigned __int64
struct node {
int x[4], y[4], s;
u64 state;
void out() {
printf("stp = %d: ", s);
for (int k = 0; k < 4; k++) {
printf("(%d, %d), ", x[k], y[k]);
}
putchar('\n');
for (int k = 63; k >= 0; k--) {
putchar(state & ((u64)1 << k) ? '1':'0');
}
putchar('\n');
}
}init, goal, cur, tmp;
queue<node> q[2];
set<u64> sq[2];
int d[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
inline u64 num(int x, int y) {
return ((u64)1 << ((x-1)*8 + (y-1)));
}
inline bool islegal(int x, int y) {
return 1 <= x && x <= 8 && 1 <= y && y <= 8;
}
bool dbfs() {
if (init.state == goal.state) {
return true;
}
if (!sq[0].empty()) sq[0].clear();
if (!sq[1].empty()) sq[1].clear();
while(!q[0].empty()) q[0].pop();
while(!q[1].empty()) q[1].pop();
q[0].push(init);
sq[0].insert(init.state);
q[1].push(goal);
sq[1].insert(goal.state);
int idx = 0, cnt, stp[2] = {0,0};
while(!q[idx].empty() || !q[idx^1].empty()) {
cnt = q[idx].size();
while(cnt--) {
cur = q[idx].front(); q[idx].pop();
stp[idx] = cur.s + 1;
for (int i = 0; i < 4; i++) {
for (int k = 0; k < 4; k++) {
tmp = cur;
tmp.x[i] = cur.x[i] + d[k][0];
tmp.y[i] = cur.y[i] + d[k][1];
tmp.state ^= num(cur.x[i], cur.y[i]);
tmp.s = cur.s + 1;
if (islegal(tmp.x[i], tmp.y[i]) == true) {
if ((cur.state & num(tmp.x[i], tmp.y[i])) != 0) {
tmp.x[i] += d[k][0];
tmp.y[i] += d[k][1];
if (islegal(tmp.x[i], tmp.y[i]) == true) {
if ((cur.state & num(tmp.x[i], tmp.y[i])) == 0) {
tmp.state |= num(tmp.x[i], tmp.y[i]);
if (sq[idx^1].find(tmp.state) != sq[idx^1].end()) {
return tmp.s + stp[idx^1] <= 8;
}
if (sq[idx].find(tmp.state) == sq[idx].end()) {
sq[idx].insert(tmp.state);
q[idx].push(tmp);
}
}
}
} else {
tmp.state |= num(tmp.x[i], tmp.y[i]);
if (sq[idx^1].find(tmp.state) != sq[idx^1].end()) {
return tmp.s + stp[idx^1] <= 8;
}
if (sq[idx].find(tmp.state) == sq[idx].end()) {
sq[idx].insert(tmp.state);
q[idx].push(tmp);
}
}
}
}
}
}
if (stp[idx] > 4) return 0;
idx ^= 1;
}
return false;
}
int main() {
//freopen("in.in", "r", stdin);
//freopen("out.out", "w", stdout);
while(scanf("%d %d", init.x, init.y) != EOF) {
init.state = num(init.x[0], init.y[0]);
for (int k = 1; k < 4; k++) {
scanf("%d %d", init.x + k, init.y + k);
init.state |= num(init.x[k], init.y[k]);
}
goal.state = 0;
for (int k = 0; k < 4; k++) {
scanf("%d %d", goal.x + k, goal.y + k);
goal.state |= num(goal.x[k], goal.y[k]);
}
init.s = goal.s = 0;
//init.out(); goal.out();
puts(dbfs() ? "YES":"NO");
}
return 0;
}
小结：双广的题目正如前面讲的那样，起始和目标状态是比较明确的。选择双广的前提，是状态的数量很多，但是，A*或者IDA*的启发函数有不好想的前提下。
下面给出一个我做的失败的题目，测试数据是都过了，不过没有在规定的时间内跑出测试数据，我自己的机子是可以的！我打表（实际上是人肉的测试数据）代码6k+.没兴趣优化，优化，过去应该没问题的。
#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
using namespace std;
const int maxn = 16;
const int maxs = 1<<24;
const int Size = 1<<18;
char W, H, n;
char mat[maxn][maxn];
char dir[5][2] = {
{0, 0}, {-1, 0}, {0, 1}, {1, 0}, {0, -1}
};
struct node {
int st, d;
node(int st = 0, int d = 0):st(st), d(d) {}
void out() {
printf("%d, %d, %d\n", d&7, (d>>3)&7, (d>>6)&7);
printf("(%d, %d), ", st & 15, (st >> 4) & 15);
printf("(%d, %d), ", (st >> 8) & 15, (st >> 12) & 15);
printf("(%d, %d)\n", (st >> 16) & 15, (st >> 20) & 15);
}
}init, goal, cur;
struct queue {
int beg, end;
node key[Size+1];
node front() {
return key[beg];
}
void push(node k) {
key[end] = k;
end = (end+1) & (Size-1);
}
void pop() {
beg = (beg + 1) & (Size-1);
}
bool empty() {
return beg == end;
}
void clr() {
beg = end = 0;
}
int size() {
return end - beg;
}
}q[2];
unsigned char h[2][maxs];
bool flg[2][3];
int num[5][3];
inline void deal(int &sta, int x, int y, int id) {
switch(id) {
case 0: sta += x + (y << 4); break;
case 1: sta += (x << 8) + (y << 12); break;
case 2: sta += (x << 16) + (y << 20); break;
}
}
inline bool islegal(int x, int y) {
return !(x < 0 || x >= H || y < 0 || y >= W) && mat[x][y] != '#';
}
inline bool opp(bool idx, int d, int da, int db, int dc) {
char ret = 0;
if (flg[idx][0] == true && (d&7) && da) {
if (abs( (d&7) - da) != 2) {
return false;
}
ret++;
}
if (flg[idx][1] == true && ((d>>3) & 7) && ((db>>3)&7)) {
if (abs( ((d>>3) & 7) - ((db>>3)&7)) != 2) {
return false;
}
ret++;
}
if (flg[idx][2] == true && ((d>>6) & 7) && ((dc>>6)&7) ) {
if (abs( ((d>>6) & 7) - ((dc>>6)&7)) != 2) {
return false;
}
ret++;
}
return ret == 3;
}
inline bool same(int x1, int y1, int x2, int y2) {
return x1 == x2 && y1 == y2;
}
int dbfs() {
memset(h, 0, sizeof(h));
//while(!q[0].empty()) q[0].pop();
//while(!q[1].empty()) q[1].pop();
q[0].clr(); q[1].clr();
q[0].push(init); h[0][init.st] = 1;
q[1].push(goal); h[1][goal.st] = 1;
bool idx = 0;
int cnt, nxt;
int xa, ya, xb, yb, xc, yc;
int a, b, c, ta, tb, tc, da, db, dc;
int ax, ay, bx, by, cx, cy;
while(!q[0].empty() || !q[1].empty()) {
cnt = q[idx].size(); // printf("idx = %d\n", idx);
while(cnt--) {
cur = q[idx].front(); q[idx].pop();// cur.out();
nxt = 0;
ax = cur.st & 15; ay = (cur.st >> 4) & 15;
bx = (cur.st >> 8) & 15; by = (cur.st >> 12) & 15;
cx = (cur.st >> 16) & 15; cy = (cur.st >> 20) & 15;
for (a = 0; a < 5; a ++) {
xa = ax + dir[a][0];
ya = ay + dir[a][1];
if (flg[idx][0] == false || islegal(xa, ya) == true) {
if (flg[idx][0] == true) {
ta = xa + (ya << 4);
da = a;
} else {
ta = 0;
da = 0;
}
for (b = 0; b < 5; b++) {
xb = bx + dir[b][0];
yb = by + dir[b][1];
if (flg[idx][1] == false || islegal(xb, yb) == true) {
if (flg[idx][1] == true) {
tb = (xb << 8) + (yb << 12);
db = b << 3;
if (flg[idx][0] == true) {
if (same(xa, ya, xb, yb)) {
continue;
}
if (same(xa, ya, bx, by) && same(xb, yb, ax, ay)) {
continue;
}
}
} else {
tb = 0;
db = 0;
}
for (c = 0; c < 5; c++) {
xc = cx + dir[c][0];
yc = cy + dir[c][1];
if (flg[idx][2] == false || islegal(xc, yc) == true) {
if (flg[idx][2] == true) {
tc = (xc << 16) + (yc << 20);
dc = c<<6;
if (flg[idx][0] == true) {
if (same(xa, ya, xc, yc)) {
continue;
}
if (same(xa, ya, cx, cy) && same(xc, yc, ax, ay)) {
continue;
}
}
if (flg[idx][1] == true) {
if (same(xb, yb, xc, yc)) {
continue;
}
if (same(xb, yb, cx, cy) && same(xc, yc, bx, by)) {
continue;
}
}
} else {
tc = 0;
dc = 0;
}
if (!(da || db || dc)) {
continue;
}
if (opp(idx, cur.d, da, db, dc)) {
continue;
}
nxt = ta + tb + tc;
if (h[idx^1][nxt] != 0) {
return h[idx^1][nxt] + h[idx][cur.st]-1;
}
if (h[idx][nxt] == 0) {
h[idx][nxt] = h[idx][cur.st] + 1;
q[idx].push(node(nxt, da + db + dc));
}
}
}
}
}
}
}
}
idx ^= 1;
}
return -1;
}
int main() {
//freopen("in.in", "r", stdin);
// freopen("out.out", "w", stdout);
int a[] = { 51, 215,108,108,316,98,17,66, 74,70};
int ca = 0;
while(scanf("%d %d %d", &W, &H, &n) != EOF) {
if (!(W || H || n)) break;
init = node(0, 0);
goal = node(0, 0);
memset(flg, false, sizeof(flg));
for (int i = 0; i < H; i++) {
getchar(); gets(mat[i]);
for (int j = 0; j < W; j++) {
if ('a' <= mat[i][j] && mat[i][j] <= 'c') {
flg[0][mat[i][j] - 'a'] = true;
deal(init.st, i, j, mat[i][j] - 'a');
}
if ('A' <= mat[i][j] && mat[i][j] <= 'C') {
flg[1][mat[i][j] - 'A'] = true;
deal(goal.st, i, j, mat[i][j] - 'A');
}
}
}
printf("%d\n", a[ca++]);
//init.out(); goal.out();
//printf("%d\n", dbfs());
}
return 0;
}
- 无匹配
评论 (0)
Copyright © 2007