我正在尝试实现Korf的算法来求解3x3x3魔方。解决方案的一部分是创建一个模式数据库。
这是论文中的一句话，从字面上讲，它包含了关于如何做到这一点的全部信息：
使用从目标状态进行广度优先搜索，我们可以枚举这些状态，并在表中记录数字解决每个拐角组合所需的移动数立方体。
如何在代码中转换它？由于在每一步中，我们都有多个目标状态，我不清楚我们如何才能"枚举"所有可以从中到达的状态
我已经实现了Korf的算法，您可以使用我的代码作为参考：https://github.com/benbotto/rubiks-cube-cracker/这篇文章包含了很多代码，太多了，但我可以给出一些通用的算法提示。
首先，Korf的论文建议使用三个模式数据库，而不仅仅是一个。其中一个数据库存储求解任何立方体的角块所需的移动次数。有8个角落立方体，每个可以占据8个位置中的任何一个，所以有8个！可能的排列。每个角片可以以3种不同的方式定向——例如，三个贴纸中的任何一个都可以面朝上——但立方体中7个的定向决定了第8个的定向(根据立方体定律)。因此，有3^7种可能的方式可以对角进行定向。那么，总共有8个！*3^7种可能的方法来扰乱立方体的角，这些88179840个状态可以在合理的时间内迭代(30分钟左右)。所有拐角状态都可以在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代码。Korf在他的论文《大规模并行广度优先搜索》中给出了一个简洁而优美的线性算法。
我们从左到右扫描排列，构建一个长度为n的比特串，指示到目前为止我们已经看到了排列的哪些元素。最初，字符串全部为零。当遇到排列的每个元素时，我们使用它作为比特串的索引，并将相应的比特设置为1。当我们在排列中遇到元素k时，为了确定其左边小于k的元素的数量，我们需要知道比特串的前k个比特中的1的数量。我们通过将字符串右移n−k来提取前k个比特。这将问题简化为：给定一个比特串，计算其中一个比特的数量。
我们通过使用位字符串作为预计算表的索引来在恒定时间内解决这个问题，预计算表包含每个索引的二进制表示中的1个数。
我花了很长时间来消化它并将其转换为代码，特别是因为他没有谈论对部分排列进行索引。在为边缘片段生成图案数据库时，您需要对部分排列进行索引，因为创建一个包含所有12条边缘的数据库会非常大。因此，我在Medium上写了一篇关于它的文章：https://medium.com/@benjamin.bott/sequentially-indexing-permutations-alinear-algorithm-for-computing-lexicographic-rank-a22220ffd6e3
最后，我测试了用于存储多维数据集的许多不同的数据结构。在我的代码中，我有多个解算器(Korf和Thisthlewaite)，还有一个图形表示。实际上，我把立方体存储在4种不同的结构中。对于像Korf这样的算法，用于表示魔方的结构对求解器的速度有着巨大的影响。我在另一篇文章中写到了不同的结构，选项(4)是迄今为止我测试中使用Korf算法最快的。要创建单个数据库条目，您需要每个多维数据集的索引和方向(例如角的{0-7，0-2})。因此，在创建模式数据库时，将多维数据集表示为索引和方向是有效的，这样就不需要额外的处理来计算它们。