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