下载文档原格式
Microcontrollers &Embe dded Systems 2011年第5期ww w .mesne 电脑鼠软件系统关键技术研究**基金项目:淮阴工学院青年教师科研基金(项目编号:2917372)。
李亚洲,严石(淮阴工学院电子与电气工程学院,淮阴223003)引 言电脑鼠(micro mouse)是一个由微处理器控制的集感知、判断、行走功能于一体,能够自动寻找最佳路径到达目的地的微型机器人。
电脑鼠走迷宫竞赛就是让电脑鼠在迷宫中从起点以最短的时间走到终点的过程[1]。
电脑鼠是集软件和硬件为一体的系统。
电脑鼠的软件系统是电脑鼠的大脑,需要具备获得迷宫信息、遍历迷宫、计算最优路径等功能。
同时,在没有硬件支持的情况下,电脑鼠软件系统应能够模拟迷宫,以验证算法的正确性。
1 总体设计根据电脑鼠比赛的要求,电脑鼠要遍历迷宫,以获得迷宫信息;电脑鼠要根据迷宫信息,获得最优路径;电脑鼠要根据最优路径,实现最终冲刺。
电脑鼠软件系统的设计包括迷宫表示、迷宫遍历、最优路径查找等模块。
2 电脑鼠软件系统关键技术2.1 迷宫表示电脑鼠迷宫由16 16个正方形单元格组成,单元格大小为18cm 18c m 。
俯视迷宫,每个单元只有4条边,每条边只能有两种状态 墙壁或通路。
针对这种情况,可以使用四维数组或者结构体表示单元格的4条边,用2个数字表示迷宫单元每条边的2种情况。
对于迷宫,可以使用坐标表示每个单元的位置。
假设电脑鼠置于起点,电脑鼠正对通路,电脑鼠正前方为正Y 方向,电脑鼠右方为正X 方向。
这样,对于迷宫中的每个单元格都对应一个确定的坐标。
设计时,可采用坐标值作为二维数组的索引。
2.2 迷宫遍历电脑鼠要尽可能遍历迷宫中每一个单元格,为寻找最优路径提供足够的信息。
对于电脑鼠探测墙壁,通过传感器得到的是前方、右方以及左方等相对方向上的信息,为了记录迷宫中每个单元格的信息,需要把相对方向转换为绝对方向。
相对方向,是指相对于电脑鼠正对的方向。
电脑鼠学习心得和遇到的问题及解决方法彭旺 16012126学习心得：在大一的时候就经常看见学长们整天在宿舍弄一个小车，后来才知道那就是视觉知道机器人。
于是到了大二选择选修课的时候就果断选了这个课。
本来我选的是机器人那个，上了才知道又要做实验还要参加比赛还要交押金甚是麻烦，顿时欲哭无泪，硬着头皮去上，因为分组问题被弄到了电脑鼠这边来，觉得比机器人那边要好玩得多。
第一次去上课就要交押金，并且那个电脑鼠还好贵的，整整两千多啊。
那是最开始就给我们讲了电脑鼠处理器运行的相关函数，后面几节课分别讲了电脑鼠在迷宫中搜索以及最后冲刺的相关程序。
好吧，我承认当时确实有点无聊。
直到后来，老师终于给了我们完整的程序，于是兴奋的我们毫不犹豫的把程序“捎”了进去，然后把电脑鼠放到迷宫中，结果发现它除了撞墙就是转圈。
探索调试：我们小组分工合作，一起研发。
电脑鼠走迷宫可以采用全迷宫探索策略，即将迷宫的所有单元均搜索一次，从中找出最佳的行走路径。
或者可以采用部分迷宫探索策略，即在有限的时间或探测次数下，只探测迷宫的一部分，从中找出次最佳的路径。
我们的电脑鼠要实现的功能有如下几个方面：路口检测:由安装在前、右、左的三个红外线发射对管SIR563ST3F 和IRM8601S实现, 发射信号为38KHz, 实现远红外测距功能, 探测前、右、左有无障碍。
行走控制:由左、右两个红外线发射对管SIR563ST3F和IRM8601S为实现, 发射信号为30.5KHz, 实现近红外测距功能, 保持电脑鼠在中轴线上行走, 避免撞墙。
路程控制:安装在左右轮内侧的红外收发对管IR204和PD204一6B, 对黑白码盘计数, 按照迷宫单元的长度为单位进行路程计数, 以记录老鼠在迷宫中的位置同时还可以准确地实现转弯。
微控制器和其它子系统共同构成一个闭环的反馈控制系统, 通过对三种传感器信号的检测行走信号、路口信号和黑白码盘计数信号, 由微控制器进行运算, 运算结果交给电机执行, 由此实现电脑鼠的智能穿越迷宫。
电脑鼠的原理分析及算法研究摘要：本文阐述了电脑鼠的定义和意义，并对电脑鼠的工作原理及硬件、软件设备进行一定的分析，研究了一些传统和经典的算法。
关键词：电脑鼠，模块，算法，蚂蚁算法Analysis of the Principle and Study of Algorithm ofMicroMouseWang Huinan 04010515(Southeast University, Nanjing, 211189)Abstract:This paper describes the definition and significance of MicroMouse. And analyzing the work principle of MicroMouse’s hardware and software equipment. Studying a number of traditional and classical algorithms.Key words: MicroMouse; Module; Algorithms; Ant algorithm本学期，我选修了机电一体化——电脑鼠。
通过学习和查找资料，我对电脑鼠的运行原理有了一定的了解，并产生了一些新的想法。
1电脑鼠的基本知识1.1电脑鼠的定义所谓“电脑鼠”，英文名叫做MicroMouse，是使用嵌入式微控制器、传感器和机电运动部件构成的一种智能行走装置的俗称，它可以在“迷宫”中自动记忆和选择路径，寻找出口，最终达到所设定的目的地。
实际上电脑鼠就是一个电力驱动小车，而这个电动小车是由一个或多个为控制器来控制，通过传感器和其他各功能器件的配合，具备一定的智能。
同时，电脑鼠拥有探测障碍物、行走、转弯、加减速好制动等基本功能。
1.2电脑鼠的意义电脑鼠可谓是一种具有人工智能的小型机器人，结合了机械、电机、电子、控制、光学、程序设计和人工智能等多方面的科技知识。
电脑鼠走迷宫智能算法的研究与优化王艺宁;蒋涵;王博;于娜【摘要】电脑鼠(Micromouse)是智能机电鼠的简称,实际上是一个由微处理器控制的,集感知、判断、行走功能于一体,能够自动寻找最佳路径到达目的地的微型机器人.该文简要分析了电脑鼠的硬件组成和工作原理,在此基础上重点对电脑鼠软件部分的探测策略模块、等高图制作模块、冲刺模块进行了分析研究与优化,并通过大量实验进行了验证.实验结果表明优化后的算法能够在一定程度上有效地提高电脑鼠走迷宫的运行速度、减少电脑鼠的搜索时间.【期刊名称】《科技创新导报》【年(卷),期】2015(000)032【总页数】3页(P129-130,132)【关键词】电脑鼠;嵌入式系统;智能算法;搜索法则【作者】王艺宁;蒋涵;王博;于娜【作者单位】天津农学院计算机与信息工程学院天津 300384;天津农学院计算机与信息工程学院天津 300384;天津农学院计算机与信息工程学院天津 300384;天津农学院计算机与信息工程学院天津 300384【正文语种】中文【中图分类】TP36该文以TQD-Micromouse-JZ电脑鼠为研究对象，以电脑鼠走迷宫比赛为背景。
电脑鼠车体采用四轮驱动结构，内核控制器采用32位ARM Cortex-M3 STM32，控制和检测红外传感器；微控制器根据检测到的传感信号，控制电机驱动电路，调整行走，按照载入搜索算法进行迷宫的探测，寻找最短路径，最终实现从起点到终点的冲刺。
该部分主要研究的是TQD-Micromouse-JZ电脑鼠的硬件设计，针对电源模块、微控制器单元模块、传感器模块和直流电机控制模块［1］四个模块进行研究。
其中ARM Cortex-M3 STM32内核控制器是电脑鼠的核心，通过检测传感器信号，结合载入的搜索算法，控制直流电机，从而实现电脑鼠在迷宫中的行走。
电脑鼠的软件部分主要用来检测迷宫环境，传送控制信号给相应的硬件模块，对在迷宫中行走的电脑鼠进行制导与导航［2］。
一种电脑鼠走迷宫的算法电脑鼠走迷宫的算法1探测策略电脑鼠走迷宫可以采用全迷宫探索策略，即将迷宫的所有单元均搜索一次，从中找出最佳的行走路径。
这种策略需要有足够的时间或探测次数，但在IEEE竞赛规则中每场竞赛只有15分钟的时间，因此是不可能的。
另一种方法是部分迷宫探索策略，即在有限的时间或探测次数下，只探测迷宫的一部分，从中找出次最佳的路径，显然只能采用这种策略。
电脑鼠在一巷道内行走，如果最后无路可走，则该巷为死巷。
电脑鼠在任一单元内，可能的行走方向最多只有三个（前、左、右），如果有二个或二个以上的可能行走方向，称为交叉，遇有交叉时，由于有多个可以行走的方向，在行走方向的选择上，可有下面的几种选择法则：•右手法则：遇有交叉时，以右边为优先的前进方向，然后是直线方向、左边方向。
•左手法则：遇有交叉时，以左边为优先的前进方向，然后是直线方向、右边方向。
•中左法则：遇有交叉时，以直线为优先的前进方向，然后是左边方向、右边方向。
与此类似的还有中右法则。
•乱数法则：遇有交叉时，取随机值作为前进方向。
•向心法则：由于终点在迷宫的中心，遇有交叉时，以向迷宫中心的方向为优先的前进方向。
2标记为了记忆迷宫的详细信息，需要对迷宫单元的位置进行线路标记。
全迷宫共有16×16个单元组成，可采用二维坐标方式标记，即用每个单元的XY坐标表示，如起点可标记为（0，0），终点为（7，7）。
此外，还需要对迷宫单元的可行进方向进行标记，可采用绝对方位或相对方位二种方式。
绝对方位：这是一种与电脑鼠行进方向无关的标记方式，以一个四位的二进制数，分别表示“东”﹑“西”﹑“南”和“北”四个方向。
以1表示允许行进（无墙壁），0表示不允许行进（有墙壁）。
相对方位：这是一种与电脑鼠行进方向有关的标记方式，以一个三位的二进制数即可实现标记，分别表示“前”“左”“右”，以1表示允许（无墙壁），0表示不允许（有墙壁）。
3阻断在电脑鼠试跑过程中或在最后冲刺时，需要对部分路径进行“阻断”，即在发现某条路径是死路（只有入口而无出口）时，在该路径的入口处（一般是交叉点）设置标记，即将入口的线路标记由1改为0。
走迷宫电脑鼠的算法分析与研究收稿日期:2010-03-30;修订日期:2010-11-08作者简介:夏炎（1984-），男，南京人，硕士研究生，研究方向：基于ARM 的嵌入式系统的设计与开发。
夏炎（南京工业大学电子与信息工程学院，南京210013）摘要:电脑鼠的灵活性和智能程度不但取决于硬件的结构和性能，还取决于软件设计的好坏，越是智能的电脑鼠，其软件设计就越不简单。
对走迷宫电脑鼠的算法做了总结和比较，并对各算法的优缺点进行了阐述。
关键词:电脑鼠；迷宫；算法中图分类号:TP18文献标识码:A 文章编号:1008-8725（2011）01-0194-03Analyzing and Researching on Maze-runningMicromouse AlgorithmXIA Yan（School of Electronics and Information Engineering,Nanjing University of Technology,Nanjing 210013,China ）Abstract:The flexibility and intelligence degree of Micromouse depended on not only structure and properties of hardware,but also whether software design was good or bad.The more intelligent the Micromouse was,the more difficult software design was.This paper concluded and compared the algorithms of maze -running micromouse,and discribed advantages and disadvantages of different algorithms.Key words:Micromouse;maze;algorithm0引言人类在科技的发展史上，一直在尝试着想要创造出一个具有肢体、感官、脑力等综合一体的智能机器人，而电脑鼠就是一个能够用来诠释肢体、感官及脑力综合工作的基本实例，这也是当初电脑鼠被发明的理由，希望能够借助电脑鼠的创作来进而研究与发明更加复杂的机械。
电脑鼠控制系统工作原理及设计方案1电脑鼠工作原理电脑鼠周围安装六组红外传感器，分别感知左方、左前方、前方、右前方、右方，发射端发射一定频率的红外线，接收端通过六个方向的反射波来判断是否有障碍物，实时地储存单元格的资料，通过六组红外传感器反馈的迷宫信息，控制电脑鼠完成避障、转弯、加速等动作，运用智能算法对迷宫的部分单元格或全部单元格进行遍历，并将迷宫的信息以有效的数据结构存储，微控制器根据这些记录信息运用迷宫高效算法找到一条最优化路径，从而实现从起点到终点的最大化冲刺。
2 硬件电路设计为完成迷宫探测和冲刺任务，电脑鼠需具备以下各功能模块：ARM微处理器作为控制核心协调各功能模块正常工作;电机及驱动模块实时控制电机启动、制动;红外检测模块负责红外线探测感知;电源为整个系统供电稳定电压，陀螺仪及指南针模块确定电脑鼠方位，根据走过的距离，从而解析出所在坐标。
硬件组成如图1所示。
2.1 电源模块电源调节器件通常使用线性稳压器件(如LM7805)，具有输出电压可调、稳压精度高的优点，但是其线性调整工作方式在工作有较大的热损耗，导致电源利用率不高、满足不了便携低功耗需求。
开关电源调节器，不同于线性稳压器件，以完全导通或关断的方式工作，通过控制开关管的导通与截止时间，有效的减少工作中的热损耗，提高了电源利用率。
本设计中电源模块为系统提供三种不同的电压，12V电源用于驱动电机，使用开关式电源LM2596将12V直流电压降到5V给红外模块、人机交互模块供电，再通过AMS1117将5V降到3.3V，供ARM处理器及其他模块使用。
2.2 微处理器模块微处理器是整个控制系统的核心，它完成从红外检测模块获取路径信息，采集瞬时速度，进行数据处理，控制算法运算，输出实时控制量等功能。
为了保证系统的实用性和易扩展性，本控制系统采用意法半导体推出的增强型系列STFM32F103RCT6，STM32F103xx增强型系列使用高性能的ARM Correx-M3 32位的RISC内核，工作频率为72MHz，内置高。
电脑鼠电路及搜索算法 Company Document number：WUUT-WUUY-WBBGB-BWYTT-1982GT本科毕业设计设计题目：电脑鼠电路的改进及搜索算法的研究学生姓名：陈昱学号：专业：应用物理学指导教师：杨济民学院：物理与电子科学学院2010年 5月 5日毕业设计内容介绍目录中文摘要 (4)英文摘要 (4)一、引言 (5)二、硬件改进 (7)（一）电源电路的改进 (7)1、原电路 (7)（1）电机驱动芯片供电 (7)（2）系统供电 (7)（3）传感器供电 (7)2、改进方案 (8)（二）传感器电路的改进 (10)1、工作原理 (10)2、原电路 (10)3、改进方案 (11)三、底层算法的研究 (12)（一）传感器驱动 (12)（二）电机控制 (14)（三）姿态纠正 (17)（四）信息采集 (19)（五）连续转弯 (21)四、迷宫算法的研究 (21)（一）传统算法 (21)（二）本文的迷宫算法 (22)五、算法的实现与调试 (24)（一）基于 uC/OS-II 多进程的软件设计 (24)（二）软件调试 (34)六、总结 (34)七、致谢 (35)参考文献 (35)电脑鼠电路的改进及搜索算法的研究陈昱（山东师范大学物理与电子科学学院济南）摘要: 简要介绍了电脑鼠走迷宫竞赛。
分析了MicroMouse615中电源系统和红外发射系统的不足，提出了改进方案，并给出了电路图。
给出了电机控制算法、用于姿态纠正的数字PID算法、传感器驱动算法、连续转弯算法、迷宫信息采集算法以及迷宫搜索与最短路径算法等算法模块。
用基于RTOS的多进程架构实现了上述各算法模块，并给出了各个算法的流程图。
用无线模块与上位机进行通讯实现了算法的实时跟踪与可视化。
关键词:数字PID 迷宫算法红外测距电机控制 RTOS中图分类号：Micromouse circuit improvements and search algorithmChen yu（Shandong Normal University Colleges of Physics & Electronics, Jinan）Abstract : Introduced the Micromouse maze the power system and infrared emission system of MicroMouse615 , proposed a improvement program, and gived the circuit diagram. Motor control algorithm was given, together with the Digital PID algorithm to correct posture, sensor-driven algorithm, continuous turning algorithms, maze of information acquisition algorithm and a maze search algorithm with the shortest path algorithm framework for multi-process mechanism was used to achieve the above algorithm module, and the flow chart of each algorithm was given .Real-time tracking and visualization of algorithm were achieved through communicating with the host computer algorithm by wireless module .Key words: Digital PID; Maze algorithm; Infrared range; Motor Control; RTOS CLASSNO:一、引言电脑鼠英文名叫做MicroMouse，是使用嵌入式微控制器、传感器和机电运动部件构成的一种智能行走装置（微型机器人）。
电脑鼠算法优化分析作者：李彤来源：《河南科技》2017年第03期摘要：电脑鼠是由微处理器控制的集感知、判断、行走功能于一体的小型机器人，其可以在“迷宫”中自动感知并记忆迷宫地图，以最快的速度到达目的地。
基于此，针对电脑鼠算法进行优化分析。
关键词：电脑鼠算法；微处理器控制；路径选择法则；自动搜索中图分类号：TP242 文献标识码：A 文章编号：1003-5168（2017）02-0024-021电脑鼠算法概述电脑鼠走迷宫可采用全迷宫探索策略，即将迷宫所有单元均搜索一次，从中找出最佳行走路径。
这种策略需要有足够的时间或探测次数，但在IEEE竞赛规则中每场竞赛只有15min，因此是不可能的。
另一种方法是部分迷宫探索策略，即在有限的时间或探测次数下，只探测迷宫的一部分，从中找出次最佳的路径，显然只能采用这种策略。
2迷宫信息的存储因为迷宫分为16×16=256个方格，所以很直观地可以想到用一个二维矩阵来存储一个迷宫的信息，矩阵中的每一个元素用于存储地图中一个方格的信息，矩阵每个元素可以定义成Byte 型，只用其中的4位就可以存储方格四面的挡板信息。
要获取某一个方格单个方向的挡板信息，只需做一个简单的运算看结果是否为0即可。
2.1数据的存储方式绝对方向和相对方向的变换：假设数值0、1、2、3分别表示绝对方向的上、右、下、左，那么就用0、1、2、3中的其中一个数值来表示当前小车车头朝向的方向，当然这个数值是动态变化的，其实转化的规则相当简单，右转方向数值加1，左转方向数值加3，后转方向数值加2，当然可能有越界的情况。
所以，得出的方向数值再进行模运算对4取余数得出的结果，就是转弯后小车的车头所面向的方向的数值。
通过矩阵可以找到当前的小车方向和转弯后的小车方向的对应关系，得出的相对方向和绝对方向的转换公式如下所示：转弯后的绝对方向=（转弯前的绝对方向+转弯数值）%4小车的车头方向一般是用一个全局变量来存储的，方便在转弯的函数中进行修改，避免C 语言中一些作用域的问题。
基于吸盘电脑鼠的设计与控制方法研究作者：薛艳来源：《中小企业管理与科技·中旬刊》2020年第12期【摘要】随着工业化水平的提高，电脑鼠作为自动化机器人开始被广泛应用于各个领域。
设计电脑鼠需要对其运动机能、行走路径、传感器应用等多种技术进行研究，以保证电脑鼠具备良好的稳定性，之后再对其速度与算法进行针对性改进。
论文在传统电脑鼠的设计与控制方式中引入吸盘结构，对吸盘吸力与电脑鼠的移动速度进行合理化匹配，通过红外线传感技术与梯形转弯策略，控制吸盘电脑鼠的电机转速与运行时间。
【Abstract】With the improvement of industrialization level， computer mouse as an automatic robot has been widely used in various fields. In order to design a computer mouse， we need to study its movement function， walking path， sensor application and other technologies， so as to ensure that the computer mouse has good stability， and then improve its speed and algorithm. This paper introduces the suction cup structure into the design and control mode of the traditional computer mouse， and rationalizes the match between the suction of the suction cup and the moving speed of the computer mouse. Through infrared sensing technology and trapezoidal turning strategy， the motor speed and running time of the computer mouse with the suction cup are controlled.【關键词】吸盘;电脑鼠;迷宫搜索;智能算法【Keywords】suction cup; computer mouse; maze search; intelligent algorithm【中图分类号】TP242 【文献标志码】A 【文章编号】1673-1069（2020）12-0185-021 引言机器信息化与自动化是当前科技发展的主旋律，并且随着机器人自动化程度的提升与规模的扩大，使其应用范围从高精尖领域逐渐渗透至日常的智能家居、物流传输、生物医疗等诸多方面。
第五章蚁群算法在迷宫电脑鼠中的应用引言许多智能问题，如下棋游戏、战略决策、机器人路径规划等都可以转化为寻找迷宫最优路径问题。
传统解决迷宫最优路径问题的算法通常会随着迷宫规模的增大、复杂性的增加，算法的空间和时间复杂性呈指数增加，从而很难用于求解大规模的问题实例。
从蚁群觅食过程中能够发现蚁巢与食物源之间的最短路径受到启发，并利用该过程与着名的旅行商问题( Traveling Salesman Problem, TSP)之间的相似性，意大利学者M. Dorigo等人提出了一种新型的模拟进化算法---蚁群算法[1,2]。
对TSP问题的求解结果显示，蚁群算法具有极强的鲁棒性和发现较好解的能力，但同时也存在一些缺陷，如收敛速度慢、易出现停滞现象等[2]。
目前，蚁群算法已在组合优化、计算机网络路由、连续函数优化、机器人路径规划、数据挖掘、电网优化等领域取得了突出的成就[2-5]，实践证明该算法是一种解决优化问题特别是组合优化问题的有力工具。
迷宫的基本信息及常用迷宫搜寻策略5.2.1 迷宫的基本信息从比赛规则中得知，迷宫是由一个个18cm×18cm大小的方格组成的，迷宫大小为16×16，即行列各有16个方格。
若将三维迷宫转化成二维图形,迷宫可用图表示.图迷宫行列与坐标对应关系5.2.2 常用搜寻法则和策略5.2.2.1迷宫搜寻法则设定搜寻法则和策略是为了电脑鼠可以以最快的方式找到终点，到达目标后随即从所走过的路径中找出一条可行路径返回起点，然后再做冲刺，直达目的；法则的设定很重要，它可以使电脑鼠不多走冤枉路，可节省很多时间而制胜。
每一只电脑鼠到达一方格时它最多有三个方向可前进，最少则因为三面都有墙，没有可以前进的方向；当遇到二个以上的可选择方向时，由于不同场合需要而有不同优先搜寻的方向顺序，常见的法则有以下几种：①右手法则：遇叉路时，以右边为优先前进方向，然后直线方向，左边方向；②左手法则：遇叉路时，以左边为优先前进方向，然后直线方向，右边方向；③中左法则：与右手法则相似，不过方向选择顺序改为直线优先，然后左边，右边；④中右法则：遇叉路时，以直线为优先前进方向，然后右边方向，左边方向；⑤求心法则：遇叉路时，以距中心最短的那个方向优先，然后依次选择。
⑥乱数法则：以电脑鼠的随机值作为下一前进方向。
5.2.2.2迷宫搜寻策略迷宫搜寻模式有全迷宫搜寻策略和部分迷宫搜寻策略两种：①全迷宫搜寻策略：电脑鼠以任一搜寻法则前进到达终点后，电脑鼠会反身继续前进，然后以原设定的搜寻法则，时时检查未走过的路，直到每一方格都搜寻过后，才回起点。
②部分迷宫搜寻策略：电脑鼠以任一搜寻法则前进到达终点后，电脑鼠将沿原路线返回起点，不再进行其它搜寻。
如果比赛规则不计算搜寻时间，可采用全迷宫搜寻策略，待地毯式的搜寻过所有方格后，再计算最佳路径，作最后的冲刺，冲刺成绩一定相当不错。
由于新制国际比赛规则加入搜寻时间的成绩计量，因此我们必须考虑部分迷宫搜寻策略，甚至还可能须考虑加入求心法则，截路径功能等更智慧的法则来协助；此时找到的路径可能不是最佳路径，但保证花的时间最短。
5.2.3 迷宫问题经典算法求解迷宫问题，经典算法有深度优先搜索和广度优先搜索两种。
①深度优先搜索(DFS)：从入口出发，顺着某一方向向前探索，若能走通，则继续往前走；否则沿原路退回(回溯)，换一个方向再继续探索．直至所有可能的通路都探索到为止。
如果恰好某一步探索到出口，则就找到了从入口到出口的路径。
为了保证在任何位置上都能沿原路退回，防止死循环，需要使用堆栈来保存大量记录。
而要求解迷宫最短路径，则必须用深度优先搜索出所有到达出口的路径，通过比较得到最短距离的路径．这样也必然要求增加数据空间来保存搜索过程中当前最短路径．增加了空间复杂度。
②广度优先搜索(BFS)：从入口出发，离开入口后依次访问与当前位置邻接的单元格(上下左右方向)，然后分别从这些相邻单元格出发依次访问它们的邻接格，并使“先被访问的单元格的邻接格‘先于’后被访问的单元格的邻接格”被访问，直至访问到迷宫出口，则找到了迷宫问题的最优解，即迷宫最短路径。
该算法的显着特点是“层层推进”，探索点会随着探索的深入急剧增加，相应地，需要大量的空间用来保存探索过程的记录．空间复杂度大。
与此同时，上述两种算法都比较抽象复杂，编程实现容易出现问题．调试比较困难，因此在本篇论文中提出了一种新的容易理解和调试的算法，该算法复杂度较低，求解较大规模的迷宫问题也有不俗的表现。
蚁群算法在迷宫电脑鼠中的应用5.3.1 蚁群算法的基本知识5.3.1.1 蚂蚁的基本习性蚂蚁是最古老的社会昆虫之一，它的个体结构和行为虽简单，但是由这些简单个体构成的蚂蚁群体，却表现出高度结构化的社会组织.蚂蚁王国俨然是一个小小“社会”。
这里，有专司产卵的后蚁;有为数众多的从事觅食打猎、兴建屋穴、抚育后代的工蚁;有负责守卫门户、对敌作战的兵蚁;还有专备后蚁招婿纳赘的雄蚁等等.蚂蚁是社会性昆虫，组成社会的三要素之一就是社会成员除有组织、有分工之外，还有相互的通讯和信息传递。
研究表明，蚁群有着奇妙的信息系统，其中包括视觉信号、声音通讯和更为独特的无声语育，即包括化学物质不同的组合、触角信号和身体动作在内的多个征集系统，来策动其他个体.蚂蚁特有的控制自身环境的能力，是在高级形式的社会性行为及不断进化过程中获得的。
5.3.1.2蚂蚁的觅食策略觅食行为是蚁群一个重要而有趣的行为.据昆虫学家的观察和研究，发现蚂蚁有能力在没有任何可见提示下找出从蚁穴到食物源的最短路径，并且能随环境变化适应性地搜索新的路径，产生新的选择.虽然单个蚂蚁的行为极其简单，但由大量的蚂蚁个体组成蚂蚁群体却表现出极其复杂的行为，能够完成复杂的任务。
[1]生物学家和仿生学家经过大量的细致观察研究发现，蚂蚁在觅食走过的路径上释放一种妈蚁特有的分泌物--信息激素(Pheromone).蚂蚁个体之间正是通过这种信息激素进行信息传递，从而能相互协作，完成复杂任务.在一定范围内蚂蚁能够察觉到这种信息激素并指导它的行为，当一些路径通过的蚂蚁越多，则留下的信息激素轨迹(trail )也就越多，招致后来更多的蚂蚁选择该路径的概率也越高，于是越发增加了该路径的信息素强度.这种选择过程称之为蚂蚁的自催化过程，形成一种正反馈机制，可理解为增强型学习系统.蚂蚁最终可以发现最短路径.自然界中蚁群的自组织行为引起了昆虫学家的注意.Deuuu-bourg 等通过“双桥实验”对蚁群的觅食行为进行了研究如图所示，对称双桥(两座桥的长度相同)A 、B 将蚁巢与食物源分开，蚂蚁从蚁巢自由地向食物源移动.实验结果显示，在初始阶段出现一段时间的震荡(由于某些随机因素，使通过某座桥上的蚂蚁数急剧增多或减少)后，蚂蚁趋向于走同一条路径. 在该实验中，绝大部分蚂蚁选择A 桥.在实验初期，A, B 两座桥上都没有外激素存在，蚂蚁将以相同的概率选择A 、B 两座桥，故此时蚂蚁在两座桥上留下的外激素量相等.经过一段时间后，由于随机波动致使大部分蚂蚁选择A 桥(也有可能为B 桥)，因此更多的外激素将会留在A 桥上，致使A 桥对后来的蚂蚁有更大的吸引力.随着时问的推移，A 桥上的蚂蚁数将越来越多,而B 桥上正好相反.等人给出了上述实验的概率模型.首先，假定桥上残留的外激素量与过去一段时间经过该桥的蚂蚁数成正比(这意味着不考虑外激素蒸发的情况);其次，某一时刻蚂蚁按桥上外激素量的多少来选择某座桥，即蚂蚁选择某座桥的概率与经过该桥的蚂蚁数成正比.当所有m 只蚂蚁都经过两座桥以后，设Am, An 分别为经过A 桥和B 桥的蚂蚁数(Am+ An=m),则第m+ 1只蚂蚁选择A 桥的概率为:hm h m h m A k B k A k A m P )()()()(++++= 式 而选择B 桥的概率为:其中参数h 和k 用来匹配真实实验数据.第(m+1)只蚂蚁首先按式计算选择概率P A (m)，然后生成一个在区间[0,1]上一致分布的随机数a ，如果a ≤P A (m)，则选择A 桥，否则选择B 桥.图双桥实验除能够找到蚁巢和食物源之间的最短路径外，蚁群还有极强的适应环境的能力，如图所示，在蚁群经过的路线上突然出现障碍物时，蚁群能够很快重新找到新的最优路径。
图蚁群的自适应行为(a.)蚁群在蚁巢和食物源之间的路径上移动(b)路径上出现障碍物(c)较短路径上的外激素以更快的速度增加(d)所有的蚂蚁都选择较短的路径5.1.1.3 人工蚂蚁与真实蚂蚁的异同比较⑴相同点比较蚁群算法是从自然中真实蚂蚁觅食的群体行为得到启发而提出的，其很多观点都来源于真实蚁群，因此算法中所定义的人工蚂蚁与真实蚂蚁存在如下共同点。
①都存在一个群体中个体相互交流通信的机制。
人工蚂蚁与真实蚂蚁都存在一种改变当前所处环境的机制：真实蚂蚁在经过的路径上留下信息素，人工蚂蚁改变在其所经过路径上存储的数字信息，该信息就是算法中所定义的信息量，它记录了蚂蚁当前解和历史解的性能状态，而且可被其他后继人工蚂蚁读写。
②都要完成一个相同的任务。
人工蚂蚁与真实蚂蚁都要完成一个相同的任务，即寻找一条从源节点（巢穴）到目的节点（食物）的最短路径。
③利用当前信息进行路径选择的随机选择策略。
人工蚂蚁与真实蚂蚁从某一个节点到下一个节点的移动是利用概率选择策略实现的，概率选择策略只利用当前的信息去预测未来的情况，而不能利用未来的信息，故选择策略在时间和空间都是局部的。
⑵不同点比较在从真实蚁群行为获得启发而构造蚁群算法的过程中，人工蚂蚁还具备了真实蚂蚁所不具有的一些特性。
①人工蚂蚁存在于一个离散的空间中，他们的移动式从一个状态到另外一个状态的转换。
②人工蚂蚁具有记忆起本身过去行为的内在状态。
③人工蚂蚁存在于一个与时间无关联的环境之中。
④人工不是完全盲目的，它还受到问题空间特征的启发。
例如有的问题中人工蚂蚁在产生一个解后改变信息量，而有的问题中人工蚂蚁每作出一步选择就更改信息量，但无论哪种方法，信息量的更新并不是随机都可以进行的。
⑤为了改善算法的优化效率，人工蚂蚁可增加一些性能，如预测未来、局部优化、回退等，这些行为在真实蚂蚁行为中是不存在的。
在很多具体的应用中，人工蚂蚁可在局部优化过程中相互交换信息，还有一些蚁群算法中的人工蚂蚁可实现简单的预测。
5.3.1.4 蚁群算法的基本特点蚁群优化算法是从自然界中蚂蚁的觅食行为受到启发而提出的一种模拟进化算法。
ACO算法可以看成是一种基于解空间参数化概率分布模型的搜索算法框架，其中解空间参数化概率模型的参数就是信息素，因而这种模型就是信息素模型.在基于模型的搜索算法框架中，可行解通过在一个解空间参数化概率分布模型上的搜索产生，此模型的参数用以前产生的解来进行更新，使得在新模型上的搜索能集中在高质量的解搜索空间内.这种方法的有效性建立在高质量的解总是包含好的解构成元素的假设前提下.通过学习这些解构成元素对解的质量的影响有助于找到一种机制，并通过解构成元素的最佳组合来构造出高质量的解。
