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