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