search - 魔方的启发式

Question

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

The obvious heuristic for Rubik's Cube is a three dimensional version of the Manhattan distance. For each cubie, compute the minimum number of moves required to correctly position and orient it, and sum these values over all cubies.Unfortunately, to be admissible, this value has to be divided by 8, since every twist moves 8 cubies. A better heuristic is to take the maximum of the sum of Manhattan distances of the corner cubies, divided by four, and the maximum of the sum of edge cubies divided by 4. The expected value of the Manhattan distance of the edge cubies is 22/4=5.5, while the corresponding values for the corner cubies is 12.333/4 that's approximately equal to 3.08 partly because there are 12 edge cubies, but only eight corner cubes.

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

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

Answer 1

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