一、枚举排列

1. 定义

枚举出一个序列a[maxn]的所有排列。

2. 解析

枚举排列 最简单的方法是运用STL的 next_permutation函数.

3. 模板

int a[maxn];

int main(){
        ......
    sort(a, a + n);
    do{
        for(int i = 0; i < n; i ++) cout << a[i] << " ";  // 打印排列
        cout << endl;
    } while(next_permutation(a, a + n));
}

二、枚举集合

1. 定义

枚举出一个序列a[maxn]的所有子集。

2. 解析

枚举子集 最简单的方法是 二进制法。

  • 设A、B为两个集合的二进制表示，则

    • 交集表示为 A & B
    • 并集表示为 A | B
    • 对称差集表示为 A ^ B
    • 补集表示为 ALL ^ A [其中 ALL = (1 << n) - 1]

  • [枚举所有子集]：
    枚举 0 到 (1 << n) - 1 中的每个数字 i，然后将数字 i 转化为二进制，
    如果 i 的第 j 位是 1，表示集合 i 包含 a[j]；
    如果 i 的第 j 位是 0，表示集合 i 不包含 a[j]。

3. 变式

  1. [枚举大小为k的所有子集]
    从 i = (1 << k) - 1 开始枚举，每次找比它大的下一个包含k个1的二进制数，方法如下：

    • 令 x = lowbit(i)，表示当前 i 的靠右的 1 的权值
    • 令 y = i + x，即让 y 等于 i 的最低 “1” 发生进位后的数字，此时必然有 y 中 1 的个数小于等于k
    • 通过 (i & -y) 得到由于进位而导致的所有从 1 变成 0 的位，然后将其除以 x 来去掉右边的所有 0 , 然后再继续右移 1 位来去掉一个 1 (因为进位后在左侧会有一个 0 变成 1) 。这样得到的数再 和 y 或一下，就可以得到下一个包含 k 个 1 的数字。 总结起来就是 i = ((i & -y) / x) >> 1 | y。

  2. [枚举一个给定集合 x 的所有子集]
    从 全集 i = x 开始，从大到小枚举子集，方法如下：

    • i = (i - 1) & x. 即通过减1来缩小子集，通过&x来限定在x的子集中。

  3. [枚举一个给定集合 x 的所有超集]
    从 最小集 i = x 开始，从小到大枚举超集，方法如下：

    • i = (i + 1) | x. 即通过+1来扩大集合，通过|x来限定生成的集合必定包含x。

4. 模板

  • 打印数字 i 代表的集合 
int n, a[maxn];  // 长度为 n 的序列

void print_subset(int s){  // 打印 s 所表示的子集
    for(int i = 0; i < n; i ++){
        if(s & (1 << i)) cout << a[i] << " ";
    }
    cout << endl;
}
  • 枚举所有子集 
void solve() {
    for(int i = 0; i < (1 << n); i ++) {
        print_subset(i);  // 用二进制数字i表示一个子集
    }
}
  • 枚举所有大小为 k 的子集 
void solve(int k) {
    for(int i = (1 << k) - 1; i < (1 << n);) {
        print_subset(i);
        int x = i & -i, y = i + x;
        i = (((i & ~y) / x ) >> 1) | y;
    }
}
  • [枚举一个给定集合 x 的所有子集] 
void solve(int x) {
    for (int i = x; i >= 0; i = (i - 1) & x) {
        print_subset(i);
    }
}
  • [枚举一个给定集合 x 的所有超集] 
void solve(int x) {
    for (int i = x; i < (1 << n); i = (i + 1) | x) {
        print_subset(i);
    }
}

三、回溯法

1. 定义

即利用递归的回溯过程，来进行状态的“还原”，从而枚举出所有的情形。

2. 解析

紫薯告诉我们，回溯法总是比生成-测试法快得多。

  • 需要一个递归深度值 idx（或一个坐标x, y）表示当前递归进度
  • 需要一个值 cur 表示根据当前选择所形成的值（如和值等）。
  • 需要一个 vis 数组标记已经递归过的位置（在回溯时还原）

3. 模板

int n, vis[maxn];

void solve(int idx, int cur) {
    if(idx == n - 1) {  // 递归出口
        // 根据 cur 更新 ans
        return;
    }
    for(int i = 1; i <= n; i ++) if(!vis[i] && 其它条件) {
        vis[i] = 1;
        solve(idx + 1, cur + i);  // 递归
        vis[i] = 0;  // 还原
    }
}

int main() {
    ......
    vis[1] = 1;
    solve(0, 1);
    ......
}

4. 例题

Uva-524：https://blog.nowcoder.net/n/2a2e5ff2a5b6479dacca40edafe57b25
Uva-167 (八皇后)：https://blog.nowcoder.net/n/2762e03342d740f3aa4bb69b8f9c8775

四、迭代加深搜索（IDA*）

1. 定义

一种通过多次dfs找解的算法。
从小到大枚举dfs深度上限maxd，每次执行只考虑不超过maxd的节点。
IDA* 能进行关于深度的剪枝，从而提高效率。
一般回溯法可以解决的问题，但是 回溯时枚举边界无法确定时，可以使用IDA*算法。

2. 解析

  • 枚举深搜的最大深度maxd，然后在maxd的限制下去进行dfs，并利用maxd来对dfs进行剪枝，使得dfs的每一层可以很快枚举完。
  • 每次针对一个maxd进行dfs时，实际上就是相当于反复去解答这道题，因此也要重新初始化。
  • 由于需要由maxd限制递归层数，因此dfs函数的参数必须包括一个idx表示当前递归的层数。
    剩下的参数就按照需要进行增添。
  • 优化技巧（IDA* 的精髓）：
    1、考虑最优性剪枝，即通过maxd可以判断出该次迭代已经不可能得到答案时要及时退出；
    2、考虑节点的搜索顺序，以加快搜索到目标节点。

3. 模板

bool dfs(int maxd, int idx, ......) {
    if(idx == maxd) {  // 达到当前枚举的最大深度maxd就处理完后退出
        if(不满足条件) return 0;
        else {
            ...... // 记录答案
            return 1;
        }
    }
    if(通过maxd可以判断出该次迭代已经不可能得到答案) return 0;  // 精髓：最优性剪枝
    for(正常的dfs枚举) {
        if(不满足条件) continue;
        if(dfs(maxd, idx + 1, ......)) return 1;
    }
    return 0;
}

int main() {
    ......
    for(int maxd = 1; ; maxd ++) {
        memset(ans, -1, sizeof(ans));  // 每次 dfs 需要重新初始化
        if(dfs(maxd, 0, ....)) break;  // 找到解就退出
    }
    ......

4. 例题

Uva-12558：https://blog.nowcoder.net/n/6aeaadbaf50347a7979571da59dce6b3
Uva-1343（题目链接）：https://vjudge.net/problem/UVA-1343

全原创