老鼠走迷宫采取?法

老鼠走迷宫采取?法

1

探测策略

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

电脑鼠在一巷道内行走，如果最后无路可走，则该巷为死巷。电脑鼠在任一单元内，可
能的行走方向最多只有三个（前、左、右）
，如果有二个或二个以上的可能行走方向，称为
交叉，遇有交叉时，由于有多个可以行走的方向，在行走方向的选择上，可有下面的几种选
择法则：



右手法则：遇有交叉时，以右边为优先的前进方向，然后是直线方向、左边方向。



左手法则：遇有交叉时，以左边为优先的前进方向，然后是直线方向、右边方向。



中左法则：遇有交叉时，以直线为优先的前进方向，然后是左边方向、右边方向。
与此类似的还有中右法则。



乱数法则：遇有交叉时，取随机值作为前进方向。



向心法则：由于终点在迷宫的中心，遇有交叉时，以向迷宫中心的方向为优先的前
进方向。

2

标记

为了记忆迷宫的详细信息，需要对迷宫单元的位置进行线路标记。全迷宫共有
1
6
×
16
个单元组成，
可采用二维坐标方式标记，
即用每个单元的
XY
坐标表示，
如起点可标记为
（
0
，
0
）
，终点为（
7
，
7
）
。此外，还需要对迷宫单元的可行进方向进行标记，可采用绝对方位或
相对方位二种方式。

绝对方位：
这是一种与电脑鼠行进方向无关的标记方式，
以一个四位的二进制数，
分别
表示“东”﹑“西”﹑“南”和“北”四个方向。以
1
表示允许行进（无墙壁）
，
0
表示不
允许行进（有墙壁）
。

相对方位：
这是一种与电脑鼠行进方向有关的标记方式，
以一个三位的二进制数即可实
现标记，分别表示“前”
“左”
“右”
，

以
1
表示允许（无墙壁）
，
0
表示不允许（有墙壁）
。

3

阻断

在电脑鼠试跑过程中或在最后冲刺时，需要对部分路径进行“
阻断”
，即在发现某条路
径是死路（只有入口而无出口）时，在该路径的入口处（一般是交叉点）设置标记，即将入
口的线路标记由
1
改为
0
。

4

试跑

试跑是获得迷宫地图（各单元路线标记）的唯一方法，因而应在规则允许的情况下，尽
可能多的获得迷宫信息，
为最后的冲刺准备尽可能多的信息。
在试跑过程中，
要对经过的单
元进行线路标记，同时还要选择一个合适的探测策略。