騎士巡邏

騎士巡邏（英語：）是指在按照国际象棋中骑士的规定走法走遍整个棋盘的每一个方格，而且每个网格只能夠经过一次。假若騎士能夠從走回到最初位置，則稱此巡邏為「封閉巡邏」，否則，稱為「開巡邏」。對於8*8棋盤，一共有26,534,728,821,064種封閉巡邏，但是到底有多少種開巡邏仍然未知。[1][2][3]

一种开巡逻走法
5×5棋盘中的一种开巡逻走法

由骑士巡逻引申出了一个著名的数学问题 ：骑士巡逻问题--找出所有的骑士巡逻路径。编写一个程序来找出骑士巡逻路径经常在计算机系的学生的练习中出现。骑士巡逻问题的变种包括各种尺寸的棋盘甚至非正方形的棋盘。

历史
土耳其行棋傀儡执行的骑士巡逻。由于其路线是一条闭路，因此从棋盘上任何一点开始都能完成巡逻。[4]

已知的最早的骑士巡逻问题可以追溯到九世紀的古印度恰圖蘭卡。[5]

欧拉是最早研究骑士巡逻的数学家中的一员，而H. C. von Warnsdorff在1823年提出了第一个系统化解决骑士巡逻问题的方法--Warnsdorff规则。

在20世纪，一批乌力波的作家将这个问题用在了其它的地方。最明显的例子：乔治·佩雷克的小说Life: A User's Manual的章节顺序就是按照10×10棋盘的骑士巡逻路径来编排的。在2010年国际象棋世界冠军对抗赛的第六场比赛中，棋手阿南德连续13次移动骑士（使用了两个骑士），在线评论员打趣地说阿南德试图在游戏过程中解决骑士巡逻问题。

实质
骑士巡逻图展现了所有可能的骑士巡逻路径，节点上的数字表示在这个节点上骑士可能路径的个数

骑士巡逻问题实际上是哈密顿路径问题的一种特殊形式，寻找骑士巡逻的闭巡逻路径的个数实际上也是哈密顿循环问题的一种特殊形式。但是和一般的哈密顿路径问题不同，骑士巡逻问题可以在线性时间内解决。[6]

路径的个数
  • 在一个8×8的棋盘中，有26,534,728,821,064中有向封闭巡逻路径（相互对称的巡逻路径被视为不同的巡逻路径）。[7][8]
  • 在6×6的棋盘中，共有9862个闭巡逻。[9]
  • 8×8棋盘中开巡逻的个数仍然未知。对于（n=1，2……）的棋盘中开巡逻的个数是：
1, 0, 0, 0, 1728, 6637920, 165575218320,……（ A165134）
  • Schwenk证明了，除了以下3種情況外，任何的m×n（mn）棋盘都至少有1个闭巡逻，。[10]
  1. m和n都为奇数
  2. m= 1, 2, 4
  3. m= 3且n= 4, 6, 8
  • Cull和Conrad证明了对于任何一个m×n（5mn）棋盘，至少有一个（可能是开巡逻）骑士巡逻路径。[11][6]

解决方法
利用人工神经网络的方法在24 × 24的棋盘中寻找到的一条闭巡逻。

借助计算机的帮助，人们已经发现了很多种寻找骑士巡逻路径的方法。其中一部分依靠算法，而另外一些则依靠启发法。

穷举法

用穷举法来寻找骑士巡逻路径适用于格数较小的棋盘，因为当方格数过多时，可能的路径过多。例如，8×8棋盘中大约有4×10^51种可能的路径。[12]如此大的运算量已经超出了现代计算机的运算能力。

分治法

利用分治法将棋盘分成很多小块，计算出每一小块中的所有可能路径，然后将这些小块合并再计算所有可能的路径。

人工神经网络方法

骑士巡逻问题同样可以使用人工神经网络来解决。[13]

Warnsdorff规则

Warnsdorff规则指在所有可走且未经过的方格中，马只可能走这样一个方格：从该方格出发,马能跳的方格数最少；如果可跳的方格数相等，则从当前位置看,方格序号小的优先。依照这一规则往往可以找到一条路径但是并不一定能够成功。

參考資料
  1. Martin Loebbing; Ingo Wegener. . The Electronic Journal of Combinatorics. 1996, 3 (1): R5. Remark: The authors later admitted that the announced number is incorrect. According to McKay's report, the correct number is 13,267,364,410,532 and this number is repeated in Wegener's 2000 book.
  2. Brendan McKay. . Technical Report TR-CS-97-03 (Department of Computer Science, Australian National University). 1997. （原始内容存档于2012-01-27）.
  3. Wegener, I. . Society for Industrial & Applied Mathematics. 2000. ISBN 0-89871-458-3.
  4. Standage, 30–31.
  5. Satyadev, Chaudhary. . Delhitraversal: Parimal Sanskrit Series No. 30.
  6. Conrad, A.; Hindrichs, T.; Morsy, H. & Wegener, I. . Discrete Applied Mathematics. 1994, 50 (2): 125–134. doi:10.1016/0166-218X(92)00170-Q.
  7. Brendan McKay. . Technical Report TR-CS-97-03 (Department of Computer Science, Australian National University). 1997 [2014-03-24]. （原始内容存档于2013-09-28）.
  8. Wegener, I. . Society for Industrial & Applied Mathematics. 2000. ISBN 0-89871-458-3.
  9. 埃里克·韦斯坦因. . MathWorld.
  10. Allen J. Schwenk. . Mathematics Magazine. 1991: 325–332.
  11. Cull, P.; De Curtins, J. (PDF). Fibonacci Quarterly. 1978, 16: 276–285.
  12. .
  13. Y. Takefuji, K. C. Lee. "Neural network computing for knight's tour problems." Neurocomputing, 4(5):249–254, 1992.

外部連結
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.