模式数据库存储所有排列

Question

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

所以十五个瓷砖问题有16个!可能的排列,但是存储的值为fringe0(空白区块),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,仍然可以存储在无符号长(仅限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);

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

Answer 2

每个数字0-15都是一个4位数字.您必须代表7个这样的数字,最低要求为28位,这完全在a的31个有符号位空间内int.因此,可以分配所有排列,并从中导出所有排列int.

要计算这个数字,给定变量a通过g:

int key = a | (b << 4) | (c << 8) | (d << 12) | (e << 16) | (f << 20) | (g << 24);

要解码(如果需要):

int a = key & 0xF;
int b = key & 0xF0;
int c = key & 0xF00; // etc

存储ints在数据库中非常有效,并且将使用最少的磁盘空间:

create table heuristics (
    key_value int not null,
    heuristic varchar(32) not null -- as small as you can, char(n) if all the same length
);

后插入所有的行,创建一个覆盖指标于超快速查找:

create unique index heuristics_covering heuristics(key_value, heuristic);

如果在插入之前创建此索引,则插入将非常非常慢.

创建数据并插入数据是相对简单的编码.