第30卷第11期 2013年11月
吉林化工学院学报
JOURNAL OF JILIN INSTTTUTE OF CHEMICAL TECHNOLOGY
文章编号：1007-2853(2013)11-0085-04
电脑鼠走迷宫算法仿真设计
付秀伟"，邹刚2
Vol. 30 No. 11 Nov.2013
(1.吉林化工学院信息与控制工程学院，吉林吉林132022;2.国家电网公司吉林供电公司，吉林吉林132011）摘要：主要研究电脑鼠走迷宫的算法，主要包括迷宫生成算法、原始全迷宫搜索算法和修正后的泛洪算法，改进后的算法可以搜索到从起点到终点的所有可行路径中的一条最佳路径，以实现快速、高效求解迷宫的目的。
关键词：电脑鼠；迷宫；算法；泛洪算法
中图分类号：TP301.6
文献标志码：A
电脑鼠的英文名称为Micromouse[】，它可以在“迷宫”中自动感知并记忆迷宫地图，通过一定的算法，寻找一条最佳路径，以最快的速度到达目的地.简而言之，电脑鼠搜索路径需要运用搜索算法才能使电脑鼠自主行走.搜索算法的主要目的是根据电脑鼠当前的位置确定下一步，以迅速达到迷宫的中心并返回，同时利用搜索迷宫时得到的隔墙信息找出从起点到终点并返回的最优路径.本文通过探讨和分析了迷宫算法提出改进的迷宫算法，并利用相关软件对迷宫算法进行仿真，
通过数据可知改进算法能更快的寻找到终点 1迷宫算法的设计
1.1算法设计思想—泛洪算法
本文的算法思想：想象你站在一个迷宫里，迷宫格之间的隔板由不透水的材料制成.你手中有一个带开关的水管当你想找出通往迷宫出口的最短路径时，你可以打开水管开关，此时水便从你所在的迷宫格向四周漫出，第一支到达出口的水流所代表的路径便是你想找的最佳路径.由此引出泛洪算
法[2)，也称为Flood算法或是洪水填充法 1.2原始算法全迷宫搜索算法
原始算法，即全迷宫搜索算法，也被称为“深度优先”算法.利用的原理是对整个迷宫进行全部搜索，通过建立等高表，在所有由起点达到终点的可行路径中找到最短路径.电脑鼠最初从人口出发，按搜索法则顺着某一方向向前探索，若能走通，则继续往前走；否则在遇到死区时，将沿原路返回至上一节点，换一个方向再维续探索，直至所
有可能的通路都探索到为止 1.3最优路径算法—
一改进的泛洪算法
洪水填充法也被称为“广度优先”算法，因为如果迷宫被表示成一个生成树，演算法会先搜查同一层的格子，接着才搜寻下一层的格子.洪水填充算法的主要优点是，它总能找到到达迷宫中心的最短路径.但值得注意的是，此方法实际走的路径被非最短路径
为了增加洪水填充法的效率，本文在原始泛洪算法上就行修正，提出了一种新的Flood算法[3].这种算法将已有的和未知的迷宫信息进行整合，在寻路方面具有目的性，也可以防止进人一
些周围已经探索过的死胡同 2迷宫算法的实现 2.1迷宫算法的总体设计
系统算法结构如图1所示，主要由以下几个模块组成：
电脑鼠走递宫的算法
迷宫的随机生成算法
搜索递宫路径的算法
全速宫搜素算法
递官过程的动态实现
修正的泛洪算法
图1系统算法结构图
收稿日期：2013-09-01
作者简介：付秀伟（1983-），男，山东新泰人，吉林化工学院助教，硕士，主要从事入式研究和电机控制方面的研究万方数据