「搜索优化」课件配套资料

写在前面

链接：https://pan.baidu.com/s/1M1MN1tzHsmqY8Or7f-vJcw
提取码：lnkw

其实课件是赶出来的= =
讲的时候也比较rush，没有网不能直播切题也很难受。
很抱歉讲的很垃圾，效果没有之前两节课好。

概念+典例篇

搜索

对状态空间进行枚举。
通过穷尽所有的可能，来找到最优解，或者统计合法解的个数。
一般拿不了满分，但可以用来打表 and 对拍 and 水部分分，所以非常重要。

搜索树

如果把要搜的状态看作节点，两个状态之间的转移看作一条边，那么这些节点就会形成一个树结构，被称为搜索树。
大多数搜索题随着搜索层数的增加，需要搜的状态呈指数级增长。
如果搜索层数很多，这棵树看上去就非常巨（图中1为起点，24为终点）。

迭代加深

通过例题引入。
给出一个分数，由分子 ?? 和分母 ??构成。
需要将其分解为一系列互不相同的单位分数（分子为1的分数），要求分解成的单位分数越少越好。如果两个方案数量一样则最小的单位分数越大越好。
例：
19/45 = 1/3+1/12+1/180 = 1/5+1/6+1/18
第二种分解方案更优。
0<??<??<1000

暴力

埃及分数问题
发现这个题暴力没法写。
想用dfs，发现找不到边界。令搜索阶段为现在枚举第几个数，则数的个数可能无限大。
想用bfs，发现状态开不下。令搜索状态为现在已经确定的数，可能的状态太多，即无法储存也难以表示。

问题的根源在于搜索树可能无限大。

直接写正解

迭代加深就是用来解决这样一种，搜索树可能无限大的问题。
从小到大地枚举数，钦定枚举的数为深度界限。
之后开始dfs，令搜索的深度都 ≤"深度界限"，看能不能搜到目标，如果能搜到，则当前的深度界限为答案。
避免了不知道什么时候停的问题。
可以发现，问题转化为判定在深度界限内能否搜到答案，成了一个判定性问题。

是不是听起来很假？可不可能有大量的时间浪费？
实际上时间浪费是比较小的，因为之前搜到的状态数甚至都不如最后一次搜到的状态数多。
反正搜索本来就是个玄学玩意，复杂度玄一点也没什么错XD

使用条件

还可以注意到，这题能够使用迭代加深，是因为搜索目标中有“使用的数越少越好”的要求。这提示了应使搜索树的深度尽量的小。
如果问题是求最优步数，搜索界限就是最多走的步数，令搜索树深度尽量小可以使答案更优，此时也可以使用迭代加深。

关于此题的一些扯

这题原先在codevs上可以测，但从去年codevs就爆炸了，所以变成了无主题。
另外写起来细节比较多，不适合上手，感兴趣可以去网上找代码。
理解思想即可，之后还会有题。

搜索剪枝

通过判断，避免对搜索树上一些无用部分的遍历过程。
例如有些状态一定不能访问到目标状态。
有一些状态一定得不到最优答案。

形象的说，就是减去了搜索树中的某些枝条。
减少枚举量，从而降低程序的复杂度。

剪枝分类

可行性剪枝和最优化剪枝，分别对应刚才的两种情况。
可行性剪枝：将不可能到达搜索目标的状态剪掉。
最优化剪枝：将不可能得到最优答案的状态剪掉。

经典小剪枝

将整数??分成??份，且每份不能为空，任意两个方案不相同(不考虑顺序)。
例：??=7，??=3，下面三种分法被认为是相同的。
1,1,5；1,5,1；5,1,1；
问有多少种不同的分法。
6<??<200 2<??<6。

显然的暴力

P1025 数的划分
暴力枚举之后的一个数，令原数减去这个数后再枚举。
当原数=0，且分成的数的个数=k时，答案+1。
要注意去重。
太快了！

优化

数的顺序不受影响，钦定分解数依次递增，每次搜索都从上一个搜到的数开始搜，去重。
剩余未被划分的数不能小于剩余划分的次数。

上面两个剪枝分别确定了当前层枚举的下界和上界。

//知识点：搜索 
/*
By:Luckyblock
*/
#include 
#include 
#include 
#include 
#include 
#define ll long long
//=============================================================
int n, k, ans;
//=============================================================
inline int read() {
  int f = 1, w = 0;
  char ch = getchar();
  for (; !isdigit(ch); ch = getchar())
    if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
  return f * w;
}
void Chkmax(int &fir_, int sec_) {
  if (sec_ > fir_) fir_ = sec_;
}
void Chkmin(int &fir_, int sec_) {
  if (sec_ < fir_) fir_ = sec_;
}
void Dfs(int length_, int sum_, int last_num_) {
  if (sum_ >= n || length_ >= k) {
    ans += (sum_ == n && length_ == k);
    return ;
  }
  int limit = n;//(n - sum_) / (k - length_);
  for (int i = last_num_; i <= limit; ++ i) {
    Dfs(length_ + 1, sum_ + i, i);
  }
}
//=============================================================
int main() {
  n = read(), k = read();
  Dfs(0, 0, 1);
  printf("%d\n", ans);
  return 0;
}

双向bfs

图1是刚才的那棵搜索树。
假设已知起点终点，从它们俩同时出发，则访问到的节点大大减少。
从图2可以直观地看出，因为有两个bfs源点，导致状态数指数级增长只进行到最大深度的一半。
更进一步地说：
搜索树的深度越大，则效率越低。而双向广搜产生了两颗搜索树，平摊了探测深度的任务，使得搜索树的深度减半，节点数几乎相当于开根号

经典小双向bfs

3×3 的棋盘上摆有八个棋子。每个棋子上标有1至8的某一数字。
棋盘中留有一个空格，空格用0来表示。
给出一种初始布局（初始状态）。
钦定目标状态为：123804765。
找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。

暴力

洛谷 P1379 八数码难题
直接从初始状态开始bfs，枚举能与空格交换的四个格子进行转移。
搜到目标状态为止。

优化1

发现上述过程中出现了很多重复状态。
考虑记忆化，把棋盘展开写成string类型，用map进行记忆化。
然后就可以过，但跑得很慢。
当时我只写了这个= =

//
/*
By:Luckyblock
*/
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define ll long long
const std :: string end = "$123804765";
//=============================================================
std :: string start;
std :: map  step;
std :: queue  q;
//=============================================================
inline int read() {
  int f = 1, w = 0;
  char ch = getchar();
  for (; !isdigit(ch); ch = getchar())
    if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
  return f * w;
}
void ChkMax(int &fir, int sec) {
  if (sec > fir) fir = sec;
}
void ChkMin(int &fir, int sec) {
  if (sec < fir) fir = sec;
}
void Check(std ::string now_, int now_step) {
  if (now_ == end) {
    printf("%d\n", now_step + 1);
    exit(0);
  }
  if (! step[now_]) {
    step[now_] = now_step + 1;
    q.push(now_);
  }
}
void Bfs() {
  q.push(start);
  while (! q.empty()) {
    std :: string now = q.front();
    int now_step = step[now];
    q.pop();
    int pos = now.find("0");
    if (pos + 3 <= 9) {
      std :: swap(now[pos], now[pos + 3]);
      Check(now, now_step);
      std :: swap(now[pos], now[pos + 3]);
    }
    if (pos - 3 >= 1) {
      std :: swap(now[pos], now[pos - 3]);
      Check(now, now_step);
      std :: swap(now[pos], now[pos - 3]);
    }
    if (pos + 1 <= 9 && pos != 3 && pos != 6) {
      std :: swap(now[pos], now[pos + 1]);
      Check(now, now_step);
      std :: swap(now[pos], now[pos + 1]);
    }
    if (pos - 1 >= 1 && pos != 4 && pos != 7) {
      std :: swap(now[pos], now[pos - 1]);
      Check(now, now_step);
      std :: swap(now[pos], now[pos - 1]);
    }
  }
}
//=============================================================
int main() { 
  std :: cin >> start;
  start.insert(0, "$");//使下标从1开始，方便。
  if (start == end) {
    printf("0");
    return 0;
  }
  Bfs();
  return 0; 
}

优化2

发现起始状态和目标状态都已知。
在上一个优化的基础上双向bfs即可。
优化了多少呢？8s->400ms

//知识点：双向bfs
/*
By:Luckyblock
*/
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define ll long long
const std :: string end = "$123804765";
//=============================================================
std :: string start;
std :: map  step, dir;
std :: queue  q;
//=============================================================
inline int read() {
  int f = 1, w = 0;
  char ch = getchar();
  for (; !isdigit(ch); ch = getchar())
    if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
  return f * w;
}
void ChkMax(int &fir, int sec) {
  if (sec > fir) fir = sec;
}
void ChkMin(int &fir, int sec) {
  if (sec < fir) fir = sec;
}
void Check(std ::string now_, std :: string nex_, int now_step) {
  if (! step[nex_]) {
    step[nex_] = now_step + 1;
    dir[nex_] = dir[now_];
    q.push(nex_);
    return ;
  }
  if (dir[now_] != dir[nex_]) {
    printf("%d\n", step[now_] + step[nex_]);
    exit(0);
  }
}
void Bfs() {
  q.push(start);
  q.push(end);
  step[start] = 0, dir[start] = 1;
  step[end] = 1, dir[end] = 2;

  while (! q.empty()) {
    std :: string now = q.front(), nex = now;
    int now_step = step[now];
    q.pop();
    int pos = now.find("0");
    if (pos + 3 <= 9) {
      std :: swap(nex[pos], nex[pos + 3]);
      Check(now, nex, now_step);
      std :: swap(nex[pos], nex[pos + 3]);
    }
    if (pos - 3 >= 1) {
      std :: swap(nex[pos], nex[pos - 3]);
      Check(now, nex, now_step);
      std :: swap(nex[pos], nex[pos - 3]);
    }
    if (pos + 1 <= 9 && pos != 3 && pos != 6) {
      std :: swap(nex[pos], nex[pos + 1]);
      Check(now, nex, now_step);
      std :: swap(nex[pos], nex[pos + 1]);
    }
    if (pos - 1 >= 1 && pos != 4 && pos != 7) {
      std :: swap(nex[pos], nex[pos - 1]);
      Check(now, nex, now_step);
      std :: swap(nex[pos], nex[pos - 1]);
    }
  }
}
//=============================================================
int main() { 
  std :: cin >> start;
  start.insert(0, "$");//使下标从1开始，方便。
  if (start == end) {
    printf("0");
    return 0;
  }
  Bfs();
  return 0; 
}

状态压缩

把复杂的状态转化为易于表示和储存的状态。

以上一个例子为例，将一个棋盘的状态，压缩成了一个字符串。
对于一个?? 行 ??列的网格图，位置(??,??) 可以被表示为一个整数???? =(???1)×??+???1。
解压时 ??=????/??+1,??=???? mod ??+1。

有什么用

在搜索中，可能会出现一些重复被搜到的状态，显然可以通过记忆化判重来减少搜索次数。
但在某些问题中，比如棋盘问题，不好直接记忆化。
可以考虑进行状态压缩，再用哈希或者map进行记忆化。

以上一个题为例，把棋盘压缩成了一个字符串，并使用了map进行记忆化。

二进制压位

通常指把存在性的状态压缩成一个二进制表示的整数。

可理解为把一个二进制中有 ?? 位的整数，看成一个长度为?? 的 bool 数组。
具体来说，就是有??个物品，状态为每一个物品是否存在。
若第??个物品存在，则整数的第??个二进制位值为1，否则为0。
如此便可以将所有 \(2^??\) 种可能的集合一一映射到\(2^??\) 个整数上。
可以使用位运算方便地判断某个物品是否存在。

如果 ?? 较小，压缩之后的整数可直接作为下标，非常方便。

启发式搜索

指通过一点神奇的判断进行剪枝。
没搜到一个状态，判断当前状态的搜索树中，可不可能出现更优的答案。如果不可能出现，就剪枝。
有预知未来的感觉。
启发式是什么意思？没什么意思，因为不好归类，就有个神仙取了这个 nb 的名字。

很久以前做的题

洛谷P2324 [SCOI2005]骑士精神

因为暴力不好写。
发现把马移动到空格，等价于空格进行移动，考虑搜索枚举空格的移动方案。
题目规定答案应在15步内，自己给搜索树加了限制，考虑迭代加深。
直接莽一波A不了，考虑优化。

优化

问题转化为判定在深度界限内能否搜到答案，成了一个判定性问题，考虑可行性剪枝。
对于一个棋盘状态，假设现在可以使用神秘力量，直接将所有棋子移到最终位置上。即检查有多少棋子不在最终位置，把这个量记录下来。
显然对于该状态，如果可以转化到合法状态，需要的步数，一定不小于上面记录的量。
如果当前状态以及用的步数 + 上面的量 >深度限制，就剪枝。
确实有预知未来的感觉（

很久以前写的代码

#include 
#include 
#include 
using namespace std;
//=======================================================
int dx[10] = {0, 1, 1, -1, -1, 2, 2, -2, -2};
int dy[10] = {0, 2, -2, 2, -2, 1, -1, 1, -1};
int target[7][7] = {{0, 0, 0, 0, 0, 0}, {0, 1, 1, 1, 1, 1}, {0, 0, 1, 1, 1, 1},
                    {0, 0, 0, 2, 1, 1}, {0, 0, 0, 0, 0, 1}, {0, 0, 0, 0, 0, 0}};
int t, judge;
int map[7][7];
//=======================================================
inline bool check(int x, int y) {
  if (x < 1 || x > 5 || y < 1 || y > 5) return 0;
  return 1;
}
inline int cnt() {
  int sum = 0;
  for (int i = 1; i <= 5; i++)
    for (int j = 1; j <= 5; j++)
      if (map[i][j] != target[i][j]) sum++;
  return sum;
}
void dfs(int now, int sx, int sy, int lim) {
  if (now == lim) {
    if (!cnt()) judge = 1;
    return;
  }
  for (int i = 1; i <= 8; i++)
    if (check(sx + dx[i], sy + dy[i])) {
      swap(map[sx][sy], map[sx + dx[i]][sy + dy[i]]);
      if (cnt() + now <= lim) dfs(now + 1, sx + dx[i], sy + dy[i], lim);
      swap(map[sx][sy], map[sx + dx[i]][sy + dy[i]]);
    }
}
signed main() {
  cin.sync_with_stdio(false);
  cin >> t;
  while (t--) {
    int sx, sy;
    judge = 0;
    for (int i = 1; i <= 5; i++)
      for (int j = 1; j <= 5; j++) {
        char tmp;
        cin >> tmp;
        if (tmp == '*')
          map[i][j] = 2, sx = i, sy = j;
        else
          map[i][j] = tmp - '0';
      }
    for (int i = 0; i <= 15; i++) {
      dfs(0, sx, sy, i);
      if (judge) {
        cout << i << endl;
        break;
      }
    }
    if (!judge) cout << -1 << endl;
  }
}

杂题篇

写在前面

搜索优化的重点还是优化，下面每一个例题都会给出暴力的思路和代码。
请使用任何您认为有效的优化手段优化它。
欢迎积极踊跃回答问题！

经典题

有一些长度相等的大木棍，ikka把它们砍成了?? 段长度≤50的小木棍。
给出每段小木棍的长度，求出原始木棍的最小可能长度。
??≤65。

例：小棒子分别为： 5 2 1 5 2 1 5 2 1，输出 6。

我会暴力！

洛谷P1120 小木棍
暴力从小到大枚举答案，考虑怎么判断一个答案合法。注意不满足单调性，不能二分答案。
记录当前拼好了几根大木棍，还剩的小木棍的总长度，当前拼的这一根大木棍拼了多长。
枚举小木棍接到当前拼的这根大木棍的后面。
最后判断能不能用光所有小木棍，且拼成了对应根数的大木棍。
18 pts！

//知识点：搜索
/*
By:Luckyblock
*/
#include 
#include 
#include 
#include 
#include 
#define ll long long
const int kMaxn = 70;
//=============================================================
int n, sum_length, length[kMaxn];
bool flag, used[kMaxn];
//=============================================================
inline int read() {
  int f = 1, w = 0;
  char ch = getchar();
  for (; !isdigit(ch); ch = getchar())
    if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
  return f * w;
}
void Getmax(int &fir_, int sec_) {
  if (sec_ > fir_) fir_ = sec_;
}
void Getmin(int &fir_, int sec_) {
  if (sec_ < fir_) fir_ = sec_;
}
//remain 用来判合法
void Dfs(int remain_, int lim_, int num_, int now_) {
  if (remain_ <= 0 || num_ >= (sum_length / lim_)) {
    flag = (remain_ == 0 && num_ == (sum_length / lim_));
    return ;
  }
  for (int i = 1; i <= n; ++ i) {
    if (! used[i]) {
      used[i] = true;
      if (now_ + length[i] == lim_) {
        Dfs(remain_ - length[i], lim_, num_ + 1, 0);
      } else if (now_ + length[i] < lim_) {
        Dfs(remain_ - length[i], lim_, num_, now_ + length[i]);
      }
      used[i] = false;
    }
  }
}
//=============================================================
int main() {
  int tmp = read();
  for (int i = 1; i <= tmp; ++ i) {
    int val = read();
    if (val <= 50) {
      length[++ n] = val;
      sum_length += val; 
    }
  }
  for (int i = 1; i <= sum_length; ++ i) {
    flag = false;
    Dfs(sum_length, i, 0, 0);
    if (flag) {
      printf("%d\n", i);
      return 0;
    }
  }
  return 0;
}

优化

保证枚举的答案，一定能整除木棍的长度和。
拼一根大木棍时，递减枚举用来拼接的小木棍的长度。
小木棍长度较小，可以用桶存剩余的个数，方便递减枚举，也方便判有无剩余。
若某组拼接不成立，且此时 已拼接的长度为0 或 当前已拼接的长度与刚才枚举的长度之和为最终枚举的答案 时，可直接跳出循环。因为继续枚举其它更小的值时，可能情况更少，且同样凑不完。
修改一些奇怪的枚举上下界。

总结篇

学到了什么

迭代加深
剪枝
双向 bfs
状态表示判重
启发式搜索

习题

P1025 数的划分
P1379 八数码难题
P2324 [SCOI2005]骑士精神
P1120 小木棍
P2730 [USACO3.2]魔板 Magic Squares

选做
P1074 靶形数独
P1092 虫食算

一些吐槽

啊我写到这才懂原来讲课内容是按着一本通提高篇来的。

鸣谢

https://www.luogu.com.cn/
Cdcq的课件

Next Dream...

杂

相关

数据结构----算法复杂度分析

TP5.0 关于validate验证器add和edit验证规则不统一的复杂情形

二、排序：时间复杂度O(n*logn)

Ext.Net学习笔记20：Ext.Net FormPanel 复杂用法

数据分析中的'疑难杂症'小结（二）

Latex的复杂插图设置（并排、竖排等等）

MAVEN 杂记

spring MongoTemplate 更新复杂对象数据

时间复杂度

搞定大厂算法面试之leetcode精讲2.时间空间复杂度

c_mt_找有k个数小于自己的数（二分->复杂化 / 排序简化）

Python复杂List转字符串还原

标签