搜索优化——实用的暴力，玄学的复杂度

本文主要通过例题讲述搜索的几种优化方式，包括 DFS 的迭代加深，IDAstar，BFS 的优先队列优化，双向 BFS 以及 Astar。 # 一、广度优先搜索 ## 1.1 双端队列 BFS 例题1 求第 $k+1$ 长边最短路。[题目链接](https://www.luogu.com.cn/problem/U152222) 由于边权 $w\le 10^6$，可以二分得到第 $k+1$ 长边的最短可能长度。因此，本题转换成了求第 $k+1$ 长边长度为 $len$ 的可能性。时间复杂度要求 $O(n\log w)$，因此需要在线性复杂度内判断可行性。 判断时，将所有边权 $>len$ 的边权值设为 $1$，$\le len$ 的边权值设为 $0$，则 $s\to t$ 的最短路若不超过 $k$，则代表只有不超过 $k$ 条比其长的边，因此其可能成为 $k+1$ 长边。 在迭代时，使用双端队列储存所有遍历到的结点，若权值为 $1$ 则从队尾入队，否则从队首入队，每次取队首进行扩展，即可得到 01 权图的最短路。 ```cpp bool vis[maxn]; int dis[maxn],n,m,k,s,t; vector<int> e[maxn],w[maxn];//模拟邻接表 bool check(ll len){ fill(dis,dis+n+10,inf); memset(vis,0,sizeof(vis));//初始化 deque<int> q;//双端队列 dis[s]=0;q.push_back(s); while(!q.empty()){ ll u=q.front();q.pop_front(); if(u==t) return dis[t]<=k;//到达汇点则返回可行性 if(vis[u]) continue; vis[u]=1; for(ll i=0;i<e[u].size();i++){ ll v=e[u][i]; if(!vis[v]){ ll c=(w[u][i]>len);//将边权转化为 01 if(dis[v]<=dis[u]+c) continue; dis[v]=dis[u]+c; if(c) q.push_back(v); else q.push_front(v);//根据边权从队首或队尾入队 } } } return 0; } ll Binary(ll l,ll r){//二分答案 ll ans=inf; while(l<=r){ ll mid=(l+r)>>1; if(check(mid)) ans=mid,r=mid-1; else l=mid+1; } return ans; } ``` ## 1.2 优先队列 BFS 对于每次扩展的代价不同时，采用优先队列（堆）优化迭代。每次取出当前代价最小的状态进行扩展，将新状态加入优先队列，反复迭代直至队列为空。 每个状态第一次被取出时，即为其最小代价，因此每个状态只扩展一次，复杂度为 $O((n+m)\log n)$，经典算法形如 Dijkstra。 例题：POJ 3635 >有 $n$ 个城市和 $m$ 条道路构成无向图，每个城市有一个加油站，价格不同。每条道路的油耗即为其权值，求多询问，对于容量为 $C$ 的车，$s\to t$ 最少花多少钱。 使用拆点的思想，将每个点拆成 $C$ 个数对 $(id,fuel)$，表示 （编号，剩余油量），且 $dis[id][fuel]$ 表示最少花费。 对于每次询问进行优先队列 BFS（即 Dijkstra），起始状态为 $(s,0)$，每个状态课扩展出： 1. 若 $fuel<C$ 可以加 $1$ 升油，花费为 $price_{id}$。 2. 若边权 $w(id,v)\le fuel$，则可以扩展到 $(v,fuel-w)$。 不断取出花费最少的状态进行扩展，直到 $t$ 被取出即可。复杂度 $O((nC+m)\log nC)$。 ```cpp int n,m,price[maxn]; int tot,ver[M],head[maxn],wth[M],nxt[M]; inline void add(int u,int v,int w){ ver[++tot]=v;wth[tot]=w;nxt[tot]=head[u];head[u]=tot; ver[++tot]=u;wth[tot]=w;nxt[tot]=head[v];head[v]=tot; } struct node{ int d,u,c; bool operator <(const node &x)const{ return d>x.d; } }; int dist[maxn][C]; bool vis[maxn][C]; inline int dijkstra(int s,int t,int cap){ memset(dist,0x3f,sizeof(dist)); priority_queue<node> q; memset(vis,0,sizeof(vis)); q.push({0,s,0}); while(!q.empty()){ node x=q.top();q.pop(); if(x.u==t) return x.d; if(vis[x.u][x.c]==1) continue; vis[x.u][x.c]=1; if(x.c<cap){ if(dist[x.u][x.c+1]>x.d+price[x.u]){ dist[x.u][x.c+1]=x.d+price[x.u]; q.push({dist[x.u][x.c+1],x.u,x.c+1}); } } for(int i=head[x.u];~i;i=nxt[i]){ int v=ver[i]; if(x.c>=wth[i]){ if(dist[v][x.c-wth[i]]>x.d){ dist[v][x.c-wth[i]]=x.d; q.push({x.d,v,x.c-wth[i]}); } } } } return -1; } int main(){ read(n);read(m); rep(i,0,n-1) read(price[i]); memset(head,-1,sizeof(head)); rep(i,1,m){ int u,v,d; read(u);read(v);read(d); add(u,v,d); } int q; read(q); while(q--){ int cap,s,t; read(cap);read(s);read(t); int ans=dijkstra(s,t,cap); if(ans==-1)puts("impossible"); else writeln(ans); } return 0; } ``` ## 1.3 双向 BFS 有时结点数较多，逐一扩展会导致记录状态的数组维度过高，空间溢出。因此需要用双向 BFS，压缩空间。双向 BFS 的基本流程是 $s,t$ 同时扩展，遇到一个状态被 $s,t$ 均扩展过则该状态为最优状态，即答案。下面是一道例题。 [Nightmare II](http://acm.hdu.edu.cn/showproblem.php?pid=3085) >给定一张 $N×M$ 的地图，地图中有 1 个男孩，1 个女孩和 2 个鬼。 字符 `.` 表示道路，字符 `X` 表示墙，字符 `M` 表示男孩的位置，字符 `G` 表示女孩的位置，字符 `Z` 表示鬼的位置。 男孩每秒可以移动 3 个单位距离，女孩每秒可以移动 1 个单位距离，男孩和女孩只能朝上下左右四个方向移动。 每个鬼占据的区域每秒可以向四周扩张 2 个单位距离，并且无视墙的阻挡，也就是在第 $k$ 秒后所有与鬼的曼哈顿距离不超过 $2k$ 的位置都会被鬼占领。 注意：每一秒鬼会先扩展，扩展完毕后男孩和女孩才可以移动。 求在不进入鬼的占领区的前提下，男孩和女孩能否会合，若能会合，求出最短会合时间。 本题较为简单，考虑用两个队列分别记录男孩和女孩的扩展状态，每一次鬼先扩展，男孩扩展 $3$ 步，女孩再扩展。注意鬼不需要记录状态，因为在第 $k$ 秒后所有与鬼的曼哈顿距离不超过 $2k$ 的位置都会被鬼占领。 在 BFS 的过程中，判断扩展到的状态是否合法。若第一次出现某个位置使得男女都能到达，则返回答案。复杂度 $O(nm\log nm)$。 ```cpp int vis[maxn][maxn],n,m,T; char g[maxn][maxn]; #define PII pair<int,int> PII ghost[2],boy,girl; int dx[]={1,-1,0,0}, dy[]={0,0,1,-1}; inline bool check(int x,int y,int step){//判断合法性 if(x>=n||x<0||y<0||y>=m||g[x][y]=='X') return 0; rep(i,0,1){ if(abs(x-ghost[i].first)+abs(y-ghost[i].second)<=2*step) return 0; } return 1; } inline int bfs(){ int cnt_ghost=0; memset(vis,0,sizeof(vis)); queue<PII> q1,q2; rep(i,0,n-1) rep(j,0,m-1)//找出男女生和鬼的位置 if(g[i][j]=='M') boy={i,j}; else if(g[i][j]=='G') girl={i,j}; else if(g[i][j]=='Z') ghost[cnt_ghost++]={i,j}; q1.push(boy);q2.push(girl); int timer=0; while(!q1.empty()||!q2.empty()){ timer++;//鬼的扩展 rep(i,0,2){//男生扩展 for(int j=0,len=q1.size();j<len;j++){ PII t=q1.front();q1.pop(); int x=t.first,y=t.second; if(!check(x,y,timer)) continue; rep(k,0,3){ int nx=x+dx[k],ny=y+dy[k]; if(check(nx,ny,timer)){ if(vis[nx][ny]==2) return timer; else if(!vis[nx][ny]){ vis[nx][ny]=1; q1.push({nx,ny}); } } } } } for(int j=0,len=q2.size();j<len;j++){//女生扩展 PII t=q2.front();q2.pop(); int x=t.first,y=t.second; if(!check(x,y,timer)) continue; rep(k,0,3){ int nx=x+dx[k],ny=y+dy[k]; if(check(nx,ny,timer)){ if(vis[nx][ny]==1) return timer; else if(!vis[nx][ny]){ vis[nx][ny]=2; q2.push({nx,ny}); } } } } } return -1; } ``` ## 1.4 Astar Astar 也写作 $A^*$，~~但是前者打起来方便~~。 该算法的本质是加入估价函数，进行启发式搜索。对于一个状态 $st$，令从初始状态扩展到该状态已经花费 $dist(st)$，该状态扩展到目标状态的预估代价为 $f(st)$，真实代价（未知）为 $g(st)$。每次取 $dist(st)+f(st)$ 最小的状态进行扩展即可。 其要求是：对于任意状态 $st$，均有 $f(st)\le g(st)$，否则就会产生严重的错误。若 $f(st)\to 0$，则退化为普通的优先队列 BFS；若 $f(st)\to g(st)$，则成为线性算法，即直接找到最短路。所以，估价函数越接近真实值，其效率越高。 例题：[第 $k$ 短路](https://hywiki.xyz/problem/993) POJ2449 先说一下：洛谷上的模板题卡了 Astar 算法，只允许使用可持久化可并堆，否则需要套取 $1\sim 2$ 个数据点。 给出一个定理（可以自行尝试用数学归纳法证明）：对于 $\forall k\in \mathbb Z^+,u\in V$，第 $k$ 此从优先队列取出包含结点 $u$ 的二元组时，对应的值即为 $s\to u$ 的第 $k$ 短路。 有了上述结论，考虑使用 Astar 优化宽搜。 根据估价函数的原则，这里取 $t$ 到每个节点 $u$ 的最短路 $f(u)$ 作为估价函数。这样既可以保证 $f(u)\le g(u)$，又使得 $f(u)$ 顺应实际距离的变化趋势。由此可得算法的具体流程： 1. 建立反图，使用 Dijkstra 在反图上求出 $t$ 到个节点的最短路 $f(u)$。 2. 从 $s$ 开始扩展，每次从优先队列中取出 $dist(u)+f(u)$ 最小的结点进行扩展。 3. 第 $k$ 次取出 $t$ 时，即求出了答案。 在此过程中可加入优化：若某一个节点被弹出的次数已经超过 $k$ 次，则无需对其进行扩展。 该算法理论上界是 $O(k\times (n+m)\log n)$，但实际效率接近 $\Theta((n+m)\log n)$。 ```cpp //#include<bits/stdc++.h> #include<iostream> #include<cstdio> #include<cstring> #include<vector> #include<queue> using namespace std; #define rep(ii,aa,bb) for(re int ii = aa; ii <= bb; ii++) #define Rep(ii,aa,bb) for(re int ii = aa; ii >= bb; ii--) typedef long long ll; typedef unsigned long long ull; const int maxn = 1e3+5; namespace IO_ReadWrite { #define re register #define gg (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1<<21, stdin), p1 == p2) ? EOF :*p1++) char buf[1<<21], *p1 = buf, *p2 = buf; template <typename T> inline void read(T &x){ x = 0; re T f=1; re char c = gg; while(c > 57 || c < 48){if(c == '-') f = -1;c = gg;} while(c >= 48 &&c <= 57){x = (x<<1) + (x<<3) + (c^48);c = gg;} x *= f;return; } inline void ReadChar(char &c){ c = gg; while(!isalpha(c)) c = gg; } template <typename T> inline void write(T x){ if(x < 0) putchar('-'), x = -x; if(x > 9) write(x/10); putchar('0' + x % 10); } template <typename T> inline void writeln(T x){write(x); putchar('\n');} } using namespace IO_ReadWrite; int n,m,s,t,k,f[maxn],cnt[maxn]; bool vis[maxn]; vector<pair<int,int> > e[maxn],fe[maxn]; priority_queue<pair<int,int> > q; inline void dijkstra(){ memset(f,0x3f,sizeof(f)); memset(vis,0,sizeof(vis)); f[t]=0; q.push(make_pair(0,t)); while(!q.empty()){ int u=q.top().second; q.pop(); if(vis[u]) continue; vis[u]=1; for(unsigned int i=0;i<fe[u].size();i++){ int v=fe[u][i].first,w=fe[u][i].second; if(f[v]>f[u]+w){ f[v]=f[u]+w; q.push(make_pair(-f[v],v)); } } } } inline void bfs(){ if(s==t) k++; q.push(make_pair(-f[s],s)); memset(cnt,0,sizeof(cnt)); while(!q.empty()){ int u=q.top().second; int dist=-q.top().first-f[u]; q.pop(); cnt[u]++; if(cnt[t]==k){ writeln(dist); return; } for(unsigned int i=0;i<e[u].size();i++){ int v=e[u][i].first,w=e[u][i].second; if(cnt[v]!=k) q.push(make_pair(-f[v]-dist-w,v)); } } writeln(-1); } int main(){ read(n);read(m); rep(i,1,m){ int u,v,w; read(u);read(v);read(w); e[u].push_back(make_pair(v,w)); fe[v].push_back(make_pair(u,w)); } read(s);read(t);read(k); dijkstra();bfs(); // } return 0; } ``` # 二、深度优先搜索 ## 2.1 剪枝 剪枝是优化 DFS 的方法之一，是基本但重要的方法，通常有一定难度。下面介绍几类常见的剪枝 1. 优化搜索顺序（启发式加速） 2. 排除等效冗余（等效性剪枝） 3. 可行性剪枝 4. 最优性剪枝 5. 记忆化搜索（树形 DP） 具体例题有许多的经典题，如“小木棒”，“生日蛋糕”等等，此处就不赘述，下面给出一道不一样的例题： >有 $m$ 个背包，容量为 $c_i$，$n$ 个物品，每个物品重量为 $w_i$，价值为 $1$，求使用这些背包装下物品的最大价值。 由于价值为 $1$，最大价值即为物品数，很容易想到二分枚举物品数量，因此难点在于如何判断二分的答案是否可行。 考虑使用 DFS，但爆搜明显超时，因此进行优化。 1. 优化搜索顺序：由于每件物品价值均为 $1$，因此考虑将所有物品按重量 $w_i$ 从小到大排序。同时，为了防止出现小物品堵塞大背包导致无解的现象，将背包按 $c_i$ 从小到大排序。 2. 可行性剪枝：令 $sC=\Sigma c_i$，$sW_k=\sum\limits_{i=1}^k w_i$。若二分到 $k$ 件物品时出现 $sW_k>sC$ 则直接无解。 3. 等效性剪枝：本题的等效性剪枝有两点，详见下方图片。因此，对于两个重量相等的物品，规定后者只能放在前者所在背包的同一个或右侧；规定对于两个剩余容量相同的背包，物品放在前者。   ```cpp #include<bits/stdc++.h> using namespace std; #define rep(ii,aa,bb) for(re int ii = aa; ii <= bb; ii++) #define Rep(ii,aa,bb) for(re int ii = aa; ii >= bb; ii--) typedef long long ll; typedef unsigned long long ull; const int maxn = 2e3+5; namespace IO_ReadWrite { #define re register #define gg (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1<<21, stdin), p1 == p2) ? EOF :*p1++) char buf[1<<21], *p1 = buf, *p2 = buf; template <typename T> inline void read(T &x){ x = 0; re T f=1; re char c = gg; while(c > 57 || c < 48){if(c == '-') f = -1;c = gg;} while(c >= 48 &&c <= 57){x = (x<<1) + (x<<3) + (c^48);c = gg;} x *= f;return; } inline void ReadChar(char &c){ c = gg; while(!isalpha(c)) c = gg; } template <typename T> inline void write(T x){ if(x < 0) putchar('-'), x = -x; if(x > 9) write(x/10); putchar('0' + x % 10); } template <typename T> inline void writeln(T x){write(x); putchar('\n');} } using namespace IO_ReadWrite; int n,m,c[maxn],w[maxn],remain[maxn]; //remain[i] 表示第 i 个背包的剩余容量，初始 remain[i]=c[i] int sC,sW[maxn]; inline bool dfs(int k,int pre){//k 可以放在 pre 及其后的背包 if(!k) return 1; if(w[k]!=w[k+1]) pre=1;//若不是同一重量，无等效性剪枝 rep(i,pre,m){//等效性剪枝 1 if(remain[i]<w[k]) continue; if(remain[i]==remain[i-1]) continue;//等效性剪枝 2 remain[i]-=w[k]; if(dfs(k-1,i)) return 1;//递归 remain[i]+=w[k];//回溯 } return 0; } inline bool check(int k){ if(sC<sW[k]) return 0;//可行性剪枝 rep(i,1,m) remain[i]=c[i];//剩余载重初始化 return dfs(k,1); } inline int Binary(int l,int r){ int ans=0; while(l<=r){ int mid=(l+r)>>1; if(check(mid)) ans=mid,l=mid+1; else r=mid-1; } return ans; } int main(){ read(m); rep(i,1,m) read(c[i]); read(n); rep(i,1,n) read(w[i]); sort(c+1,c+m+1);sort(w+1,w+n+1); //优化搜索顺序 rep(i,1,m) sC+=c[i]; rep(i,1,n) sW[i]=sW[i-1]+w[i]; writeln(Binary(0,n)); return 0; } ``` ## 2.2 迭代加深 对于一类题目，其搜索树既宽又深，若使用 DFS 会 TLE，使用 BFS 队列会 MLE，这是可以采用一种将 DFS,BFS 相结合的方法：迭代加深（IDDFS）。  如上图所示，目标状态的深度可能不算太深，但因为搜索树巨大，导致 DFS 时容易误入歧途。若每一层的结点数过多，BFS 同样不适用，这时候就需要 IDDFS，具体操作如下： 1. 先设定层数 $depth=1$，DFS 搜索到第一层即停止。 2. 若没有找到答案，令 $depth=2$，即搜索到第二层即停止。 3. 如此循环往复，每次令 $depth$ 加一，进行限制层数的搜索，直到找到答案。 注意 $depth$ 的处理顺序遍历即可，不需要二分，因为当 $depth$ 较大时，效率极慢。同时对每次搜索时重复遍历的状态不用担心，因为这些状态数量与新扩展的一层的结点数比起来就是小巫见大巫。 下面是一道例题 [POJ 3134](http://poj.org/problem?id=3134)。 >给定数字 $x,n$，只能用乘法和除法，**算过的结果可以被利用**，问最少算多少次可以得到 $x^n$。 此题等价于初始数字 $1$，用加减法最少多少次算到 $n$。 将步数作为 IDDFS 中的 $depth$，初始 $depth=0$，每扩展一次用前一步的值和之前产生的所有值相加减得到新的值，判断等否等于 $n$。 加入可行性剪枝：若当前已经使用 $k$ 步，则还能使用 $depth-k$ 步。若当前值 $val\times 2^{depth-k}<n$，则不可能达到，直接返回无解。 ```cpp int val[maxn], pos, n;//我换了个码风试试 inline bool dfs(int k, int depth){ if(k > depth) return 0;//IDDFS 限制 if(val[pos]<<(depth-k) < n) return 0;//可行性剪枝 if(val[pos] == n) return 1; pos++;//扩展 rep(i, 0, pos - 1){ val[pos] = val[pos - 1] + val[i];//加 if(dfs(k + 1, depth)) return 1; val[pos] = abs(val[pos - 1] - val[i]);//减 if(dfs(k + 1, depth)) return 1; } pos--;//回溯 return 0; } int main(){ while(1) { read(n); if(!n) return 0; int depth; val[pos = 0] = 1;//初始化 for(depth = 0; !dfs(0, depth); depth++, val[pos = 0] = 1);//IDDFS writeln(depth); } return 0; } ``` ## 2.3 IDAstar 前置芝士：2.2 迭代加深，1.4 Astar 算法。 IDAstar 的本质是对迭代加深的优化，即在 IDDFS 中加入估价函数。可以把该算法看作 Astar 在 IDDFS 中的应用。 下面给出一道例题。[AHOI2012 铁盘整理](https://www.luogu.com.cn/problem/P2534) >求一个长度为 $n$ 且互不相同的数列 $\rm R$，每次将 $[1,i]$ 翻转，求最少翻转几次使得该序列单调递增。 以下是曾经的我写的题解，请多包涵： 首先看到数据范围，很容易想到搜索加优化加离散化。 用数组 $b$ 储存排序后的半径，用数组 $a$ 表示 $b$ 中第一次大于等于 $R_i$ 的元素的下标（离散化），用 $\text{lower\_bound}$ 实现即可。 离散化后，设计深搜的优化技巧。优化技巧无非几种：剪枝，迭代加深，预估（可行性剪枝）。对于本题，采用后两者。刚才的离散化有助于设计预估函数：对于一个序列，每次反转 $[1,i]$ 只能改变 $i,i+1$ 的差。因此有几对相邻数的差不为 $1$，就要翻转几次。 代码如下： ```cpp scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); b[i]=a[i]; }//输入 sort(b+1,b+n+1);//排序 for(int i=1;i<=n;i++){ a[i]=lower_bound(b+1,b+n+1,a[i])-b; }//离散化 a[n+1]=n+1;//翻转（n,n+1) ...... inline int step(){//预估函数 int ret=0; for(int i=1;i<=n;i++) ret+=(abs(a[i]-a[i+1])==1?0:1);//计算差不为 1 的个数。 return ret; } ``` 然后码一个暴力 $\rm{dfs+IDA}$，声明标记变量 $flag$。 - 判断预估函数的返回值：若为 $0$ 则表示满足，$flag$ 标为 $1$ 并返回； - 预估步数已经超过，则直接返回（剪枝）； - 扩展 $n$ 种区间，翻转递归并回溯。 ```cpp #include<bits/stdc++.h>//抄袭有奖 using namespace std; const int maxn=1e20; int n,a[maxn],b[maxn]; bool flag; inline int step(){ int ret=0; for(int i=1;i<=n;i++) ret+=(abs(a[i]-a[i+1])==1?0:1); return ret; }//预估函数 inline void dfs(int s,int f,int pre){ if(flag) return ; int num=step(); if(num==0) { flag=1; return ; }//成功 if(s+num>f) return ;//剪枝 for(int i=1;i<=n;i++){ if(i==pre) continue;//避免重复 reverse(a+1,a+i+1);//翻转 dfs(s+1,f,i);//递归 reverse(a+1,a+i+1);//回溯 } } int main(){ scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); b[i]=a[i]; } sort(b+1,b+n+1);//排序 for(int i=1;i<=n;i++){ a[i]=lower_bound(b+1,b+n+1,a[i])-b; } a[n+1]=n+1;//离散化 int i=0; while(1){ dfs(0,i,0); if(flag){ printf("%d",i); return 0; } i++; }//迭代加深 return 0; } ``` # 三、习题 1. POJ 1077 八数码问题（Astar） 要求：使用康托展开或 `unordered_map` 对状态图进行存储记录，用逆序对判断可行性，用每个数里目标状态的曼哈顿距离之和作为估价函数。 定理：将初始状态和目标状态各自逐行拼接成序列，若两个序列逆序对数量的奇偶性相同则一定有解，反之一定无解。 2. LibreOJ 10022 埃及分数（迭代加深） 3. POJ 1011，POJ 1190 经典题，DFS 剪枝 4. AcWing 175 电路维修（双端队列 BFS） 5. hdu 1560 DNA Sequence，IDAstar