Yukang's Page

走出迷宫-路径搜索

2010-07-22

上次把那个迷宫弄出来,然后想了想解法,找了些资料。再把界面上弄了一下,右边迷宫大小,然后有一个选项percent,是代表要推倒的墙占的总百分比,如果数字越小生成的迷宫就越稀疏,有可能有多条 通路从起点到终点,数字大那么生成的迷宫就越密集,但至少有一条通路。

单迷宫解法


迷宫第一定律:一般而言,只要在出发点单手摸住一面墙出发,手始终不离开墙面,总可以找到迷宫的出口。对于单迷宫而言,这一种万能的破解方法,即沿着某一面墙壁走。 或者换句话说,你在走的时候,左(右)手一直摸着左(右)边的墙壁,这种方法可能费时最长,也可能会使你走遍迷宫的每一个角落和每一条死路,但你绝不会永远困在里面。 直觉上好像是可以,实现一下也确实能找到终点的,也就是靠着墙,一直靠左或者一直靠右。实现的时候甚至都不用记录哪些点已经访问过了,哪些点还没访问过。 这也是一种人能来做的算法,毕竟人不可能像计算机一样dfs、bfs。

BFS


用BFS肯定也是可以的,如果是单路径的迷宫,用BFS实在是太慢了,它会把大部分的点都遍历一边。感觉就像是一颗石子掉到水中,要找岸边的终点那得等波纹波及到岸边。 非常之慢。但如果是有多条通路的迷宫,BFS是能保证找到最短路径的。也许双向BFS会好一点,不过猜想对于单迷宫,也提高不了多少。

DFS


那用DFS也是可以的。不过效率还是很差,像苍蝇一般在迷宫的各个角落转悠,直到大部分点都遍历了。稍微改变一下DFS优先搜索的方向会有一些提高,比如我这个图优先走下方或者优先走左方。

A


A是一种启发式搜索算法,在这里我用点与点的曼哈顿距离来作为启发函数,效果不好,因为曼哈顿距离也就大概的告诉了搜索路径现在应该往哪个方向走比较好。不过总得来说 这么一点启发得到的效果还是要比BFS和DFS要好些。评估函数选择合适也是能找到最短路径的,曼哈顿是可以的。如果墙比较稀疏(肯定有多条路径),那么A*算法会快得许多。

用键盘走


呵呵,对于小点的迷宫用键盘来移动可以比较快解决,人是有直觉和经验的,在合适复杂度上面这种直觉给的启发可比上面好,但是如果迷宫太大了就不行咯。或者还有其他算法去走出迷宫么?

使用微信打赏

若你觉得我的文章对你有帮助,欢迎点击上方按钮对我打赏

扫描二维码,分享此文章