下载文档原格式
一种电脑鼠走迷宫算法作者：周杰来源：《电脑知识与技术》2018年第03期摘要：该文通过对电脑鼠走迷宫算法的研究，提出了一种电脑鼠走迷宫算法，该算法引用了斜线K和Z用以更新期望坐标，并将迷宫分割为多个部分，以斜线K上的点为起点坐标，下一条斜线K上的点为期望终点坐标，找到起点坐标和终点坐标的最优解，以局部最优，引出全局最优找到最佳路径，并与传统走迷宫算法进行比较，提高了迷宫搜索效率。
关键词：迷宫；斜线；局部最优；最佳路径中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2018）03-0053-031 概述电脑鼠是一种机电一体化装置，是由单片机、传感器、机电运动部件组成的一种能在迷宫行走的小型机器人可以通过预先设定的算法，探索迷宫，可以找到一条从预设的起点到终点的最佳路径，运行环境是由一个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）表示向西前进一步。
![课程设计_老鼠走迷宫[1]](https://uimg.taocdn.com/5ab2538d680203d8ce2f245c.webp)
HUNAN CITY UNIVERSITY 数据结构课程设计报告设计题目：老鼠走迷宫专业：计算机科学与技术学生姓名：邓宇班级学号： 0906401-23指导教师：杨格兰、胡奇光2011 年 6 月 18 日一、设计时间2011年6月20日——24日二、设计地点湖南城市学院第一实验楼计算机系机房509三、设计目的1.培养实际工作所需要的动手能力，进一步熟悉基本概念；2.熟练掌握对实际问题的抽象技能，了解程序基本的流程；3.培养查阅资料，独立思考问题的能力。
四、设计人邓宇五、指导老师杨格兰、胡奇光六、设计课题老鼠走迷宫开发环境：Visual Studio 2010 Ultimate UML Activity DiagramVisual C # 2008 Express EditionsAdobe Photoshop CS4七、基本思路及关键问题的解决方法技术要求：程序开始运行时显示一个迷宫地图，迷宫中央有一只老鼠，迷宫的右下方有一个粮仓。
游戏的任务是使用键盘上的方向键操纵老鼠在规定的时间内走到粮仓处。
要求：1、老鼠形象可辨认，可用键盘操纵老鼠上下左右移动；解决方案：老鼠图片形象可以用Photoshop来制作，通过键盘按键事件发送消息到对象（老鼠），实现老鼠的移动。
2、迷宫的墙足够结实，老鼠不能穿墙而过；解决方案：在老鼠每一步的移动中检测是否撞墙，若是则停止走动。
由于地图是图片，要检测就需要取出墙壁那点的颜色（显然不是白色），然后作比较来作碰撞检测。
3、若老鼠在规定时间内走到粮仓处，提示成功，否则提示失败；解决方案：加载定时器，设定60秒钟，若在规定的时间，及时间变成0时，弹出对话框提示用户游戏失败。
4、添加编辑迷宫功能，可修改当前迷宫。
解决方案：备用一张地图图片资源，可以用于更换地图。
八、算法及流程图Visio流程图：因为这是面向对象而非面向工程的程序设计，事件和判断都具有同时性和并发性。
UML建模图如下：九、调试过程中出现的问题及解决方法本次课程设计出现最严重的问题是通过键盘来如何控制对象（老鼠）的移动，刚开始做时试用了多种方法但是没有效果。
一、实习问题：电子老鼠闯迷宫二、问题描述：有一只电子老鼠被困在如下图所示的迷宫中。
这是一个7*7单元的正方形迷宫，黑色部分表示建筑物，白色部分是路。
电子老鼠可以在路上向上、下、左、右行走，每一步走一个格子。
现给定一个起点start和一个终点finish，求出电子老鼠最少要几步从起点走到终点。
三、问题分析：该问题可用分支限界法来解决。
迷宫问题的解空间是一个图。
解此问题的队列式分支限界法从start开始将它作为第一个扩展结点。
与该扩展结点相邻并且可达的方格成为可行结点被加入到活结点队列中，并且将这些方格标记为1，即从起始方格start到这些方格的距离为1。
接着，算法从活结点队列中取出队首结点作为下一个扩展结点，并将与当前扩展结点相邻且未标记过的方格标记为2，并存入活结点队列。
这个过程一直继续到算发搜索到目标方格finish或活结点队列为空时为止。
在实现算法时，首先定义一个表示迷宫上方格位置的类Position，它的两个私用成员row 和col分别表示方格所在的行和列。
在迷宫的任何一个方格处，电子老鼠可沿右、下、左、上4个方向进行。
沿这4个方向的移动分别记为移动哦0,1,2,3。
在表中，offset[i].row和在实现上述算法时，用二维数组grid表示所给的方格阵列。
初始时，grid[i][j]=0,表示该方格允许走；而grid[i][j]=1表示该方格被封锁，不允许走。
为了便于处理方格边界的情况，算法在所给方格阵列四周设置一道“围墙”，即增设标记为“1”的附加方格。
算法开始时测试初始方格与目标方格是否相同。
如果这两个方格相同，则不必计算，直接放回起始位置标记为2。
由于数字0和1用于表示方格的开放或封锁状态，所以在表示距离时不用这两个数字，因而将距离的值都加2。
实际距离应为标记距离减2。
算法从起始位置start开始，标记所有标记距离为3的方格并存入活结点队列，然后依次标记所有标记距离为4,5…..的方格，直至到达目标方格finish或活结点队列为空时为止。
东南大学第二届IEEE标准电脑鼠走迷宫竞赛电脑鼠原理及其应用机电动力试验平台第二届IEEE标准电脑鼠走迷宫竞赛论文东南大学第二届IEEE标准电脑鼠走迷宫竞赛电脑鼠原理及其应用机电动力试验平台目录一．软件程序框图 (3)二．参赛软件研发过程 (4)三．软硬件调试过程 (4)四．各组员分工 (4)五．体会心得 (5)附录 (6)参考书目 (9)软件程序框图东南大学第二届IEEE标准电脑鼠走迷宫竞赛电脑鼠原理及其应用机电动力试验平台参赛软件研发过程在void main()函数中，采用压栈的方式进行电脑鼠搜索，数组uint8 GmcCrossway[MAZETYPE*MAZETYPE]用于暂存未走过支路坐标。
数组uint8 GucMapBlock[MAZETYPE][MAZETYPE]记录每个点的地图信息，初始化为0x00。
函数void mouseGoahead(int8 cNBlock)、void mazeSearch(void)、void mouseTurnleft(void)、东南大学第二届IEEE标准电脑鼠走迷宫竞赛电脑鼠原理及其应用机电动力试验平台void mouseTurnright(void)、void mouseTurnback(void)和void objectGoTo(int8 cXdst, int8 cYdst)控制电脑鼠的运动状态。
void mapStepEdit(int8 cX, int8 cY)为制作等高图函数，它把记录等高值的数组uint8 GucMapStep[MAZETYPE][MAZETYPE]（初始化为0xff）赋值。
当电脑鼠搜索时无方向可走时就按照这个等高图的信息退回上个点，冲刺时也是一样的道理。
另外，为了缩短转弯时间，并且保证电脑鼠的稳定性，采取转弯时整步，直走时半步。
我们在Mouse_Drive.c文件中，加入全局变量int8 maincheck，初始化为0（其中0为不转弯，1为转弯）。
摘要 摘 要 一种电脑鼠走迷宫的算法■ 上海商学院 张新谊─────────────────────────────────────────────────────────────────电脑鼠（Micromouse ）实际上是一个由微处理器控制的，集感知、判断、行走功能于一体，能够自动寻找最佳路径到达目的地的小型机器人。
国际电工和电子工程学会（IEEE ）每年都要举办一次国际性的电脑鼠走迷宫竞赛。
本文介绍一种能满足IEEE 学会颁布规则的电脑鼠走迷宫算法。
───────────────────────────────────────────────────────────────── 关键词 运行时间 迷宫时间 碰触 排障时间─────────────────────────────────────────────────────────────────电脑鼠的英文名称为Micromouse ，实际上是一个由微处理器控制的，集感知、判断、行走功能于一体，能够自动寻找最佳路径到达目的地的小型机器人。
它可以在“迷宫”中自动感知并记忆迷宫地图，通过一定的算法，寻找一条最佳路径，以最快的速度到达目的地。
1997年，在美国举办了第一届电脑鼠竞赛，随后，电脑鼠竞赛传入欧洲，首届欧洲电脑鼠竞赛于1980年在伦敦举办，之后英国的电脑鼠比赛便由电子工程协会（IEE ）主办。
1980年11月日本电脑鼠协会（JMA ）在东京举办了第一届竞赛，此后，日本每年都要举办一届电脑鼠竞赛。
我国台湾也于1986年10月举办了首届电脑鼠比赛。
现在国际电工和电子工程学会（IEEE ）每年都要举办一次国际性的电脑鼠走迷宫竞赛，各国选手报名踊跃，主要是大学生，为此部分大学还开设了“电脑鼠原理和制作”选修课程。
由于电脑鼠要由参赛选手自己设计制作，不仅要求选手具有嵌入式系统应用﹑传感器﹑控制技术等多方面的知识、经验和实践能力，还要求具有编写寻找最佳路径算法的能力。
老鼠走迷宫问题python课程设计一、课程目标知识目标：1. 学生能理解迷宫问题在算法中的应用，掌握利用Python进行迷宫路径寻找的基本算法。
2. 学生能够掌握利用循环和条件语句来控制程序流程，解决迷宫问题。
3. 学生能理解二维列表的使用方法，并将其应用于表示迷宫结构。
技能目标：1. 学生能够运用Python编程语言，设计并实现一个解决老鼠走迷宫问题的程序。
2. 学生能够通过调试程序，找出并修正代码中的错误，提高问题解决能力。
3. 学生能够运用算法思维，将复杂问题分解为简单步骤，逐步解决。
情感态度价值观目标：1. 学生在课程中培养解决问题的兴趣，增强对编程和算法的热爱。
2. 学生通过合作学习，培养团队协作能力和沟通能力。
3. 学生在解决迷宫问题的过程中，培养面对困难勇于挑战、不断尝试的精神。
课程性质：本课程为Python编程的实践应用课，通过解决迷宫问题，让学生在动手实践中掌握编程技能和算法思维。
学生特点：学生具备基本的Python编程知识，对算法有一定了解，具有较强的逻辑思维能力和好奇心。
教学要求：课程要求学生在理解迷宫问题的基础上，通过编程实践，掌握相关知识点，实现课程目标。
在教学过程中，注重培养学生的动手能力、问题解决能力和团队协作能力。
通过分解课程目标为具体的学习成果，为教学设计和评估提供依据。
二、教学内容1. 迷宫问题基本概念：介绍迷宫问题的定义、分类以及在计算机科学中的应用。
- 教材章节：第二章 算法与程序设计，第三节 算法应用实例。
2. Python编程基础回顾：回顾循环、条件语句、列表等基本知识，为解决迷宫问题打下基础。
- 教材章节：第一章 Python语言基础，第二节 控制结构；第三节 数据结构。
3. 二维列表表示迷宫：讲解如何使用二维列表来表示迷宫结构，以及如何进行路径查找。
- 教材章节：第二章 算法与程序设计，第二节 数据结构进阶。
4. 迷宫问题求解算法：介绍深度优先搜索、广度优先搜索等基本算法，并分析其在迷宫问题中的应用。
天津职业技术师范大学Tianjin University of Technology and Education课程设计专业班级：应电0814学生姓名：乔伟 09 李月 19 华焱建 43指导教师：刘新月系别：电子工程学院目录1 电脑鼠走迷宫 (1)1.1电脑鼠技术指标 (1)1.2电脑鼠方案论证及选择 (1)1.2.1核心控制器 (1)1.2.2传感器 (1)1.2.3电动机 (1)1.2.4电源 (1)1.3电脑鼠总体电路图 (2)1.4电脑鼠系统组成框图 (2)1.5电脑鼠单元电路设计 (2)1.5.1传感器单元 (2)1.5.2步进电机驱动单元 (3)1.5.3电源单元 (4)1.6运动算法设计 (5)1.7迷宫坐标信息采集算法 (5)1.8迷宫算法 (7)1.9测试结果分析及改进 (8)1.10总结 (8)2 智能电梯控制系统 (9)2.1主要技术指标 (9)2．2方案论证及选择 (9)2.3系统组成框图 (9)2.4单元电路设计 (10)2.4.1单片机最小系统模块 (10)2.4.2开关控制模块 (11)2.4.3电机驱动模块 (11)2.4.4液晶显示模块 (11)2.4.5报警模块 (12)2.4.6 电路总图 (13)2.5软件流程图以及任务描述 (13)2.6元件清单 (14)2.7 调试过程 (15)2.8总结 (15)参考文献 (16)附录1 电梯代码 (17)附录2 个人总结 (28)1电脑鼠走迷宫1.1电脑鼠技术指标依据IEEE标准迷宫构建相应数据结构，结合数据结构进行迷宫搜索算法的设计；分析电脑鼠硬件需求进行产品选型，构建硬件平台；实现电脑鼠自动搜索迷宫，从中选出最佳路径进行冲刺的功能。
1.2电脑鼠方案论证及选择1.2.1核心控制器基于所需完成任务要求我们知道，电脑鼠核心控制器需要有很快的信息处理速度。
那么，普通的8位单片机不能满足快速处理的条件，不能胜任任务。
为了实现高速信息处理，采用由Liminary公司生产的LM3S615控制器，该控制器是以ARM-Cortex-M3为内核的32位SOC系统，拥有50-MHz工作频率，可以胜任任务所要求的高速信息处理能力。
计 算 机 系 统 应 用 2012 年 第21卷 第 9 期80 研究开发 Research and Development基于向心法则的电脑鼠走迷宫算法设计与优化①贺少波, 孙克辉(中南大学 物理与电子学院, 长沙 410083)摘 要: 电脑鼠是一个集自主迷宫搜索、搜索完后最短路冲刺、传感与控制于一体的自主移动机器人系统. 具体设计和实现了基于向心法则迷宫搜索算法, 并对算法和迷宫搜索流程进行优化, 实验证明优化后的算法, 在保持原有算法高效的基础上具有更加好的局部效应, 相比同类型的算法, 优化后的向心法则是一种非常高效的迷宫搜索算法.关键词: 电脑鼠; 迷宫搜索; 自主移动机器人; 向心法则Design and Optimization of Micro-mouse Solving the Maze Algorithm Based on Central MethodHE Shao-Bo, SUN Ke-Hui(School of Physics and Electronic, Central South University, Changsha 410083, China)Abstract : Micro-mouse is an autonomous mobile robot(AMR) with self-maze search, the short sprint after the search, sensing and controller. In this paper, the maze search algorithm is designed and implemented based on the central method. The method and maze search process was optimized. Experimental results proved that the optimized algorithm improves on the efficient of the original method, and it has a better local effect. Finally, compared with other algorithms, we found that the central method is a very efficient maze search algorithm Key words : micro-mouse; maze search; autonomous mobile robot; central method1 引言迷宫电脑鼠的概念最早由IEEE Spectrum 杂志在70 年代提出, 就是使用嵌入式微控制器、传感器和机电运动部件构成的一种智能行走装置, 可以在”迷宫”中自动记忆和选择路径, 寻找出口, 最终达到所设的目的地[1]. 目前电脑鼠走迷宫比赛在许多国家都很受关注, 迷宫电脑鼠在我国起步较晚, 直到2007年才在我国上海地区举行了首届电脑鼠比赛[2]. 文献[1-3]给出了有关迷宫电脑鼠的比赛规则和要求.迷宫求解是一个经典求解问题, 现有的迷宫求解算法主要可以分为两大类, 传统算法及其改进的算法、新兴智能算法. 新兴智能算法如遗传算法[4]、 蚁群算法[5]、粒子群算法[6]等, 这类算法适用于解大型迷宫, 由于算法存在随机性, 得到的结果不一定是最优解;① 收稿时间:2011-12-20;收到修改稿时间:2012-01-17传统算法最基本的是深度搜索和广度搜索[7], 传统算法存在搜索效率不高的问题, 在很多情况下都有可能会遍历整个迷宫才能找到解, 所以许多人在传统算法的基础上, 进一步改善这些算法, 经过改进后的算法有Flood Fill 算法[8]、Djikstra’s [9]等, 这些算法在搜索效率上有了较大的提高. 向心法则算法[3][10]是一种新型的深广结合的迷宫搜索算法. 文献[3][10]指出了向心法则的思想, 即以指向迷宫中心的方向为优先的前进方向, 但文献[3]中算法只能以迷宫中心为中心, 局限性很大, 文献[10]中没有给出向心法则具体实现方法, 且算法中心为迷宫中心, 所以, 本文把向心法则的中心扩展为任意目标点, 并具体实现和对其进行优化. 现阶段的文献中都只提到如何从起点搜索到迷宫目标点, 并没有提及到达目标点后如何继续往回搜索, 并回到起点, 本文提出对迷宫进行回程二次搜索的概念,2012 年 第21卷 第 9 期 计 算 机 系 统 应 用Research and Development 研究开发 81以使所得到的解接近最优解.本文实验用的电脑鼠硬件是广州周立功单片机公司提供的MicroMouse615, 其微处理器是Luminary 公司生产的基于Cortex-M3内核的ARM 处理器——LM3S615, 具有许多优点, 在尺寸上也完全符合比赛要求[3].2 迷宫环境建模电脑鼠在迷宫中行走时必须知道自己的位置和行走方向, 因此需要建立坐标系对迷宫方格进行标记和定义电脑鼠行走的方向变量. 为了方便迷宫信息存储, 迷宫墙壁数据采用16*16矩阵表示, 并初始化为0, 电脑鼠每走到新的一格, 就要根据传感器的检测结果更新当前位置的墙壁信息, 这里采用数组MouseBlock[i][j]表示方格(i, j) 的墙壁信息, 其中bit0~bit3分别表示该方格上、下、左、右有无墙壁信息(1为有路, 即没有墙壁; 0为无路, 即有墙壁), 这样当电脑鼠到过某一格并记录墙壁信息后, 该坐标处墙壁信息肯定不为0, 这也可以作为是否到过某一节点的判断依据.设置迷宫方向变量MouseDir, MouseDir=0~3分别表示电脑鼠向上、右、下、左前进, 每当电脑鼠转动90度或180度, 方向变量MazeDir 就做相应的调整, 这样电脑鼠就始终能知道自己的前进方向. 当某个节点具有两个或三个可行方向时, 本文定义其为分支节点, 并入栈对其进行保存, 当该节点的两个或三个可行方向都走过时, 节点出栈. 可见, 当栈长度为0时全迷宫搜索完毕. 分支节点的保存是非常重要的, 当电脑鼠无路可走时, 得回到分支节点处继续搜索.寻找最优路径在整过迷宫搜索过程中非常重要, 当电脑鼠无路可走时, 则要选取一条最短路跑到最近的分支节点堆栈处继续迷宫搜索, 同时电脑鼠迷宫搜索完毕后还得计算出一条从起点到终点的最短路进行冲刺. 最优路径计算算法可采用文献[11]中的加权等高图法.3 向心法则实现及改进3.1 向心法迷宫搜索算法原理当电脑鼠处于某个坐标位置时, 首先检测墙壁, 获取墙壁信息, 统计电脑鼠的前方、左方和右方可行走情况, 当存在可行走方向时, 按照向心法则选择前进的方向, 并到达下一格. 向心法则是由右手法则、左手法则、中左法则和中右法则按照一定的规则有机组合起来, 使得搜索方向始终以目标点所在方向为最优方向, 属于启发式算法的一种.右手法则: 首先检测电脑鼠右边是否可行, 可行则右转, 否则检测前面是否可行, 可行则不转向, 否则左转;左手法则: 首先检测电脑鼠左边是否可行, 可行则左转, 否则检测前面是否可行, 可行则不转向, 否则右转;中右法则: 首先检测电脑鼠前面是否可行, 可行则不转向, 否则检测右边是否可行, 可行则右转, 否则左转;中左法则: 首先检测电脑鼠前面是否可行, 可行则不转向, 否则检测左边是否可行, 可行则左转, 否则右转;(a)向心法则策略(b)迷宫搜索演示图1 向心法则迷宫搜索向心法则在搜索策略上采用如图1(a)所示的方法(原始向心法则思想)进行, 以目标点(比如迷宫目标点计 算 机 系 统 应 用 2012 年 第21卷 第 9 期82 研究开发 Research and Development(7, 7))将搜索区域分成四部分, 在每个区域根据当前电脑鼠的行走方向决定搜索策略, 可见向心法则是始终以离中心最近的方向前进的. 图1(b)为采用向心法则迷宫搜索路径示意图, 电脑鼠近贴着目标点搜索, 寻找效率是非常高效的, 但如果(6, 9)处左侧挡板没有, 电脑鼠将错失进入终点的机会, 所以现在的向心法则也有需要优化的地方. 3.2 向心法迷宫搜索算法的优化如图2(a)所示, 如果此时电脑鼠搜索策略不进行调整的话, 电脑鼠由于处于右上方, 将采用中左法则, 即会前进一格到达(6, 9)处, 直接”忽略”终点, 由于入口只有一个, 错失后将要经过很多步才能再返回此处到终点, 这样使得搜索效率大大下降, 所以这里根据实践经验对向心法进行改进. 改进后如图2(b)所示, 当电脑鼠位于左上方、右上方和右下方如图2(b)所处的位置时, 且当电脑鼠的行走方向如图2(b)所示时, 对搜索法则进行调整, 由原来的中左法则、中右法则调整为左手法则、右手法则, 这样就可大大提高电脑鼠的局部搜索效率. 由于电脑鼠到达阴影处四个位置的任意一个即可判定为电脑鼠到达终点, 所以调整区域每次为2格, 在实际运行中, 目标点可能只有中心处一格, 则相应的调整区域为1格, 当然, 调整区域可以适当往外围扩展, 以增大调整区域, 无论如何, 调整后同样是以目标点方向为最优先方向, 且具有更好的局部效应.在实际迷宫中, 可能会有很多如图2(c)所示的U 型口, 当U 型口外墙壁三个位置墙壁信息已知, 则可以把该处墙壁信息预测出来, 减少无谓的搜索, 且电脑鼠在此类U 型口一进一出很容易碰壁出错, 即减少此类无谓搜索可提高电脑鼠运行的稳定性和搜索的高效性.根据比赛规则, 电脑鼠首先从起点出发, 找到目标点(图2(b)阴影)后再回到起点, 在实际比赛中, 可以在搜索到目标点后根据已知的迷宫信息直接计算出一条最短路回到起点, 这样做可以节省搜索时间, 但是由于只搜索了一条路, 往往这条路不是最短的. 为了提高迷宫搜索的有效性, 出发时应当以(7, 7)为中心进行向心法则搜索, 找到目标点后再继续往回搜索并回到起点. 这里往回搜索时可以以起点或前文所述的第一个分支节点为中心进行向心法则搜索, 当检测到往回搜索的路径与原来路径重合时, 直接回到起点准备冲刺.(a) 忽略点(b)搜索法则调整 (c)墙壁信息预测图2 算法改进示意图4 迷宫求解结果4.1 向心法则迷宫图3 向心法则迷宫搜索结果为了实际展示算法的性能, 本文搭建如图3所示的迷宫, 并模拟一次完整的比赛. 首先以迷宫终点之一(7, 7)为中心进行向心法则迷宫搜索, 电脑鼠判断已搜索到迷宫终点(图中黑点1处), 电脑鼠向后转, 并调整算法中心为第一个分支节点(1, 5), 即图中黑点2处, 继续利用向心法则进行迷宫搜索. 由于第一分支节点2012 年 第21卷 第 9 期 计 算 机 系 统 应 用Research and Development 研究开发 83在不同迷宫中所处位置一般不同, 可见本文对向心法则的改进能实现任一点为中心的向心法则搜索. 当电脑鼠到达(0, 6)时, 电脑鼠判断已和之前的路径连接起来, 此时直接回到起点, 利用加权等高图法计算出一条最短路准备冲刺到(7, 7), 冲刺完毕后回到起点, 即完成一次比赛. 利用本文向心法则, 电脑鼠的搜索结果如图3所示, 可见, 电脑鼠回程第二次搜索时搜到了一条更短的路. 4.2 与其它算法对比与其它迷宫搜索算法比较, 对图3所示迷宫进行起点到终点的搜索, 其搜索结果如表1所示. 左手法则、右手法则、中左法则和中右法则不属于启发式搜索算法, 所以其搜索效率也是最低的, 从表1中左手法则和右手法则的搜索结果来看, 搜到目标点所需的搜索时间最长, Djikstra ’s 搜索算法和Flood Fill 搜索算法是电脑鼠比赛中使用较多的算法, 它们的效率也是很高的, 从表1中可以看出, 两者搜索的步数和拐弯次数一样. 向心法则与这两者一样, 效率很高, 其搜索效率略优于Djikstra ’s 搜索算法和Flood Fill 搜索算法. 回程二次搜索后, 利用等高图法计算出冲刺时的最短路步数为23步, 拐弯数8次, 明显优于Flood Fill 和Djikstra ’s 的最短路49步和拐弯次数16次.需要指出的是, 在比赛中或实际情况下迷宫是随机的, 在不同的迷宫中, 不同的搜索算法搜索的路径一般是不相同的, 且效率也不一样, 也就是说两种不同的高效算法A 和B, 在这个迷宫中A 比B 搜到的路径短, 换个迷宫, 搜到的路径就可能变长, 也可能一样; 如果做的不是全迷宫搜索, 而只是部分的, 就无法保证所得的最短路是迷宫真正的最短路.5 结论本文研究和实现了基于向心法则的电脑鼠走迷宫算法, 并结合实验测试对其进行了优化, 提出了一些能提高比赛效率的方法. 与现有常用算法比较后发现, 本文算法在搜索步数、拐弯次数, 以及冲刺路径方面具有一定的优势. 实验测试表明, 优化后的搜索算法在保证原有算法高效的前提下, 能更好的处理一些特殊迷宫, 提高了算法效率和实用性.参考文献1 UK Micromouse Championship. UK Micromouse Hampion- ship Mieromouse Championship, 2006. http:// /micromouse/toh.asp2 IEEE 国际电工和电子工程学会.IEEE 电脑鼠(迷宫)竞赛规则和介绍.嵌入之梦.2009.htttp:/// xgzl/2007-08-28/24.html3 周立功.IEEE 电脑鼠开发指南.广州致远电子有限公司, 2008.4 王科俊,徐晶,王磊,张燕.基于可拓遗传算法的机器人路径规划.哈尔滨工业大学学报,2006,38(7):1135−1138.5 张美玉,黄翰,郝志峰,杨晓伟.基于蚁群算法的机器人路径规划.计算机工程与应用,2005,41(5):34−37.6 刘关俊.基于粒子群算法的移动机器人路径规划研究.长沙:中南大学,2007.7 张公敬,杨厚俊,刘征.注水法求解迷宫最优路径.计算机仿真,2007,24(8):171−208.8 Manoj Sharma, Kaizen Robeonics. Algorithms for Micro- mouse. International Conference on future Computer and Communication, 2009,(38):581−585.9 Mishra S, Bande P. Maze solving algorithms for micro mouse. IEEE International Conference on Signal Image Technology and Internet Based Systems, 2008,(104): 86−93.10 张新谊.一种电脑鼠走迷宫的算法.单片机与嵌入式系统的应用,2007,(5):84−85.11 王凤林,王宜怀.一种电脑鼠走迷宫算法的设计与实现.计算机应用与软件,2010,27(12):270−273.基于向心法则的电脑鼠走迷宫算法设计与优化作者：贺少波， 孙克辉作者单位：中南大学 物理与电子学院, 长沙 410083刊名：计算机系统应用英文刊名：Computer Systems & Applications年，卷(期)：2012(9)本文链接：/Periodical_jsjxtyy201209018.aspx。
