一种电脑鼠走迷宫的算法电脑鼠走迷宫的算法1探测策略电脑鼠走迷宫可以采用全迷宫探索策略，即将迷宫的所有单元均搜索一次，从中找出最佳的行走路径。

这种策略需要有足够的时间或探测次数，但在IEEE竞赛规则中每场竞赛只有15分钟的时间，因此是不可能的。

另一种方法是部分迷宫探索策略，即在有限的时间或探测次数下，只探测迷宫的一部分，从中找出次最佳的路径，显然只能采用这种策略。

电脑鼠在一巷道内行走，如果最后无路可走，则该巷为死巷。

电脑鼠在任一单元内，可能的行走方向最多只有三个（前、左、右），如果有二个或二个以上的可能行走方向，称为交叉，遇有交叉时，由于有多个可以行走的方向，在行走方向的选择上，可有下面的几种选择法则：•右手法则：遇有交叉时，以右边为优先的前进方向，然后是直线方向、左边方向。

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

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

与此类似的还有中右法则。

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

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

2标记为了记忆迷宫的详细信息，需要对迷宫单元的位置进行线路标记。

全迷宫共有16×16个单元组成，可采用二维坐标方式标记，即用每个单元的XY坐标表示，如起点可标记为（0，0），终点为（7，7）。

此外，还需要对迷宫单元的可行进方向进行标记，可采用绝对方位或相对方位二种方式。

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

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

相对方位：这是一种与电脑鼠行进方向有关的标记方式，以一个三位的二进制数即可实现标记，分别表示“前”“左”“右”，以1表示允许（无墙壁），0表示不允许（有墙壁）。

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

4试跑试跑是获得迷宫地图（各单元路线标记）的唯一方法，因而应在规则允许的情况下，尽可能多的获得迷宫信息，为最后的冲刺准备尽可能多的信息。

在试跑过程中，要对经过的单元进行线路标记，同时还要选择一个合适的探测策略。

下面以1/4迷宫为例进行说明。

假设迷宫图布局如图三所示，共有8×8=64个单元，起点在左下角（Start），终点在右上角（End）。

选用一个8×8的矩阵map保存迷宫地图信息，矩阵的每个元素为1个字节，高4位表示探测到的可行进路径，以绝对方位标记，次序为“北”﹑“东”﹑“西”﹑“南”。

低4位记录自起点的交叉点的个数。

探测策略采用右手法则，在初始状态，矩阵map各元素的值均为FFH，00H表示死巷。

图三1/4迷宫在探测过程中，如果下一个可行进的单元已经探测过（对应的矩阵元素值非00H或非FFH），只有在发现死巷时，才对map中的数据进行修改。

对于其它情况，无论探测结果与矩阵中对应元素存储的信息是否一致，均不修改存储的信息。

对于复杂的迷宫，往往不能仅使用一种探测策略，而要综合考虑，如增加向心法则。

当发现交叉点时，应将该单元坐标和线路特征保存（如入栈），再分析可行的下一个单元是否已经探测过，如果均未探测过，则根据探测策略，选择一方向进行探测。

如果部分单元已经探测，则选择未被探测的单元进行探测。

遇有死巷，应返回最近的交叉点，同时将死巷阻断，修改入口单元的相应数值。

图四为首次探测时电脑鼠的行走路线示意，电脑鼠在探测过程中，将获得行走过的各单元的线路特征，表一为电脑鼠探测到（5，0）单元时的二维表（以十六进制表示，高4位为线路标记，低4位为交叉点数）。

图四首次探测行走路线7 FFH FFH FFH FFH FFH FFH FFH end6 FFH FFH FFH FFH FFH FFH FFH FFH5 30H 50H FFH FFH FFH FFH FFH FFH4 90H 90H FFH FFH FFH FFH FFH FFH3 90H D1H FFH FFH FFH FFH FFH FFH2 90H 90H FFH FFH FFH FFH FFH FFH1 90H B2H FFH FFH FFH FFH FFH FFH0 80H C0H 60H 60H 60H 60H FFH FFH0 1 2 3 4 5 6 7表一探测到（5，0）时的map二维表从图四可以看出，该巷为一死巷，当电脑鼠探测到（7，0）时，发现是死巷，将按原路返回到最近的交叉点（1，1），进行阻断，即将向“南”修改为不可行，并修改交叉点的数据，由原值B2H改为90H，死巷中的数据全写零，并继续完成探测，最后得表二。

7 FFH FFH FFH FFH FFH FFH FFH end6 FFH FFH FFH FFH FFH FFH FFH B0H5 30H 50H FFH FFH FFH FFH FFH B0H4 90H 90H FFH FFH FFH FFH FFH 90H3 90H D1H FFH FFH FFH FFH FFH 90H2 90H 90H FFH FFH FFH FFH FFH A2H1 90H C0H 60H 60H 60H 60H 60H 90H0 80H 00H 00H 00H 00H 00H 00H 00H0 1 2 3 4 5 6 7表二执行阻断后的二维表根据IEEE电脑鼠竞赛规定，当电脑鼠到达终点后，可进行返回探测，从而获得更多的迷宫地图信息。

图五为返回探测时的行走路径。

在返回探测中，未发现死巷，返回起点，探测后的结果如表三。

图五返回时的探测路径7 50H 60H 60H 60H 60H 60H 30H end6 C0H 60H 70H FFH FFH FFH C0H B4H5 30H 50H D2H FFH FFH FFH FFH B3H4 90H 90H C0H 60H 30H FFH FFH 90H3 90H D1H 60H 71H A0H FFH FFH 90H2 90H 90H FFH FFH FFH FFH FFH A2H1 90H C0H 60H 60H 60H 60H 60H 90H0 80H 00H 00H 00H 00H 00H 00H 00H0 1 2 3 4 5 6 7表三返回探测后的二维表图六第二次探测路径第二次探测如图六，在（3，3）和（2，5）分别执行阻断，将获得二维表四7 50H 60H 60H 60H 60H 60H 30H end6 C0H 60H 70H 72H 60H 30H C0H B4H5 30H 50H 90H 00H 00H D3H HHH B3H4 90H 90H C0H 60H 30H 90H HHH 90H3 90H D1H 60H 30H A0H 90H HHH 90H2 90H 90H HHH 00H 00H C0H 60H A2H1 90H C0H 60H 60H 60H 60H 60H 90H0 80H 00H 00H 00H 00H 00H 00H 00H0 1 2 3 4 5 6 7表四第二次探测后的二维表5数据补全由于不可能将所有的单元均探测到，在有了一定的数据基础上，就可以实现数据补全了。

数据补全，就是对未探测到的单元，通过周围已有的相数据，可进行补充的一种方法。

方法是寻找单元数据为FFH的单元，如果该单元的“东”﹑“西”﹑“南”﹑“北”四个相邻的单元均为非00H或FFH，分析“东”﹑“西”和“南”﹑“北”四个单元的二组数据，看是否有指向该单元的可行方向，如果有，在该方向是相通的，可对数据进行大胆的假设。

对照表四，（6，5）是未探测过的，其值为FFH，分析与之相邻的（5，5）（7，5）和（6，6）（6，4）二组数据，（6，4）的数据为FFH，放弃在南北方向上的补全，考虑东西方向，（5，5）向东是可行的，（7，5）向西是可行的，因而可以大胆设想，（6，5）是东西可行的，数据可设为60H，将60H填入表四，就得到补全后的表五。

7 50H 60H 60H 60H 60H 60H 30H end6 C0H 60H 70H 72H 60H 30H C0H B4H5 30H 50H 90H 00H 00H D3H 60H B3H4 90H 90H C0H 60H 30H 90H HHH 90H3 90H D1H 60H 30H A0H 90H HHH 90H2 90H 90H HHH 00H 00H C0H 60H A2H1 90H C0H 60H 60H 60H 60H 60H 90H0 80H 00H 00H 00H 00H 00H 00H 00H0 1 2 3 4 5 6 7表五补全后的二维表6等高表经过有限次的探测、阻断与补全后，已经可以得到描述迷宫图线路的二维表，虽然不是全部，但已经是部分或大部分，其中可能包含了若干条可以到达终点的路径，为了寻找到达终点的路径，需要制作等高表。

等高表是指已探测的各单元距离起点的步数（一个单元为一步），起点的步数为0，表六为通过表五所获得的等高表。

等高值以十进制数表示。

19 20 21 22 23 24 25 2818 17 16 17 18 19 26 275 6 15 20 21 224 7 14 13 12 21 193 8 9 10 11 22 182 9 23 24 171 10 11 12 13 14 15 16表六等高表7可行路径在等高表中，可行路径上任一单元到起点的步数都是已知的，按从大到小的次序，可以返回起点。

按从小到大的次序，可到达终点，这样的可行路径可能不止一个，而是多个。

可行路径的查找，从起点开始，在允许前进的方向上，按比当前等高值高1的方向前进，直到终点。

有时可能会遇到下一单元的等高值小于当前值（如（6，2）点）或比当前值高1以上的情况，如果当前单元不是交叉点，可以不予理会，进入下一个单元，按等高值增加的方向查找。

如果是交叉点，则要进行趋势分析，找出等高值就增加的方向。

舍弃等高值减少的方向。

图七是根据表六得到的所有可行路径，共有A、B、C、D四条。

图七所有的可行路径8可行路径的步数可行路径的步数，指由起点到达终点，所经过的单元数，可由等高表计算得出。

线路A：由（0，0）到（7，4），19步，（7，4）到（7，5）1步，（7，5）到（7，6）1步，（7，6）到（7，7），28-27=1步。

总计=19+1+1+1=22步。

线路B：由（0，0）到（6，2），24步，（6，2）到（7，2）1步，（7，2）到（7，4）,19-17=2步，（7，4）到（7，5），1步, （7，5）到（7，6），1步。