4

我正在通过 Ant Colony Optimization 实现一个 15 谜题求解器，并且我正在考虑一种有效地将每个状态散列成一个数字的方法，因此我浪费的字节数最少。

状态由 16 个数字的列表表示，从 0 到 15（0 是洞）。

像：

[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,0]

所以我想创建一个唯一的数字来识别那个状态。我可以将所有数字转换为以 16 为基数的数字，但我认为这不是很有效有什么想法吗？

谢谢

4

2 回答 2

7

您的状态与 16 个元素的排列同构。一个 45 位的数字足以枚举那些（log2 16！），但如果它是有益的，我们不妨向上舍入到 64 位。问题归结为找到从状态到其在状态枚举中的位置的有效转换。

知道 0..16 中的每个数字只出现一次，我们可以创建 log2 16 = 4 位的 16 个变量，其中第 i个变量表示数字 i 出现的位置。这有相当多的冗余：它需要 log2(16) * 16 位，但这正是 64 位。它可以非常有效地实现（未经测试的伪代码）：

state2number(state):
  idx = 0
  for i in [0;16):
    val = state[i]
    idx |= i << (val * 4)
  return idx

我不知道这是否是您所说的“将所有数字转换为基数 16 数字”的意思。它非常高效，当展开或进行其他微优化时，它只有几十个周期。它比需要多占用两个字节，但 64 位仍然非常节省空间，并且直接将其用作某个数组的索引对于 64 位和 45 位都是不可行的。

于 2013-12-23T23:59:09.840 回答
3

有16个！= 2.09*10^13 个可能的状态，需要大约 44.25 位进行编码。

因此，如果您想以字节为单位对状态进行编码，则至少需要 6 个字节才能完成。

为什么不这样编码：
让我们命名值 a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p

该值可以是

b`:= b - (b>a)?1:0;
c`:= c - (c>a)?1:0 - (c>b)?1:0
d`:= d - (d>a)?1:0 - (d>b)?1:0 - (d>c)?1:0
....

hashNumber= a+b *15+c*15*14+d`*15*14*15+....

这将为您提供每个可能状态到适合 6 个字节的数字的双射映射。

如果您需要，将数字转换回其引用状态也很容易。

不是最佳但快速的是：
每个数字使用 4 位（省略最后一个，因为它可以从前 15 个数字中计算出来）需要 15*4 位 = 60 位。可以存储为 7.5 个字节，或者如果您可以浪费更多，只需使用 8 个字节。

于 2013-12-24T00:00:50.613 回答