老鼠走迷宫的算法分析

《老鼠走迷宫的算法分析》由会员分享，可在线阅读，更多相关《老鼠走迷宫的算法分析（6页珍藏版）》请在装配图网上搜索。

1、一种电脑鼠走迷宫的算法电脑鼠走迷宫的算法1 探测策略 电脑鼠走迷宫可以采用全迷宫探索策略，即将迷宫的所有单元均搜索一次，从中找出最 佳的行走路径。这种策略需要有足够的时间或探测次数，但在IEEE竞赛规则中每场竞赛只 有 15 分钟的时间，因此是不可能的。另一种方法是部分迷宫探索策略，即在有限的时间或 探测次数下，只探测迷宫的一部分，从中找出次最佳的路径，显然只能采用这种策略。电脑鼠在一巷道内行走，如果最后无路可走，则该巷为死巷。电脑鼠在任一单元内，可 能的行走方向最多只有三个（前、左、右），如果有二个或二个以上的可能行走方向，称为 交叉，遇有交叉时，由于有多个可以行走的方向，在行走方向的选择上

2、，可有下面的几种选 择法则： 右手法则：遇有交叉时，以右边为优先的前进方向，然后是直线方向、左边方向。 左手法则：遇有交叉时，以左边为优先的前进方向，然后是直线方向、右边方向。 中左法则：遇有交叉时，以直线为优先的前进方向，然后是左边方向、右边方向。 与此类似的还有中右法则。 乱数法则：遇有交叉时，取随机值作为前进方向。 向心法则：由于终点在迷宫的中心，遇有交叉时，以向迷宫中心的方向为优先的前 进方向。2 标记为了记忆迷宫的详细信息，需要对迷宫单元的位置进行线路标记。全迷宫共有16X16 个单元组成，可采用二维坐标方式标记，即用每个单元的 XY 坐标表示，如起点可标记为（0， 0），终点为（7

3、， 7）。此外，还需要对迷宫单元的可行进方向进行标记，可采用绝对方位或 相对方位二种方式。绝对方位：这是一种与电脑鼠行进方向无关的标记方式，以一个四位的二进制数，分别 表示“东”、“西”、“南”和“北”四个方向。以1表示允许行进（无墙壁），0表示不 允许行进（有墙壁）。相对方位：这是一种与电脑鼠行进方向有关的标记方式，以一个三位的二进制数即可实 现标记，分别表示“前”“左”“右”， 以 1 表示允许（无墙壁）， 0表示不允许（有墙壁）。3 阻断在电脑鼠试跑过程中或在最后冲刺时，需要对部分路径进行“阻断”，即在发现某条路 径是死路（只有入口而无出口）时，在该路径的入口处（一般是交叉点）设置标记，

4、即将入 口的线路标记由1 改为0。4 试跑试跑是获得迷宫地图（各单元路线标记）的唯一方法，因而应在规则允许的情况下，尽 可能多的获得迷宫信息，为最后的冲刺准备尽可能多的信息。在试跑过程中，要对经过的单 元进行线路标记，同时还要选择一个合适的探测策略。下面以1/4迷宫为例进行说明。假设迷宫图布局如图三所示，共有8X8=64个单元，起 点在左下角（Start），终点在右上角（End）。选用一个8X8的矩阵map保存迷宫地图信息， 矩阵的每个元素为1 个字节，高4位表示探测到的可行进路径，以绝对方位标记，次序为“北” 、“东”、“西”、“南”。低4位记录自起点的交叉点的个数。探测策略采用右手法则，

5、在初始状态，矩阵map各元素的值均为FFH, 00H表示死巷。图三1/4迷宫在探测过程中，如果下一个可行进的单元已经探测过（对应的矩阵元素值非00H或非 FFH）,只有在发现死巷时，才对map中的数据进行修改。对于其它情况，无论探测结果与 矩阵中对应元素存储的信息是否一致，均不修改存储的信息。对于复杂的迷宫，往往不能仅 使用一种探测策略，而要综合考虑，如增加向心法则。当发现交叉点时，应将该单元坐标和 线路特征保存（如入栈），再分析可行的下一个单元是否已经探测过，如果均未探测过，则 根据探测策略，选择一方向进行探测。如果部分单元已经探测，则选择未被探测的单元进行 探测。遇有死巷，应返回最近的交叉

6、点，同时将死巷阻断，修改入口单元的相应数值。图四为首次探测时电脑鼠的行走路线示意，电脑鼠在探测过程中，将获得行走过的各单 元的线路特征，表一为电脑鼠探测到6, 0）单元时的二维表（以十六进制表示，高4位为 线路标记，低4位为交叉点数）。图四首次探测行走路线7FFHFFHFFHFFHFFHFFHFFHend6FFHFFHFFHFFHFFHFFHFFHFFH530H50HFFHFFHFFHFFHFFHFFH490H90HFFHFFHFFHFFHFFHFFH390HD1HFFHFFHFFHFFHFFHFFH290H90HFFHFFHFFHFFHFFHFFH190HB2HFFHFFHFFHFFHFFH

7、FFH080HC0H60H60H60H60HFFHFFH01234567表一 探测到（5, 0）时的map二维表从图四可以看出，该巷为一死巷，当电脑鼠探测到7 0）时，发现是死巷，将按原路 返回到最近的交叉点（1, 1）,进行阻断，即将向“南”修改为不可行，并修改交叉点的数 据，由原值B2H改为90H,死巷中的数据全写零，并继续完成探测，最后得表二。7FFHFFHFFHFFHFFHFFHFFHend6FFHFFHFFHFFHFFHFFHFFHB0H530H50HFFHFFHFFHFFHFFHB0H490H90HFFHFFHFFHFFHFFH90H390HD1HFFHFFHFFHFFHFFH90

8、H290H90HFFHFFHFFHFFHFFHA2H190HC0H60H60H60H60H60H90H080H00H00H00H00H00H00H00H01234567表二执行阻断后的二维表根据IEEE电脑鼠竞赛规定，当电脑鼠到达终点后，可进行返回探测，从而获得更多的 迷宫地图信息。图五为返回探测时的行走路径。在返回探测中，未发现死巷，返回起点，探 测后的结果如表三。图五返回时的探测路径750H60H60H60H60H60H30Hend6C0H60H70HFFHFFHFFHC0HB4H530H50HD2HFFHFFHFFHFFHB3H490H90HC0H60H30HFFHFFH90H390HD

9、1H60H71HA0HFFHFFH90H290H90HFFHFFHFFHFFHFFHA2H190HC0H60H60H60H60H60H90H080H00H00H00H00H00H00H00H01234567表三返回探测后的二维表-7 - 6 - 5 - 4 - 3 - 2 -图六第二次探测路径第二次探测如图六，在（3, 3）和（2, 5）分别执行阻断，将获得二维表四750H60H60H60H60H60H30Hend6C0H60H70H72H60H30HC0HB4H530H50H90H00H00HD3HHHHB3H490H90HC0H60H30H90HHHH90H390HD1H60H30HA0H

10、90HHHH90H290H90HHHH00H00HC0H60HA2H190HC0H60H60H60H60H60H90H080H00H00H00H00H00H00H00H01234567表四第二次探测后的二维表5数据补全由于不可能将所有的单元均探测到，在有了一定的数据基础上，就可以实现数据补全了。 数据补全，就是对未探测到的单元，通过周围已有的相数据，可进行补充的一种方法。方法 是寻找单元数据为FFH的单元，如果该单元的“东”、“西”、“南”、“北”四个相邻 的单元均为非00H或FFH,分析“东”、“西”和“南”、“北”四个单元的二组数据， 看是否有指向该单元的可行方向，如果有，在该方向是相通的

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

12、A0H90HHHH90H290H90HHHH00H00HC0H60HA2H190HC0H60H60H60H60H60H90H080H00H00H00H00H00H00H00H01234567表五补全后的二维表6等咼表经过有限次的探测、阻断与补全后，已经可以得到描述迷宫图线路的二维表，虽然不 是全部，但已经是部分或大部分，其中可能包含了若干条可以到达终点的路径，为了寻找到 达终点的路径，需要制作等高表。等高表是指已探测的各单元距离起点的步数（一个单元为 一步），起点的步数为0表六为通过表五所获得的等高表。等高值以十进制数表示。19202122232425281817161718192627561

13、520212247141312211938910112218292324171101112131415160表六等高表7可行路径在等高表中，可行路径上任一单元到起点的步数都是已知的，按从大到小的次序，可以 返回起点。按从小到大的次序，可到达终点，这样的可行路径可能不止一个，而是多个。可 行路径的查找，从起点开始，在允许前进的方向上，按比当前等高值高 1的方向前进，直到 终点。有时可能会遇到下一单元的等高值小于当前值（如6 2）点）或比当前值高1以上 的情况，如果当前单元不是交叉点，可以不予理会，进入下一个单元，按等高值增加的方向 查找。如果是交叉点，则要进行趋势分析，找出等高值就增加的方向。舍

14、弃等高值减少的方 向。图七是根据表六得到的所有可行路径，共有A、B、C、D四条。图七所有的可行路径8可行路径的步数可行路径的步数，指由起点到达终点，所经过的单元数，可由等高表计算得出。线路 A：由（0, 0）至到（7，4），19 步，（7, 4）至到（7，5）1 步，（7, 5）至I（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）至I（7, 5）, 1 步，（7, 5）至I（7, 6）, 1

15、步。（7, 6）至0（7, 7）, 28-27=1 步, 总计=24+1+2+1+1+1=30 步。同理可得线路C： 22+1+1=24。线路D： 28。9 最佳路径 电脑鼠要在最短的时间内完成由起点到终点的冲剌，路径的选择至关重要，步数少的路 径，是最佳路径的条件之一，但不是唯一条件。考虑电脑鼠在拐弯时，同样需要时间，所以 要对拐弯次数加权后加到步数中得到加权步数。加权步数=步数+拐弯次数X拐弯权重拐弯次数：一个90 度的拐弯算一次，一个180 度的拐弯算二次。拐弯权重：这是一个对结果有重要影响的参数，要结合电脑鼠的结构和试跑确定。如果 电脑鼠无加速功能，是以恒速前进，其值可选0.41.0

16、之间，如果电脑鼠有变速功能，可根 据变速的范围，其最值可适当增加。表7 与表 8，分别列出了不同的拐弯权重，对加权步数 的影响。线路步数拐弯次数拐弯权重加权步数名次A2240.5241B30100.5354C24100.5292D28120.5343表七 拐弯权重为 0.5时，各线路的加权步数线路步数拐弯次数拐弯权重加权步数名次A2241.5281B30101.5453C24101.5392D28121.5464表八 拐弯权重为 1.5时，各线路的加权步数从表七与表八中，已经明显看出了拐弯权重对加权步数的影响，线路B与线路D的排 名次序发生了逆转。结论本文详细介绍了一种电脑鼠走迷宫的算法，实践表明该算法可以基本满足电脑鼠走迷宫 竞赛的要求。电脑鼠走迷宫已有的算法很多，新算法也层出不穷。本文仅为抛砖引玉，以供 同行参考。