电脑鼠算法优化分析

李彤

（天津渤海职业技术学院，天津 300000）

电脑鼠算法优化分析

李彤

（天津渤海职业技术学院，天津 300000）

电脑鼠是由微处理器控制的集感知、判断、行走功能于一体的小型机器人，其可以在“迷宫”中自动感知并记忆迷宫地图，以最快的速度到达目的地。基于此，针对电脑鼠算法进行优化分析。

电脑鼠算法；微处理器控制；路径选择法则；自动搜索

1 电脑鼠算法概述

电脑鼠走迷宫可采用全迷宫探索策略，即将迷宫所有单元均搜索一次，从中找出最佳行走路径。这种策略需要有足够的时间或探测次数，但在IEEE竞赛规则中每场竞赛只有15min，因此是不可能的。另一种方法是部分迷宫探索策略，即在有限的时间或探测次数下，只探测迷宫的一部分，从中找出次最佳的路径，显然只能采用这种策略。

2 迷宫信息的存储

因为迷宫分为16×16=256个方格，所以很直观地可以想到用一个二维矩阵来存储一个迷宫的信息，矩阵中的每一个元素用于存储地图中一个方格的信息，矩阵每个元素可以定义成Byte型，只用其中的4位就可以存储方格四面的挡板信息。要获取某一个方格单个方向的挡板信息，只需做一个简单的运算看结果是否为0即可。

2.1 数据的存储方式

绝对方向和相对方向的变换：假设数值0、1、2、3分别表示绝对方向的上、右、下、左，那么就用0、1、2、3中的其中一个数值来表示当前小车车头朝向的方向，当然这个数值是动态变化的，其实转化的规则相当简单，右转方向数值加1，左转方向数值加3，后转方向数值加2，当然可能有越界的情况。所以，得出的方向数值再进行模运算对4取余数得出的结果，就是转弯后小车的车头所面向的方向的数值。通过矩阵可以找到当前的小车方向和转弯后的小车方向的对应关系，得出的相对方向和绝对方向的转换公式如下所示［1］：

转弯后的绝对方向=（转弯前的绝对方向+转弯数值）%4

小车的车头方向一般是用一个全局变量来存储的，方便在转弯的函数中进行修改，避免C语言中一些作用域的问题。

2.2 寻路算法

寻路是小车在运行的整个过程中进行的第一个操作，目的是让小车在迷宫中探索，同时记录已经走过的路径信息，直到小车找到终点就可以结束探索寻路的过程。当然也可以在找到终点后继续探索整个迷宫，尽可能多地收集迷宫的信息，以便后期进行最短路径分析计算时能够运用更多的信息，找到更佳的最短路径，得到更好的成绩。

寻路算法的2个关键点如下。一是在岔路口的转弯策略以及小车运行的稳定性。转弯策略决定了从小车开始运行到找到终点的时间长短。良好的转弯寻路策略可以大量减少不必要的寻路时间。小车运行的稳定性对于寻路过程也十分重要，所以小车的行进和转弯的过程一定要在机械和软件方面都调节到最稳定的状态。二是正确使用堆栈，整个选路算法的运行过程中会大量地使用堆栈的入栈和出栈操作，如果对入栈和出栈的条件判断不正确，有可能造成数据紊乱，最好使用调试版上的数码管实时显示堆栈栈顶的数据，发现有错误就在程序中寻找错误，直到整个寻路算法稳定为止。

2.3 转弯算法

在寻路过程中，如果小车遇到迷宫中的岔路口时，应该考虑选择哪个方向继续探索。常规的策略有右手法则、左手法则、优先向前法则、向心法则等。

2.3.1 右手法则。小车在搜过程中有2个以上的搜索方向时，优先选择向右转，其次是向前行进，最后才考虑向左转弯。

2.3.2 左手法则。小车在搜过程中有2个以上的搜索方向时，优先选择向左转，其次是向前，最后向右。

2.3.3 优先向前法则。优先向前行进不转弯，然后考虑向左或向右可自行设定。

2.3.4 随即策略。在可前进的方向中随机选择一个前进，没有什么规律可循。

上述的策略都有一个共同的缺陷，就是在选择转弯方向时，没有考虑小车当前在迷宫的哪个位置，一味地调用一种寻路策略都是不科学的。

2.3.5 向心法则。把整个16×16的迷宫地图分解为左下、右下、左上、右上4个均等的区域，在不同的区域中选择不同的转弯策略，使得小车始终向着迷宫的中心靠近，这样就可以以最快的速度接近终点。

2.4 优化算法

在电脑鼠的寻路过程中有一个比较特殊的过程，就是在小车遇到死胡同时，应让小车回到上一个岔路口，换言之，需要实现将小车从当前的位置移动到一个指定的任意位置，而且还要使得移动过程经历的路径尽可能短。后期最短路径的生成问题其实是上述问题的一个特例，仅把当前位置设为了迷宫起点，把要达到的位置设为中点。

综上所述，只需要集中精力解决上述第一个问题即可，即怎样从当前的位置寻找一条最短的路径到达一个指定的任意位置。要实现上面的功能，就需要用到等高表。等高表是以一个二维矩阵的形式表现的，对于16×16的迷宫地图而言，可以开辟一个16×16的二维矩阵来表示等高表，数值类型选择Byte型就够用了，等高表中的每一项对应迷宫每一个方格，用于存储起点到该方格最短路径。

3 软件中可改进的部分优化建议

3.1 直接到指定的坐标

控制小车直接从当前的坐标到一个指定的坐标是整个软件设计中要实现的最为关键的功能，在寻路的过程中涉及到频繁地回到以前所经历的岔路口的过程，这就是一个从当前坐标移动到指定坐标的典型情况，还有从起点到终点的冲刺过程其实是一句代码完成的，就是将迷宫的起点作为小车的运行起点，将迷宫的终点作为小车运行的终点来调用这个关键的功能。该功能的实现要用到迷宫的等高表信息。

3.2 消除不必要的停顿

在出厂代码试跑中，小车每到一个岔路口就会停顿一下，然后再重新加速前进。根据上次比赛对代码的分析，出现这种现象的原因在于出厂示例代码的架构安排不合理，出场的示例代码中小车的前进和在岔路口是否转弯的判断是分离的，所以小车每到一个岔路口，程序就会从控制前进的函数跳回到主函数中进行是否需要转弯的判断，然后转弯后又跳回到控制前进的函数中运行程序。这样就造成了不必要的停顿。其实在岔路口是否转弯应在控制前进的函数结束前判断，不需要跳回主函数进行正以上缺陷的方法是增加控制前进的子过程的返回条件，在不需要转弯的岔路口不跳出前进的子路程即可。

3.3 去除“傻瓜式”寻路过程

在出厂实例代码的试跑过程中，发现其寻路过程效率非常低，经常在一些三面都有挡板的单个方格间打转，其原因是因为没有进行数据补全，迷宫里方格的信息，通过推断方法也可以得到，利用某个方格四周方格的信息，就有可能推断出这个方格的信息。

3.4 防止小车在终点浪费时间

普通的代码中并没有在小车到达终点之后进行特殊的处理，造成小车在终点的4个方格中转一圈才返回终点，这显然是应该改进的，需要对终点的判定增加特殊的处理。

3.5 限制探索迷宫的深度

在小车找到终点后，可以继续探索迷宫，但是比赛的迷宫有256个方格，全部探索完是相当耗时间的，所以需要控制遍历迷宫的深度，可以通过已经探测的方格个数来衡量迷宫的探测程度，给探测的迷宫方格数设置一个上限，在到达探索的上限后返回迷宫起点，结束寻路的过程。

3.6 改进转弯的模式

传统的左拐弯和右拐弯都是先让电机停转，然后一个电机正转，另外一个电机反转实现转弯，电机的停转会浪费很多时间，所以相对而言，没有电机停转过程的前进中拐弯方式是比较理想的转弯方式。

4 结语

电脑鼠是一个系统工作，在比赛中对光和静电影响很大，在遇到静电问题可刷三合油减小对电脑鼠比赛误差。

［1］周慈航，吴光文.基于嵌入式实时操作系统的程序设计技术［M］.北京：北京航空航天大学出版社，2006.

Optimization Analysis of Computer Mouse Algorithm

Li Tong

（Tianjin Bohai Vocational and Technical College，Tianjin 300000）

The computer mouse is controlled by a microprocessor,and integrates the sensing,judging and walking functions into a small robot.It can automatically sense and memory maze map in the maze,reach the destination at the fastest speed.Based on this,the optimization of computer mouse algorithm was analyzed.

computer mouse algorithm；microprocessor control；path selection rule；automatic search

TP242

A

1003-5168（2017）02-0024-02

2017-01-12

李彤（1988-），男，硕士，助教，研究方向：电脑鼠算法优化。