我正在学习骑士之旅算法。我使用递归精细实现,但需要很长时间,而且几乎不是封闭式游览。
现在,我正在寻找一种快速算法来查找封闭游览。有人可以推荐我一些算法吗?
更新:我在某处读到过这样的启发式寻找封闭骑士之旅:Min[F(x, y)]
其中F(x ,y) 是 f(x,y)=Min(x-1, n-x) + Min(y-1, n-y)
的集合,(x, y)
是下一步的位置,n
是棋盘的大小。但我该如何使用这种启发式方法呢?
最佳答案
骑士之旅问题实际上是在相应的图中找到一个哈密顿循环,已知该问题是NP困难的,因此这个问题也可能很难解决。
但是,有几种启发式方法可以让您执行快速查找。 Warnsdorff 规则就是此类启发法之一:
每一步都移动到正方形,从那里可以进行较少可能的移动。如果有多个这样的方格,则移动到其中任何一个。
这是一个非常好的启发式方法,长期以来一直被认为是骑士路径问题的解决方案,并且在计算机使用之后发现了表明规则的第二部分可能导致错误决策的示例。
关于algorithm - 寻找封闭骑士之旅的快速算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/15828645/