给定一个迷宫，指明起点和终点，找出从起点出发到终点的有效可行路径，就是迷宫问题（maze problem）。
迷宫可以以二维数组来存储表示。0表示通路，1表示障碍。注意这里规定移动可以从上、下、左、右四方方向移动。坐标以行和列表示，均从0开始，给定起点（0,0）和终点（4,4），迷宫表示如下：
那么下面的迷宫就有两条可行的路径，分别为： （1）(0,0) (0,1) (0,2) (0,3) (0,4) (1,4) (2,4) (2,3) (3,3) (4,3) (4,4)； （2）(0,0) (1,0) (2,0) (3,0) (4,0) (4,1) (4,2) (4,3) (4,4) ；
可见，迷宫可行路径有可能是多条，且路径长度可能不一。
迷宫问题的求解可以抽象为连通图的遍历，因此主要有两种方法。
第一种方法是：深度优先搜索（DFS）加回溯。
其优点：无需像广度优先搜索那样（BFS）记录前驱结点。 其缺点：找到的第一条可行路径不一定是最短路径，如果需要找到最短路径，那么需要找出所有可行路径后，再逐一比较，求出最短路径。
第二种方法是：广度优先搜索（BFS）。 其优点：找出的第一条路径就是最短路径。 其缺点：需要记录结点的前驱结点，来形成路径。
下面将给出上面两种方法的具体步骤和实现。
3.1.1实现步骤
（1）给定起点和终点，判断二者的合法性，如果不合法，返回； （2）如果起点和终点合法，将起点入栈； （3）取栈顶元素，求其邻接的未被访问的无障碍结点。求如果有，记其为已访问，并入栈。如果没有则回溯上一结点，具体做法是将当前栈顶元素出栈。
其中，求邻接无障碍结点的顺序可任意，本文实现是以上、右、下、左的顺序求解。 （4）重复步骤（3），直到栈空（没有找到可行路径）或者栈顶元素等于终点（找到第一条可行路径）。
3.1.2具体实现
程序输出：path:(0,0) (0,1) (0,2) (0,3) (0,4) (1,4) (2,4) (2,3) (3,3) (4,3) (4,4)。
可见该条路径不是最短路径。因为程序中给定的迷宫还有一条更短路径为：(0,0) (1,0) (2,0) (3,0) (4,0) (4,1) (4,2) (4,3) (4,4) ；
如果我们调整调用寻找下一个未访问的相邻结点的顺序，可换成先左右，后上下，可能会得到更短的路径，但无法确保在任何情况下都能得到最短路径。
3.2.1改进办法
根据上面的方法我们可以在此基础之上进行改进，求出迷宫的最短的路径。具体做法如下： （1）让已经访问过的结点可以再次被访问，具体做法是将mark标记改为当前结点到起点的距离，作为当前结点的权值。即从起点开始出发，向四个方向查找，每走一步，把走过的点的值+1；
（2）寻找栈顶元素的下一个可访问的相邻结点，条件就是栈顶元素的权值加1必须小于下一个节点的权值(墙不能走，未被访问的结点权值为0)；
（3）如果访问到终点，记录当前最短的路径。如果不是，则继续寻找下一个结点；
（4）重复步骤（2）和（3）直到栈空（迷宫中所有符合条件的结点均被访问）。
3.2.2具体实现
程序输出最短路径如下：
如果将程序的迷宫改为如下:
输出：
代码相关说明： 对比3.1.2的代码，根据改进的办法，可以看到上段代码修改的地方主要有三个地方： （1）mark标记改为结点权值，记录起点到结点的路径长度。因此起点的权值为0。 （2）为适应mark标记，将迷宫的墙改为-1，以免与结点权值混淆。 （3）求解下一个访问的结点，判断条件是结点的权值要小于其当前权值。
广度优先搜索的优点是找出的第一条路径就是最短路径，所以经常用来搜索最短路径，思路和图的广度优先遍历一样，需要借助于队列。
具体步骤： （1）从入口元素开始，判断它上下左右的邻边元素是否满足条件，如果满足条件就入队列； （2）取队首元素并出队列。寻找其相邻未被访问的元素，将其如队列并标记元素的前驱节点为队首元素。 （3）重复步骤（2），直到队列为空（没有找到可行路径）或者找到了终点。最后从终点开始，根据节点的前驱节点找出一条最短的可行路径。
具体实现： 以C++为例：
程序输出：
代码的几点说明： （1）BFS求迷宫最短路径，记录每个节点的前驱节点使用了mark标记。可见，三种方法中mark标记可以根据实际需求灵活为其赋予意义。 （2）特殊的，起始节点的前驱设置为其本身。
告诫。看着别人的代码去理解问题是如何求解的，对于求解算法题来说，这种方法是错误的。正确的步骤是看别人的思路，理解如何求解后，给出自己的实现，才能够真正的深刻的掌握该题的求解。经过自己思考的才能真正成为自己的东西。不然的话，看着别人的代码痛苦不说，而且每个人的实现在很多细节都不相同，即是花了很长时间，暂时弄明白了，我想过不了多久就会忘记。这样，得不偿失啊！
[1] [2]
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/163243.html