魔方的启发式

Question

我正在尝试了解用于设计启发式的模式数据库。我正在阅读 Richard E. Korf 的书Heuristic Search。其中一段说

魔方的明显启发是曼哈顿距离的三维版本。对于每个立方体，计算正确定位和定向所需的最小移动次数，并将所有立方体的这些值相加。不幸的是，要允许该值必须除以 8，因为每次扭曲移动 8 个立方体。更好的启发式是取角立方体曼哈顿距离之和的最大值除以4，以及边立方体之和除以4的最大值。边立方体曼哈顿距离的期望值为22/ 4=5.5，而角立方的对应值是 12.333/4，大约等于 3.08，部分原因是有 12 个边角立方，但只有 8 个角立方。

我的问题是为什么取角立方体的曼哈顿距离总和除以四和取边立方的曼哈顿距离总和的最大值除以四比取曼哈顿距离总和除以八更好的启发式方法？

此外，他们如何获得 5.5 和 3.08 的期望值？

Answer 1

从这个意义上说，它更接近距离的真实值更好，因为考虑角/边缘隔间的移动会产生更小的误差。通过诱导误差，我的意思是计算一些距离，即使你已经计算了不同的距离，这会修改你的立方体，因此当前的计算会产生错误，下一个也是如此，下一个......一般来说 - 较小的数量您可以找到（几乎）独立的元素，这些元素仍然保证启发式是可接受的，这是首选的，因为像这样的启发式（简单求和）假设每个动作的独立性，这在 rubics 立方体中根本不正确。因此，违反独立性的次数越少，启发式就越可靠。