文档介绍：电脑鼠走迷宫算法改进及仿真测试(部分) 迷宫算法改进迷宫最优路径是指从迷宫的入口到达迷宫出口的最短通路。传统求解迷宫路径问题的算法大多采用广度优先搜索(BFS) 或深度优先搜索(DFS) 。由于需要全迷宫搜索,随着迷宫规模的增大和复杂性的增加,上述两种算法的空间和时间复杂性将呈指数增加。针对以上问题,本论文对传统算法进行优化改进讨论,核心思想是利用已经探索得知的迷宫信息排除不包含最短路径信息的迷宫格,不予探索。 1、单行、单列死点的死胡同排除算法该算法核心内容是进行数据补全,减少电脑鼠进入“死胡同”的次数。其实迷宫单元的信息并不是只有访问过才能够得到,通过推断的方法也是可以得到的。利用某个单元四周的方格的信息,就可以推断出此单元的信息,而并不需要每一个单元都进行访问。如果一个迷宫单元三个方向有挡板,并且当该迷宫格不是终点时,那么电脑鼠进入该迷宫格后必然返回,这对于寻找最短路径信息无用, 此时将该迷宫格第四个方向一同标记,亦即将迷宫格封闭,不让电脑鼠进入该迷宫格,以达到缩短探索时间的目的。如图中圆圈区域,当其四周搜索过时, 电脑鼠不应对此区域进行访问。图2. 10 死胡同实例根据电脑鼠迷宫特性,迷宫四周的挡板是肯定存在的,可先进行预先处理。而且终点四个单元的周围的八块挡板有且仅有一个是不存在的。当电脑鼠到达终点,在明确哪个挡板不存在的同时,无论其它挡板是否进行探测过,都可将它视为挡板存在。 2、多行、多列死点的死区域排除算法传统搜索算法中电脑鼠从当前单元移动到下一单元的依据是有无挡板的存在及是否访问过,而未考虑从下一单元是否可以在不经过当前单元的情况下到达终点。形象的说,此种搜索只着眼于当前电脑鼠的移动,而不考虑实际效果。当电脑鼠不能从下一单元在不经过当前单元到达终点时,电脑鼠的运行就做了“无用功”,这对于迷宫搜索的执行效率产生很大的副作用。如图所示,方形区域内即是这种情况,也就是死区域。为防止“无用功”的产生,应进行死区域的判断。死区域排除算法的核心内容是电脑鼠从当前单元运行到下一单元前,判断从下一单元是否可以在已探索及推断的迷宫信息下,不经过当前坐标的情况下到达迷宫终点。如果不能,就是死区域。测试表明(见节) 进行死区域的判断可以有效的减少对于无效迷宫单元的访问,以减少搜索时间。图2. 11 死区域实例 3、死岔路口排除算法在电脑鼠搜索过程中,有这样的一个过程:当电脑鼠移动到下一单元时,进行判断,当有两个及以上方向可进行搜索即为岔路口时,保存此迷宫单元坐标, 按搜索算法进行既定方向的搜索,以便于电脑鼠在遇到“死胡同”时,返回到上一岔路口,沿另一方向进行搜索。但当电脑鼠到达上一岔路口,在增加了迷宫信息的条件下,另一方向是否有必要进行访问?如果没有必要,则继续返回此岔路口的上个岔路口。以此类推,直到电脑鼠到达可进行另一方向有必要进行搜索的岔路口或是到达起点。如图所示,电脑鼠从 A 出发,经 Q、 P 到达 B 点,途中对 Q、 P 两单元进行岔路口保存。当到达 B单元时发现无路可前进,返回上一岔路口 P,但到达 P时检测到没有必要进行另一方向的搜索,继续返回到岔路口 Q。也就是说电脑鼠从 B单元经 P单元返回 Q单元。显然,电脑鼠直接从 B单元返回 Q单元的路程更短。图2. 12 死岔路口实例死岔路口排除算法就是指在电脑鼠返回岔路口时,根据电脑鼠从岔路口之后搜索到的迷宫更新信息进行判断,此岔路口是否该返回进行另一方向的搜索。这可以有效的节省电脑鼠返回岔路口的时间。图2. 13 死岔路口排除算法流程图 4、终点优先传统算法中,电脑鼠移动的方向策略是不变的,可能导致如图所示情况。图中采用右手法则进行迷宫的搜索,当第一次搜索到迷宫终点时电脑鼠对终点“过而不入”,但当电脑鼠完成既定方向的搜索,必将返回此处完成对终点的访问。现在假设,如果电脑鼠先进行对终点的访问,但电脑鼠从终点返回时,结合死区域排除算法,发现电脑鼠可以不进行另一方向的搜索。这种情况下,对终点先进行访问,必然会减少搜索时间。这就是终点优先。图2. 14 电脑鼠对终点过而不入终点终点终点电脑鼠遇到死胡同前边没有岔路口岔路口指针数-1 上一岔路口另一方向是否有必要进行访问返回起点返回上一岔路口是是否否终点优先是指电脑鼠在运行到终点附近时,优先对终点进行访问。在对迷宫进行全搜索的状态下,迷宫终点优先情况效果不大,但如果配合死区域排除算法, 搜索效率可能会得到进一步的提升。对于以上四种排除算法,由于 1中所说的单行、单列死路的死胡同是多行、多列死点的死区域的特例,可将多行、多列死点的死区域排除算法与死岔路口排除算法和终点优先算法相结合,效率会比单一的排除算法更高。具体仿真测试见节。第3章基于 VB 的电