Dan*_*Ali 3 c++ artificial-intelligence heuristics a-star rubiks-cube
所以我试图通过使用 C++ 的不同算法来解决魔方。我已经尝试了迭代深化搜索 (IDS) 并得到了正确的结果，但现在我被困在 A* 算法上。我做了一些研究，发现立方体的角和边缘的 3D 曼哈顿距离是开发 A* 启发式的方法之一，但我不知道如何编码它。你们能帮助或指导我如何开发定义允许的功能吗？
我正在寻找任何可以帮助我走出困境的建议。谢谢。
IDA* 是求解魔方的最佳算法之一，因为状态空间很大，如果您进行适当的移动修剪，则不会有很多重复项。要获得高效的求解器，您需要移动修剪和良好的启发式方法。通常每个面有三个移动 - 向前/向后 90 度和 180 度。6张脸有18步。
简单的移动修剪：如果您通过保留一个历史移动来对您的移动进行一些简单的修剪，您可以将魔方的分支因子从 18 缩小到 15 左右。因为任何一次移动都可以将一个面变成任何配置，所以您应该永远不要连续两次移动同一张脸。第一个动作后，将有 5 个面，每个面 3 个动作 = 每步 15 个动作。
高级移动修剪：设三个面为“第一”面，其中三个为“第二”面，其中第二个面与第一个面相对。这里的规则是，在您移动第一个面后，您可以移动任何其他面 - 因此将有 15 次移动。但是，在您移动第二张脸之后，您不能再次移动同一张脸或对面的第一张脸。在这种情况下，分支因子为 12。总分支因子约为 13。
启发式：模式数据库(PDB) 为魔方提供了很好的启发式方法。例如，您要做的是忽略边缘，然后彻底解决所有角落，将结果存储在哈希表中。（使用完美的散列函数，然后会有一个独特的紧凑映射，非常节省内存。）有 8800 万个组合，不到 16 个值，您可以将其存储在 44 MB 的内存中。当您需要某个状态的启发式方法时，您只需使用哈希函数在表中查找角配置，其中包含解决该配置所需的移动总数。这是该问题的可接受（且一致）的启发式方法。最重要的是，您可能想要做边缘，但 12-edge PDB 需要 500GB 的内存来存储并且可能不适合内存。所以，你可以做边缘的子集。您还可以使用立方体对称性和许多其他技巧来获得更好的启发式值。但是，通过良好的并行 IDA* 实现和一些大型 PDB，您可以最佳地解决随机魔方实例。
有很多关于这个主题的研究论文 - 我建议使用谷歌学者在线查找它们。
如果您想从更简单的事情开始，以下是实现“更简单”启发式的方法：
对于立方体中的每个角/边，自行计算到达目标位置/方向需要多少次移动。将其加到所有立方体上。
由于立方体的面每转一圈就会移动 4 个角和 4 条边，因此将第一步中的数字除以 8。这就是该问题的一个可接受的启发式方法。
如果您忽略方向，则每个立方体最多需要移动两次才能到达其目标位置，这意味着您的最终启发式将小于 2。考虑到方向只会略微提高这一点。因此，这种方法在实践中不会特别有效。