首页 > 代码库 > 数据结构与算法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)