随笔 - 89  文章 - 118  trackbacks - 0
<2016年5月>
24252627282930
1234567
891011121314
15161718192021
22232425262728
2930311234

留言簿(16)

随笔分类(56)

随笔档案(89)

文章分类

推荐博客

搜索

  •  

最新随笔

最新评论

阅读排行榜

有一个二维数组,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__ 
= 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(
21), end(68);
    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__ = 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();
        }

    }

}

 

 

我上传了两个工程,求一条路径的程序点此下载,求最短路径的程序点此下载

文章结束!愿它对您有所帮助。

posted on 2008-03-18 17:47 胡满超 阅读(8733) 评论(4)  编辑 收藏 引用

FeedBack:
# re: 迷宫最短路径问题解析 2009-02-24 11:33 胡满超
回复:
我想请问,如果将初始位置设为(9,9),末端位置设为(0,2),结果和设计预期有出入。这是怎么回事,怎么解决呢?
------------
(9,9)点为墙!算法忘记判断。  回复  更多评论
  
# re: 迷宫最短路径问题解析 2014-12-22 15:19 11
。。。。。。。。  回复  更多评论
  
# re: 迷宫最短路径问题解析 2016-04-16 20:09 rover
stack<Postion> path__;
这个里面 ”<> “符号是什么意思?我在C++语言里面没见过呢? 初学者,大神勿喷。  回复  更多评论
  
# re: 迷宫最短路径问题解析 2016-05-03 13:05 胡满超
@rover
这个是C++模板  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理