a-star - 用于 2x2 魔方求解的 A* 算法中的 h(n) 选择

Question

我目前正在研究一个 2x2 魔方求解机器人项目。它通过一个 2x2 颜色传感器阵列接收立方体数据，并使用一些伺服电机和臂来解决它。我在看 wiki，我认为 A* 可能是编写程序来解决它的一种方法。但是，我不知道如何定义立方体的预期成本函数（h）。它不是在 2D 平面上找到最短路径，其中 h(n) 可以只是某种形式的实际距离（欧几里得、曼哈顿等）。我本来想计算已经组合了多少块，但它不会真正起作用，因为我只能在立方体上移动 2~3 次，并且很多块都断开了。我应该如何写这个成本函数？或者在我的情况下是否有更好的 A* 替代方案？（我猜 2x2 使用 IDA* 太简单了。

标签： a-starrubiks-cube

Answer 1

具有迭代深化、深度优先搜索 (IDA*) 的 A* 是一个不错的选择。对于启发式，定义一个或多个模式数据库，其中每个键是一个立方体状态，每个值是从该立方体状态到已解决状态的距离。为了保持数据库合理的小，每个数据库都可以保存多维数据集整体状态的一个子集。关于启发式，给定一个立方体状态，在每个数据库中查找距离。这些距离中的最大值是到求解状态的最佳估计距离（即，求解立方体至少需要那么多移动）。

例如，可以创建一个包含所有 8 个立方体的方向的数据库。只是方向在乎你，而不是位置。由于每一块都可以处于三个方向之一 - 在顶层，任何贴纸都可以指向，例如 - 有 3^8 种可能的状态。我不是 2x2 的专家，但我很确定不可能只迷惑一件。也就是说，不可能有一个已解决的 2x2 然后只翻转一个立方体。假设这是正确的，实际上有 3^7=2187 种可能的方向状态。然后，您将使用 BFS 从已解决状态迭代并找到这 2187 个状态中的每一个，将每个状态编码为 0-2186 的整数，并存储从该状态到已解决状态的距离。换句话说，数据库只是一个哈希表。

您可以以相同的方式创建多个数据库。例如，8 块的位置。8 件中的 4 件的位置和方向。等等。

当需要解决多维数据集时，请使用 IDA*。每次遇到状态时，检查所有模式数据库提供的最大距离。这是你的启发式函数。相应地修剪。

我有一篇关于 Medium 的文章进行了更详细的介绍，但它是针对 3x3 的。不过，同样的策略也有效。

Ps 2x2 足够小，可以创建一个完美的模式数据库，每个状态到已解决状态的距离精确，并将该数据库存储在磁盘上仅 1.8MB。（有 3,674,160 个状态，上帝的数字是 11。11 可以放在一个半字节中。3,674,160/1024^2/2 ~= 1.8MB。）使用该数据库，IDA* 将能够立即有效地解决 2x2。