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