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

Question

我正在学习骑士的巡回算法。我使用递归精细实现，但它需要很长时间，而且几乎不是封闭的旅行。

现在，我目前正在寻找一种快速算法来查找封闭式游览。有人可以推荐我一些算法吗？

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

Answer 1

骑士之旅问题实际上是在对应的图中找到一个哈密顿循环，已知它是 NP 难的，所以这个问题也可能很难解决。

但是，有几种启发式方法可以让您执行快速查找。Warnsdorff 规则就是这样的启发式方法之一：

在每一步移动到方格，从该方格可以进行的动作较少。如果有几个这样的方格，移动到其中任何一个。

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

Answer 2

我今天解决了这个问题，在 Knight Graph 中实现了深度优先搜索（该图对 Knight 的可能动作进行建模）。

当我整个下午都在想为什么 Warnsdorff 的启发式方法还不够时，问题是我的出发点。

我从 (0,0) 位置开始 DFS。如果你从中间的某个地方开始，比如 (3,3)，看起来 DFS 得到了极大的改进。更改后，算法速度从（1 小时内无解）变为（1 秒内有1 个解）。

我也测试了你的 Min[F(x,y)] 启发式方法，它的性能似乎与 Warnsdorff 的规则相同（对于 8x8 表）。