国际象棋棋盘中，马/骑士（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×n（m≤n且m≥5）棋盘，至少有一个（可能是开路径）的马周游路径。
上面我简单用图表示的现象，十分没有说服力，因为我也没办法确定这样一定正确。事实上，这个想法和Warnsdorff规则不谋而合。
Warnsdorff在1823年提出了一个启发性的贪心算法，我们称为Warnsdorff规则，指在所有可走且未经过的方格中，马只可能走这样一个方格：从该方格出发,马能跳的方格数最少；如果可跳的方格数相等，则从当前位置看，方格序号小的优先。依照这一规则往往可以找到一条路径但是并不一定能够成功。换言之，在进行深搜时优先拓展拥有最少下一步可能移动位置的子节点。
此外，Warnsdorff 算法还有两个改进版本 W+和 W2，但在8 × 8这样小规模的棋盘上
优化效果并不明显。这个问题可以通过分治法和神经网络来解决。
Further Read：Knight's tour - Wikipedia 下面的参考文献
没有评论 :
发表评论