prune algorithm

定义

剪枝，就是减少搜索规模，尽早排除不可能的选项，和一定不会成为最优解的选项，形象的说就好像剪掉了搜索树的枝，所以叫做剪枝。

常见的剪枝方式

一、优化搜索顺序

在一些搜索问题中，搜索树的各个层次，各个分支之间的顺序不是固定的，不同的搜索顺序会产生不同的搜索树形态。通俗的说就是 将所给的数据进行从小到大或者从大到小的排序，然后再进行搜索。

大部分情况下，我们应该优先搜索分支较少的结点；在没有剪枝的情况下，因为最终都会枚举完全部的点，所以是一样的；但是在有剪枝的情况下，走分支较少的点，剪枝的效果更明显；

一般而言，求解最优解会使用广度优先搜索（bfs），枚举所有方案会使用深度优先搜索（dfs）。

二、排除等效冗余

在根索过程中，如果我们能够判定从搜索树的当前节点上沿着某几条不同分支到达的子树是等效的，那么只需要对其中的一条分支执行搜索。就是当一个数据不能得到解或者最优解时，后面和它一样大的数据就不进行搜索。

简单来说，如果不考虑顺序，那么优先考虑组合，而不要考虑排列；即不要搜索重复状态；

重复性剪枝

比如现在有<1,2>和<2,1>，不考虑顺序的话，枚举一个就够了；这时就可以使用重复性剪枝，我们规定选出来的数的位置是递增的，在搜索的时候，用一个参数来记录上一次选取的数的位置，那么此次选择我们从这个数之后开始选取，这样最后选出来的方案就不会重复了。

当然，搜索的效率也要比直接二进制枚举更高。

void dfs(int s,int cnt,int pos) {
	...
	...
	for (int i=pos;i<n;i++) {
        if (!xuan[i]){
            xuan[i]=true;
            dfs(s +a[i]，cnt +1，i+1);//1表示从上一次选取的位置后面开始选xuan[i] = false;
        }
    }
}

三、可行性剪枝

在搜索过程中，及时对当前状态进行检查，如果发现分支已经无法到达递归边界，就执行回溯。这就好比我们在道路上行走时，远远看到前方是一个死胡同，就应该立即折返绕路，而不是走到路的尽头再返回。某些题目条件的范围限制是一个区间，此时可行性剪枝也被称为“上下界剪枝”。

在搜索的时候，发现搜到一半不合法了，就可以提前退出了；

奇偶性剪枝

除此之外，还有一类经典可行性剪枝叫做奇偶性剪枝。这个和离散数学思想类似，可以将n x m 的网格染成黑白两色。我们记每个格子的行数和列数之和为x，如果x为偶数，那么格子就是白色,反之奇数时为黑色。容易发现相邻的两个格子的颜色肯定不一样，也就是说每走一步颜色都会不一样。更普遍的结论是:走奇数步会改变颜色，走偶数步颜色不变。

那么如果起点和终点的颜色一样，而T是奇数的话，就不可能逃离迷宫。同理，如果起点和终点的颜色不一样，而T是偶数的话，也不能逃离迷宫。遇到这两种情况时，就不用进行 DFS 了，直接输出“NO”。

四、最优性剪枝

在最优化问题的搜索过程中，如果当前花费的代价已经超过了当前搜到的最优解，那么无论采取多么优秀的策略到达递归边界，都不可能更新答案。此时可以停止对当前分支的搜索，执行回溯。

比如我们要求一个最小值，发现当前搜到的值已经大于等于最优解了，就可以提前退出了；

五、记忆化搜索（DP）

可以记录每个状态的搜索结果，在重复遍历一个状态时直接检索并返回。我们对图进行深度优先遍历时，标记每个节点是否已经被访问过。

一般这种跟DP归在一起，主要还是由上面四种手段来剪枝；

模板题

图的遍历

题目描述

给出 $N$ 个点，$M$ 条边的有向图，对于每个点 $v$，求 $A(v)$ 表示从点 $v$ 出发，能到达的编号最大的点。

输入格式

第 $1$ 行 $2$ 个整数 $N,M$，表示点数和边数。

接下来 $M$ 行，每行 $2$ 个整数 $U_i,V_i$，表示边 $(U_i,V_i)$。点用 $1,2,\dots,N$ 编号。

输出格式

一行 $N$ 个整数 $A(1),A(2),\dots,A(N)$。

样例 #1

样例输入 #1

样例输出 #1

4 4 3 4

提示

对于 $60%$ 的数据，$1 \leq N,M \leq 10^3$。
对于 $100%$ 的数据，$1 \leq N,M \leq 10^5$。

AC代码

这题是典型的DFS剪枝，通过对已经访问过的点进行标记以防止重复访问，很好的提高了访问效率。

#include <bits/stdc++.h>
using namespace std;
#define M 100007
#define N 1007
#define INF 0x3f3f3f3f
#define ll long long
#define db double
vector<int> g[M];
int v[M];
int n, m;
void search(int root, int& max) {
    if (v[root]) {
        return;
    }
    v[root] = max;
    for (vector<int>::iterator i = g[root].begin(); i != g[root].end(); i++) {
        search(*i, max);
    }
}
int main() {
    int x, y;
    ios::sync_with_stdio(false);
    cout.tie(NULL);
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> x >> y;
        g[y].push_back(x);
    }
    for (int i = n; i >= 1; i--) {
        search(i, i);
    }
    for (int i = 1; i <= n; i++)
        cout << v[i] << " ";
    return 0;
}

Charles's Castle

prune-algorithm