面对迷宫问题,求解路径一共有三种方式。分别为:栈解迷宫(深度优先搜索)、递归法(深度优先搜索)与本文提到的队解迷宫(广度优先搜索),有兴趣可以参阅这篇文章。其中,栈指的是堆栈,队指的是队列。搜索中,利用了其堆栈的先进后出和队列的先进先出的特性。其中,前两种算法无法直接求出最短路径,而广度优先搜索会直接求出其最短路径。下面来具体讨论下队解迷宫的问题。

问题

这个迷宫问题的解答,主要参考了《LINUX一站式编程》中的第12章“栈与队列”的正文和习题。

假设有这样一个迷宫,用一个5*5的数组来表示,其中0表示有路可走,1表示无路可走。那么,如何找到一个通路,使得可以从左上角的(0,0)点走到右下角的(4,4)点?

迷宫
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0

搜索过程

其中2代表已经走过的路,故观察2的覆盖流程即算法的运行流程。

2 1 0 0 0 
2 1 0 1 0 
0 0 0 0 0 
0 1 1 1 0 
0 0 0 1 0 
**********
2 1 0 0 0 
2 1 0 1 0 
2 0 0 0 0 
0 1 1 1 0 
0 0 0 1 0 
**********
2 1 0 0 0 
2 1 0 1 0 
2 2 0 0 0 
2 1 1 1 0 
0 0 0 1 0 
**********
2 1 0 0 0 
2 1 0 1 0 
2 2 0 0 0 
2 1 1 1 0 
2 0 0 1 0 
**********
2 1 0 0 0 
2 1 0 1 0 
2 2 2 0 0 
2 1 1 1 0 
2 0 0 1 0 
**********
2 1 0 0 0 
2 1 0 1 0 
2 2 2 0 0 
2 1 1 1 0 
2 2 0 1 0 
**********
2 1 0 0 0 
2 1 2 1 0 
2 2 2 2 0 
2 1 1 1 0 
2 2 0 1 0 
**********
2 1 0 0 0 
2 1 2 1 0 
2 2 2 2 0 
2 1 1 1 0 
2 2 2 1 0 
**********
2 1 2 0 0 
2 1 2 1 0 
2 2 2 2 0 
2 1 1 1 0 
2 2 2 1 0 
**********
2 1 2 0 0 
2 1 2 1 0 
2 2 2 2 2 
2 1 1 1 0 
2 2 2 1 0 
**********
2 1 2 0 0 
2 1 2 1 0 
2 2 2 2 2 
2 1 1 1 0 
2 2 2 1 0 
**********
2 1 2 2 0 
2 1 2 1 0 
2 2 2 2 2 
2 1 1 1 0 
2 2 2 1 0 
**********
2 1 2 2 0 
2 1 2 1 2 
2 2 2 2 2 
2 1 1 1 2 
2 2 2 1 0 
**********
2 1 2 2 2 
2 1 2 1 2 
2 2 2 2 2 
2 1 1 1 2 
2 2 2 1 0 
**********
2 1 2 2 2 
2 1 2 1 2 
2 2 2 2 2 
2 1 1 1 2 
2 2 2 1 2 
**********
2 1 2 2 2 
2 1 2 1 2 
2 2 2 2 2 
2 1 1 1 2 
2 2 2 1 2 
**********
2 1 2 2 2 
2 1 2 1 2 
2 2 2 2 2 
2 1 1 1 2 
2 2 2 1 2 
**********

通过上面的流程,可以清晰的看出执行的流程利用了队列的先进先出的特性。即在走过(0,0)点后,将改点进行标记为2,并压入队列。随后,在弹出队列,继续判断其可走的方向,并将其可走的方向依次压入队列。再弹出队列…依次反复,直到第一个找到终点(4,4)的时候弹出循环。

范例程式码(C++)

 

[code lang=”cpp”]
/**
* 队解迷宫算法.
*
* 利用广度优先算法.
*/
#include <iostream>
#include <cstdlib>

using namespace std;

#define MAX_ROW 5
#define MAX_COL 5

int tail = 0;
int head = 0;

struct point {
int row;
int col;
int predecessor;
} queue[512];

int maze[MAX_ROW][MAX_COL] = {
0,1,0,0,0,
0,1,0,1,0,
0,0,0,0,0,
0,1,1,1,0,
0,0,0,1,0,
};

void enqueue(struct point p)
{
queue[tail++] = p;
return;
}

struct point dequeue()
{
struct point p;
p = queue[head++];
return p;
}

int _is_empty()
{
return head == tail;
}

void print_maze()
{
int i, j;
for (i = 0; i < MAX_ROW; i++) {
for (j = 0; j < MAX_COL; j++) {
cout<<maze[i][j]<<‘ ‘;
}
cout<<endl;
}
cout<<"**********"<<endl;
}

void visit(int row, int col)
{
struct point p = {row, col, head -1};
maze[row][col] = 2;
enqueue(p);
return;
}

int main(int argc, char * argv[])
{
struct point p;
visit(0, 0);
while (!_is_empty()) {
p = dequeue();
if (p.row == MAX_ROW – 1 && p.col == MAX_COL – 1)
{
break;
}
if( p.row + 1 < MAX_ROW && maze[p.row + 1][p.col] == 0)
{
visit(p.row + 1, p.col);
}
if( p.row – 1 >= 0 && maze[p.row – 1][p.col] == 0)
{
visit(p.row – 1, p.col);
}
if( p.col + 1 < MAX_COL && maze[p.row][p.col + 1] == 0)
{
visit(p.row, p.col + 1);
}
if( p.col – 1 >= 0 && maze[p.row][p.col – 1] == 0)
{
visit(p.row, p.col – 1);
}
print_maze();
}

if (p.row == MAX_ROW – 1 && p.col == MAX_COL – 1) {
cout<<‘(‘<<MAX_ROW – 1<<‘,'<<MAX_COL – 1<<‘)'<<endl;
while (p.predecessor != -1) {
p = queue[p.predecessor];
cout<<‘(‘<<p.row<<‘,'<<p.col<<‘)'<<endl;
}
} else {
cout<<"NO PATH"<<endl;
}
return 0;
}

[/code]


解法延伸

第一种,使用堆栈进行深度优先搜索

堆栈的先进后出实现了深度优先搜索。其中,如果一个点被探测过了,就标记为2,避免以后重复探索。为了记载历史路径信息,使用了predecessor数组。代码和解如下:

[code lang=”cpp” collapse=”true”]
//堆栈版迷宫问题
struct point{int row, col;} stack[512];
int top = 0;
int LEN=5;
int maze[5][5] = {
0,1,0,0,0,
0,1,0,1,0,
0,0,0,0,0,
0,1,1,1,0,
0,0,0,1,0,
};
void push(struct point p)
{
stack[top++] = p;
return;
}
struct point pop()
{
return stack[–top];
}
int is_empty()
{
return top == 0;
}
void print_maze()
{
int i,j;
for(i=0;i<LEN;i++)
{
for(j=0;j<LEN;j++)
printf("%d",maze[i][j]);
putchar(‘\n’);
}
printf("**********\n");
}
struct point predecessor[5][5] = {
{{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1}},
{{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1}},
{{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1}},
{{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1}},
{{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1}},
};
void visit (int row, int col, struct point pre)
{
struct point visit_point = {row, col};
maze[row][col] = 2;
predecessor[row][col] = pre;
push(visit_point);
}
int main()
{
struct point p = {0,0};
int MAX_ROW = 5;
int MAX_COL = 5;
maze[p.row][p.col] = 2;
push(p);
while(!is_empty()) {
p = pop();
if(p.row == MAX_ROW -1 && p.col == MAX_COL -1)
break;
if(p.col+1< MAX_COL && maze[p.row][p.col+1] == 0)
visit(p.row,p.col+1,p);
if(p.row+1< MAX_ROW && maze[p.row+1][p.col] == 0)
visit(p.row+1,p.col,p);
if(p.col-1>=0 && maze[p.row][p.col-1] == 0)
visit(p.row,p.col-1,p);
if(p.row-1>=0 && maze[p.row-1][p.col] == 0)
visit(p.row-1,p.col,p);
print_maze();
}
if(p.row == MAX_ROW -1 && p.col == MAX_COL -1) {
printf("(%d,%d)\n",p.row,p.col);
while(predecessor[p.row][p.col].row != -1) {
p = predecessor[p.row][p.col];
printf("(%d,%d)\n",p.row,p.col);
}
} else {
printf("No Path\n");
}
return 0;
}
[/code]

运行结果如下:

1


第二种,使用递归(系统帮你进行了深度优先搜索)

系统在递归调用时,系统内部有一个堆栈,所以使用递归时,虽然你没有显示地使用堆栈,但是系统内部的堆栈也能起到和第一种方法相同的功能。代码和的解答如下:

[code lang=”cpp” collapse=”true”]
//递归版迷宫问题
struct point{int row, col;} stack[512];
int top = 0;
int MAX_ROW=5, MAX_COL=5;
int maze[5][5] = {
0,1,0,0,0,
0,1,0,1,0,
0,0,0,0,0,
0,1,1,1,0,
0,0,0,1,0,
};
void push(struct point p)
{
stack[top++] = p;
return;
}
struct point pop()
{
return stack[–top];
}
int is_empty()
{
return top == 0;
}
void print_maze()
{
int i,j;
for(i=0;i<MAX_ROW;i++)
{
for(j=0;j<MAX_COL;j++)
printf("%d",maze[i][j]);
putchar(‘\n’);
}
}
struct point predecessor[5][5] = {
{{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1}},
{{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1}},
{{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1}},
{{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1}},
{{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1}},
};
void visit (int row, int col, struct point pre)
{
maze[row][col] = 2;
predecessor[row][col] = pre;
}
void tranverse_maze(struct point& p)
{
std::cout<<"———"<<std::endl;
print_maze();
std::cout<<"———"<<std::endl;
std::cout<<p.row<<","<<p.col<<std::endl;
if(p.row == MAX_ROW -1 && p.col == MAX_COL -1)
{
return;
} else if (p.row+1<=MAX_ROW -1 && maze[p.row+1][p.col] == 0) {
visit(p.row+1,p.col,p);
p.row++;
tranverse_maze(p);
} else if (p.col-1>=0 && maze[p.row][p.col-1] == 0) {
visit(p.row,p.col-1,p);
p.col–;
tranverse_maze(p);
} else if (p.row-1>=0 && maze[p.row-1][p.col] == 0) {
visit(p.row-1,p.col,p);
p.row–;
tranverse_maze(p);
} else if (p.col+1<=MAX_COL-1 && maze[p.row][p.col+1] == 0) {
visit(p.row,p.col+1,p);
p.col++;
tranverse_maze(p);
} else {
p.row=predecessor[p.row][p.col].row;
p.col=predecessor[p.row][p.col].col;
tranverse_maze(p);
return;
}
}
int main()
{
print_maze();
struct point p = {0,0};
int MAX_ROW = 5;
int MAX_COL = 5;
maze[p.row][p.col] = 2;
tranverse_maze(p);
if(p.row == MAX_ROW -1 && p.col == MAX_COL -1) {
printf("(%d,%d)\n",p.row,p.col);
while(predecessor[p.row][p.col].row != -1) {
p = predecessor[p.row][p.col];
printf("(%d,%d)\n",p.row,p.col);
}
} else {
printf("No Path\n");
std::cout<<"———"<<std::endl;
std::cout<<p.row<<","<<p.col<<std::endl;
}
return 0;
}
[/code]

运行结果如下:
2


文章来源:胡旭个人博客 => 广度优先搜索算法队解迷宫问题

参考文章:http://blog.csdn.net/feliciafay/article/details/9624909

转载请注明出处,违者必究!

Share:

Leave a Reply

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.