首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 其他教程 > 其他相关 >

双向广度优先搜索算法框架及八数码有关问题例程

2012-07-27 
双向广度优先搜索算法框架及八数码问题例程?双向广度优先搜索算法是对广度优先算法的一种扩展。广度优先算

双向广度优先搜索算法框架及八数码问题例程

?

双向广度优先搜索算法是对广度优先算法的一种扩展。广度优先算法从起始节点以广度优先的顺序不断扩展,

直到遇到目的节点;而双向广度优先算法从两个方向以广度优先的顺序同时扩展,一个是从起始节点开始扩展,另

一个是从目的节点扩展,直到一个扩展队列中出现另外一个队列中已经扩展的节点,也就相当于两个扩展方向出现了

交点,那么可以认为我们找到了一条路径。双向广度优先算法相对于广度优先算法来说,由于采用了从两个跟开始扩展

的方式,搜索树的深度得到了明显的减少,所以在算法的时间复杂度和空间复杂度上都有较大的优势!双向广度优先算

法特别适合于给出了起始节点和目的节点,要求他们之间的最短路径的问题。另外需要说明的是,广度优先的顺序能够保证

找到的路径就是最短路径!

???????? 基于以上思想,我们给出双向广度优先算法编程的基本框架如下:

数据结构:

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优化查找后的版本》

热点排行