双向广度优先搜索算法框架及八数码问题例程
最新推荐文章于 2023-10-20 14:55:00 发布
hazqfp 
于 2012-02-27 20:03:10 发布
阅读量1.2k 
收藏 5
点赞数
文章标签： 算法 框架 扩展 duplicates 优化 function
双向广度优先搜索算法是对广度优先算法的一种扩展。广度优先算法从起始节点以广度优先的顺序不断扩展，
直到遇到目的节点；而双向广度优先算法从两个方向以广度优先的顺序同时扩展，一个是从起始节点开始扩展，另
一个是从目的节点扩展，直到一个扩展队列中出现另外一个队列中已经扩展的节点，也就相当于两个扩展方向出现了
交点，那么可以认为我们找到了一条路径。双向广度优先算法相对于广度优先算法来说，由于采用了从两个跟开始扩展
的方式，搜索树的深度得到了明显的减少，所以在算法的时间复杂度和空间复杂度上都有较大的优势！双向广度优先算
法特别适合于给出了起始节点和目的节点，要求他们之间的最短路径的问题。另外需要说明的是，广度优先的顺序能够保证
找到的路径就是最短路径！
基于以上思想，我们给出双向广度优先算法编程的基本[框架](https://so.csdn.net/so/search?q=%E6%A1%86%E6%9E%B6&spm=1001.2101.3001.7020)如下：
数据结构：
Queue q1, q2; //两个队列分别用于两个方向的扩展（注意在一般的广度优先算法中，只需要一个队列）
int head[2], tail[2]; //两个队列的头指针和尾指针
算法流程:
一、主控函数:
void solve()
{
1. 将起始节点放入队列q1,将目的节点放入队列q2
2. 当 两个队列都未空时，作如下循环
1) 如果队列q1里的未处理节点比q2中的少（即tail\[0\]-head\[0\] < tail\[1\]-head\[1\]),则扩展（expand()）队列q1
2) 否则扩展（expand()）队列q2 (即tail\[0\]-head\[0\] >= tail\[1\]-head\[1\]时)
3. 如果队列q1未空，循环扩展（expand()）q1直到为空
4. 如果队列q2未空，循环扩展（expand()）q2知道为空
}
二、扩展函数:
int expand(i) //其中i为队列的编号(表示q0或者q1)
{
取队列qi的头结点H
对头节点H的每一个相邻节点adj，作如下循环
1 如果adj已经在队列qi之前的某个位置出现，则抛弃节点adj
2 如果adj在队列qi中不存在\[函数 isduplicate(i)\]
1） 将adj放入队列qi
2) 如果adj 在队列(q(1-i))，也就是另外一个队列中出现\[函数 isintersect()\]
输出 找到路径
}
三、判断新节点是否在同一个队列中重复的函数
int isduplicate(i, j) //i为队列编号，j为当前节点在队列中的指针
{
遍历队列,判断是否存在【线性遍历的时间复杂度为O（N)，如果用HashTable优化，时间复杂度可以降到O(1)\]
}
四、判断当前扩展出的节点是否在另外一个队列出现，也就是判断相交的函数：
int isintersect(i,j) //i为队列编号，j为当前节点在队列中的指针
{
遍历队列,判断是否存在【线性遍历的时间复杂度为O（N)，如果用HashTable优化，时间复杂度可以降到O(1)\]
}
以上为双向广度优先搜索算法的基本思路，下面给出使用上面的算法框架编写的八数码问题的代码：
问题描述:
给定 3 X 3 的矩阵如下:
2 3 4
1 5 x
7 6 8
程序每次可以交换"x"和它上下左右的数字，
经过多次移动后得到如下状态:
1 2 3
4 5 6
7 8 x
输出在最少移动步数的情况下的移动路径[每次移动的方向上下左右依次表示为’u’, ‘d’, ‘l’, ‘r’]
例如：
如果过输入:【将矩阵放到一行输出】
2 3 4 1 5 x 7 6 8
则输出:
ullddrurdllurdruldr
原题见ACM PKU 1077
C++代码如下：【注意，这是没有使用HASH优化的版本，压线通过了ACM PKU在线测试的内存和时间要求】
/*
* Author: puresky
* Date: 2010.01.12
* Purpose: solve EIGTH NUMBER problem!
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXN 1000000
#define SWAP(a, b) {char t = a; a = b; b = t;}
typedef struct _Node Node;
struct _Node
{
char tile[10]; // represent the tile as a string ending with ‘\0’
char pos; // the position of ‘x’
char dir; //the moving direction of ‘x’
int parent; //index of parent node
};
int head[2], tail[2];
Node queue[2][MAXN];// two queues for double directoin BFS
//shift of moving up, down, left ,right
int shift[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
//for output direction!
char dir[4][2] = {{‘u’, ‘d’}, {‘d’, ‘u’}, {‘l’, ‘r’}, {‘r’, ‘l’}};
//test case
char start[10] = “23415x768”;
char end[10] = “12345678x”;
//read a tile 3 by 3
void readtile()
{
int i;
char temp[10];
for(i = 0; i < 9; ++i)
{
scanf(“%s”, temp);
start[i] = temp[0];
}
start[9] = ‘\0’;
}
//print result
void print_backward(int i)
{
if(queue[0][i].parent != -1)
{
print_backward(queue[0][i].parent);
printf(“%c”, queue[0][i].dir);
}
}
void print_forward(int j)
{
if(queue[1][j].parent != -1)
{
printf(“%c”, queue[1][j].dir);
print_forward(queue[1][j].parent);
}
}
void print_result(int i, int j)
{
//printf(“%d,%d\n”, i, j);
print_backward(i);
print_forward(j);
printf(“\n”);
}
//init the queue
void init(int qi, const char* state)
{
strcpy(queue[qi][0].tile, state);
queue[qi][0].pos = strchr(state, ‘x’) - state;
queue[qi][0].parent = -1;
head\[qi\] = tail\[qi\] = 0;
}
//check if there are duplicates in the queue
//time comlexity:O(n)
//We can optimise this function using HashTable
int isduplicate(int qi)
{
int i;
for(i = 0; i < tail[qi]; ++i)
{
if(strcmp(queue[qi][tail[qi]].tile, queue[qi][i].tile) == 0)
{
return 1;
}
}
return 0;
}
//check if the current node is in another queue!
//time comlexity:O(n)
//We can optimise this function using HashTable
int isintersect(int qi)
{
int i;
for(i = 0 ; i < tail[1 - qi]; ++i)
{
if(strcmp(queue[qi][tail[qi]].tile, queue[1 - qi][i].tile) == 0)
{
return i;
}
}
return -1;
}
//expand nodes
int expand(int qi)
{
int i, x, y, r;
Node\* p = &(queue\[qi\]\[head\[qi\]\]);
head\[qi\]++;
for(i = 0; i < 4; ++i)
{
x = p->pos / 3 + shift\[i\]\[0\];
y = p->pos % 3 + shift\[i\]\[1\];
if(x >= 0 && x <= 2 && y >= 0 && y <= 2)
{
tail\[qi\]++;
Node\* pNew = &(queue\[qi\]\[tail\[qi\]\]);
strcpy(pNew->tile, p->tile);
SWAP(pNew->tile\[ 3 \* x + y\], pNew->tile\[p->pos\]);
pNew->pos = 3 \* x + y;
pNew->parent = head\[qi\] - 1;
pNew->dir = dir\[i\]\[qi\];
if(isduplicate(qi))
{
tail\[qi\]--;
}
else
{
if((r = isintersect(qi)) != -1)
{
if(qi == 1)
{
print\_result(r, tail\[qi\]);
}
else
{
print\_result(tail\[qi\], r);
}
return 1;
}
}
}
}
return 0;
}
//call expand to generate queues
int solve()
{
init(0, start);
init(1, end);
while(head\[0\] <= tail\[0\] && head\[1\] <= tail\[1\])
{
//expand the shorter queue firstly
if(tail\[0\] - head\[0\] >= tail\[1\] - head\[1\])
{
if(expand(1)) return 1;
}
else
{
if(expand(0)) return 1;
}
}
while(head\[0\] <= tail\[0\]) if(expand(0)) return 1;
while(head\[1\] <= tail\[1\]) if(expand(1)) return 1;
return 0;
}
int main(int argc, char** argv)
{
readtile();
if(!solve())
{
printf(“unsolvable\n”);
}
//system(“pause”); //pause
return 0;
}
ACM Judge Online: 372K 内存， 938MS 时间
使用HASHTABLE优化后的版本见：《八数码问题HashTable优化查找后的版本》