algorithm - 散列 15 拼图状态的有效方法的想法

Question

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

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

喜欢:

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

所以我想创建一个唯一编号来标识该州。我可以将所有数字转换为 16 进制数，但我认为这效率不高有什么想法吗？

谢谢

Answer 1

你的状态同构于 16 个元素的排列。一个 45 位的数字足以枚举它们(log2 16!)，但如果有利的话，我们也可以四舍五入到 64 位。问题简化为找到从状态到它在状态枚举中的位置的有效转换。

知道 0..16 中的每个数字只出现一次，我们可以创建 16 个 log2 变量，每个变量 16 = 4 位，其中第 i^th 变量表示数字 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 位都不可行。