论文《基于现实迷宫地形的电脑鼠设计》深度分析（四）—

论文概述

《基于现实迷宫地形的电脑鼠设计》是由吴润强、庹忠曜、刘文杰、项璟晨、孙科学等人于2023年发表的一篇优秀期刊论文。其针对现阶段电脑鼠计算量庞大且不适用于现实迷宫地形的问题，特基于超声波测距与传统迷宫算法原理，设计出一款可在现实迷宫地形下自动寻找出口的电脑鼠。该电脑鼠适用于岔路数量与道路宽度不定、多死路弯道并且相对较大的迷宫地形，具有适应性强、计算量小、兼容性和可塑性强等优点，对于现实迷宫地形下的自动应用具有一定研究价值。

关键词 电脑鼠；超声波测距；迷宫算法；自动应用

该论文内容相对较多，特对其进行拆开分析，本文特围绕现实迷宫算法进行展开分析。

一、随机算法

在现实环境的下的寻路过程与目前电脑鼠所研究的迷宫遍历大致相同，但在实际生活中知晓迷宫地形的大致分布与全地形探索迷宫不太现实，故而向心算法等常用的算法不具备太多的普适性。

但是在所能前进的方向里随机选择一个方向前行的随机算法对于现实生活中的绝大多数迷宫地形任然适用。假设当电脑鼠从入口进入迷宫地形之后将入口摆上障碍物，使得电脑鼠无法从入口出来，那么从理论上而言电脑鼠终将在不断的尝试中从到达迷宫终点。

优点：普适性强，几乎适应一切迷宫地形

缺点：时间耗费较大且有可能从入口驶出

出于以上优缺点的考虑，该算法比较适用于地下溶洞、动物洞穴等未知地形的迷宫环境，在不偏重其进出迷宫的时间间隔的前提下，携带附加设备对迷宫内环境进行研究。

二、偏好算法

此算法是基于优先向前法则、左手法则和右手法则的基础上进行总结与修改：当电脑鼠前进道路中出现多方向，优先向前法，优先选择直行，然后考虑向左或向右行驶；而左（右）手法则中优先选择向左（右）转，其次是向前行驶，最后向右（左）行驶。

原三种算法仅针对于当前道路中最多只存在三个可行的方向，并且其左右路口的方向又过于理想。在现实中的路口可能呈非理想状态的树状分布，见图13,此时的原有算法便存在一定的局限性。

图13 树状分布道路

故根据现实情况改善优先向前法则为直行偏好算法，改善左手法则与右手法则为两端偏好算法。

2.1 直行偏好算法

基于该算法理论，当小车前进方向无障碍物时，则不考虑其如今行驶道路两边的可行路口，一直保证直行状态；当l0并非极大值时，则分别对小车左右两边的障碍物进行超声波测距：

出于之间对于实际应用情况的假设，我们无需进行迷宫地形的遍历，同时对已经行走的路程并无记忆储存，在执行该算法时会不可避免地重复之前的路程而陷入的“T”型死锁之中，见图14。

图14 “T”型死锁图

当电脑鼠沿直线到达点A时，前方的障碍物阻碍电脑鼠的继续前进，故根据左右两边的探测距离前往距离较远的B点。到达B点后因为死路情况而进行掉头，经过A点到达C点，同理因为C点的死锁情况进行掉头，之后使得电脑鼠在B点与C点进行往复运动，造成死锁情况。

优点：算法简便，时间耗费较小；

缺点：存在“T”型死锁；

而迷宫有较大的可能存在该“T”型结构，故而直行偏好算法的适用度较低，仅可用于无“T”型结构的迷宫地形。

2.2 两端偏好算法

首先确定一个偏好方向（左或右，本文以左进行举例），根据超声波探测判断前方可前行道路的数量。

若探测到的数据均为合理值，则前方无可前行的道路，此时执行掉头功能；

若探测的数据仅存在一个极大值，则前方仅有一个可前行的道路，向该方向进行转弯功能；

若探测的数据存在多个极大值，则前方道路树状分布多个可前行的道路，此时其测量的数据编号，选择最靠近左边的道路进行转弯前行。

根据此算法可在大部分现实迷宫地形中较为快速的到达终点，但对于的特殊迷宫，其出口位于迷宫中央，则电脑鼠便有可能从入口驶出和始终找不到出口，见图15。

首先确定一个偏好方向（左或右，本文以左进行举例），根据超声波探测判断前方可前行道路的数量。

若探测到的数据均为合理值，则前方无可前行的道路，此时执行掉头功能；

若探测的数据仅存在一个极大值，则前方仅有一个可前行的道路，向该方向进行转弯功能；

若探测的数据存在多个极大值，则前方道路树状分布多个可前行的道路，此时其测量的数据编号，选择最靠近左边的道路进行转弯前行。

图15 特殊迷宫地图

电脑鼠从入口A处进入，根据偏好方向向左前行到B点，再根据仅存的前进方向前进到C点，同理电脑鼠向DE方向前进，路过出口D点时由于出口方向相对在右，不符合偏好方向而继续前往E点。

之后电脑鼠经过F点再次到达入口A点，根据偏好向左的算法其会从A点驶出。若假设当电脑鼠进入迷宫后将入口堵住，则电脑鼠会在BCEF四点进行反复循环，而不会从D点离开迷宫。

优点：适用性于大部分迷宫地形，逻辑清晰且时间耗费较少；

缺点：对于出口位于迷宫中间的特殊迷宫地形不太适用；

该算法适用于现实生活中出口不位于迷宫中间的迷宫地形，可用于现实中树状分布乃至与网状分布的迷宫地形进行出口寻找。

三、沿壁算法

该算法是在两端偏好的算法上进行的进一步修改，同两端偏好算法确定偏好方向，根据超声波探测与中线对齐原理，始终与左侧的障碍物保持一定的距离。此时我们可以将电脑鼠视为沿着左侧的障碍物进行行驶，根据左手法则可同两端偏好算法般从出口驶出。

沿壁算法与两端偏好算法相比有优缺点如下，

优点：只需考虑沿壁一侧的距离把控，减少了舵机旋转测距与多路口判断等工作量；

缺点：无法保证车辆居中行驶，车辆可能会因距离的把控不当而与另一侧的障碍物相互碰撞。

在迷宫地形各分叉道路宽度相差不大时，可使用沿壁算法缩短车辆的行驶时间；而当迷宫中存在个别较为狭窄的道路时，可选择两端偏好算法，保证车辆的安全行驶。

四、开源代码讲解

智能车的迷宫算法通常涉及路径规划和导航。我们可以使用一些经典的算法来解决迷宫问题，比如深度优先搜索（DFS）、广度优先搜索（BFS）和A*算法。下面我将以深度优先搜索（DFS）为例，给出一个简单的迷宫求解代码示例，并进行讲解。

def is_safe(maze, x, y):# 检查当前位置是否在迷宫内并且是可通行的return 0 <= x < len(maze) and 0 <= y < len(maze[0]) and maze[x][y] == 1def solve_maze(maze):# 定义迷宫的起点和终点start = (0, 0)end = (len(maze) - 1, len(maze[0]) - 1)# 创建一个路径列表path = []# 开始深度优先搜索if dfs(maze, start[0], start[1], end[0], end[1], path):return pathelse:return "No path found"def dfs(maze, x, y, end_x, end_y, path):# 如果到达终点，返回Trueif (x, y) == (end_x, end_y):path.append((x, y))return True# 检查当前位置是否安全if is_safe(maze, x, y):# 将当前位置加入路径path.append((x, y))# 尝试向四个方向移动# 向下if dfs(maze, x + 1, y, end_x, end_y, path):return True# 向右if dfs(maze, x, y + 1, end_x, end_y, path):return True# 向上if dfs(maze, x - 1, y, end_x, end_y, path):return True# 向左if dfs(maze, x, y - 1, end_x, end_y, path):return True# 如果四个方向都无法前进，回溯path.pop()return False# 示例迷宫（1表示可通行，0表示不可通行）
maze = [[1, 0, 1, 1],[1, 1, 0, 1],[0, 1, 1, 0],[1, 1, 1, 1]
]# 解决迷宫并打印路径
path = solve_maze(maze)
print(path)

运行这段代码后，输出的路径将是从起点到终点的坐标列表，表示智能车在迷宫中找到的路径。这种算法适合小型迷宫，对于较大的迷宫或复杂的路径规划问题，建议使用更高效的算法，如A*算法。