algorithm - 你怎么知道你已经接近解决方案了？

Question

我已经搜索但没有找到答案。

我正在尝试使用在 Java 中实现的模拟退火 (SA) 算法来解决 8 个皇后谜题（更具体地说是 N 个皇后谜题），但在目标函数方面我有点卡住了。我怎么知道我是否接近我的目标（最佳解决方案）？

我想出了两种方法来给尝试“积分”（积分越多越好）：

但我不能决定这些是否有好处。你们能给我一些提示或任何其他输入吗？:)

score 1 · Accepted Answer

与解的距离通常定义为相互攻击的皇后的数量。

模拟退火采用的一种方法是随机放置所有皇后，然后选择一个受到攻击的随机皇后并将其移动到同一行的随机列中。

而不是试图将它们一一放置。

这不是和随机解决方案一样吗？

不。

我们选择一个随机的移动，但这个移动实际发生的概率取决于移动的好坏以及我们与解决方案的接近程度。

好棋总会发生，但如果是坏棋，则棋子实际发生的概率开始时很高，但随着我们越来越接近解决方案，它会变得越来越低。所以，还是有机会走坏的，所以它最终会走出一个糟糕的位置，但总体来说，它主要是试图做出好的举措。

这是模拟退火背后的基本思想——它有一个“温度”的概念（与到解的距离有关）——随着温度变低（它越来越接近解），做出坏动作的概率减少。

当我们越来越接近解决方案时，为什么不选择最好的举措呢？

这也将起作用，只要仍然有机会选择一个不好的举动（尽管我不确定这仍然会被归类为模拟退火，或者这是否会导致一个高性能的解决方案 - 分析每一步的所有动作将是相当昂贵）。

需要有一个糟糕的举动的机会，因为有时你需要远离一个局部最优，一个说只有两个皇后在互相攻击，但你不能直接从那里得到解决方案——反之亦然最好的举动将是下一步的最佳举动。

score -1 · Accepted Answer

我不确定“接近”在这里的定义是否很好。考虑到所有可以将连续皇后作为树状结构的地方，您可以构建一个非常深的分支，但这是一个完全错误的分支。这可能发生在其他算法中（想到A* ），在这些算法中，你确实可以“像乌鸦飞过一样”非常接近，但距离解决方案还有很长的路要走。

从技术上讲，我想知道您是否缺少合适的指标来解决您的问题；即，满足链接中给出的四个属性的一个，您为您提供了一种定义“接近”的可靠方法。

2 回答 2