rubiks-cube - 如何创建用于解决魔方的模式数据库？

Question

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

这是paper的引文，从字面上包含有关如何执行操作的全部信息:

用一个
从目标状态进行广度优先搜索，我们可以枚举这些状态，并在表格中记录数字
解决每个角点组合所需的动作
库比斯。

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

Answer 1

我已经实现了Korf的算法，并且您可以将我的代码用作参考:https://github.com/benbotto/rubiks-cube-cracker/这是很多代码，太多内容不能包含在本文中，但是我可以给出一些常规的算法技巧。

首先，Korf的论文建议使用三个模式数据库，而不仅仅是一个。其中一个数据库存储解决任何多维数据集的角点所需的移动次数。有8个角球室，每个角球可以占据8个位置中的任何一个，所以有8个!可能的排列。每个角块可以以3种不同的方式定向-例如，三个贴纸中的任何一个都可以面朝上-但7个立体角的方向决定了第8个角的方向(根据立方体的定律)。因此，有3 ^ 7种可能的方式可以确定角的方向。那么一共有8个! * 3 ^ 7种可能的方式可以使多维数据集的角变乱，并且可以在合理的时间量(大约30分钟)内迭代这些88,179,840个状态。可以通过11步或更少的移动就可以达到所有角状态，因此可以将角模式数据库中的每个条目存储在半字节(4位)中。在磁盘上，角落模式数据库占用大约42MB。

广度优先搜索可用于填充此数据库。进行移动并使用拐角状态在数据库中创建索引。如果以前只用较少的动作就可以看到状态，则可以修剪搜索树:没有理由继续沿分支前进；否则，将状态添加到数据库并继续搜索。如上所述，由于在搜索过程中可以进行大量修剪，因此在现代计算机上迭代所有可能的角状态不会花费很长时间。

我的广度优先搜索算法:https://github.com/benbotto/rubiks-cube-cracker/blob/master/Controller/Searcher/BreadthFirstCubeSearcher.cpp

我的角落模式数据库:https://github.com/benbotto/rubiks-cube-cracker/blob/master/Model/PatternDatabase/Korf/CornerPatternDatabase.cpp

这是角落数据库的索引位置:https://github.com/benbotto/rubiks-cube-cracker/blob/master/Controller/Command/Solver/KorfCubeSolver.cpp#L30

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字节)。

出于效率方面的考虑，我使用非递归算法实现了广度优先搜索(此代码中的效率至关重要)。尽管这种类型的搜索对于构建角落数据库很好，但是对于索引边缘数据库而言，内存成本过高。因此，我使用了自定义的迭代加深深度优先搜索来索引边缘。 “自定义”部分是在达到已遇到的状态时提早退出。

我的自定义IDDFS实现:https://github.com/benbotto/rubiks-cube-cracker/blob/master/Controller/Searcher/PatternDatabaseIndexer.cpp

我的各种边缘模式数据库:https://github.com/benbotto/rubiks-cube-cracker/tree/master/Model/PatternDatabase/Korf

当然，上面的磁盘数据库大小假定数据库只包含进入每种状态的移动次数，每步存储在半字节中。也就是说，数据库是一个哈希表，每个状态都是该表的索引。因此，您需要一种“完美的哈希”算法，该算法需要对多维数据集进行排列并返回索引。在他的论文中，并且他有多本关于组合拼图的论文，Korf对于如何创建这样的哈希非常简洁。归结为计算 Lehmer codes。 Korf在他的论文 Large-Scale Parallel Breadth-First Search中给出了一种简短的线性算法。

我们从左到右扫描排列，构造了一个长度为n的位串，表示到目前为止我们已经看到了排列的哪些元素。最初，字符串全为零。当遇到排列的每个元素时，我们使用
将其作为位串的索引，并将相应的位设置为1。当我们在置换中遇到元素k时，要确定其左边小于k的元素数，我们需要知道位串的前k个位中的元素数。我们通过将字符串右移n-k来提取前k位。这样可以减少问题:给定一个位串，计算其中的一位数。

我们通过使用位字符串作为预计算表的索引来固定时间解决此问题，该表包含每个索引的二进制表示形式中的位数。

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

最后，我测试了许多用于存储多维数据集的不同数据结构。在我的代码中，我有多个求解器(Korf和Thisthlewaite)，以及一个图形表示。我实际上将多维数据集存储在4种不同的结构中。使用像Korf一样的算法，您用来表示Rubik's Cube的结构对求解器的速度具有巨大的(特别强调!)影响。我在 another post中描述了不同的结构，在我的测试中，使用Korf算法的选项(4)迄今为止最快。要创建单个数据库条目，您需要每个多维数据集的索引和方向(例如，{0-7，0-2}代表拐角)。因此，在创建模式数据库时，将多维数据集表示为索引和方向非常有效，因此不需要其他处理即可计算它们。