文章目录
- 搜索
- dfs
- bfs
- 双向搜索
- 启发式搜索（记忆化搜索）
- IDA*(A*+迭代加深搜索)
- Dancing Links（精确覆盖问题）
- 优化（剪枝）
搜索
dfs
复杂度
共进行a步，每步循环n次， O（an）
用途
常用于判断是否存在满足条件的路径
例题
全排列
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int n;
bool vis[10];
int ans[10];void print() {for(int i = 1; i <= n; i++) printf("%5d", ans[i]);printf("\n");
}void dfs(int step) {if(step == n) {print();return ;}for(int i = 1; i <= n; i++) {if(!vis[i]) {vis[i] = 1;ans[step+1] = i;dfs(step+1);vis[i] = 0;}}
}int main () {while(~scanf("%d", &n)) {memset(vis, 0, sizeof(vis));memset(ans, 0, sizeof(ans));dfs(0);}return 0;
}
bfs
常用于找最短路径
双向搜索
从起点和终点同时出发，相遇时结束搜索
复杂度
共a步，每步的循环次数降为 O（an/2）
例题
「USACO09NOV」灯 Lights
开关灯问题
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 1e9+7;inline int read() {int x = 0, f = 1; char c = getchar();while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();}while(c >= '0' && c <= '9') {x = x *10 + c - '0';c = getchar();}return x*f;
}bool flag;
int n, m, cnt, minn = INF;
int a[40];
ll ed, p[40], bin[40];
map<ll, int> b;void dfs(int x, ll now, int step) { // x表示现在要操作第几盏灯， now表示现在各灯的状态， step为当前操作数 if(x == cnt + 1) { // 所有灯都操作过了 if(now == ed) minn = min(minn, step);if(!flag) { // 搜索前一半 int t = b[now]; // 记录当前状态下的操作数 if(!t || t > step) b[now] = step; // 如果当前状态还没出现过，或者此次达到当前状态需要的操作数更少就更新 }else { // 搜索后一半 int t = b[ed-now]; // 找到第一次搜索中互补的状态if(!t) return ; // 如果每有，则此次搜索不满足条件minn = min(minn, step+t); } return ;}dfs(x+1, now, step); // 不开灯 dfs(x+1, now^p[x], step+1); // 开灯
}int main() {
// freopen("test.in", "r", stdin);n = read(); m = read();bin[1] = 1;for(int i = 2; i <= n+1; i++) bin[i] = bin[i-1] << 1; // bin[1] = 001, bin[2]=010, bin[3]=100ed = bin[n+1] - 1; // 结束状态，表示所有灯都被打开 for(int i = 1; i <= m; i++) {int u = read(), v = read();p[u] += bin[v]; p[v] += bin[u]; // p[3] = 101, 即灯 3 与 灯 1 相关联，互相影响 } for(int i = 1; i <= n; i++) p[i]+=bin[i]; // 每个灯与自己互相影响cnt = n/2;dfs(1, 0, 0); // 折半搜索的前一半flag = 1; // 标记为搜索后一半 cnt = n;dfs(n/2+1, 0, 0); // 折半搜索另一半 printf("%d\n", minn); return 0;
}
启发式搜索（记忆化搜索）
参考这篇博客，讲的实在是太好了
启发式搜索（英文：heuristic search）是一种改进的搜索算法。它在普通搜索算法的基础上引入了启发式函数，该函数的作用是基于已有的信息对搜索的每一个分支选择都做估价，进而选择分支。简单来说，启发式搜索就是对取和不取都做分析，从中选取更优解或删去无效解。
例题
P1048 [NOIP2005 普及组] 采药
#include<bits/stdc++.h>
using namespace std;
int n, T;
int mem[105][1005];
int val[105], t[105];int dfs(int pos, int tleft) {if(mem[pos][tleft] != -1) return mem[pos][tleft];if(pos == n+1) return mem[pos][tleft] = 0; // 边界int dfs1 = 0, dfs2 = 0; // 赋初始值，防止影响比较大小 dfs1 = dfs(pos+1, tleft); // 不采if(t[pos] <= tleft) dfs2 = dfs(pos+1, tleft-t[pos]) + val[pos]; // 采 return mem[pos][tleft] = max(dfs1, dfs2);
}int main() {memset(mem, -1, sizeof(mem));cin >> T >> n;for(int i = 1; i <= n; i++) cin >> t[i] >> val[i];cout << dfs(1, T) << endl;return 0;
}
IDA*(A*+迭代加深搜索)
算法参考
算法解释： 以寻找最短路径为例，直接用bfs最坏情况要搜遍整个地图，不优秀。
怎么优化呢？能不能有个大概方向的指引让我们搜索过程少走一些弯路呢？
当然可以，这时候我们只需要对下一步要走的四个方向设置一个可比较的参量
可以利用当前已经走过的步数+到达目标还需要的最少步数作为比较的值，到达目标的距离直接用曼哈顿距离即可（横平竖直 |x1-x2|+|y1-y2|），这样选择代价最小的方向查询即可
例题参考
例题1
P1379 八数码难题
#include<bits/stdc++.h>
using namespace std;
const int maxn = 10;
int dx[] = {1,-1,0,0};
int dy[] = {0,0,-1,1};
int flag, now[maxn], goal[maxn]; // now[i] = 2 标记数字 i 当前在位置 2 上
int dis[maxn][maxn], a[maxn][maxn], mp[maxn][maxn];
// dis[i][j] 表示把 从 i 位置移到 j 位置需要的步数
inline int calcx(int x) { // 计算出第几行 return (x - 1) / 3 + 1;
} inline int calcy(int x) { // 计算出位于第几列 return x%3 ? x%3 : 3;
}inline int h() { // 当前位置到目标位置的曼哈顿距离 int t = 0;for(int i = 1; i <= 9; i++) t += dis[now[i]][goal[i]];return t;
}inline int check() {for(int i = 0; i < 9; i++) {if(now[i] != goal[i]) return 0; // 只要有一个数字 无法到达，就不行 }return 1;// 刚好到达目标处
}void dfs(int step, int x, int y, int lim) {
// cout << "*" << endl; if(step + h() > lim) return ;if(check()) {flag = 1;return ;}for(int i = 0, nx, ny; i < 4; i++) {nx = x + dx[i]; ny = y + dy[i];if(flag) return ;if(nx > 0 && nx <= 3 && ny > 0 && ny <= 3) {swap(a[x][y], a[nx][ny]); swap(now[a[x][y]], now[a[nx][ny]]);dfs(step+1, nx, ny, lim);swap(a[x][y], a[nx][ny]); swap(now[a[x][y]], now[a[nx][ny]]);}}
}void pre() {// 预处理出估值函数，从某个点到另一个点的曼哈顿距离 for(int i = 1; i <= 9; i++)for(int j = i+1; j <= 9; j++)dis[i][j] = dis[j][i] = abs(calcx(i)-calcx(j)) + abs(calcy(i)-calcy(j));
}int main() {freopen("test.in", "r", stdin);pre();// goal[0] = 5； 空格在5号位置 goal[0]=5;goal[1]=1;goal[2]=2;goal[3]=3;goal[4]=6;goal[5]=9;goal[6]=8;goal[7]=7;goal[8]=4;int sx, sy;for(int i = 1, x, y, z; i <= 9; i++) {scanf("%1d", &z); // 每次只读一位数字x = calcx(i); y = calcy(i);mp[x][y] = z; // 二维坐标地图 now[z] = i; // 数字 z 对应的位置编号 if(!z) sx = x, sy = y;}//迭代加深搜索//迭代加深就类似于用 DFS 方式实现的 BFS，它的空间复杂度相对较小。for(int i = 0; ; i++) { // 限制 i 步内完成搜索 memcpy(a, mp, sizeof(mp)); // 用 mp 覆盖 adfs(0, sx, sy, i);if(flag) {printf("%d\n", i);break;} }return 0;
}
例题2
埃及分数
参考
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
#define ll long longint maxd; // 最少的分数个数
ll ans[maxn], tmp[maxn];ll get_first(ll x, ll y) { // 第一个比 x/y 小的分数 ll i = y/x;return x*i >= y ? i : i+1;
}ll gcd(ll a, ll b) {return b == 0 ? a : gcd(b, a%b);
}bool better(ll dep) { // 更新当前解，当然是越小的分母即越大的分数越多越好 for(ll i = dep; i >= 0; i++) { // 由于分母是由小到大存储的，因此是逆序枚举 ，越往后越容易出现更优解if(tmp[i] != ans[i]) return ans[i] == -1 || ans[i] > tmp[i];} return false;
}ll dfs(ll dep, ll from, ll aa, ll bb) {if(dep == maxd) {if(bb % aa) return 0;// 最后一个分数，分母不能整除分子，即不能表示为单位分数，搜索失败 tmp[dep] = bb/aa; // 不要忽略最后一个分数// 回溯过程中寻找更优解 if(better(dep)) memcpy(ans, tmp, sizeof(ll)*(dep+1)); return 1;}bool ok = 0;from = max(from, get_first(aa, bb));//更新from这一步容易忽略,假设第d-1个分数的分母是a,第d个分数的分母不一定要从a+1开始，还要考虑1/(a+1)是否小于等于aa/bbfor(ll i = from; ; i++) {if(bb*(maxd+1-dep) <= aa*i) break; // aa/bb >= 1/i*(maxd+1-d), 结束条件 tmp[dep] = i; // 新分母// 通分算剩下的分数 ll b2 = bb*i;ll a2 = aa*i - bb;ll g = gcd(a2, b2);// 用于约分if(dfs(dep+1, i+1, a2, b2)) ok = 1;// 找到了一组解，但不能结束，因为可能还有更优解 }return ok;//返回从第cur层到maxd层是否成功找到了解，ok一旦为true就一直是true}int main() {freopen("test.in", "r", stdin);int a, b, kase = 0;while(~scanf("%d%d", &a, &b)) {ll ok = 0;// 迭代加深搜索 for(maxd = 1; ; maxd++) { // 最后由 0~maxd 个分数相加得到最终结果 memset(ans, -1, sizeof(ans));if(dfs(0, get_first(a, b), a, b)) {ok = 1;break;}}printf("Case %d: %d/%d=", ++kase, a, b);for(ll i = 0; i <= maxd; i++) {if(i) printf("+");printf("1/%d", ans[i]);}printf("\n");}return 0;
}
Dancing Links（精确覆盖问题）
留坑（要用链表）逃
优化（剪枝）
- 记忆化搜索
- 可行性剪枝（当前搜索的答案已经不可行时不在继续搜索）
- 最优化剪枝（当前搜索的答案已经没有已有答案优时不在继续搜索）
例题
工作分配问题
INPUT：
5
9 2 9 1 9
1 9 8 9 6
9 9 9 9 1
8 8 1 8 4
9 1 7 8 9
OUTPUT
5
#include<bits/stdc++.h>
using namespace std;
int n, ans = 1e7;
int t[20][20];
int col[20];void dfs(int L, int sum) {if(sum > ans) return ; // 最优化剪枝 if(L == n+1) {ans = min(ans, sum);return ;}for(int i = 1; i <= n; i++) {if(!col[i]) {col[i] = 1;dfs(L+1, sum+t[L][i]);col[i] = 0;}}
}int main() {freopen("test.in", "r", stdin);while(~scanf("%d", &n)) {for(int i = 1; i <= n; i++) {for(int j = 1; j <= n; j++) {scanf("%d", &t[i][j]);}}dfs(1, 0);printf("%d\n", ans);}return 0;
}
