C++ 寻找最短路径

原创
2016/08/15 15:26
阅读数 650

    一次和同事讨论如何在很多有效点中找到一条路径可以从指定有效点,走到方格最下面的点。此处介绍一下何为有效点,在一个有很多小方格组成的大方格中,每个小方格都有一个特有的属性,1表示白色,0表示黑色。黑色的小方格表示有效点,白色表示无效点。我们的目标就是从从指定位置的黑方格开始寻找一条路径,路径由黑方格组成,即有效点组成,直到到达大方格最下面的有效点。

    我们最初的讨论算法思想是最基本的办法,每个点都有8个位置可走(左,右,上,下,左上,右上,左下,右下,其中有一个方向是到达该点的方向,不做计算,所以实际上是7个位置可走),其中有一个路径可走的判定条件,即只能走8个位置点中的有效点。首先,给八个点增加一个优先级属性,如果同时存在多个可走的方向,则最先走优先级最高的点。依次找点,直到找到出口,如果发现已无路可走,则向上回溯,查找上一个节点是否有其他的路径可走,依次类推,直到找到可走的路径。基本上的路径寻找就是:寻找下一个节点,如果有,则继续寻找下一个节点,如果没有,则退回当前点为父节点,寻找其他没有走的子节点,如果所有的子节点都走完了,则继续寻找该节点的父节点,依次查找,知道查遍所有的点,如果当前点没有父节点,并且没有可走的子节点,则判定失败。

    此方法的好处是逻辑比较简单,但是计算量很大,代码量也很大,并且还要先去建立树,设置优先级,比较繁杂,实现起来不太高效。有没有可能不用回溯就可以完成呢,即不走回头路呢,一次性的找到可能的出路呢?答案是肯定的,通过网上搜索关键词“走迷宫算法”,终于找到了一个可以解决这个问题的算法,接下来我来分析一个实现起来比较简单的算法。

    从一个点出发,寻找8个方向的可能的路径,每个点都同时出发,将所有离初始点距离相等的点组成兄弟节点,依次遍历这些兄弟节点,再次寻找这些兄弟节点的下一个节点,判断是否满足特定的退出条件,直到找到一个出口。原始的算法思想是:要保证走的路最短,前进过程中到达每个点所走的步数都是最少的.怎样达成这个条件呢.两点,第一,要多条路同时试着走,不能一条路走了不通再返回走别的路;第二,走到一个点,这个点就被占用了,不能再通过别的路走到这个点了.

我们首先设计一个Path类,首先增加一个step,表示到这一点时一共走了几步.还有增加两个指针,一个指针把一条路上的所走过的点连接起来,另一个指针把花费步数相同的所有点连接起来,即将兄弟节点都连接起来,这样一来就可以同时走好多条路了.px,py表示点的坐标,flag表示当前点的状态,findDes表示当前点和父节点的关系。

    int px;
	int py;
	int flag;    //0:不通  1:通   2:走过该点
	Path *fp;   //父指针,这是以后找路劲用的,只输出步数的话它就没什么用
	Path *bp;   //兄弟指针,通过它连在一起的点所花费的步数都相同
	int step;    //表示来到这里花了多少步
	string findDes;

 接下来,就要处理当前节点和子节点的关系,及兄弟节点的子节点和当前节点的关系。首先,我们设置当前节点的子节点为下一个执行的节点,然后将其他的节点与该下一个执行节点通过兄弟指针连接,可以保证通过该节点找到他的兄弟节点。

//设置当前节点的子节点,及该子节点的兄弟节点
void Path::AddChildBroNode(Path* pCur, Path* pBr,string findDes)
{
	this->findDes = findDes;
	this->step = pCur->step + 1;
	this->fp = pCur;
	this->flag = 2;
	//如果不相等,则已经有兄弟节点了,将之前的兄弟节点组合一个链表
	//如果相等,则说明该节点为当前节点的第一个字节点
	if (pBr->bp != pCur)
	{
		this->bp = pBr->bp;
	}
	
	pBr->bp = this;
}

最后,我们需要执行的真正的算法过程了。首先我们先遍历一下当前节点的所有下一个节点,保存这些节点的相关信息,包括确定下一个节点和兄弟节点的连接。

if (curx > 0 && ce[cury][curx - 1].flag == 0)  //向左查找
		{
			ce[cury][curx - 1].AddChildBroNode(pCurr, pBr,"L");			
		}

		if (curx>0&& cury < (iLm - 1) && ce[cury + 1][curx - 1].flag == 0)    //左下查找
		{
			ce[cury + 1][curx - 1].AddChildBroNode(pCurr, pBr,"LD");
		}

		if (curx < (iRm - 1) && ce[cury][curx + 1].flag == 0)  //向右查找
		{
			ce[cury][curx + 1].AddChildBroNode(pCurr, pBr,"R");		
		}

		if (curx < (iRm - 1)&& cury < (iLm - 1) && ce[cury + 1][curx + 1].flag == 0)  //右下查找
		{
			ce[cury + 1][curx + 1].AddChildBroNode(pCurr, pBr,"RD");
		}

		if (cury > 0 && ce[cury - 1][curx].flag == 0)   //向上查找
			ce[cury - 1][curx].AddChildBroNode(pCurr, pBr,"U");
		

		if (cury > 0 && curx < (iRm - 1) && ce[cury - 1][curx + 1].flag == 0)  //右上角
			ce[cury - 1][curx + 1].AddChildBroNode(pCurr, pBr,"RU");

		if (curx > 0 && cury > 0&& ce[cury - 1][curx - 1].flag == 0)   //左上角()
			ce[cury - 1][curx - 1].AddChildBroNode(pCurr, pBr,"LU");

		if (cury < (iLm - 1) && ce[cury + 1][curx].flag == 0)   //向下查找
		{
			ce[cury + 1][curx].AddChildBroNode(pCurr, pBr,"D");
		}

现在已经将当前节点的所有子节点找到并且相连为兄弟节点。最后一步就是遍历所有的兄弟节点的下一个节点,使其相连,并且确定下一个节点。

//遍历当前指针的所有兄弟
		if (pCurr->bp)
		{
			pCurr = pCurr->bp;
			curx = pCurr->px;
			cury = pCurr->py;
		}
		else if (pBr->fp == pBr->bp)     //从长兄开始,如果兄弟都没有子节点,则判定已经没有出路了
		{
			cout << "无路可逃了,重新规划路线" << endl;
			break;
		}
		else if (pCurr != pBr->bp)  //当前节点不是兄弟节点,则查找子节点
		{
			pCurr = pBr->bp;		
			curx = pCurr->px;
			cury = pCurr->py;
			pBr->fp = pCurr;
		}
		else        //当前节点为叶子节点了,则退出
		{
			cout << "无法走出迷宫,请检查数值是否正确" << endl;
			break;
		}

此处需要指出的是,当前的节点有两个退出条件,一个是当前节点没有子节点,二是当前节点和兄弟节点都没有子节点,此时,可退出程序执行,此路是死路了。

ok,到目前为止,我们的迷宫寻路算法就出来了,我们也要转变一种思维,就是人为和机器为的的区别,如果是人为的话,肯定一次只能找一条路,不可能同时找很多条路,所以拿到问题先要去分析一下,不是盲目的先去实践,这样只会更多的浪费实践。机器的好处时,比人脑的执行速度快,但最基本的思想却是出自人脑,所以,尽可能的多去尝试几种不同的解决方案,或许就能节省很多的时间和功夫,也能是自己成长的更快。

最后附上代码:

http://www.oschina.net/code/snippet_2609705_58605

展开阅读全文
打赏
0
1 收藏
分享
加载中
更多评论
打赏
0 评论
1 收藏
0
分享
返回顶部
顶部