骑士旅游

编辑:球队网互动百科 时间:2020-04-07 02:18:05
编辑 锁定
本词条缺少名片图,补充相关内容使词条更完整,还能快速升级,赶紧来编辑吧!
骑士旅游(Knight tour)在十八世纪初倍受数学家与拼图迷的注意,它什么时候被提出已不可考,骑士的走法为西洋棋的走法,骑士可以由任一个位置出发,它要如何走完所有的位置?
骑士的走法,基本上可以使用递归来解决,但是纯綷的递归在维度大时相当没有效率,一个聪明的解法由J.C. Warnsdorff在1823年提出,简单的说,先将最难的位置走完,接下来的路就宽广了,骑士所要走的下一步,「为下一步再选择时,所能走的步数最少的一步。」,使用这个方法,在不使用递归的情况下,可以有较高的机率找出走法(找不到走法的机会也是有的)。
中文名
骑士旅游
辉煌时期
十八世纪初
类    别
西洋棋的走法
适    用
国际象棋
在一个n m 格子的棋盘上,有一只国际象棋的骑士在棋盘的左下角,骑士只能根据象棋的规则进行移动,要么横向跳动一格纵向跳动两格,要么纵向跳动一格横向跳动两格。 例如, n=4,m=3 时,若骑士在格子(2;1) ,则骑士只能移入下面格子:(1;3),(3;3) 或 (4;2);对于给定正整数n,m,I,j值 (m,n<=50,I<=n,j<=m) ,你要测算出从初始位置(1;1) 到格子(i;j)最少需要多少次移动。如果不可能到达目标位置,则输出"NEVAR"。
骑士旅游的伪码:
FOR(m = 2; m <= 总步数; m++)
[
测试下一步可以走的八个方向,记录可停留的格数count。
IF(count == 0)
[
游历失败
]
ELSE IF(count == 1)
[
下一步只有一个可能
]
ELSE
[
找出下一步的出路最少的格子
如果出路值相同,则选第一个遇到的出路。
]
走最少出路的格子,记录骑士的新位置。
]
词条标签:
计算机学