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