algorithm - 哪些元启发式适合构建扫雷求解器？

Question

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

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

Answer 1

“蚁群优化、模拟退火、遗传编程”……大词，但我不确定您会如何使用它们中的任何一个!

我建议有两个求解器:

1. 完美的求解器:毫无疑问地找到完美的答案并解决它。
2. 不完美的解决方案:存在疑问且您想找到危害最小的解决方案。

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

完美的求解器需要找到所有的组合可能性并检查其中哪些可行。实际上并没有那么困难，因为您会一次考虑 1-5 个图 block (作为人类求解器，我通常会限制自己使用那么多图 block )，最多只有 32 个组合很容易检查。

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

想想看，这两种方法是一样的!在完美求解器中，您会选择地雷概率为 0 的方 block 。所以，总结一下:

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

第 1 步并不像听起来那么糟糕，因为只有少数组契约(Contract)时满足这两个条件(连续且与已解决的非地雷位置相邻)。