database - 有效地存储 8 个不同数字和 8 个零的所有排列

Question

我正在研究 Loyd's 15 Puzzle 的最佳求解器，我遇到了一种使用 7-8 不相交模式数据库的技术(Korf，Richard E. 和 Felner，Ariel 2001，Disjoint Pattern Database Heuristics，人工智能 2002 年 1 月)。

描述该技术的论文指出，每个条目都包括一个修改版拼图的唯一状态和一个短整数启发式，用一个字节或更少的字节存储在数据库中。

这引出了我的问题:如何将 8 个数字的每个唯一排列存储在 16 个可能的位置，并将一个短整数全部存储在一个字节中？还是我走错了路，应该存储不同的东西？

提前致谢!

Answer 1

这篇文章不是很明确，但技术相当清楚。这两个不相交的数据库由所有 7 个和 8 个图 block (分别)与一个小整数相关联的位置组成。由于所有位置都已存储，因此不必在数据库中实际存储 key 。能够计算出所有键域中特定键的索引就足够了。那么“数据库”只是一个小整数向量，其大小是可能键的总数(分别为 16!/9! 和 16!/8!)。 key 根本不存储，因为它是隐式的。

存储在数据库中的值将始终适合一个字节(显然)，但在论文的后面有一个关于减少数据最大幅度的方法的建议。例如，如果您可以将最大值减少到 15，则可以将两个条目存储在一个字节中，从而将数据库的大小减少 2 倍。

这是一个相当快速的算法，用于为 [0, n) 中的 k 个值子集的给定排列生成唯一索引。它生成的索引不是基于排列的字典顺序，而是基于使用 Fisher-Yates shuffle 生成的排列。算法。

FY shuffle 对其输入向量产生均匀分布的随机排列；可以对其进行修改，以通过简单地在 k 步后停止混洗并将输出截断为 k 个元素来生成其输入向量的 k 子集的均匀分布的随机排列。 (提前停止洗牌“只是”一种优化。)

FY shuffle 需要一系列随机数:rnd(n), rnd(n-1), ..., rnd(1)，其中rnd(x) 产生一个在 (0, x] 范围内均匀分布的随机数。每个不同的序列产生一个不同的排列，因此可以通过枚举可能的序列来枚举排列。给定的序列可以使用 factorial base system 映射到一个唯一的整数。

同样，我们通过截断为长度为 k 的数字来枚举长度为 k 的排列；我们不使用 n 个权重 n!, (n-1)!, ..., 1!，而是使用第一个 k 权重 n! ... (n-k+1)!，通过将每个权重除以 (n - k + 1 )!。实际上，不需要除法，因为数字是使用 Horner's method 计算的, 则 d₀, d₁, ..., d_k-1 对应的索引计算为:

(…((d<sub>0</sub>*n + d<sub>1</sub>)*(n-1) + d<sub>2</sub>)*(n-2) + …) + d<sub>k-1</sub>

要从排列中推导出索引，我们需要通过观察排列中每个值的结束位置来推导出 FY 算法的序列。下面的代码基于从左到右的 FY，这与链接的维基百科文章中的算法相反。 (从左到右使截断结果更容易。)因此生成随机排列的算法将是:

Shuffle(n, k):
  Create Vec[n] with initial values 0,1,...,n-1
  for i from 0 to k-1:
    generate random j in the range [i, n-1]
    swap Vec[i], Vec[j]
  Result is the first k elements of Vec.

该算法的重要特征是第 i 步肯定会产生 Vec[i] 的最终值；后续步骤不会改变 Vec[i]。因此，为了反转算法，我们可以通过找到 Vec[i] 的值在上一步中的位置来推导出第 i 步中 j 的值。如果我们还跟踪每个值的位置，这很容易做到。

这是 C99 中的实际代码，可能比上面的解释更容易理解:

// Input: v is an array of k unique elements, each in the
//        range [0, n)
// Output: The index of v in the set of all possible such vectors.
int permindex(int n, int k, int* v) {
  int val[n], pos[n];
  // This initialization would probably have been better as
  //   for (int i = 0; i < n; ++i) val[i] = pos[i] = i;
  // The "optimization" below is intended to show that this
  // entire operation is O(k) rather than O(n); it involves
  // only initializing elements in the val and pos arrays which 
  // we might actually reference.
  for (int i = 0; i < k; ++i) {
    val[i] = i;
    pos[v[i]] = v[i];
  }
  int index = 0;
  for (int i = 0; i < k; ++i) {
    int loc = pos[v[i]]; 
    index *= n - i;
    index += loc - i;
    pos[val[i]] = loc;
    val[loc] = val[i];
  }
  return index;
}