枚举搜索 | 少年宫NOIP竞赛班维基

简介

枚举和搜索是求解问题时最基础最重要的手段，在实际的应用和算法竞赛中，枚举和搜索无处不在。算法竞赛中的许多问题常常涉及到求解最优的方案或者统计方案，这类问题多数都能使用搜索或者枚举进行求解，当然很多问题由于效率上的要求设计出了更加巧妙的算法。熟练掌握搜索枚举之后，能够简化许多问题的求解，能够更容易进行程序的对拍检验，枚举搜索也是许多算法的基础，掌握好枚举和搜索能够辅助许多重要算法的学习。

枚举和搜索就类似于dp中的递推和记忆化搜索，是同一思路的不同展现形式。枚举通常来说更简短，可是思考时难度更大，需要考虑更为周全。搜索代码一般更长一些，但求解一些问题时有独到之处，也更容易编码。

状态

枚举搜索的核心是当前的状态。状态由当前维护的关键数据所决定，包括了保存的外部数据，以及当前搜索函数的参数或者枚举时的迭代变量。外部数据主要包括了诸如某元素是否访问，当前枚举的序列，维护的标记之类的，搜索时这类比较大的数据不太适合当做参数传递。

设计出来的状态决定了你需要维护哪些数据，有了状态之后还需要设计状态之间的关系，也就是枚举和搜索的策略。数据和策略决定了枚举搜索算法的运行方式，性能和正确性，需要谨慎考虑。搜索时相对容易进行一些提前结束的剪枝，如果枚举时效率不够可以考虑使用搜索。

全排列

全排列问题就是按升序输出一个序列的所有排列组合。许多问题中虽然不需要你输出排列组合，但会需要你考虑所有排列组合的情况。对于排列组合，标准库中有一系列好用的函数，最常用的是 next_permutation，若没有下一个排列就会返回 False 否则就会将传入的区间转换成下一个排列，效率是线性的，输出全排列可以使用如下代码：

do {
  for (int i = 0; i < n; i++)
    printf("%d%c", a[i], i==n-1 ? '\n' : ' ');
} while (next_permutation(a, a + n));

使用搜索也能够完成全排列的输出，只是代码会更长。程序需要保存当前构建的元素序列 a 以及某个元素是否被访问过的标记数组 vis。程序中变量 d 是当前的深度，从$0$开始，当到达$n$的时候就已经安排好所有$n$个元素了，此时输出。搜索函数的意义实际是枚举所有未访问元素的全排列，递归时从小到大枚举没有被访问过的元素然后进入下一层，这里其实就是插入一个元素更新标记后，构建剩余没有访问过的元素的从小到大的全排列。由于每次枚举从小到大，先会枚举第一个元素最小的，最终输出的序列就会按照字典序的升序。注意所有外部数组当中的元素在更新之后要进行恢复。

vector<int> a;
bool vis[N];
void dfs(int d) {
  if (d == n) {
    for (int i = 0; i < n; i++) {
      printf("%d%c", a[i] + 1, i==n-1 ? '\n' : ' ');
    }
  }
  for (int i = 0; i < n; i++) {
    if (!vis[i]) {
      vis[i] = true;
      a.push_back(i);
      dfs(d + 1);
      vis[i] = false;
      a.pop_back();
    }
  }
}
use dfs(0) to output.

如果不使用 vector 使用数组，就没有必要重置值了，因为当前 a[0..d-1] 的内容一定都是最新的，代码如下：

int a[N];
bool vis[N];
void dfs(int d) {
  if (d == n) {
    for (int i = 0; i < n; i++) {
      printf("%d%c", a[i] + 1, i==n-1 ? '\n' : ' ');
    }
    return;
  }
  for (int i = 0; i < n; i++) {
    if (!vis[i]) {
      vis[i] = true;
      a[d] = i;
      dfs(d + 1);
      vis[i] = false;
    }
  }
}

注意这种利用搜索枚举全排列的方式只适用于元素不重复的情况，当列表中有元素重复的时候，就会出现构建重复序列的情况。此时我们又只能使用标准库函数了，这里介绍一下如何求一个序列的下一个排列。需要找到最长的非递增后缀，可以发现这个后缀的任何排列组合都会比这个后缀字典序小，改动是没有效果的。最长的非递增后缀前一个位置 $p$ 是一个重要的位置，因为根据定义这个位置比后一个元素小然后元素依次非递增，一定可以通过上升 $p$ 的元素构建字典序更大的序列。将后面所有的元素反转（排成正序），找到后面元素中大于 $p$ 位置最小的元素交换两者即可，此处也可以先交换再反转。代码如下：

bool next_p(vector<int> &v) {
  int p = v.size() - 2;
  while (p >= 0 && v[p] >= v[p+1]) p--;
  if (p <= -1) return false;
  reverse(v.begin() + p + 1, v.end());
  swap(v[p], *upper_bound(v.begin() + p + 1, v.end(), v[p]));
  return true;
}

所有子集

枚举一个集合所有的子集是一个常见的需求。比如对于背包问题，如果不知道动态规划的解法，一个非常稳妥的做法就是枚举物品集合的所有子集，分别看是否符合背包容量限制，然后进行更新。为了方便起见，通常的策略是使用一个整数压缩状态，如果有 $n$ 个物品就枚举 $[0,2^n)$ 的每个数字，第 $i$ 位是$0$ 就表示不取第 $i$ 个物品，第 $i$ 位是$1$ 就表示取第 $i$ 个物品。具体实现如下：

int tot = 1 << n;
int ans = 0;
for (int i = 0; i < tot; i++) {
  int sum_w = 0, sum_v = 0;
  for (int j = 0; j < n; j++) {
    if (i >> j & 1) {
      sum_v += v[j];
      sum_w += w[j];
    }
  }
  if (sum_w >= W) ans = max(ans, sum_v);
}

除了二进制枚举以外也可以直接搜索，分两种情况当前取然后枚举之后元素的子集，以及当前不取枚举之后元素的子集，容易发现这样就覆盖了所有的情况。使用搜索看上去会比枚举麻烦一些，可是在搜索的过程中，可以利用一些条件来进行剪枝，降低实际运行时的复杂度，一个简单的策略是当当前物品的重量超过背包限制时就停止搜索，其他还有很多优化手段，比如分支定界法，这里给出一个相对简单的搜索剪枝实现：

void dfs(int d, int sum_w) {
  if (sum_w > W) return;
  if (d == n) {
    int sum_v = 0;
    for (int j = 0; j < n; j++) {
      if (a[j]) sum_v += v[j];
    }
    if (sum_w >= W) ans = max(ans, sum_v);
  } else {
    a[d] = true;
    dfs(d + 1, sum_w + w[d]);
    a[d] = false;
    dfs(d + 1, sum_w);
  }
}

所有大小为k的子集

题意可以参照：https://vjudge.net/problem/HRBUST-2179

有时会需要枚举所有大小为 $k$ 的子集，这时候并没有直接的标准库函数可以使用，一种取巧的方式是利用 next_permutation 函数来做。其中 $k$ 元素为 $1$ 剩余 $n-k$个元素为 $0$ 然后求数组的全排列，如果第 $i$ 个数为 $1$ 就输出这个数字，具体代码如下：

vector<int> a;
for (int i = 0; i < k; i++) a.push_back(0);
for (int i = 0; i < n - k; i++) a.push_back(1);
do {
  int rem = k;
  for (int i = 0; i < n; i++) {
    if (!a[i]) printf("%d%c", i + 1, --rem == 0 ? '\n' : ' ');
  }
} while (next_permutation(a.begin(), a.end()));

如果使用搜索，需要升序枚举所有 $k$ 个元素，可以多加一个变量维护集合中的最大元素或者说从哪里开始枚举一下一个元素。于是从起点开始枚举，最终构建完成所有 $k$ 个元素就要输出，已经考虑完所有 $n$ 个元素就要返回。边界上需要仔细注意，如果传参传入的是当前位置，调用时从那个位置加一开始，那么传参的时候就要传入 $-1$，要保持一致性，如果传入当前位置加一就没有问题了，直接传入 $0$ 即可。代码如下：

void dfs(int d, int x) {
  if (d == k) {
    for (int i = 0; i < k; i++) {
      printf("%d%c", a[i] + 1, i==k-1 ? '\n' : ' ');
    }
    return;
  }
  if (x == n) return;
  for (int i = x; i < n; i++) {
    a[d] = i;
    dfs(d + 1, i + 1);
  }
}

简介

状态

全排列

所有子集

所有大小为k的子集

推荐习题