标签

2014年12月28日星期日

SOJ 1153 马的周游问题

题目描述
国际象棋棋盘中,马/骑士(Knight)行日字型,和中国象棋一样。给定一个马的起点位置,我们要求出马把棋盘中所有位置周游一遍并且不会出现重复的路线
对这样一个8 * 8的棋盘编号如下:
01 02 03 04 05 06 07 08
09 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24
25 26 27 28 29 30 31 32
33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48
49 50 51 52 53 54 55 56
57 58 59 60 61 62 63 64

从维基上盗个

算法思想及解题用到的主要数据结构
本题中我们将会用到深度优先搜索+回溯的算法。对于马棋子的当前位置,我们找出它能够往下走的下一位置,从中选择一个位置走,当马无法找到新的可行位置,而问题又未解决(即棋盘未被周游)时,我们让它回溯到前一个状态,说明前一个选择的位置是一条死路。我们继续选择可行的位置,直到没有新的可行位置,我们回溯到前一状态。
在一个假设不限大小,所有位置都合法的棋盘,一个马棋子能够走八个方向,也即有八个可选的位置。对于一个马的位置状态,我们求解出所有这八个位置,然后通过合法性判断剔除出超出8x8范围的位置。同时,由于周游要求所有的位置只被寻访一次,我们建立一个布尔型数组记录已被寻访过的位置,并在每次选择前先将已被寻访的位置剔除。(一个8x8大小的布尔矩阵是64字节,我们可以用一个double类型的8字节(64位)来表示,通过位操作来改变这个记录)。但由于题目的棋盘范围为8x8,盲目地选择位置搜索仍然会带来不必要的时间耗损。

逐步求精算法描述
一条成功周游的路线,我们在找寻时假设有N个合法的next位置,我们假设所有的next位置会导向死路的概率相同,我们倾向于先搜索可行路径更少的节点,这样就能够及早地发现死路及早回溯。


如图,若在选择next节点前,我们先根据next节点的next节点个数进行升序排序,在通常情况下能够避免在找寻中在错误的路径中耗费太多时间,同时,一条可行的路径在搜索过程中,next节点的个数应该是越来越少的。
我们在position这个数据结构中添加一个变量potential记录这个位置的合法next位置的数目,在选择下一节点前,先通过排序,选择potential更小的节点进行访问。
上面的这个优化思路是可行的。为什么?
维基百科告诉我们,马的周游问题其实就是一个古老的图问题----哈密尔顿路径的一种形式.题目要求寻找的是一条“开路径”(遍历所有位置后不需要回到初始位置)。Cull和Conrad证明了对于任何一个m×nmnm5)棋盘,至少有一个(可能是开路径)的马周游路径。
上面我简单用图表示的现象,十分没有说服力,因为我也没办法确定这样一定正确。事实上,这个想法和Warnsdorff规则不谋而合。
Warnsdorff在1823年提出了一个启发性的贪心算法,我们称为Warnsdorff规则,指在所有可走且未经过的方格中,马只可能走这样一个方格:从该方格出发,马能跳的方格数最少;如果可跳的方格数相等,则从当前位置看,方格序号小的优先。依照这一规则往往可以找到一条路径但是并不一定能够成功。换言之,在进行深搜时优先拓展拥有最少下一步可能移动位置的子节点。
此外,Warnsdorff 算法还有两个改进版本 W+和 W2,但在8 × 8这样小规模的棋盘上
优化效果并不明显。这个问题可以通过分治法和神经网络来解决。

Further Read:Knight's tour - Wikipedia 下面的参考文献

没有评论 :

发表评论