如何创建解决魔方的模式数据库？

Question

我正在尝试实现Korf 算法来求解 3x3x3 魔方。解决方案的一部分是创建模式数据库。

这是从论文中引用的内容，从字面上看，包含了如何做到这一点的全部信息：

使用从目标状态开始的广度优先搜索，我们可以枚举这些状态，并在表中记录解决每个角块组合所需的移动次数。

你如何在代码中转换它？由于在每个步骤中，我们都有多个目标状态，因此我不清楚如何“枚举”从中可以到达的所有状态。

Answer 1

我已经实现了Korf的算法，你可以使用我的代码作为参考： https: //github.com/benbotto/rubiks-cube-cracker/ 代码很多，太多了，无法包含在其中这篇文章，但我可以提供一些通用的算法技巧。

\n\n

首先，科尔夫的论文建议使用三个模式数据库，而不仅仅是一个。其中一个数据库存储解决任何立方体角块所需的移动次数。有 8 个角块，每个角块可以占据 8 个位置中的任意一个，所以有 8 个！可能的排列。每个角块都可以以 3 种不同的方式定向（例如，三个贴纸中的任何一个都可以面朝上），但其中 7 个立方体的方向决定了第 8 个立方体的方向（根据立方体定律）。因此，角的方向有 3^7 种可能的方式。那么一共有8个！* 3^7种可能的方式对立方体的角进行打乱，并且可以在合理的时间（30分钟左右）内迭代这88,179,840个状态。所有角点状态都可以在 11 次或更少的移动中达到，因此角点模式数据库中的每个条目都可以存储在半字节（4 位）中。在磁盘上，角图案数据库占用约 42MB。

\n\n

可以使用广度优先搜索来填充该数据库。应用移动并使用角的状态在数据库中创建索引。如果之前已经看到过该状态且移动次数较少，则可以修剪搜索树：没有理由继续沿分支向下移动；否则，将该状态添加到数据库中并继续搜索。如上所述，由于在搜索过程中可以完成大量修剪，因此在现代计算机上迭代所有可能的角状态不会花费很长时间。

\n\n

\n
• 我的广度优先搜索算法：https://github.com/benbotto/rubiks-cube-cracker/blob/master/Controller/Searcher/BreadthFirstCubeSearcher.cpp
\n
• 我的角图案数据库：https://github.com/benbotto/rubiks-cube-cracker/blob/master/Model/PatternDatabase/Korf/CornerPatternDatabase.cpp
\n
• 这是我索引角落数据库的地方：https://github.com/benbotto/rubiks-cube-cracker/blob/master/Controller/Command/Solver/KorfCubeSolver.cpp#L30
\n

\n\n

Korf 建议另外两个数据库：一个用于 12 条边中的 6 条，另一个用于其他 6 条边。Korf 使用的是有限的硬件（Sun SPARC Ultra！），但由于我使用的是更现代的机器，所以我选择在每个边缘数据库中使用 7 个边缘。这极大地加快了求解器的速度。不管怎样，7条边可以占据12个位置，所以有12P7（12！/（12-7）！）排列。每个角可以以 2 种方式定向，因此 7 条边有 2^7 种可能的方向。同样，这是足够小的数量的立方体状态来迭代，并且所有状态都可以在 10 次或更少的移动内达到。将每个条目存储在半字节中，每个 7 边数据库占用约 244MB（12P7 * 2^7 / 2 字节）。

\n\n

出于效率原因（并且在此代码中效率很重要），我使用非递归算法实现了广度优先搜索。虽然这种类型的搜索对于构建角落数据库效果很好，但对于索引边缘数据库来说内存成本太高。因此，我使用自定义迭代加深深度优先搜索来索引边缘。“自定义”部分是当它达到已经遇到的状态时它会提前退出。

\n\n

\n
• 我的自定义 IDDFS 实现： https://github.com/benbotto/rubiks-cube-cracker/blob/master/Controller/Searcher/PatternDatabaseIndexer.cpp
\n
• 我的各种边缘图案数据库： https://github.com/benbotto/rubiks-cube-cracker/tree/master/Model/PatternDatabase/Korf
\n

\n\n

当然，上面的磁盘数据库大小假设数据库只包含到达每个状态的移动次数，每个状态都存储在一个半字节中。也就是说，数据库是一个哈希表，每个状态都是表中的一个索引。因此，您需要一个“完美哈希”算法，该算法采用立方体排列并返回索引。科尔夫在他的论文中（他有多篇关于组合谜题的论文）对于如何创建这样的散列相当简洁。归根结底就是计算莱默码。Korf 在他的论文《大规模并行广度优先搜索》中给出了一个简短而有趣的线性算法。

\n\n

\n

我们从左到右扫描排列，构造一个长度为 n 的位串，指示到目前为止我们已经看到的排列的哪些元素。最初该字符串全为零。当遇到排列的每个元素时，我们使用它作为位串的索引并将相应的位设置为 1。当我们在排列中遇到元素 k 时，为了确定其左侧小于 k 的元素数量，我们需要知道位串的前 k 位中的 1 的数量。我们通过将字符串右移 n \xe2\x88\x92 k 来提取前 k 位。这将问题简化为：给定一个位串，计算其中的 1 位的数量。

\n\n

我们通过使用位串作为预计算表的索引来在恒定时间内解决这个问题，其中包含每个索引的二进制表示形式中的 1 的数量。

\n

\n\n

我花了很长时间来消化它并将其转换为代码，特别是因为他没有谈论索引部分排列。在生成边片的模式数据库时，您需要索引部分排列，因为创建所有 12 条边的数据库将非常大。因此，我在 Medium 上写了一篇关于它的文章：https://medium.com/@benjamin.botto/sequentially-indexing-permutations-a-linear-algorithm-for-computing-lexicography-rank-a22220ffd6e3

\n\n

最后，我测试了许多不同的数据结构来存储多维数据集。在我的代码中，我有多个求解器（Korf 和 Thisthlewaite），以及图形表示。我实际上将立方体存储在 4 种不同的结构中。对于像 Korf 这样的算法，用于表示魔方的结构对求解器的速度具有巨大（特别强调！）的影响。我在另一篇文章中写了有关不同结构的文章，在我的测试中，选项 (4) 是迄今为止最快的 Korf 算法。要创建单个数据库条目，您需要每个立方体的索引和方向（例如，角为 {0-7, 0-2}）。因此，在创建模式数据库时，将立方体表示为索引和方向是有效的，因此不需要额外的处理来计算它们。

\n