首页 > 代码库 > 数据结构与算法4: 经典问题之迷宫问题(Maze path)

数据结构与算法4: 经典问题之迷宫问题(Maze path)

数据结构与算法4: 经典问题之迷宫问题(Maze path)

写在前面

               本节实践了教材[1][2]的两种经典迷宫算法。注意体会栈的运用。如果有改进意见请帮助我。

              


1.迷宫问题直观感受

   下面给出迷宫问题的一个直观感受图,引入图只是为了帮助直观理解,这里不涉及OpenGL等其他绘图内容。

     下图中棕色代表通道阻塞,白色代表可用通道,红色代表起始位置,绿色代表当前位置,黄色代表出口。

     (采用C++ 和OpenGL 绘制,目前是2D版本,3D版本有空时再补上)

          迷宫1:

            

               

          迷宫2:

                    

2.迷宫算法

2.1 迷宫初始化

    无论是2D还是3D的迷宫表达当期位置,是通道还是出口入口,其实都可以用一个二维字符数组表达。

      用二维字符数组来表达迷宫地图,这种思想来自[1],我觉得他很重要,反映了迷宫的本质。

      例如上述迷宫1,地图文件如下,解释见下文:

11111111111
10000010001
10100010101
e0100000101
10111110101
10101000101
10001010001
11111010001
101m1010001
10000010001
11111111111

例如上述迷宫2,地图文件如下:

1111111111
1m01000101
1001000101
1000011001
1011100001
1000100001
1010001001
1011101101
11000000e1
1111111111

下面的实现过程中,我采用的方法是,定义一个数组存贮每个单元格(Cell),每个单元格里面存储着字符,字符定义如下:

‘1‘ :代表通道阻塞,不可用

‘0‘ :代表可用通道

‘m‘ :起点(原意是指一只老鼠)

‘e‘: 出口

‘.‘ : 点号,代表已经访问过的点

基础结构定义如下:

class Pos2D
{
public:
	Pos2D()
	{
		row = col = 0;
	}
    Pos2D(int r,int c)
	{
		row = r,col = c;
	}
	bool operator != (const Pos2D& pos)
	{
		return !(*this == pos);
	}
	bool operator == (const Pos2D& pos)
	{
		return this->row == pos.row 
			&& this->col == pos.col;
	}
    
public:
	const static Pos2D NotAvailablePos;
    int row,col;
};

struct Cell
{
	Pos2D pos;
	char content;	// 'm' startpos '0' represents passage,'1' blocked,'e' exit,'.' visited
	int  triedTime;
};

Maze代表迷宫类,包含数据结构:

class Maze
{
//for convenient we set it to public
public:
	static const char ENTRY_CONTENT = 'm',EXIT_CONTENT='e',BLOCKED_CONTENT='1',PASSAGE_CONTENT='0',VISITED_CONTENT='.';
	Cell *cellArray;  //array to store cells
	int rowCnt,colCnt;// map file row and col count
	Pos2D startPos,exitPos; 
};

cellArray保存所有的单元格节点,rowCnt和colCnt代表地图文件的行数和列数。

2.2算法1

   
   教材【1】提供的算法一的基本思想:

      首先将入口设为当前位置;然后从当前位置出发,按照固定顺序(例如:右左上下顺序)探测第一个可用下一个单元,然后将这下一个单元设为当前单元,重复探测,直至遇到出口;如果探测的过程中发现,在当前节点,无论右左上下哪个位置都不能到达下一个可用位置,则退回到当前节点的上一个节点,将上一个节点设为当前单元,继续探测。依次类推。

       这里注意几点:

      1)每个走过的单元,必须标记为已经走过,后面不能再重复走。

         因为走过的单元, 分为两种,第一种可以找到出口的,那么你再次走回来,可能陷入同一段路径的循环,

          比如  A->B->C->A->B->C。我们要消除这种重复路径。

         第二种,是不能找到出口的,既然第一次走过就不能找到出口,为什么还要走第二次?

        所以,走过的单元不能再重复的走。

      2)每次从单元格四个方向中选个一个可用单元,要保持对这四个方向的计数,上次尝试过得方向,下一次就不能重复再试了,反 证法可以说明。

    3)程序出口问题,要么是试验后找到路径,这时栈里保存的就是整个路径;要么是找不到路径,那么栈为空,因为你不断回退,最后到了起点,起点还是没有路径,因此退栈后即为空栈。

提醒注意的是,实际实现迷宫判断算法代码都要以下列出的简单;为了给出路径信息,我在代码中添加了多处辅助代码。

算法一种实现为:

从四个方向中找第一个可用单元:

//find first avaliable pos
Pos2D Maze::getFirstAvailablePos(Pos2D curPos)
{   
	int row = curPos.row,col = curPos.col;
	int triedTime =  cellArray[row*colCnt+col].triedTime;
	Pos2D firstAvailPos = Pos2D::NotAvailablePos;
	Pos2D nextPosArray[] = {
		 Pos2D(row,col+1),Pos2D(row,col-1)	//right and left
		,Pos2D(row+1,col),Pos2D(row-1,col)	//down and up
	};
	if(triedTime == 4)
		return Pos2D::NotAvailablePos;
	// try in right left down up order
	bool bfind = false;
	while(triedTime < 4)
	{
		 firstAvailPos = nextPosArray[triedTime];
		 Cell& nextCell = cellArray[firstAvailPos.row*colCnt+firstAvailPos.col];	
		 if(nextCell.content == Maze::PASSAGE_CONTENT || nextCell.content == Maze::EXIT_CONTENT)
		 {
			 bfind = true;
			 break;
		 }
		 triedTime++;
	}
	cellArray[row*colCnt+col].triedTime = triedTime; //update tried time
	if(bfind)
		return firstAvailPos;
	else
		return  Pos2D::NotAvailablePos;
}
bool Maze::getoutOfMaze(pair<list<Pos2D>,list<Pos2D>>& resultPair)
{
	Pos2D curPos = startPos;
	bool bfind = false;
	stack<Pos2D> posStack;
	resultPair.second.push_front(curPos);
	do
	{   
		Cell& curNode = cellArray[curPos.row*colCnt+curPos.col];
		cellArray[curPos.row*colCnt+curPos.col].content = Maze::VISITED_CONTENT; //marked as visited 
		//try at most four time(right left down up) to find a available neighbour node
		Pos2D nextAvailablePos = getFirstAvailablePos(curPos);
		if(nextAvailablePos != Pos2D::NotAvailablePos)
		{   
			if(nextAvailablePos == exitPos) // successfully found path
			{
				resultPair.first.push_front(exitPos);
				resultPair.first.push_front(curPos);
				while(!posStack.empty())
				{
					resultPair.first.push_front(posStack.top());
					posStack.pop();
				}
				resultPair.second.push_back(exitPos);
				bfind = true; 
				break;
			}
			posStack.push(curNode.pos); // push current pos to stack
			curPos = nextAvailablePos;	// set the next available pos as current pos
			resultPair.second.push_back(curPos);
		}else
		{   
			//pop until we find a node has chance to try
			while(curNode.triedTime == 4 && !posStack.empty())
			{
				curPos = posStack.top();
				posStack.pop();
				curNode = cellArray[curPos.row*colCnt+curPos.col];
				resultPair.second.push_back(curPos);
			}
			if(posStack.empty())
			{   
				bfind = false; 
				break;
			}
		}
	}
	while (!posStack.empty());

    return bfind;
}

上述函数的参数pair<list<Pos2D>,list<Pos2D>>& resultPair,是一对保存两个单元格位置链表的,第一个链表用于保存搜索到的路径,第二个链表保存搜索过程中经过的单元的整个过程描述。

例如执行地图1的过程为:

input maze map file name:
map1.txt

---Finding Process---
(8,3)   (9,3)   (9,4)   (9,5)   (8,5)   (7,5)   (6,5)   (5,5)   (5,6)   (5,7)
(6,7)   (6,8)   (6,9)   (7,9)   (7,8)   (7,7)   (8,7)   (8,8)   (8,9)   (9,9)
(9,8)   (9,7)   (9,8)   (9,9)   (8,9)   (8,8)   (8,7)   (7,7)   (7,8)   (7,9)
(6,9)   (5,9)   (4,9)   (3,9)   (2,9)   (1,9)   (1,8)   (1,7)   (2,7)   (3,7)
(3,6)   (3,5)   (3,4)   (3,3)   (2,3)   (2,4)   (2,5)   (1,5)   (1,4)   (1,3)
(1,2)   (1,1)   (2,1)   (3,1)   (3,0)
---Sum: 54 steps---
Get out by :
(8,3)           (9,3)           (9,4)           (9,5)           (8,5)
(7,5)           (6,5)           (5,5)           (5,6)           (5,7)
(6,7)           (6,8)           (6,9)           (5,9)           (4,9)
(3,9)           (2,9)           (1,9)           (1,8)           (1,7)
(2,7)           (3,7)           (3,6)           (3,5)           (3,4)
(3,3)           (2,3)           (2,4)           (2,5)           (1,5)
(1,4)           (1,3)           (1,2)           (1,1)           (2,1)
(3,1)           (3,0)

例如执行地图2的过程为:

input maze map file name:
map2.txt

---Finding Process---
(1,1)   (1,2)   (2,2)   (2,1)   (3,1)   (3,2)   (3,3)   (3,4)   (2,4)   (2,5)
(2,6)   (1,6)   (1,5)   (1,4)   (1,5)   (1,6)   (2,6)   (2,5)   (2,4)   (3,4)
(3,3)   (3,2)   (3,1)   (4,1)   (5,1)   (5,2)   (5,3)   (6,3)   (6,4)   (6,5)
(7,5)   (8,5)   (8,6)   (8,7)   (8,8)
---Sum: 34 steps---
Get out by :
(1,1)           (1,2)           (2,2)           (2,1)           (3,1)
(4,1)           (5,1)           (5,2)           (5,3)           (6,3)
(6,4)           (6,5)           (7,5)           (8,5)           (8,6)
(8,7)           (8,8)


2.3 算法2

      算法一比较好理解,符合我们常规思路,算法而更简洁,但是理解起来相对难些。

     教材【2】提供的算法2思路如下:

                 将入口设为当前位置。每次从当前位置开始,将其邻近的可用单元(是通道并且没有经历过)全部入栈,然后将栈顶元素出栈作为新的当前位置,重复操作,直到当前位置为出口位置,则搜索成功。如果再没有找到出口之前,栈已经为空,则搜索路径失败。

     算法的注意点:对于这个算法而言,同一个单元可能多次入栈,但是当同一个单元第二次出栈时,由于第一次已经把邻近单元都尝试过了,所以这个不会有新的单元入栈,我把这种单元称为死单元

     以一个简单例子为例,说明本算法。

     地图7(跳过了中间好多的地图)如下:

      

1111111
1e00001
1110111
1000001
100m001
1111111

搜索过程如下:

input maze map file name:
map7.txt

---Finding Process---
(4,3)   (4,4)   (4,5)   (3,5)   (3,4)   (3,3)   (3,2)   (3,1)   (4,1)   (4,2)
(4,2)   (2,3)   (1,3)   (1,4)   (1,5)   (1,2)   (1,1)
---Sum: 16 steps---
Get out by :
(4,3)           (4,4)           (4,5)           (3,5)           (3,4)
(3,3)           (3,2)           (3,1)           (4,1)           (4,2)
(4,2)           (2,3)           (1,3)           (1,4)           (1,5)
(1,2)           (1,1)

     这个过程中,我们看到给出的路径之中,存在两个无用的尝试(3,2)-(3,1)-(4,1)-(4,2)-(4,2)和(1,4)-(1,5),这些都是本算法的一个特点,但是最终程序还是找到了路径。我们应该将这种无用路径从最终结果中删除,我们怎么样确定哪些路径无用呢?

笔者的观点,如果一个当前单元,它没有新的邻近单元入栈,说明这个单元为死单元,那么应该将它之前的一段删除,那么删除到什么时候停止呢? 删除到与下一个节点,能一步达到的那个路径节点位置。举例来说:

我们发现(1,5)是个死单元,那么当前单元为(1,5)时栈顶为(1,2),回溯回去发现(1,3)节点可以一步到达(1,2)因此需要删除(1,4)和(1,5)两个节点。按照这种思路,给出了包含删除无效路径的算法2一种实现

//push all Neighbour available pos
bool Maze::pushAllNeighbourCellStack(stack<Pos2D> &posStack,Pos2D curPos)
{
	int row = curPos.row,col = curPos.col;
	Pos2D nextPosArray[] = {
		Pos2D(row-1,col),Pos2D(row+1,col)	//up and down
		,Pos2D(row,col-1),Pos2D(row,col+1)	//left and right
	};
	bool bfind = false;
	for(int i =0;i < 4;i++)
	{    
		Pos2D nextPos = nextPosArray[i];
		Cell& nextCell = cellArray[nextPos.row*colCnt+nextPos.col];	
		if(nextCell.content == Maze::PASSAGE_CONTENT 
			|| nextCell.content == Maze::EXIT_CONTENT)
		{   
			bfind = true;
			posStack.push(nextPos);
		}
	}
	return bfind;
}
//check if two pos can reach in one step
bool Maze::is2PosNeighbour(Pos2D& fisrtPos,Pos2D& secondPos)
{   
	bool bNeighbour = false;
	if(fisrtPos.row == secondPos.row)
	{
		if(fisrtPos.col-secondPos.col ==1 || fisrtPos.col-secondPos.col ==-1)
			bNeighbour = true;
	}else if(fisrtPos.col == secondPos.col)
	{
		if(fisrtPos.row-secondPos.row ==1 || fisrtPos.row-secondPos.row ==-1)
			bNeighbour = true;
	}
	return bNeighbour;
}
bool Maze::getoutOfMaze2(pair<list<Pos2D>,list<Pos2D>>& resultPair)
{
	Pos2D curPos = startPos;
	stack<Pos2D> posStack;
	bool bfind = false;
	while(curPos != Maze::exitPos )
	{   
		cellArray[curPos.row*colCnt+curPos.col].content = Maze::VISITED_CONTENT;
		bfind = pushAllNeighbourCellStack(posStack,curPos);
		if(posStack.empty())
		{
			return false;
		}else
		{   
			resultPair.second.push_back(curPos);
			if(bfind)
			{
				resultPair.first.push_back(curPos);
			}else  //dead cell,modify the path
			{   
				std::list<Pos2D>::reverse_iterator rend = resultPair.first.rend();
				std::list<Pos2D>::reverse_iterator rbegin = resultPair.first.rbegin();
				list<Pos2D> removeList;
				removeList.push_front(curPos);
				Pos2D nextPos = posStack.top();
				while(rbegin != rend)
				{
					Pos2D& pos = *rbegin;
					if(is2PosNeighbour(nextPos,pos))
					{
						break;
					}
					else
					{   
						removeList.push_front(pos);
						resultPair.first.remove(pos);
					}
					rbegin = resultPair.first.rbegin();
				}
				std::cout<<"remove path: "<<std::endl;
				std::copy(removeList.begin(),removeList.end(),std::ostream_iterator<Pos2D>(std::cout,"\t\t"));
				std::cout<<std::endl;
			}
			curPos = posStack.top();
			posStack.pop();
		}
	}
	resultPair.second.push_back(exitPos);
	resultPair.first.push_back(Maze::exitPos);
	return true;
}

再次对上述地图7测试,结果如下:

input maze map file name:
map7.txt
remove path:
(4,2)
remove path:
(3,2)           (3,1)           (4,1)           (4,2)
remove path:
(1,4)           (1,5)

---Finding Process---
(4,3)   (4,4)   (4,5)   (3,5)   (3,4)   (3,3)   (3,2)   (3,1)   (4,1)   (4,2)
(4,2)   (2,3)   (1,3)   (1,4)   (1,5)   (1,2)   (1,1)
---Sum: 16 steps---
Get out by :
(4,3)           (4,4)           (4,5)           (3,5)           (3,4)
(3,3)           (2,3)           (1,3)           (1,2)           (1,1)


这次删除无效子路径后,给出的即为最简单路径。


3.无法找到出口路径的情况

例如地图4如下:

这种情况,黄色块代表的出口,被阻塞通道包围,是无法找到出口路径的,那么算法1测试结果如下:

input maze map file name:
map4.txt

---Finding Process---
(1,1)   (1,2)   (2,2)   (2,1)   (3,1)   (3,2)   (3,3)   (3,4)   (2,4)   (2,5)
(2,6)   (1,6)   (1,5)   (1,4)   (1,5)   (1,6)   (2,6)   (2,5)   (2,4)   (3,4)
(3,3)   (3,2)   (3,1)   (4,1)   (5,1)   (5,2)   (5,3)   (6,3)   (6,4)   (6,5)
(7,5)   (8,5)   (8,6)   (8,5)   (8,4)   (8,3)   (8,2)   (8,3)   (8,4)   (8,5)
(7,5)   (6,5)   (5,5)   (5,6)   (5,7)   (5,8)   (6,8)   (6,7)   (6,8)   (5,8)
(4,8)   (4,7)   (4,6)   (4,5)   (4,6)   (4,7)   (3,7)   (3,8)   (2,8)   (1,8)
(2,8)   (3,8)   (3,7)   (4,7)   (4,8)   (5,8)   (5,7)   (5,6)   (5,5)   (6,5)
(6,4)   (6,3)   (5,3)   (5,2)   (5,1)   (6,1)   (7,1)   (6,1)   (5,1)   (4,1)
(3,1)   (2,1)   (2,2)   (1,2)   (1,1)
---Sum: 84 steps---
No Path to get out!

算法2测试结果:

input maze map file name:
map4.txt
remove path:
(1,5)           (1,4)
remove path:
(2,5)           (2,6)           (1,6)           (1,5)
remove path:
(3,2)           (3,3)           (3,4)           (2,4)           (1,4)

remove path:
(8,6)
remove path:
(7,5)           (8,5)           (8,4)           (8,3)           (8,2)

remove path:
(6,8)           (6,7)
remove path:
(4,6)           (4,5)
remove path:
(1,8)
remove path:
(5,8)           (4,8)           (4,7)           (3,7)           (3,8)
(2,8)           (3,8)
remove path:
(6,7)
remove path:
(5,7)           (4,7)
remove path:
(5,6)           (4,6)
remove path:
(5,2)           (5,3)           (6,3)           (6,4)           (6,5)
(5,5)           (4,5)
remove path:
(4,1)           (5,1)           (6,1)           (7,1)
remove path:
(3,2)

---Finding Process---
(1,1)   (1,2)   (2,2)   (2,1)   (3,1)   (3,2)   (3,3)   (3,4)   (2,4)   (2,5)
(2,6)   (1,6)   (1,5)   (1,4)   (1,5)   (1,4)   (4,1)   (5,1)   (5,2)   (5,3)
(6,3)   (6,4)   (6,5)   (7,5)   (8,5)   (8,6)   (8,4)   (8,3)   (8,2)   (5,5)
(5,6)   (5,7)   (5,8)   (6,8)   (6,7)   (4,8)   (4,7)   (4,6)   (4,5)   (3,7)
(3,8)   (2,8)   (1,8)   (3,8)   (6,7)   (4,7)   (4,6)   (4,5)   (6,1)   (7,1)
(3,2)
---Sum: 50 steps---
No Path to get out!

算法1和算法2均表示,尝试后无法找到路径。


程序到这里写完了,关于迷宫问题还有很多思考,留待日后反思。


参考资料:

[1] 《数据结构与算法 c++版 第三版》   Adam Drozdek编著  清华大学出版社

[2]  《数据结构》  严蔚敏 吴伟明  清华大学出版社


数据结构与算法4: 经典问题之迷宫问题(Maze path)