魔方启发式算法

Question

我正在尝试理解模式数据库以设计启发式算法。我正在阅读Richard E. Korf的书《Heuristic Search》。其中一段话说：

“魔方的明显启发式是曼哈顿距离的三维版本。对于每个小立方体，计算正确定位和定向所需的最小移动次数，并将这些值总和在所有小立方体上。不幸的是，为了是可接受的，必须将此值除以8，因为每个扭转会移动8个小立方体。更好的启发式是将角落小立方体的曼哈顿距离之和的最大值除以4，边缘小立方体的曼哈顿距离之和的最大值也除以4。边缘小立方体的曼哈顿距离的期望值为22/4=5.5，而角落小立方体的相应值为12.333/4，约等于3.08，部分原因是有12个边缘小立方体，但只有8个角落小立方体。”

我的问题是，为什么将角落小立方体的曼哈顿距离之和的最大值除以4和边缘小立方体的曼哈顿距离之和的最大值除以4作为启发式比将曼哈顿距离之和除以8更好？

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

- a_123

---

我认为这个问题在技术上是符合主题的，但你在cs.stackexchange.com上提问可能会更有好运。 - alexw

请勿在多个网站上发布相同的问题。每个社区都应该有一个诚实的机会来回答问题，而不浪费任何人的时间。此外，这篇文章也发布在CS.SE上（http://cs.stackexchange.com/q/55660/755）。 - D.W.

@alexw，感谢您尝试帮助s_123，但是在未来，如果您要建议另一个网站，请提醒人们不要跨贴--您可以建议他们在发布到另一个网站之前删除他们的问题。这将有助于他们获得更好的体验。谢谢。 - D.W.

是的，我注意到你在CS.SE上投了关闭票。为什么不在这里投票关闭呢？SO已经变得非常庞大了，而我相信像CS.SE这样的网站正是为了提供更具体的场所来回答某些类型的问题（比如算法设计）。 - alexw

Answer 1

在这方面，更接近距离的真实值是更好的选择，因为考虑到角落/边缘魔方块的移动会导致更少的误差。所谓的误差是指即使您已经计算出不同的距离，仍然要计算某些距离，这将修改您的魔方块，因此当前的计算存在误差，以及下一个和下一个... 一般来说，您可以找到较小数量的（几乎）独立元素，仍保证启发式方法是可用的，这样的启发式方法（简单求和）假设每个移动是独立，但在魔方中显然并不是这样。因此，违反独立性的数量越小，启发式方法就越可靠。

- lejlot