状态

状态是求解过程中的一步。确定状态是什么，如何表示，如何标记，是状态空间搜索中的一环。

首先确定状态是什么，这就需要具体问题具体分析。如何表示状态？状态一般是排列或组合比，如，迷宫最短路中当前所在点 (r, c) 是组合，八数码问题的盘面是排列。状态存储使用数组，以集合 {1, 2, 3, 4} 例，排列 {1, 2, 4, 3} 数组就是 [1, 2, 4, 3]，组合 {1, 3, 4} 数组就是 [1, 0, 1, 1]。

其次如何标记，如果 N 元组 N 个坐标组成的空间较小，直接在空间里标记即可，比如二维迷宫最短路，坐标 (r, c) 直接使用 d[r][c] 标记。但是如果个数较多，或是值较大，状态又没有充满整个空间，就会浪费很多存储空间，因此给状态编号，所需的存储空间就是状态总数，开一个不少于状态总数的一维数组即可。

给状态编号就是编码，还原就是解码。

排列（不放回有序抽样）

排列即从备选集合中顺序有关地挑选元素，不可再次挑选，N 元素排列总数为 N!。

如何编码？首先找找规律吧。

排列 编码 数码 (6, 2, 1, 1)
1234 0 0 0 0 0
1243 1 0 0 1 0
1324 2 0 1 0 0
1342 3 0 1 1 0
1423 4 0 2 0 0
1432 5 0 2 1 0
2134 6 1 0 0 0
2143 7 1 0 1 0
2314 8 1 1 0 0
2341 9 1 1 1 0
2413 10 1 2 0 0
2431 11 1 2 1 0
3124 12 2 0 0 0
3142 13 2 0 1 0
3214 14 2 1 0 0
3241 15 2 1 1 0
3412 16 2 2 0 0
3421 17 2 2 1 0
4123 18 3 0 0 0
4132 19 3 0 1 0
4213 20 3 1 0 0
4231 21 3 1 1 0
4312 22 3 2 0 0
4321 23 3 2 1 0

合理猜测，数码代表逆序数，第 n 位权重是 n! 即 n 阶乘，因此编码是逆序数乘权重，解码是将编码解析得到逆序数，再用逆序数取数。

编码

数组 fact 存储阶乘，事先计算好，因为阶乘增长很快，数组不会很大。接下来对每一位求逆序数，逆序数乘权重，加和到编码中。

int encode_permutation(int k)
{
  int code = 0;
  for (int i = 0; i < k; i++) {
    int cnt = 0;
    for (int j = i+1; j < k; j++) if (P[i] > P[j]) cnt++;
    code += (cnt * fact[k-i-1]);
  }
  return code;
}

解码

解码需要安置一个元素后将它从备选集合中去除，所以比较麻烦。首先，除权重得到每一位的逆序数，逆序数就是在备选集合中的顺位，循环计数到该元素后退出，取元素标记已挑选。数组 v 记录备选集合元素是否已被挑选，c 用于计数。

void decode_permutation(int k, int code, int *a)
{
  int v[MAXN];
  memset(v, 0, sizeof(v));
  for (int i = 0; i < k; i++) {
    int cnt = code / fact[k-i-1];

    // select
    int j = 0, c = 0;
    for (j = 0; j < k; j++) {
      if (v[j] == 0) {
        if (cnt == c) break;
        else c++;
      }
    }
    v[j] = 1;
    a[i] = S[j];

    code = code % fact[k-i-1];
  }
}

组合（不放回无序抽样）

组合即从备选集合顺序无关地挑选元素，不可再次挑选，N 元素的组合总数为 2^N。

组合就是子集，可用位矢量法和二进制法表示。位矢量法就是将元素选中标志存储于一个数组中，一般 1 选中 0 不选中。以集合 s = {1, 2, 3, 4} 为例，子集 sub = {1, 3, 4} 可表示为 [1, 0, 1, 1]。那么既然元素只有选中、不选中两种，那么二进制足够表示，前例用二进制法表示就是 1011 == 13（低位在前，不过反着来也没问题）。不难看出，位矢量表示就是状态本身，二进制表示就是状态编号。

编码

二进制表示是编码，位矢量表示转化为编码需按照一定顺序（从低到高或从高到低都行）依次放入 code 二进制位中。C[i] 代表第 i 位的二进制位即选中标志，用 C[i] << i 移至第 i 位，或运算合并到 code 中。

int encode_combination(int n)
{
  int code = 0;
  for (int i = 0; i < n; i++) {
    code = code | (C[i] << i);
  }

  return code;
}

解码

同理，位矢量表示是状态，二进制表示转化为状态就是将二进制位依次取出存入数组。

void decode_combination(int n, int code, int *a)
{
  for (int i = 0; i < n; i++) {
    a[i] = code&1;
    code = code >> 1;
  }
}

允许重复排列（放回有序抽样）

允许重复排列即从备选集合顺序有关地挑选元素但是可再次挑选，由于可以重复，选择元素个数可以不定，总数与选择元素个数有关，N 选 K 允许重复排列总数为 N^K。不难看出，N 选 K 则是 K 位 N 进制，编码、解码就是进制转化。

允许重复组合（放回无序抽样）

允许重复组合即从备选集合顺序无关地挑选元素但是可再次挑选，同理总数与选择元素个数有关，N 选 K 允许重复组合总数为 K^N。状态用位矢量法表示，只不过原先的选中标志变为选中数目。而二进制显然不够，因此使用 K 进制。

问题

八数码问题

盘面是状态，它是 9 位数的排列，通过编码、解码标记状态就不用开 9 维数组了。

Travelling by Stagecoach (POJ 2686)

状态压缩，车票是一个集合（组合），将集合编码为整数，也就是集合的二进制表示，如此一来集合就可以作为数组下标使用。

参考

  • 《离散数学及其应用》罗森 著：四种计数问题
  • 《算法竞赛入门经典（第 2 版）》刘汝佳 著：编码解码排列，问题来源
  • 《概率（第一卷）》施利亚耶夫 著：四种抽样，能和计数问题对应
  • 《挑战程序设计竞赛（第 2 版）》秋叶拓哉 岩田阳一 北川宜稔 著：问题来源