在高铁上玩了会图灵完备，玩到编程的最后一关，要求我编程使小机器人可以自己走迷宫。机器人只能看见前面一格，摆明了是贪心法，记忆化搜索之类的都没有办法使用。我没设计出好算法，于是看了提示，大概内容如下: 提示：一直朝左手边（或者右手边）走，都可以走出迷宫 伪代码： 向前走一步 左转 判断面前是不是墙壁，如果是就不断右转直到面前不是墙壁 与面前方块交互 回到第一行代码 这个算法为什么会凑效？我感到不是那么自然，于是尝试给一个让自己信服的解释 如果所在位置不是岔路或者死路（deg(V)=2），这个算法显然是一直走下去的，这个容易判断。所以以下理解预设的情景是遇到死胡同/岔路口
第一个问题:回头路 刚来岔路口,这时尝试左转,若左手边可通行就选择左侧,左侧不可通行则选择前侧,若前侧不可通行则选择右侧,若右侧仍然不可通行,最后才选择后方. 于是我们得到这个算法的一致优先级:左手边>正前方>右手边>后方 因此,对于deg(V)=1的死胡同,我们总能往回走.在deg(V)=1的点处算法是proper的.
于是deg(V)=1,deg(V)=2的点都是proper的.我们要处理deg(V)>2的点,即岔路口.
第二个问题:岔路口 从岔路口选一个方向走下去,撞到死胡同了,这时候回到该岔路口的位置,方向与来的时候正好相反.以机器人第一次到岔路口时的朝向为正向. 迷宫问题的岔路必然至少有两条是连通的,因此通向死胡同的岔路不会超过两条.
- 若机器人第一次是在岔路口左转的,那么它回来的时候,左手边就是正向,前方就是右向,右手边就是后向,右手边必定连通.这时可保证优先级是不变量:正>右>后(左已经是死路)
- 若机器人第一次是在岔路口直行,那么它回来的时候,它的左手边是右向,前方是后向(必定连通),优先级仍是不变量:右>后(此时正,左都走过了,则只有右可能为通路). 到了这一步,deg(V)=4且左侧,前侧至少一侧可通行但不连通的岔路,是可行的.但还有一种情况,就是左前右三个方向都可通行,但是最后都因不连通而回来了.这时能否正确往后走呢?
- 机器人从右侧回来,这时机器人左转就是后向,原路返回.优先级仍然是不变量. 综上,所有deg(V)=4的分支点都是proper的.deg(V)=3的分支点其实就是deg(V)=4的某个方向直接被挡住了,因此自然也都是proper的. 于是,我们证明对deg(V)=1,2,3,4的点,这个算法都能保证优先级不变量正确,从而实现一种深度优先搜索.
总结 这个算法的巧妙之处在于,通过先朝一个方向转,然后不断朝相反方向转找通路的操作,保证了对于任何一个岔路口,不管是来还是回,方向优先级都是一个不变量.维护这个不变量,就事实上仅利用前面所能看见的一格,制造了先左后中后右的前序递归深度优先搜索.