algorithm - 寻找封闭骑士之旅的快速算法

Question

我正在学习骑士的游览算法。我用递归的方式实现的很好，但是耗时很长，几乎不是闭路漫游。

现在，我正在寻找一种快速算法来查找封闭式游览。谁能给我推荐一些算法？

更新:我在某处读到过一个启发式方法，可以找到像这样的封闭式骑士之旅:Min[F(x, y)] 其中 F(x ,y) 是一组 f(x,y)=Min(x-1, n-x) + Min(y-1, n-y) 而 (x, y) 是下一步的位置，n 是棋盘的大小。但是我该如何使用该启发式呢？

Answer 1

knight's tour problem实际上是在对应的图中寻找一个哈密尔顿圈，这个已知是NP-hard的，所以这个问题也可能很难解决。

但是，有几种试探法可以让您执行快速查找。 Warnsdorff 规则就是其中一种启发式方法:

在移动到正方形的每一步上，从那里可以进行较少可能的移动。如果有多个这样的方 block ，移动到其中任何一个。

这是一个很好的启发式算法，长期以来一直被认为是骑士路径问题的解决方案，并且在计算机使用中发现了规则的第二部分可能导致错误决策的示例。