电脑鼠走迷宫大赛探索过程算法优化研究——死路排除算法——死区域算法1摘要电脑鼠走迷宫大赛是由国际电工和电子工程学会（IEEE）举办的人工智能领域的一项国际性赛事，集机械、电子、控制、光学、程序设计和人工智能等多方面科技知识于一体[1]，具有很高的知名度。

迷宫算法的优劣直接影响比赛的最终成绩。

本文从经典迷宫算法入手，先后提出了能排除单行当列死路的“死路排除算法”和能够排除任意形状死区域的“渗透法”，然后通过测试验证两种改进算法的优越性。

改进算法的核心思想是通过已经获得的迷宫信息排除不包含最短路径信息的死区域。

同时，文中创造性的将“渗透思想”用于迷宫算法当中，很好的实现了死区域的判定与排除。

与经典算法相比，改进算法在时间、空间方面都有良好的优化效果。

2背景简介电脑鼠走迷宫大赛是国际电工和电子工程学会（IEEE）每年都会举办的一项国际性赛事，于1972年由美国机械杂志发起。

比赛中的电脑鼠是一个小型的由微处理器控制的机器人车辆，在复杂迷宫中具有译码和导航功能。

该比赛自推出以来，受到了世界各国师生的青睐。

2007年和2008年，上海市计算机学会率先在中国主办了两次IEEE标准电脑鼠走迷宫邀请赛（长三角地区），有三十多所院校参加，反响强烈。

2009年比赛范围扩展到全国，共有9个赛区的52所高校参赛[2]。

2.1电脑鼠走迷宫大赛规则[3]电脑鼠的基本功能是从起点开始走到终点，这个过程称为一次“运行”，所花费的时间称为“运行时间”；电脑鼠从第一次激活到每次运行开始所花费的时间称为“迷宫时间”；电脑鼠在比赛时手动辅助的动作称为“碰触”。

竞赛使用这3个参数，从速度、求解迷宫的效率和电脑鼠的可靠性三个方面来进行评判。

电脑鼠的得分是通过计算每次运行的“排障时间”来衡量的，即将迷宫时间的1/30加一次运行时间；如果未被碰触过，则再减去10s（奖励时间），这样得到的就是排障时间。

电脑鼠在迷宫中停留或运行的总时间不可超过15min，在限时内允许运行多次。

如果进入迷宫是为了进行探测和记忆，则这次运行就称为“试跑”；如果进入迷宫是根据先前的记忆和经验，按照智能算法确定最佳路径，并以最快的速度到达目的地，则这次运行就称为“冲刺”。

2.2迷宫、电脑鼠规格迷宫由256个方块组成，每个方块18 平方厘米，排成16行×16列。

迷宫的隔板沿方块的四周布设，形成迷宫通道。

如图1为迷宫照片。

图2为电脑鼠样例照片，该电脑鼠采用ARM7处理器——LM3S615作为主控芯片。

五组可测距的红外线传感器按照某固定频率对迷宫格周围障碍进行采样，获取迷宫隔板信息。

图1 迷宫照片图2 电脑鼠样例照片2.3已有算法迷宫最优路径是指从迷宫的入口到达迷宫出口的最短通路。

经典求解迷宫路径问题的算法大多采用广度优先搜索（BFS）或深度优先搜索（DFS）[4]。

由于需要全迷宫搜索，随着迷宫规模的增大和复杂性的增加，上述两种算法的空间和时间复杂性将呈指数增加。

针对以上问题，本文对经典算法优化改进，核心思想是利用已经探索得知的迷宫信息排除不包含最短路径信息的迷宫格，不予探索。

文章首先实现了能够排除单行、单列死路的死点路排除算法；随后实现了能够排除多行、多列死点的死区域算法。

本文第2部分给出两种算法分别的设计思想和设计流程，第3部分通过实际测试验证了上述算法并对结果进行分析。

文章的结论在第4部分呈现。

3算法介绍3.1死点算法3.1.1基本思想该算法首先将迷宫等分成16×16的迷宫格，见图6。

并将迷宫隔板两面分别进行标记，以示区别。

可以对迷宫格进行虚拟隔板标记，这种标记在实际效果上等同于隔板，只是无法用传感器探测到而已；如果一个迷宫格三个方向有隔板（或者是标记），并且当该迷宫格不是终点时，那么电脑鼠进入该迷宫格后必然返回，这对于寻找最短路径信息无用；算法将该迷宫格第四个方向一同标记，亦即将迷宫格封闭，不让电脑鼠进入该迷宫格，以达到缩短探索时间的目的。

3.1.2流程图图3 图解示例为了进一步说明死点算法在实际探索过程中的工作过程，如图4做如下解释：图4 死点算法实际效果图解图中红色虚线是预标记的虚拟隔板，绿色虚线为封闭死点时标记的虚拟隔板，在初始化中将迷宫边界内壁预标记：1、电脑鼠运动到P格时，会将迷宫格1的上方标记，而其左方已在出发时标记，这样迷宫格1三个方向被标记，满足封闭条件，则将其右方也标记上，即将迷宫格1封闭，同时可将迷宫格2的左方标记上；2、电脑鼠继续沿图示虚线运动，迷宫格2同样三方被标记，将其封闭，如此循环可得迷宫格3、4、5、6、7将相继封闭，并将迷宫格8下方被标记；3、电脑鼠运动到迷宫格8时，右方传感器没有检测到障碍，但由于右方被标记，因此向左转。

减少了探索迷宫格1、2、3、4、5、6、7的时间。

3.2死区算法——渗透法3.2.1基本思想A、新思路的探索上述死点算法实现了利用已有信息排除单行、单列死点的功能，但无法排除多行、多列的死区域，而且在算法实现上隔板标记的循环语句较为繁琐，将会影响电脑鼠的信息处理速度和运动的稳定性。

死区域排除也是通过已有信息将不包含最短路径信息的区域进行封闭，然而单纯依靠单格的连续封闭的方法从空间和时间上都较难实现，下面我们引入一种新的思想来解决这个问题。

B、渗透法当一个区域只有一个出口与外面相连并且终点不在此区域内时，这个区域被称作死区域。

渗透法排除死区域继承了死点算法的隔板标记的思想，在沿途对已获隔板信息进行分析和标记，并希望实现唯一出口处被标记一个虚拟隔板。

渗透法的核心是判别死区域，要说明其原理我们从“渗透”一词说起，“渗透”在化学上的解释是低浓度溶液中的水或其他溶液通过半透性膜进入较高浓度溶液中的现象，而我们对死区域的判定也正是应用这种思想；做个比喻，设想单出口区域即死区域的出口处有一个“半透膜”，而整个迷宫内假设都充满了“高浓度的溶液”，电脑鼠从起点出发，每当遇到路口时，将“低浓度溶液”中的“水分”渗入路口相连的方向，水分渗入“高浓度溶液”后，则变为“低浓度溶液”，进而在逐步深入，如果“水分”不能最终扩散渗入终点，则说明此路口所连区域是个死区域，可以将路口标记上虚拟的隔板，进而排除该死区域。

需要注意的是：进行封闭的区域是未探索区域，即仍为“高浓度的溶液”区域，以防将电脑鼠封死在已走的区间内。

C、渗透算法的实现除了已经提到的隔板标记的算法，还需要实现溶液的渗透和扩散，在初始化中我们将未探索的迷宫格全部赋值为0，当“水分”渗入后该区域值变为0xff，这样来实现“低、高浓度溶液”模型的建立。

“溶液的扩散”就是把与值为0xff的迷宫格之间无虚拟隔板相隔的相邻迷宫格同样赋值为0xff，再不断的这样赋值下去，直到整个区域内都赋了值0xff而无法继续扩散时结束。

这样就实现了渗透的算法。

3.2.2流程图初始化：迷宫边界被标记，所有迷宫格赋值ff，其他初始化右手法则探索迷宫，记录并按规则标记虚拟迷宫信息存于MapBlock[][]中，循环判断区域虚拟标记信息，若满足迷宫区域封闭条件则封闭判断是否满足加强右手法则中向右转、向前直行、向左转的条件：当前格对应方向右方、前方、左方既无传感器探测到的隔墙板信息，又无被标记的隔墙板信息Y回到已经记录的上一节点处，沿另外方向探索迷宫，判断已记录节点数N是否归0NN表明迷宫已探索完毕，回到起点准备冲刺Y冲刺完毕后回到起点，结束运行电脑鼠当前迷宫格P，某方向N无隔墙板迷宫格P的N方向迷宫格为Q未探索，将Q赋值ff，并不断无回流的扩散判断终点是否被赋值ffN对迷宫格Q相应方向进行预封闭，判断电脑鼠是否处于预封闭区域将预封闭迷宫格封闭N是否所有未探相邻迷宫格均已判断结束YYYN迷宫区域封闭子程序图53.2.3图解实例下面结合图6我们对渗透法做进一步解释：图6 渗透法实际效果图解图中未赋值迷宫格默认赋值为0，蓝色宽箭头表示“ff ”渗透的方向，红色虚线是预标记的虚拟隔板，绿色虚线为死区出口处标记的虚拟隔板：1、 初始化使迷宫边界均被标记虚拟隔板，电脑鼠从起点沿长虚线箭头方向运行，走过的迷宫格自动赋值为ff ，运动到图5-1中被圈的迷宫格时，先后进行上方右方的渗透，无红色虚拟隔板则不受阻碍，渗透后迷宫如图5-2所示，其中两蓝色箭头示意了终点被赋值ff 的一种渗透路径；2、 由于终点最终被渗透扩散后赋值ff ，则判定两个方向目前均不是死区的出口，不进行封闭，继续向前探索；3、 电脑鼠运动到图5-3中被圈位置时，下方区域A 的边界均已被预标记上虚拟隔板，此时判断出下方迷宫格的值为0，则将ff 渗入；4、 如图5-4, “ff ”在区域A 内不断扩散直至充满整个区域，由于整个区域只有一个出口且不能回流，ff 不能流出延伸到终点，所以可判定该区域是死区域；即将当前电脑鼠所在迷宫格的下方标记虚拟隔板； 5、 电脑选择左转，将减少探索整个区域A 的时间。

4 实测数据分析为验证上述两种算法的效率，本文针对以下3个不同的迷宫，对上述算法和经典算法进行了3组性能测试，从所用时间和搜索空间两方面进行比较，测试结果如表1所示。

迷宫1 迷宫2 迷宫3经典算法死路排除算法 死区域算法时间（秒）迷宫1 66 44 39 迷宫276 58 47 迷宫3 7851 42 平均值 73.3333333351 42.66666667 空间（探索区域/全迷宫×100%）迷宫1100% 64.06% 57.80% 迷宫2100% 81.25% 67.19% 迷宫3100% 73.43% 59.38% 平均值100% 72.91% 61.46%表1以上3个迷宫为人工随机摆放，但已经存在相当的普遍性。

从表1中可以看出： a) 探索时间上：经典算法>死路排除算法>死区域算法；死路排除算法、死区域算法所需时间仅为经典算法的69%和58%；b) 探索空间上：经典算法>死路排除算法>死区域算法；死路排除算法、死区域算法所探索的空间仅为经典算法的73%和61%； c) 死路排除算法、死区域算法在时间、空间上比经典算法都有相当的优化，优化程度前者在30%左右，后者在40%左右，效果非常理想。

为直观反映空间优化的效果，我们用迷宫3的三种算法做如下比较，其中蓝色为死路排除算法未探索区域，黄色为死区域算法未探索区域，显然优化效果明显。

5结论本文从已有经典迷宫算法引出对迷宫算法的优化，先是提出了排除单死路的“死路排除算法”，后来又进一步提出了排除死区域的“渗透法”。

“渗透法”的提出从一种更直观形象的角度对死区域进行了描述，降低了死区域判断时间、空间上的复杂度，减少了迷宫格信息预处理的计算量，最终完美的实现了死区域的排除。

改进算法的核心思想在于通过已经获得的迷宫信息排除死区域，只要迷宫存在死区域，就一定会在时间、空间上有所优化。