一种电脑鼠走迷宫算法

周杰

摘要：该文通过对电脑鼠走迷宫算法的研究，提出了一种电脑鼠走迷宫算法，该算法引用了斜线K和Z用以更新期望坐标，并将迷宫分割为多个部分，以斜线K上的点为起点坐标，下一条斜线K上的点为期望终点坐标，找到起点坐标和终点坐标的最优解，以局部最优，引出全局最优找到最佳路径，并与传统走迷宫算法进行比较，提高了迷宫搜索效率。

关键词：迷宫；斜线；局部最优；最佳路径

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2018）03-0053-03

1 概述

电脑鼠是一种机电一体化装置，是由单片机、传感器、机电运动部件组成的一种能在迷宫行走的小型机器人可以通过预先设定的算法，探索迷宫，可以找到一条从预设的起点到终点的最佳路径，运行环境是由一个16X16正方形单元格所组成的迷宫，其中单元格的大小为18cmX18cm，文献[1][2]给出了电脑鼠走迷宫的相关规则，每一个单元格有相应的挡板组成，电脑鼠的目的是在最短的时间内找到出口，在整个电脑鼠中最重要的是硬件的可靠性和算法的优劣，在当今单片机迅速发展的时代，硬件稳定性上已经趋于稳定，本文主要研究和设计搜索迷宫算法，并提出了一种电脑鼠搜索迷宫的算法。

2 迷宫环境建模

电脑鼠不具有思维能力，它只能按照我们设定的算法运行，因此需要模拟现场运行环境[6][7].

构建一个16X16的迷宫，迷宫的水平方向为Y轴，垂直方向为X轴，第一个坐标为（1，1），那么依次下去最上角的坐标为（16，16）。迷宫构建图，如图1 所示，迷宫内的挡板信息未知。

假设起点为（1，1）终点为（16，16），现在规定，X方向为地理北，Y方向为地理南，如圖2所示。

对于当前坐标，和下一步目标，两个坐标的差值比如（X1，Y1）-（X2，Y2）。

（1，0）表示电脑鼠向北前进一步。其中差值（0，1）表示向东前进一步，（-1，0）表示向南前进一步，（0，-1）表示向西前进一步。从起点为其构造如图所示的切线Z1，如图3所示，Z2一直到Zn，总是希望以最短的路径由一条斜线到达另外斜线上的坐标，然后以该点为起始点总是希望以最短的路径到达下一条斜线上的坐标，依次寻找下去，就可以找到从起点到达终点的路径由于每次选取的都是两条斜线之间行走的步数是最短的，然后记录下行走的路径，处理掉重复的路径，因此能找到，起点到终点的最佳路径。

3 搜索迷宫算法

3.1 迷宫特殊情况

搜索迷宫，找到最短路径的方法分为以下几种基本情况：

理想情况：起点（1，1），终点（16，16）两点之间直线最短，以先搜索左上迷宫为原则，那么希望走过的路径为（1，1）（2，2）（3，3）（4，4）（5，5）（6，6）……（16，16），但是对于迷宫，迷宫的每一个格子都有相应的挡板信息，不能走直线，起始坐标为（1，1），下一步希望到达（2，2），但是由于（2，2）-（1，1）的权值为2，在迷宫里如果两个坐标相减权值大于1那么意味着不能直接到达，以两点之间距离最短的原则进行最佳路径选择，现在人为的规定最佳路径如图4所示：

路径（1，1）（2，1）（2，2）（3，2）（3，3）（4，3）（4，4）……（16，15）（16，16）为最佳路径，现以（1，1）为起点，那么下一步它需要到达（2，1），而（2，1）-（1，1）权值为1能一步到达，差值可以表示为（1，0），（1，0）表示电脑鼠向北前进一步。其中差值（0，1）表示向东前进一步，（-1，0）表示向南前进一步，（0，-1）表示向西前进一步。如果能到达（2，1），那么起点就是（2，1），那么下一步要到达（2，2）则（2，2）和（2，1）的差值为（0，1）电脑鼠右转探测，前面是否有挡板，如没有挡板，前进一格到达（2，2），依次下去，如果理想状态下，就能按照我们预设的最佳路径（1，1）（2，1）（2，2）（3，2）（3，3）（4，3）（4，4）……（16，15）（16，16）到达终点。

特殊情况1：迷宫是随机的，挡板信息也是随机的，理想状态下的路径肯定无法达到，当遇到以下情况时为情况1处理.

此时从（1，1）出发目的是想到达（2，2），规定了行走路线是（1，1）（2，1）（2，2）（3，2）（3，3）（4，3）（4，4）……（16，15）（16，16），借助（2，1），此时将到达（2，1），是当想到目达（2，2）的时候，（2，2）-（2，1）值为（0，1），表示向东行走一步，此时电脑鼠传感器扫描，发现前面有挡板不能直接到达。

那么此时如图6所示我们画出一条斜线Z1，此时Z1通过三个点（3，1），（2，2），（1，3）。发现这三个点的横纵坐标之和是相等的值为4。当发现下一步期望坐标（2，2）无法直接到达时，找到和它横纵坐标之和相等的点，而此时电脑鼠在（2，1），用（3，1），（1，3）与（2，1）相减得到一个权值，选取权值最小的坐标来代替目的坐标即用（3，1），来代替（2，2）来作为下一步目标那么，人为的规定最佳路径也随之改变。

假设现在到达了（3，1），那么（3，1）将作为我们的起点坐标相应的最佳路径就更改为：（1，1）（2，1）（3，1）（4，1）（4，2）（5，2）（5，3）……（15，14）（16，15）（16，16）。下一步期望坐标更改为（4，2）借助（4，1）。

特殊情况2：遇到以下情况时为情况2处理。

迷宫是随机的，行进过程中可能会遇到死区，比如特殊情况1，电脑鼠到达了（3，1），那么（3，1）将作为我们的起点坐标相应的最佳路径就更改为（1，1）（2，1）（3，1）（4，1）（4，2）（5，2）（5，3）……（15，14）（16，15）（16，16）。下一步期望坐标更改为（4，2）借助（4，1），扫描迷宫，成功到达（4，2），下一步希望到达（5，3）借助（5，2），发现（5，2）不能直接到达，于是舍弃找到它关于K3对称得点（4，3），借助（4，3）到达，如果（4，3）能到达，再扫描能否经过（4，3）到达（5，3），能到达就继续下一步，如果不能到达就找到和（5，3）权值相等的坐标，从权值相等的坐标中找到差值为1的（4，4），扫描能否到达，能到达，更新路径继续扫描。

特殊情况3：遇到以下情况时为情况3处理.

假设电脑鼠到达（4，2），扫描（4，2）发现，既不能到达（5，2） 也不能到达（4，3），退回这时候的起点坐标（3，1）扫描右侧，看能否到达，如果能，就前进到（3，2），这时候不以（4，2）作为目标，而是从权值相等的坐标里面，找到能一步到达的点，如果有则到达，如果不能到达，则返回上一步起点。

特殊情况4：当行进到某一点发现下一步目标不可达，这时查找和它权值相等的坐标，发现斜线上只有一点时，斜线上的坐标即为终点坐标。此时起点坐标为（7，5）下一步希望到达（8，6）但是借助（8，5），，与扫描能否到达，发现不能到达，这时找到和其对称点（7，6）发现可以到达，电脑鼠到达（7，6），希望到达（8，5）发现不可达，这时找到与（8，6）权值相等的坐标，发现斜线上只有一点（7，7），以该点为下一步坐标，扫描发现有挡板不能到达，由于（7，7）是终点坐标，于是找到（7，6）的对称点（6，7）需要借助（6，6）发现无挡板，电脑鼠到达（6，6）再经过（6，7）到达（7，7）

3.2 完成迷宫搜索

将16*16的迷宫缩小为8*8迷宫进行模拟，根据设定的规则以（1，1）为起点（8，8）为终点，将电脑鼠放在起点坐标，车头向北，这时候人为规定行走路径为：（1，1）（2，1）（2，2）（3，2）（3，3（4，3）（4，4）（5，4）（5，5）（6，5）（6，6）（7，6）（7，7）（8，7）（8，8），現在电脑鼠在坐标（1，1），下一步希望到达（2，1），坐标（2，1）-（1，1）为（1，0），表示往北前进一步，此时传感器扫描挡板，发现可行，电脑鼠到达（2，1），下一步希望到达坐标（2，2），坐标（2，2）-（2，1），表示往东走，传感器扫描挡板信息，发现（2，2）不能直接到达，此时为特殊情况1，将对期望坐标（2，2）修改为（3，1），路径行走路线重新修改，修改路线方法为平移，修改后的坐标的横坐标比原坐标大1平移（1，-1），如果修改后的坐标的纵坐标比原坐标大1平移（-1，1），走过的和超出界限的不做修改如（1，1）（8，8），修改后的坐标为（1，1）（2，1）（3，1）（4，1）（4，2）（5，2（5，3）（6，3）（6，4）（7，4）（7，5）（8，5）（8，6）（8，7）（8，8），此时电脑鼠行进到（5，2），期望的下一步（5，3）不能到达，于是找到Z斜线上的替代坐标，同样为情况1，更新起点坐标为（6，2），那么路线更改为（1，1）（2，1）（3，1）（4，1）（4，2）（5，2）（6，2）（7，2）（7，3）（8，3）（8，4）（8，5）（8，6）（8，7）（8，8）。电脑鼠到达（6，2），下一步希望到达（7，2），扫描挡板信息，发现（7，2）不可达，此时为情况2，找到（7，2）对称点（6，3），到达坐标（7，3），按照情况1，2处理，电脑鼠到达（7，7）情况4处理，，最后到达（8，8），找到了终点坐标。记录下行走路径为（1，1）（2，1）（3，1）（4，1）（4，2）（5，2）（6，2）（6，3）（7，3）（7，4）（7，5）（7，6）（7，7）（8，7）（7，7）（7，8）（8，8）。

4 结论

本文设计了一种走迷宫的算法，从起点坐标开始每次找到下一条斜线Z上的点的最佳路径，有局部的最优构造出全局的最优，电脑鼠走迷宫有经典的，右手法则，左手法则，中左法则，中右法则[3][4][5]与传统算法作比较如表1所示：

本文提出的算法有效地提高了电脑鼠对整个迷宫的探索，以局部最优完成全局最优的探索。下一步研究计划对各类特殊迷宫进行测试，以及电脑鼠从终点返回起点的路径探索。

参考文献：

[1] 周立功.IEEE电脑鼠开发指南[M].广州：广州致远电子有限公司，2008.

[2] IEEE 国际电工和电子工程学会.IEEE 电脑鼠（迷宫）竞赛规则和介绍 .嵌入之梦 [EB/OL].htttp：//www.embedream.com/ xgzl/2007-08-28/24.html.

[3] 贺少波.基于向心法则的电脑鼠走迷宫算法设计与优化[J].计算机系统应用，2012，21（9）.

[4] 王凤林.一种电脑鼠走迷宫算法的设计与实现[J].计算机应用与软件，2010，27（12）：270-273.

[5] 郭长生 ， 龚涛 ，李龙.一种电脑鼠走迷宫搜索算法[J].华中科技大学学报：自然科学版， 2013 ， 41 （s1） ：388-391.

[6] 王斌，张卫钢.基于IEEE标准的电脑鼠走迷宫的智能算法研究[J].电子设计工程，2011，19（12）：42-45.

[7] 张新谊.一种电脑鼠走迷宫的算法[J].单片机与嵌入式系统应用，2007（5）：84-85.