我知道有几个类似的线程,但我没有找到一个解决方案,甚至在这样以外。
我的问题是:
我实现了warnsdorff的骑士之旅问题的算法,但在某些情况下没有给出解决方案。在一些地方,我读到它可以更好地工作与一些修改,但没有人指定哪些修改是那些。有人知道解决办法吗?我知道其他算法,但它们要复杂得多。
有时即使是8x8棋盘也不能给出一个好的解决方案。我认为阅读我的代码毫无意义,因为这是一个经典的警告:检查可能的移动,并选择下一步中可能移动最少的一个。
最佳答案
W+的链接不再存在,使得被接受的答案不可用。
对warnsdorff算法的改进包括:
Arnd Roth的提议:
Roth认为Warnsdorff启发式方法中的问题在于随机分层规则。
提议是通过选择与董事会中心之间欧几里德距离最大的继任者来打破这种联系。
这里的问题是当一个以上的继任者共享相同的距离时会发生什么。阿恩德·罗斯声称这种改进首先
在有428行的电路板上发生故障,所有电路板的故障率均小于1%
少于2000行的板。
Ira Pohl的提议:
为了打破这种联系,波尔决定再次适用华斯道夫的规则。为了达到这一目的,我们必须把所有未被探视的邻居的度数之和,以及那些被捆绑的继承者的度数之和,并选择总和最小的平方。
这里的一个问题是,无论我们应用warnsdorff规则多少次,我们都会导致(两个相邻的
如果我们从角落的广场开始。此外,如果我们申请
warnsdorff的大量启发式然后渐近地
这相当于彻底的搜索。
波尔还建议,如果我们在第二次应用warnsdorff后未能产生接班人,可以使用固定的任意方块顺序来打破联系。他的说法是,这成功地在8*8板上产生了一个解决方案。
通过使用这些增强功能之一,我们有更好的机会通过防止可能的锁定来系统地创建解决方案。