迷宫最优路径搜索
作者:tyc611.cublog.cn,2008-11-4
【问题描述】
有一个用矩阵描述的迷宫,矩阵元素取值0或1(0表示可以进入,1表示不能进入)。现在要找到一条从最左上角到最右下角的最短路径(最左上角和最右下角的矩阵元素均为0)。
比如,对于如下4*4矩阵描述的迷宫:
0, 0, 0, 0,
1, 0, 1, 0,
0, 0, 1, 0,
0, 1, 0, 0,
0, 0, 0, 0
它的最短路径为8(路径上所有位置数),移动方向依次为:右、右、右、下、下、下、下。
【问题分析】
这里,可以把矩阵各元素及可移动的方向看成一个无向图,如果可以从一个位置向上、下、左、右方向移动(相应的矩阵元素值为0),则相当于图中的一条边。因此,可以用图的宽度最优搜索来查找最短路径。
C++实现如下:
#include
#include
#include
#include
using namespace std;
// 查找从迷宫左上角到右下角的最优路径(路径最短)
// 利用图的宽度优先搜索(层次遍历)实现
int SearchMaze(int *A, int m, int n, vector &path)
{
// 迷宫位置类型
typedef pair Position;
// 移动操作类型
typedef unsigned char MoveType;
const MoveType UNVISITED = 'N'; // 未访问
const MoveType START = 'S'; // 起点
const MoveType UP = 'U'; // 向上
const MoveType RIGHT = 'R'; // 向右
const MoveType DOWN = 'D'; // 向下
const MoveType LEFT = 'L'; // 向左
// 用于暂存位置的队列
queue posQueue;
// 标记,用于区分层次遍历的各层,以便计算路径长度
Position tag(-1, -1);
// 目标位置
Position target(m - 1, n - 1);
// 状态数组,用于记录迷宫的每个位置是否已经访问
vector state(m * n, UNVISITED);
// 标记能否到达目标位置
bool succeed = false;
// 把起始位置压入队列,开始搜索
posQueue.push(make_pair(0, 0));
posQueue.push(tag);
int pathLength = 1;
state[0] = START;
// 搜索目标位置
while (!posQueue.empty()) {
Position cur = posQueue.front();
posQueue.pop();
if (cur == target) {
// 找到目标位置
succeed = true;
break;
}
if (cur == tag) {
// 本层遍历结束,进入下一层
if (!posQueue.empty()) {
++pathLength;
posQueue.push(tag);
}
continue;
}
// 从当前位置向上、下、左、右搜索
int i = cur.first;
int j = cur.second;
int index;
// 向上
index = (i - 1) * n + j;
if (i > 0 && A[index] == 0 && state[index] == UNVISITED) {
posQueue.push(Position(i - 1, j));
state[index] = UP;
}
// 向右
index = i * n + j + 1;
if (j < n - 1 && A[index] == 0 && state[index] == UNVISITED) {
posQueue.push(Position(i, j + 1));
state[index] = RIGHT;
}
// 向下
index = (i + 1) * n + j;
if (i < m - 1 && A[index] == 0 && state[index] == UNVISITED) {
posQueue.push(Position(i + 1, j));
state[index] = DOWN;
}
// 向左
index = i * n + j - 1;
if (j > 0 && A[index] == 0 && state[index] == UNVISITED) {
posQueue.push(Position(i, j - 1));
state[index] = LEFT;
}
}
if (succeed) {
// 能够到达目标位置,输出移动操作序列
path.clear();
path.reserve(pathLength);
int i = m - 1;
int j = n - 1;
int index = i * n + j;
for (; state[index] != START; index = i * n + j) {
assert(state[index] != UNVISITED && "不可能是未访问位置!");
path.push_back(state[index]);
switch (state[index])
{
case UP:
++i;
break;
case RIGHT:
--j;
break;
case DOWN:
--i;
break;
case LEFT:
++j;
break;
}
}
reverse(path.begin(), path.end());
return pathLength;
}
return -1;
}
int main()
{
const int m = 8;
const int n = 8;
int A[m * n] = {
0, 0, 0, 0, 1, 0, 0, 0,
1, 0, 1, 0, 0, 0, 1, 0,
0, 0, 1, 0, 1, 0, 1, 0,
0, 1, 1, 0, 0, 0, 1, 0,
0, 0, 0, 0, 1, 1, 0, 0,
0, 1, 1, 0, 0, 0, 0, 1,
0, 0, 0, 0, 1, 0, 1, 1,
1, 0, 0, 0, 1, 0, 0, 0,
};
vector path;
int length = SearchMaze(A, 8, 8, path);
if (length > 0) {
cout << "Shortest path length: " << length << endl;
cout << "The Path: ";
copy(path.begin(), path.end(), ostream_iterator(cout));
cout << endl;
} else {
cout << "Can't reach the destination!" << endl;
}
}
程序运行结果:
Shortest path length: 15
The Path: RRRDDDDDRRDDRR
阅读(2182) | 评论(1) | 转发(0) |