一种新颖的电脑鼠走迷宫算法研究

王昕++++袁晓堂++++陈晨++++马浩++++袁臣虎

摘 要： 一款性能稳定，功能全面，算法优良的高效智能“电脑鼠”能在短时间内快速稳定地完成复杂迷宫的搜索和冲刺。本文将向心算法和洪水算法融合形成向洪算法，介绍了该算法的工作原理，并对该算法进行优化和评估后完成迷宫搜索、迷宫二次回程搜索。向洪算法在保持向心算法和洪水算法优势的基础上减轻了处理器的运算负担，使电脑鼠运行稳定性进一步提高。实验表明，与传统算法相比，加载该算法的“电脑鼠”可以探寻出更加有利的路径，获取更全面的迷宫信息，是一种高效的迷宫搜索算法。

引言

“电脑鼠”是一个具备自主运动能力的微型机器人，它能够在特定的迷宫中行进和搜索，由起点出发，自行搜索到迷宫的终点，并利用搜索过程中记录的迷宫墙壁资料寻找出由迷宫起点到达终点的最短路径，然后根据最短路径规划出最快的运动方式和路径，并以最快的速度完成由迷宫起点到终点的冲刺。

要在指定的复杂迷宫中比赛，就像是一个人置身于未知的环境中，必须靠自身的判断力、敏捷的动作和正确精准地探查周遭环境赢得最终比赛的胜利。“电脑鼠”必须具备三项基本功能：

（1）稳定及快速的行走能力；

（2）正确的预判能力；

（3）路径记忆功能；

随着人工智能的发展和新兴智能算法的突破，迷宫算法革新对迷宫求解来说相当重要，迷宫算法从非图论（NGT）发展到图论（GT）[2]，从简单的左右手法则、中左、中右法则发展到洪水填充法则、深度优先探索法则（DFS），且随着机器人多路径规划的不断深入探索，A■和D■等启发式算法也开始运用其中，甚至新兴智能算法如蚁群算法、遗传算法、粒子群算法应运而生。……