我已经实现了Korf算法,你可以使用我的代码作为参考:
https://github.com/benbotto/rubiks-cube-cracker/。这是一段很长的代码,太多了不能包含在这篇文章中,但我可以给出一些通用的算法提示。
首先,Korf的论文建议使用三个模式数据库,而不是一个。其中一个数据库存储解决任何魔方的角块所需的移动次数。有8个角块,每个角块都可以占据8个位置中的任意一个,因此有8!种可能的排列方式。每个角块可以朝向3种不同的方式——例如,任何三个贴纸都可以朝上——但是7个角块的方向决定了第8个角块的方向(按照魔方的规则)。因此,角块可以朝向3^7种可能的方式。总的来说,魔方的8个角块可以有8!* 3^7种可能的打乱方式,并且这些88,179,840个状态可以在合理的时间内迭代(大约30分钟)。所有角块状态可以在11步或更少的步数内到达,因此角块模式数据库中的每个条目都可以存储在一个nibble(4位)中。在磁盘上,角块模式数据库占用约42MB的空间。
可以使用广度优先搜索来填充此数据库。应用移动并使用角落的状态创建一个索引到数据库中。如果该状态以较少的移动次数被看到过,则可以修剪搜索树:没有继续向下分支的理由;否则,将状态添加到数据库中并继续搜索。如上所述,在现代计算机上迭代所有可能的角状态不需要很长时间,因为在搜索期间可以进行大量修剪。
Korf建议使用两个额外的数据库:一个包含12个边中的6个,另一个包含其余6个。由于我使用的是更现代化的机器,因此选择在每个边数据库中使用7个边。这极大地加快了求解器的速度。无论如何,7个边可以占据12个位置,因此有12P7(12!/(12-7)!)种排列方式。每个角可以朝向2个方向,因此有2^7种可能的7个边的朝向。同样,这是一个足够小的魔方状态数量,可以迭代处理,所有状态都可以在10步或更少的步数内到达。将每个条目存储在一个nibble中,每个7个边的数据库占用约244MB(12P7 * 2^7 / 2字节)。
出于效率原因(并且效率在这段代码中很重要),我实现了广度优先搜索使用非递归算法。虽然这种类型的搜索对于构建角数据库效果很好,但是索引边缘数据库的内存成本太高。因此,我使用了自定义的迭代加深深度优先搜索来索引边缘。 "自定义"部分是当它到达已经遇到的状态时,它会提前退出。
上述磁盘数据库大小当然假定数据库只包含到达每个状态所需的步数,每个步数存储在一个四位半字节中。也就是说,数据库是一个哈希表,每个状态都是表中的索引。因此,您需要一种“完美哈希”算法,它接受魔方的排列并返回索引。在他的论文中,Korf 对如何创建这样的哈希算法非常简洁。它归结为计算
Lehmer codes。Korf 在他的论文
Large-Scale Parallel Breadth-First Search 中提供了一个简短而简单的线性算法。
我们从左到右扫描排列,构建一个长度为n的位字符串,表示我们迄今为止看到的排列元素。最初,该字符串全部为零。遇到每个排列元素时,我们将其用作位字符串的索引,并将相应位设置为1。当我们在排列中遇到元素k时,为了确定左边小于k的元素数量,我们需要知道位字符串的前k位中有多少个1。通过将字符串向右移动n - k来提取前k位。这将问题简化为:给定一个位字符串,计算其中一位的数量。
我们通过使用位字符串作为预计算表中的索引来以恒定时间解决此问题,该表包含每个索引的二进制表示中的1的数量。
我花了很长时间才消化并将其转化为代码,特别是因为他没有讨论索引部分排列。在生成边缘块的模式数据库时,您需要对部分排列进行索引,因为创建包含所有12个边缘的数据库会非常庞大。因此,我在Medium上写了一篇关于此的文章:
https://medium.com/@benjamin.botto/sequentially-indexing-permutations-a-linear-algorithm-for-computing-lexicographic-rank-a22220ffd6e3
最后,我测试了多种不同的数据结构来存储魔方。在我的代码中,我有多个求解器(Korf和Thisthlewaite),还有一个图形表示。实际上我使用了4种不同的结构来存储魔方。像Korf这样的算法,用于表示魔方的结构对求解器的速度有着
巨大的(特别强调!)影响。我在
另一篇文章中写到了不同的结构,而在我的测试中,选项(4)是使用Korf算法迄今为止最快的。要创建单个数据库条目,您需要每个魔方块的索引和方向(例如角落的{0-7,0-2})。因此,在创建模式数据库时,将魔方表示为索引和方向是高效的,以便无需进行额外的处理即可计算它们。