java - 存储所有排列的模式数据库

Question

我正在寻找一些关于存储条纹图案数据库的所有可能排列的建议。

所以十五个瓷砖问题有 16 个!可能的排列，但是存储 fringe 的值，因此 0(空白图 block )、3、7、11、12、13、14、15 是 16!/(16-8)! = 518,918,400 个排列。

我希望将所有这些排列与启发式函数的值一起存储在数据结构中(每次迭代广度优先搜索时都会递增)，到目前为止，我正在这样做，但速度非常缓慢，并且采取了我 5 分钟存储 60,000 这是我没有的时间!

目前我有一个看起来像这样的结构。

Value Pos0 Pos3 Pos7 Pos11 Pos12 Pos13 Pos14 Pos15

我存储给定数字的位置的位置。当我计算启发式值时，我必须使用这些位置作为 ID，我可以快速搜索到给定的组合并检索该值。

我对此非常不确定。拼图的状态用一个数组例子来表示:

int[] goalState = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}

我的问题是存储这些值的最佳数据结构是什么？以及检索它们的最佳方法。

(这个问题最初是基于存储在数据库中，但现在我想将它们存储在某种形式的本地数据结构中——因为从数据库中检索速度很慢)

Answer 1

我无法理解，0,3,7,11,12,13,14,15 在您的情况下有什么特殊含义。他们的立场是不变的吗？他们的位置是否足以识别整个拼图状态？

不管怎样，这里是一个通用的方法，你可以随时缩小范围:

由于您最多有 16 种可能的状态，因此我会尝试使用十六进制数字来表示您的排列。所以状态 {1,2,3,6,5,4,7,8,9,10,11,12,13,14,15,0} 看起来像 0x123654789ABCDEF0 = 1312329218393956080。可能的最大数字是 0xFEDCBA9876543210，它仍然可以存储在 unsigned long(仅从 Java 8 起)或 BigInteger 中(有很多示例，我更喜欢这个)。这样的数字对于每个排列都是唯一的，并且可以用作主键，如果您拥有整个状态，从数据库中检索它会非常快。

//saving your permutation
String state = "0xFEDCBA9876543210";
BigInteger permutationForDatabase = new BigInteger(state, 16);
//and then you can insert it into database as a number

//reading your permutation
char searchedCharacter = 'A';//lets say you look for tile 10
BigInteger permutation = ...;//here you read the number from the database
int tilePosition = permutation.toString(16).indexOf(searchedCharacter);

可能有更优雅/高性能的解决方案来获取磁贴位置(可能是一些位操作魔法)。