0

我必须建立一个扫雷求解器，但真的不知道从哪里开始。问题是，我必须使用一些元启发式算法，比如蚁群优化、模拟退火、遗传编程等。我在网上找到了一些相关的资料，但我不确定哪些有用，哪些没用，因为没有什么是“完美契合”的。看来我必须自己调整一些元启发式算法，而不是遵循以前做过的人写的一些文章。这就是为什么我想在开始之前了解所有我需要知道的事情。

  1. 如何制定我的问题以使其适合使用元启发式来解决它？我知道这基本上是一个 CSP（约束满足问题），但不知道如何利用这些知识找到合适的算法来解决它。
  2. 哪种元启发式方法适合解决我的问题（以及为什么）？
  3. 我应该注意哪些特定于我的问题的事情？
4

2 回答 2

3

“蚁群优化、模拟退火、基因编程”......大词，但我不知道你会如何使用它们中的任何一个！

我建议有两个求解器：

  1. 完美解决者：有一个完美的答案，毫无疑问并解决它。
  2. 不完美的求解器：有疑问并且您想找到危害最小的解决方案。

先应用完美求解器，如果失败，再应用不完美求解器。

完美的求解器需要找到所有的组合可能性并检查它们中的哪些有效。实际上这并不难，因为您一次会考虑 1-5 个图块（作为人类求解器，我通常限制自己使用那么多图块），最多只有 32 个易于检查的组合。

对于不完美的求解器，您可以考虑所有组合，找出有效组合，使用有效组合计算不同位置的地雷概率，并选择最小地雷概率的一个。

想想看，这两种方法是一样的！在完美求解器中，您将选择具有 0 地雷概率的图块。所以，总结一下：

  1. 选择 1-10 个相邻或最多有一个间隙连接的未标记图块，并且每个图块都连接到至少一个已显示的非地雷位置。
  2. 找出所有有效的组合
  3. 如果我在任何位置的概率为 0，请立即选择该选项。
  4. 或者，以最小的地雷概率跟踪位置。
  5. 转到步骤 1

第 1 步并不像听起来那么糟糕，因为只有少数组合同时满足这两个条件（与已解决的非矿山位置相邻和相邻）。

于 2012-10-06T14:01:38.350 回答
0

Metaheuristics 可能不是 Minesweeper 的最佳算法 - 至少不是简单的部分。

相反，一个简单的推理规则引擎可能已经标记了许多炸弹并揭示了空闲点。使用该信息标记炸弹后，需要进行推理以进一步推理。如需灵感，请参阅 drools 的conway 的生活游戏示例。

于 2012-10-07T07:28:51.227 回答