3

所以我试图通过使用 C++ 的不同算法来解决魔方。我已经尝试过迭代深化搜索 (IDS) 并且做对了，但现在我陷入了 A* 算法。我做了一些研究，发现立方体角落和边缘的 3D 曼哈顿距离是为 A* 开发启发式的方法之一，但我不知道它是如何编码的。你们能否帮助或指导我如何开发定义上可接受的功能？

我正在寻找可以帮助我摆脱这个困境的所有建议。谢谢。

4

1 回答 1

5

IDA* 是解决魔方的最佳算法之一，因为状态空间很大，如果进行适当的移动修剪，则不会有很多重复。要获得高效的求解器，您需要移动修剪和良好的启发式算法。通常每个面有 3 次移动 - 向前/向后 90 度和 180 度。有 6 个面，有 18 个动作。

  1. 简单的移动修剪：如果你通过保留一个历史移动来对你的移动进行一些简单的修剪，你可以将魔方的分支因子从 18 缩小到大约 15。因为任何单一的移动都可以将一个面变成任何配置，你应该永远不要连续两次移动同一张脸。在第一步之后，将有 5 个面，每个面 3 步 = 每步 15 步。

  2. 高级移动修剪：让三个面为“第一”面，其中三个为“第二”面，其中第二个面与第一个面相对。这里的规则是，在您移动第一个面之后，您可以移动任何其他面 - 所以会有 15 次移动。但是，在您移动第二张脸之后，您不能再次移动同一张脸或相反的第一张脸。在这种情况下，分支因子为 12。总的分支因子约为 13。

  3. 启发式：模式数据库（PDB）为魔方提供了很好的启发式方法。例如，您所做的是忽略边缘，然后彻底解决所有角落，将结果存储在哈希表中。（使用一个完美的散列函数，然后会有一个独特的紧凑映射，它非常节省内存。）有 8800 万个组合和少于 16 个值，你可以将它存储在 44 MB 的内存中。当您想要某个状态的启发式方法时，您只需使用哈希函数在表中查找角点配置，其中包含解决该配置所需的移动总数。对于该问题，这是一个可接受的（且一致的）启发式方法。除此之外，您可能想要做边缘，但 12 边缘 PDB 需要 500GB 的内存来存储，并且可能不适合内存。所以，你可以做边的子集。您还可以使用立方体对称性和许多其他技巧来获得更好的启发式值。但是，通过良好的并行 IDA* 实现和一些大型 PDB，您可以优化地解决随机魔方实例。

有很多关于这个主题的研究论文——我建议使用谷歌学者在网上查找它们。

如果您想从更简单的开始，以下是如何实现“更简单”的启发式方法：

  1. 对于立方体中的每个角/边，计算它自己需要多少次移动才能到达目标位置/方向。把它加到所有立方体上。

  2. 由于立方体的一个面每转一圈会移动 4 个角和 4 个边，因此将第一步中的数字除以 8。这是该问题的一个可接受的启发式方法。

如果您忽略方向，每个立方体最多需要两次移动才能到达其目标位置，这意味着您的最终启发式将小于 2。将方向考虑在内只会稍微提高这一点。因此，这种方法在实践中不会特别有效。

于 2020-02-10T04:13:00.673 回答