小算法系列-迷宫最短路径 - amialy的专栏
- 博客频道 - CSDN.NET
1072人阅读
这个实现方法非常好，不但找出路径还找出了最短路径。使用“权值”方法来判断，简洁清楚，很喜欢，收藏～
有一个二维数组，0表示路，-1表示墙，求其中任意两点的最短路径。
我们先看，怎么求一条路径：求两点路径是一个数据结构上的典型的迷宫问题，很多数据结构的书上都有介绍，解决办法如下：
从一点开始出发，向四个方向查找，每走一步，把走过的点的值+1(即本节点值+1)，防止重复行走，并把走过的点压入堆栈(表示路径)，如果遇到墙、或者已走过的点则不能前进，如果前方已经无路可走，则返回，路径退栈，这样递归调用，直到找到终点为止。
迷宫如下图所示：&
从(2, 1)到(6, 8)，程序如下所示：
struct&Postion{&&&&int&_X,&_Y;&&&&Postion() {}&&&&Postion(int&X,&int&Y)&&&&&&&&:&_X(X),&_Y(Y) {}};bool&isCanGo(const&int&prePosValue,&&&&&&&&&&&&&const&int&posX,&&&&&&&&&&&&&const&int&posY){&&&&if&(&&&posX&&&0&||&posX&&&9&&&&&&&&//&越界&&&&&&&&||&posY&&&0&||&posY&&&9&&&&&&&&&&&&&&&&||&maze[posX][posY]&==&-1&&&&//&墙&&&&&&&&||&maze[posX][posY]&&=&1)&&&&//&走过&&&& {&&&&&&&&return&false;&&&&}&&&&return&true;}stack&Postion&&path__;&&&&&&&&&&&&//路径&&&&&&&&Postion&offset[4];&&&&&&&&&&&&&&&&//路径bool&shortestPath(stack&Postion&&&path,&&&&&&&&&&&&&&&&&&const&Postion&&start,&&&&&&&&&&&&&&&&&&const&Postion&&end){&&&&if&(&&&start._X&==&end._X&&&&&&&&&&&&start._Y&==&end._Y)&&&& {&&&&&&&&path__&=&&&&&&&&&return&true;&&&&}&&&&&&&&for&(int&i&=&0;&i&&&4;&i++)&&&& {&&&&&&&&int&nNextPos_X&=&start._X&+&offset[i]._X;&&&&&&&&int&nNextPos_Y&=&start._Y&+&offset[i]._Y;&&&&&&&&if&(isCanGo(maze[start._X][start._Y],&nNextPos_X,&nNextPos_Y))&&&&&&&& {&&&&&&&&&&&&maze[nNextPos_X][nNextPos_Y]&=&maze[start._X][start._Y]&+&1;&&&&&&&&&&&&path.push(Postion(nNextPos_X,&nNextPos_Y));&&&&&&&&&&&&if&(shortestPath(path,&Postion(nNextPos_X,&nNextPos_Y),&end))&&&&&&&&&&&&&&&&return&true;&&&&&&&&&&&&path.pop();&&&&&&&&}&&&&}&&&&return&false;}int&main(int&argc,&char*&argv[]){&&&&offset[0]._X&=&-1;&&&&offset[0]._Y&=&0;&&&&//&上&&&&offset[1]._X&=&1;&&&&offset[1]._Y&=&0;&&&&//&下&&&&offset[2]._X&=&0;&&&&offset[2]._Y&=&-1;&&&&//&左&&&&offset[3]._X&=&0;&&&&offset[3]._Y&=&1;&&&&//&右&&&&printMat(maze);&&&&Postion&start(2,&1),&end(6,&8);&&&&maze[start._X][start._Y]&=&1;&&&&&&&&&&&&//&置起点值1,&防止走回起点&&&&shortestPath(stack&Postion&(),&start,&end);&&&&printPath(path__);&&&&printMat(maze);&&&&return&0;}
这时，我们经过运算，到达终点，有44步之多。如果我们调整调用offset的顺序，即先左右，后上下，可能会得到更短的路径，但无法确保在任何情况下都能得到最短路径。
得到最短路径的方法，解决方法如下：
每走一步，就对前方的节点赋值为此节点+1，走过的路径也可以重复行走。但有一个条件，就是本节点+1必须小于已走过的节点的权值(墙不能走)，这样走遍所有的节点，记录最短的路径。
主要修改了以下两个函数：
bool&isCanGo(const&int&prePosValue,&&&&&&&&&&&&&const&int&posX,&&&&&&&&&&&&&const&int&posY){&&&&if&(&&&posX&&&0&||&posX&&&9&&&&&&&&//&越界&&&&&&&&||&posY&&&0&||&posY&&&9&&&&&&&&&&&&&&&&||&maze[posX][posY]&==&-1)&&&&//&墙&&&& {&&&&&&&&return&false;&&&&}&&&&if&(maze[posX][posY]&==&0)&&&&//&未走过&&&&&&&&return&true;&&&&else&&&&&&&&&&&&&&&&&&&&&&&&//&更近的路径&&&&&&&&return&(prePosValue&+&1)&&&maze[posX][posY];}void&shortestPath(stack&Postion&&&path,&&&&&&&&&&&&&&&&&&const&Postion&&start,&&&&&&&&&&&&&&&&&&const&Postion&&end){&&&&if&(&&&start._X&==&end._X&&&&&&&&&&&&start._Y&==&end._Y)&&&& {&&&&&&&&if&(path.size()&&&path__.size()&||&path__.empty())&&&&//&更短的路径&&&&&&&&&&&&path__&=&&&&&&&&&return;&&&&}&&&&&&&&for&(int&i&=&0;&i&&&4;&i++)&&&& {&&&&&&&&int&nNextPos_X&=&start._X&+&offset[i]._X;&&&&&&&&int&nNextPos_Y&=&start._Y&+&offset[i]._Y;&&&&&&&&if&(isCanGo(maze[start._X][start._Y],&nNextPos_X,&nNextPos_Y))&&&&&&&& {&&&&&&&&&&&&maze[nNextPos_X][nNextPos_Y]&=&maze[start._X][start._Y]&+&1;&&&&&&&&&&&&path.push(Postion(nNextPos_X,&nNextPos_Y));&&&&&&&&&&&&shortestPath(path,&Postion(nNextPos_X,&nNextPos_Y),&end);&&&&&&&&&&&&path.pop();&&&&&&&&}&&&&}}
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：5437次
排名：千里之外
原创：10篇数据结构课程设计_迷宫问题1 精心收集的各类精品文档，欢迎下载使用
扫扫二维码，随身浏览文档
手机或平板扫扫即可继续访问
数据结构课程设计_迷宫问题1
举报该文档为侵权文档。
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由：
将文档分享至：
分享完整地址
文档地址：
粘贴到BBS或博客
flash地址：
支持嵌入FLASH地址的网站使用
html代码：
&embed src='/DocinViewer-4.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布，请您等待！
3秒自动关闭窗口迷宫最短路径问题新算法
扫扫二维码，随身浏览文档
手机或平板扫扫即可继续访问
迷宫最短路径问题新算法
举报该文档为侵权文档。
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由：
将文档分享至：
分享完整地址
文档地址：
粘贴到BBS或博客
flash地址：
支持嵌入FLASH地址的网站使用
html代码：
&embed src='/DocinViewer-4.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布，请您等待！
3秒自动关闭窗口迷宫最短路径_百度知道
迷宫最短路径
/* 当前位置不是墙壁并且没走过 */\pos.top&gt,
if(S;}int Push(SqStack *pS,e,0;
printf(&quot,0;%2d &quot,0;* 打印出整个迷宫;elem[pS-&
return 1;0);
*pe = pS-&n&quot,1，0表示墙壁 */
&#47.j]==1) {
/top - 1,1;n&#92,0;top==StackSize-1)
&#47,0.i][pos,0;
InitStack(&S),0}下面程序如何修改为最短路径.di++.n&quot.i][pos,0};
if (e,1,1,
{0;top+1;top=0,1;
int di,ElemType e){
if (pS-&gt,1,1,1;&#47.i--;
printf(&quot？#include &quot,1,0;* 设定当前位置是该方向上的相邻块“右下左上” *&#47,
{0;),0;10,0}
else if (e，求得的路径放在栈中 *&#47.i==pos_end.
int maze[10][10]={
while(Pop(&S,0,1.pos,j.j--，退出循环; /* top指向栈顶的上一个元素 *&#47,&e);typedef struct {
ElemType elem[StackSize];top==0)
maze[}int Pop(SqStack *pS,0;n&quot,0.i &&* 离散迷宫矩阵.pos.j)
&#47.di&lt,0，-1是走过的不通的路径 */
pS-&gt,e);j&* 留下不能通过的标记,1,
return 0; Push(&S,0,1;
pS-&gt,pos_end,1,1,1;
getch(),0,0}.pos,0;
if (pos,1,1.di==4 && S,0;* 求得的路径放在栈中 */;
while(e,1,
{0;top]=e,1.di==2) pos.i;* 下一个位置是当前位置的右邻 *&#47,1;
&#47,1,0.j]=-1;* 加入路径 *&#47,1.pos.j]=2.j=8;);top=pS-&}SqStack,ElemType* pe){
if (pS-&gt,1,1;4){
e,1;i++) {
return 1;.j;&#92,0;&#92,0,0,
{0,0,1.pos = pos,%d)&quot.i=e,e).top&gt，2的是所找到的路径,0},0;
pos_end.i][e;0){
Pop(&S;InitStack(SqStack *pS){
return 0;* 栈满 *&#47.di==4) pos,0}.top&gt,0;* 标记已走过 *&#47,1;
else if (e;
int i,1;}main(){
SqStack S,e;
ElemType e,maze[i][j]).j==pos_end,
if (e;elem[pS-&gt，并退回一步 *&#47,
&#47,0,1,0.j=e.i=8;10,0};
pS-&* 换下一个方向搜索 *&#47,0;n(%d;
for(i=0;0){
maze[e.di==3) pos.h&quot,1,1;pos_
&#47,1;top = pS-&gt,0;
PosType pos,
pos,0},1;* 如果已经到达终点;j++)
printf(&quot,1,1,0};
Push(&S,1,1;
Pop(&S;),1;i&lt.i=1; pos,1;#define StackSize 100typedef struct{
int i,1,1,0,1,1,1.j).j=1,0};
}while(S;* 栈空 */
if (maze[typedef struct{
PosT}PosType.i.di = 1;&#47.i++;
&#47,0,0,0,&e);} ElemT* 当前位置不能通过 *&#47,0,j;stdio
1）被置为1，2）被加入队列中。[迷宫老鼠] 使用F I F O分枝定界。（3，1）将会被取出。为避免再次回到这两个位置，3）和（3。节点（1，1）被加入队列中用堆栈不一定能得出最短路径，2）从队列中移出并被扩充，改用队列可以实现最短路径，所以此节点即被删除，即迷宫的出口，1）置为1，1）被删除，2）和（2，2）变为新的E-节点，1）展开，1）加入到队列中（即活节点表），而下一个E-节点（2，将其加入队列，以免再次返回到这个位置，3）是可行的移动（剩余的两个节点是障碍节点），1）作为E-节点且活动队列为空，总能找出从迷宫入口到出口的最短路径，所得到的迷宫状态如图17-1b 所示，1）被扩充，它的相邻节点（1。（1，展开此节点后，1）两个节点。节点（3，而（3，2）和（2，1）被置为1，节点（2，当此节点被展开时，所得到的迷宫如图17-1c 所示，2）被删除，由于此节点不能到达任何新的节点，到达节点（3。1
0c）节点（1。迷宫的位置（1 ，节点（3，只有（1，将队列清空。随后节点（1，并把相应的迷宫位置置为1。使用F I F O搜索，下面是《数据结构算法与应用-C++语言描述》里面的一段话，1）被删除，1）成为新的E-节点，初始时取（1。检查它的三个相邻节点（见图1 6 - 1的解空间），节点（3，3）变成下一个E-节点。此时队列中包含（1，节点（3，将位置（ 1，（3，3）
其他类似问题
您可能关注的推广
最短路径的相关知识
等待您来回答
下载知道APP
随时随地咨询
出门在外也不愁迷宫问题_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
评价文档：
&&¥1.00
喜欢此文档的还喜欢
题​目​：​假​设​迷​宫​由​m​行​n​列​构​成​,​有​一​个​入​口​和​一​个​出​口​,​入​口​坐​标​为​(,)​,​出​口​坐​标​为​(​m​,​n​)​,​试​找​出​一​条​从​入​口​通​往​出​口​的​最​短​路​径​。​设​计​算​法​并​编​程​输​出​一​条​通​过​迷​宫​的​最​短​路​径​或​报​告​一​个​“​无​法​通​过​”​的​信​息​。​
​
​要​求​：​用​栈​和​队​列​实​现​,​不​允​许​使​用​递​归​算​法​
​
​这​个​程​序​没​有​主​界​面​供​用​户​选​择​,​如​果​需​要​可​以​看​我​的​另​外​一​个​文​档​“​迷​宫​问​题”
阅读已结束，如果下载本文需要使用
想免费下载本文？
把文档贴到Blog、BBS或个人站等：
普通尺寸(450*500pix)
较大尺寸(630*500pix)
你可能喜欢