我已经为大型（更高维度）井字游戏考虑了一些启发式方法。我如何检查其中哪些实际上是一致的？
无论如何，一致性是什么意思？
问问题
1779 次
2 回答
1
启发式为给定状态产生某种成本值。在这种情况下，一致性意味着对一个状态的估计加上移动到下一个状态的成本小于或等于对那个新状态的估计。如果这不是真的，那么这意味着——如果启发式是准确的——从一个状态转换到下一个状态可能会产生负成本，这通常是不可能或不正确的。
当涉及到寻路时，这是很直观的证明，因为您预计沿路径的每一步都需要一些时间，因此步骤 1 的估计值必须低于任何步骤 2 的估计值。对于 tic- 可能有点复杂tac-toe，因为您可能必须任意决定什么构成系统中的“成本”。如果您的启发式可以由于下棋而上升或下降 - 例如。因为你用正数编码好的动作，用负数编码坏的动作——那么你的启发式就不能保持一致。
然而，缺乏一致的启发式并不总是一个问题。如果没有一个，您可能无法保证达到最佳解决方案，但与蛮力状态搜索相比，它仍然可以加快搜索速度。
于 2009-10-09T09:39:24.440 回答
0
编辑：这个答案混淆了可接受性和一致性。我已将其更正为可受理性，但最初的问题是关于一致性的，这个答案并没有完全回答这个问题。
您可以通过区分所有不同的情况来分析地做到这一点，从而证明您的启发式确实是可以接受的。
对于有根据的搜索，当且仅当它低估了到合适状态的“距离”时，对于搜索问题（例如，搜索游戏中的最佳移动），启发式是可以接受的。
示例：通过城市之间的高速公路网络搜索到目标城市的最短路线。在这里，人们可以使用欧几里德距离作为一种启发式方法：到目标的直线长度总是比可能的最佳方式短或等长。
诸如A*之类的算法需要可接纳性，然后才能保证您处于最佳状态（即，如果存在目标状态，它们将找到到达目标状态的最佳“路线”）。
我建议在AI 教科书中查找该主题。
于 2009-10-08T19:55:27.127 回答