前言
搜索, 往往也被称为暴力, 是省选及以下比赛拿到部分分的最好方法, 如果优化得当, 甚至可能与正解复杂度媲美, 并且在洛谷中有大量水题, 然而一些搜索优化技巧却比较不为人所熟知, 于是就有了这篇文章
感谢搜索, 搜索为我带来了提高组省一
朴素 DFS
DFS , 全称 Depth-First Search , 即深度优先搜索, 是最朴素的暴力, 它没有统一的模版, 但是很好实现
因为搜索算法的复杂度本就为 NP , 且基本不可能卡满, 不具有太大参考价值, 因此我们会使用定性半定量分析, 或不给出时间复杂度
正确的 DFS 一定需要想清楚三个部分:
- 出口条件, 否则会无限递归
- 状态定义, 即函数的参数 ( 至少有一个参数可以作为函数的返回值 ) , 类似动态规划
- 我在函数内要做什么, 包括是否有后效性 ( 是否需要恢复现场 ) 等细节
P1019 单词接龙是一道纯 DFS 题
对于以上所述的三个部分, 我们有:
- 没有可以接上的字符串即退出
- 存长度和上次接入的单词, 存上次单词是为了判断是否有包含关系
- 更新长度和上次单词, 继续调用, 单词是否使用过显然需要恢复现场
DFS 部分代码如下:
int valid(string a, string b) // 用于求两个字符串重复长度
{
bool flag;
int length = min(a.length(), b.length());
for (int i = 1; i < length; i++)
{
flag = false;
for (int j = 0; j < i; j++)
{
if (a.at(a.length() - i + j) != b.at(j)) { flag = true; }
}
if (!flag) { return i; }
}
return 0;
}
void dfs(int length, const string& current)
{
max_ = max(length, max_);
for (int i = 1; i <= n; i++)
{
if (visited[i]) { continue; }
int overlap = valid(current, words[i]);
if (overlap)
{
visited[i] = true;
dfs(length + words[i].length() - overlap, words[i]);
visited[i] = false;
}
}
}
记忆化搜索
如果 DFS 具有返回值, 那么可以进行记忆化搜索, 优化得当的记忆化搜索时间复杂度与 DP 相同
对于记忆化, 一般建议使用 map 来存储, 不容易超空间
P1464 Function是一道纯记忆化搜索题, 甚至题目已经告诉如何 DFS 了, 无需分析, 记得开 long long
DFS 部分代码如下:
long long function(long long x, long long y, long long z)
{
if (x <= 0 || y <= 0 || z <= 0) { return 1; }
if (memory[{ x, y, z }]) { return memory.at({ x, y, z }); }
if (x > 20 || y > 20 || z > 20)
{
memory[{ x, y, z }] = function(20, 20, 20);
return memory[{ x, y, z }];
}
if (x < y && y < z)
{
memory[make_tuple(x, y, z)] = function(x, y, z - 1) + function(x, y - 1, z - 1) - function(x, y - 1, z);
return memory[{ x, y, z }];
}
memory[{ x, y, z }] = function(x - 1, y, z) + function(x - 1, y - 1, z) + function(x - 1, y, z - 1) - function(x - 1, y - 1, z - 1);
return memory[{ x, y, z }];
}
最优期望剪枝
如果要求一个最值, 可以考虑最优期望剪枝, 这是一种很通用的剪枝
以最大值为例, 每次 DFS 时, 求出继续递归下去, 且每次选择都是最优的 ( 无论是否可能 ) , 最大可能得到的值是多少, 如果这个值仍然小于等于当前最大值, 可以直接返回, 不可能取得最值
这种方法要求求出的最大可能得到的值必须大于等于真实值, 这种方式实际上是 IDA* 中的估价函数的弱化
P1731 生日蛋糕是比较难的一道纯最优期望剪枝题, 涉及三个剪枝:
- 如果从当前层开始, 一直取最小表面积, 仍然大于等于当前最小值, 直接返回
- 如果从当前层开始, 一直取最小体积, 体积仍然会超出限制
n, 直接返回 - 该剪枝是剪枝 1 的加强版, 根据当前剩余体积算出最小可能的表面积 ( 显然层数越少, 表面积越小, 所以算只做一层的表面积 ) , 如果加上已有的表面积大于等于当前最小值, 直接返回
首先在主函数预处理出最小的可能体积和最小的可能表面积, 并求前缀和, 方便剪枝操作, 代码如下:
for (int i = 1; i <= m; i++)
{
// 原题中带 π 了, 可以直接忽略
min_v[i] = min_v[i - 1] + i * i * i;
min_s[i] = min_s[i - 1] + i * i * 2;
}
然后, 我们很容易就能实现 DFS 过程, 代码如下:
void dfs(int layer, int v, int s)
{
if (v + min_v[layer] > n) { return ; }
if (s + min_s[layer] >= answer) { return ; }
if (s + 2 * (n - v) / r[layer + 1] >= answer) { return ; }
if (!layer)
{
if (v == n) { answer = min(answer, s); }
return ;
}
for (int i = min(r[layer + 1] - 1, int(sqrt(n - v))); i >= layer; i--)
{
for (int j = min(h[layer + 1] - 1, (n - v) / (i * i)); j >= layer; j--)
{
r[layer] = i;
h[layer] = j;
// 这里三目运算符表示, 从上向下看, 顶部的圆形面积实际就是最大一层的顶部面积
// 注意要倒序遍历层数, 这样表面积与体积才会单调下降, 否则剪枝会出错
dfs(layer - 1, v + i * i * j, s + 2 * i * j + (layer == m ? i * i : 0));
}
}
}
迭代加深搜索
迭代加深搜索, 又称 ID , 即 Iterative DFS , 是一种使用 DFS 实现类似 BFS 的效果的算法, 它能解决的问题与 BFS 一致
我们知道, DFS 递归会形成一棵搜索树, 这棵树每次向下增长的节点巨大, 以至于可能对于第
对于这种情况, 我们可以设定一个最大递归深度, 到达该深度就不再递归, 如果没有取到可能的答案, 将最大递归深度增加, 尽管这样会多次重复遍历搜索树的一部分, 但这一部分可以忽略不计
对于迭代加深搜索, DFS 需要返回值以确定是否取到答案
UVA529 Additional Chains是为数不多的纯迭代加深题, 但难度不高, 需要注意的是最大递归深度可以从
由于第一个数已经决定, 所以深度初始为 2 即可
主函数部分如下:
max_depth = log2(n);
while (!dfs(2) && max_depth++);
for (int i = 1; i <= max_depth - 2; i++) { cout << result[i] << ' '; }
cout << result[max_depth - 1] << endl;
如果只迭代加深仍然无法通过, 再加上一个最优期望剪枝即可: 一个数显然不能是它前一个数的两倍以上, 否则根据二进制表示, 一定会有
DFS 部分代码如下:
bool dfs(int index)
{
if (index > max_depth) { return false; }
if (result[index - 1] == n) { return true; }
if ((long long)(result[index - 1]) << (max_depth - index + 1) < n) { return false; } // 最优期望剪枝
bool visited[10001] = { false };
for (int i = 1; i < index; i++) // 当前位置还未确认, 因此不取等
{
for (int j = 1; j < index; j++)
{
int temp = result[i] + result[j]; // 从已经确定的数中枚举组合成新的数, 确保满足限制
if (temp > n) { break; }
if (visited[temp] || temp < result[index - 1]) { continue; }
result[index] = temp;
visited[temp] = true;
if (dfs(index + 1)) { return true; }
}
}
return false;
}
IDA*
IDA* , 中文译名是启发式迭代加深搜索, 我们知道, 迭代加深搜索有一个最大深度, 根据最优期望优化的思想, 考虑在 DFS 内判断到达目标状态最少还需要几步, 称为估值, 用估值加上当前深度再与最大深度比较, 这就是启发式迭代加深, 计算估值的函数一般称为 eval 即估值函数, 估值函数必须大于真实值
复杂度比较玄学
P2324 骑士精神是 IDA* 经典题, 第一个思路是, 骑士比较多, 但空格只有一个, 所以我们可以移动空格而不是骑士
然后设计估值函数, 对于当前状态和目标状态中的每一个不同点, 都至少需要一步移动
DFS 部分代码如下:
const vector<pair<int, int> > offsets = { { 1, 2 }, { 1, -2 }, { -1, 2 }, { -1, -2 },
{ 2, 1 }, { -2, 1 }, { 2, -1 }, { -2, -1 } };
const int target[10][10] = { { 0, 0, 0, 0, 0, 0 }, { 0, 2, 2, 2, 2, 2 }, { 0, 1, 2, 2, 2, 2 },
{ 0, 1, 1, 0, 2, 2 }, { 0, 1, 1, 1, 1, 2 }, { 0, 1, 1, 1, 1, 1 } };
int eval()
{
int result = 0;
for (int i = 1; i <= 5; i++)
{
for (int j = 1; j <= 5; j++) { result += target[i][j] != matrix[i][j]; }
}
return result;
}
bool dfs(int blank_i, int blank_j, int index)
{
if (index + eval() > max_depth) { return false; }
if (!eval()) { return true; } // 如果与目标状态没有不同, 则成功
for (auto offset : offsets)
{
int x = blank_i + offset.first, y = blank_j + offset.second;
if (x < 1 || x > 5 || y < 1 || y > 5) { continue; }
swap(matrix[x][y], matrix[blank_i][blank_j]);
if (dfs(x, y, index + 1)) { return true; }
swap(matrix[x][y], matrix[blank_i][blank_j]);
}
return false;
}
折半搜索
类似于迭代加深搜索, 搜索树的增长是指数级的, 但更加简单粗暴, 我们将搜索树从中间劈开, 分别求, 然后求这两部分的交集, 即为最终答案, 因而折半搜索有个别名, 称为 meet-in-the-middle , “在中间相遇”
CF525E Anya and Cubes 是少见的折半搜索题, 裸的搜索很好写, 我们直接开始折半, 首先是主函数:
int main()
{
factorials.emplace_back(1);
for (int i = 1; i <= 20; i++) { factorials.emplace_back(factorials.at(i - 1) * i); } // 预处理阶乘
cin >> n >> k >> target;
for (int i = 1; i <= n; i++) { cin >> a[i]; }
dfs1(1, 0, 0);
dfs2(n / 2 + 1, 0, 0);
cout << answer << endl;
return 0;
}
前一半就是普通搜索:
void dfs1(int index, int counter, ll sum)
{
if (index > n / 2)
{
memory[counter][sum]++;
return ;
}
dfs1(index + 1, counter, sum); // 不选这个数
dfs1(index + 1, counter, sum + a[index]); // 选这个数, 不用阶乘
if (counter < k && a[index] <= 20) { dfs1(index + 1, counter + 1, sum + factorials.at(a[index])); } // 选这个数且用阶乘
}
后一半需要合并答案, 前后半互不影响, 服从加法原理:
void dfs2(int index, int counter, ll sum)
{
if (index > n)
{
// 如果这次搜索用了 counter 个阶乘, 上一次至多用了 k - counter
// 如果这次搜索的和是 sum , 上次的和必须是 target - sum
for (int i = 0; i <= k - counter; i++) { answer += memory[i][target - sum]; }
return ;
}
dfs2(index + 1, counter, sum);
dfs2(index + 1, counter, sum + a[index]);
if (counter < k && a[index] <= 20) { dfs2(index + 1, counter + 1, sum + factorials.at(a[index])); }
}
不知道为什么, 这道题的题解合并答案复杂的令人望而却步, 个人喜欢 quarmer 大佬的那一篇
这道题的时间复杂度是可以分析的, 每次有三个决策, 前后一半的复杂度各是
另, 去年 ( 2022 年 ) 的联赛提高组出了一道折半思想的题目, 但是似乎随机权也可以做
搜索顺序优化
在某些搜索的某个阶段中, 搜索下一状态的顺序并不影响正确性, 但可以影响时间, 那么显然改变搜索顺序是明智的
一般来说, 求出一个可行解或判断有没有解才能使用, 因为在最优化问题中, 欲求得最值, 定要遍历每个状态, 则优化失效; 这种优化的典型代表是各类数独求解, 如例题:
P1074 靶形数独这道题的思路是, 先搜索填过数较多的一行, 实现是容易的; 这题是最优化问题, 但这个优化使得每一个解的时间都得到了优化, 故也有效用
IDA* 可以勉强算是一种搜索顺序优化, 因为估值函数高的更容易被提前返回, 会更靠后搜索, 但这样解释有些奇怪
状态压缩
状态压缩是一种通用的思想, 虽然它只能优化代码常数, 足够大的常数优化在 OI 中常用的数据范围内, 也是相当优越的, 在搜索中尤为明显: 搜索是 NP 复杂度的算法, 对其内层函数复杂度的优化对于整体复杂度优化是极其显著的
状态压缩的核心是将标记数组状态压缩成一个二进制串, 从而用整形存储这个串, 在 DLX ( Dancing Links X , 舞蹈链 ) 能解决的精确覆盖类问题中经常使用, 比如数独类问题, 和经典的智慧珠游戏; 具体能够优化多少十分玄学, 可以说遇强则强, 实力不详
由于这种思想比较抽象, 我们借助以下的这道题目来理解
UVA1309 Sudoku本来是一道 DLX 精确覆盖问题, 但是状态压缩加上一定的搜索顺序优化也可以水过这道黑题
首先, 根据平时玩数独的经验, 我们整理出一些剪枝思路:
- 如果存在一个格子任何数都填不了, 直接返回即可
- 类似的, 如果存在一个格子只剩下一个候选数, 直接填上即可
这启发我们存储每个格子的候选数, 并且将其压缩成一个二进制串, 长度是 16 ; 众所周知, 对于一个数
注意到
数独问题具有后效性, 因此需要恢复现场, 但由于我们使用了二进制操作, 不具有可减性, 且有大量剪枝, 因此在函数开始时将所有会改变的状态数组全部复制一份, 恢复现场时再复制回来
因此我们得到所有变量和数组的定义如下 ( t 是组数, 因为输出要用; counter 是还有多少剩余空格 )
char sudoku[16][16], sudoku_history[2][1001][16][16];
int t, counter, state[16][16], state_history[2][1001][16][16], ones[(1 << 16) + 1];
初始化 ones 数组代码如下:
for (int i = 0; i <= (1 << 16) - 1; i++)
{
int temp = i;
while (temp)
{
ones[i]++;
temp -= temp & -temp;
}
}
但是这些剪枝对于一道黑题来说还是不够的, 再次运用经验, 得到以下剪枝:
- 找出所有格子中候选数最少的, 先填它
- 对于每一行, 每一列, 每一宫, 如果其中所有格子的候选数不能凑齐 1 到 16 , 直接返回
- 对于每一行, 每一列, 每一宫, 如果某个字母只能出现在某一位置, 直接填上
首先, 我们可以将更新状态的抽象出一个函数, 如下:
void update_state(int x, int y, int num)
{
sudoku[x][y] = char(num + 'A');
for (int i = 0; i < 16; i++)
{
state[x][i] &= ~(1 << num); // 将一行的该候选数全部去掉
state[i][y] &= ~(1 << num); // 将一列的该候选数全部去掉
}
// 以下代码都是为了去除一宫中的该候选数
int block_x = x / 4 * 4, block_y = y / 4 * 4;
for (int i = 0; i < 4; i++)
{
for (int j = 0; j < 4; j++) { state[block_x + i][block_y + j] &= ~(1 << num); }
}
state[x][y] = 1 << num; // 将这一格修改为只有 num 一个候选数
}
接着实现剪枝 1 , 代码如下:
if (n == 0) { return true; }
int x, y, min_ = INT_MAX, min_state;
for (int i = 0; i < 16; i++)
{
for (int j = 0; j < 16; j++)
{
if (sudoku[i][j] != '-') { continue; }
if (ones[state[i][j]] < min_)
{
min_ = ones[state[i][j]];
x = i;
y = j;
min_state = state[i][j];
}
}
}
memcpy(state_history[1][depth], state, sizeof(state));
memcpy(sudoku_history[1][depth], sudoku, sizeof(sudoku));
while (min_state)
{
int temp = min_state & -min_state, num = int(log2(temp)); // temp 是 lowbit 值, num 是实际候选数
update_state(x, y, num); // 试填
if (dfs(n - 1)) { return true; } // 如果试填后成功, 则直接返回
memcpy(state, state_history[1][depth], sizeof(state));
memcpy(sudoku, sudoku_history[1][depth], sizeof(sudoku)); // 恢复现场
min_state -= temp;
}
剩余的剪枝可以合并在一起, 对于剪枝 3 , 我们维护一个 16 位二进制串, 若某一位为 1 , 说明只能填在一个特定位置, 反之则说明可以填在多个位置 ( 哪里都不能填的已经剪掉了 )
寻找只能填在一个位置的数是非常困难的, 正难则反, 考虑哪些数可以填在多个地方, 故将二进制串初始化为全 1 , 如果遍历到一格时, 这一格的候选数在之前维护的行内总候选数也出现过, 则这个数一定至少可以填在两个地方
由于行, 列, 宫的代码非常相似, 故以行为例, 代码如下:
for (int i = 0; i < 16; i++)
{
// set 表示行中的总候选数
// used 表示行中已经填上的数
int set = 0, locked = (1 << 16) - 1, used = 0;
for (int j = 0; j < 16; j++)
{
// state[i][j] 是当前位置候选数集合
// set & state[i][j] 即为重复出现的候选数集合
// locked & ~(set & state[i][j]) 即为除去重复出现的候选数集合, 即除去所有可以填在多个地方的数
locked &= ~(set & state[i][j]);
set |= state[i][j];
if (sudoku[i][j] != '-') { used |= state[i][j]; }
}
if (set != (1 << 16) - 1) // 如剪枝 2 所述
{
memcpy(state, state_history[0][depth], sizeof(state));
memcpy(sudoku, sudoku_history[0][depth], sizeof(sudoku));
return false;
}
// 以下如剪枝 3 所述
// 事实上, 这两个循环可以简化成一层, 有常数上的优化
while (locked)
{
int temp = locked & -locked;
if (!(used & temp)) // 确保当前的数字没有填写过
{
for (int j = 0; j < 16; j++) // 枚举填写的位置
{
if (state[i][j] & temp) // 判断是否可以填写
{
update_state(i, j, int(log2(temp)));
n--;
break; // 根据剪枝 3 的定义, 该位置是唯一的
}
}
}
locked -= temp;
}
}
以下是无注释版完整代码, 仅供参考:
#include <iostream>
#include <cmath>
#include <cstring>
#include <climits>
#include <algorithm>
using namespace std;
char sudoku[16][16], sudoku_history[2][1001][16][16];
int t, counter, state[16][16], state_history[2][1001][16][16], ones[(1 << 16) + 1];
void update_state(int x, int y, int num);
bool dfs(int n);
void show();
int main()
{
for (int i = 0; i <= (1 << 16) - 1; i++)
{
int temp = i;
while (temp)
{
ones[i]++;
temp -= temp & -temp;
}
}
while (cin >> sudoku[0])
{
if (t) { cout << endl; }
t++;
for (int i = 1; i < 16; i++) { cin >> sudoku[i]; }
fill(state[0], state[0] + 256, (1 << 16) - 1);
counter = 0;
for (int i = 0; i < 16; i ++)
{
for (int j = 0; j < 16; j ++)
{
if (sudoku[i][j] != '-') { update_state(i, j, sudoku[i][j] - 'A'); }
else { counter++; }
}
}
dfs(counter);
show();
}
return 0;
}
void update_state(int x, int y, int num)
{
sudoku[x][y] = char(num + 'A');
for (int i = 0; i < 16; i++)
{
state[x][i] &= ~(1 << num);
state[i][y] &= ~(1 << num);
}
int block_x = x / 4 * 4, block_y = y / 4 * 4;
for (int i = 0; i < 4; i++)
{
for (int j = 0; j < 4; j++) { state[block_x + i][block_y + j] &= ~(1 << num); }
}
state[x][y] = 1 << num;
}
bool dfs(int n)
{
int depth = n;
memcpy(state_history[0][depth], state, sizeof(state));
memcpy(sudoku_history[0][depth], sudoku, sizeof(sudoku));
for (int i = 0; i < 16; i++)
{
for (int j = 0; j < 16; j++)
{
if (sudoku[i][j] != '-') { continue; }
if (state[i][j] == 0)
{
memcpy(state, state_history[0][depth], sizeof(state));
memcpy(sudoku, sudoku_history[0][depth], sizeof(sudoku));
return false;
}
if (ones[state[i][j]] == 1)
{
update_state(i, j, int(log2(state[i][j])));
n--;
}
}
}
for (int i = 0; i < 16; i++)
{
int set = 0, locked = (1 << 16) - 1, used = 0;
for (int j = 0; j < 16; j++)
{
locked &= ~(set & state[i][j]);
set |= state[i][j];
if (sudoku[i][j] != '-') { used |= state[i][j]; }
}
if (set != (1 << 16) - 1)
{
memcpy(state, state_history[0][depth], sizeof(state));
memcpy(sudoku, sudoku_history[0][depth], sizeof(sudoku));
return false;
}
while (locked)
{
int temp = locked & -locked;
if (!(used & temp))
{
for (int j = 0; j < 16; j++)
{
if (state[i][j] & temp)
{
update_state(i, j, int(log2(temp)));
n--;
break;
}
}
}
locked -= temp;
}
}
for (int j = 0; j < 16; j++)
{
int set = 0, locked = (1 << 16) - 1, used = 0;
for (int i = 0; i < 16; i++)
{
locked &= ~(set & state[i][j]);
set |= state[i][j];
if (sudoku[i][j] != '-') { used |= state[i][j]; }
}
if (set != (1 << 16) - 1)
{
memcpy(state, state_history[0][depth], sizeof(state));
memcpy(sudoku, sudoku_history[0][depth], sizeof(sudoku));
return false;
}
while (locked)
{
int temp = locked & -locked;
if (!(used & temp))
{
for (int i = 0; i < 16; i++)
{
if (state[i][j] & temp)
{
update_state(i, j, int(log2(temp)));
n--;
break;
}
}
}
locked -= temp;
}
}
for (int i = 0; i < 16; i++)
{
int set = 0, locked = (1 << 16) - 1, used = 0;
for (int j = 0; j < 16; j++)
{
int block_x = i / 4 * 4, block_y = i % 4 * 4,
delta_x = j / 4, delta_y = j % 4;
locked &= ~(set & state[block_x + delta_x][block_y + delta_y]);
set |= state[block_x + delta_x][block_y + delta_y];
if (sudoku[block_x + delta_x][block_y + delta_y] != '-') { used |= state[block_x + delta_x][block_y + delta_y]; }
}
if (set != (1 << 16) - 1)
{
memcpy(state, state_history[0][depth], sizeof(state));
memcpy(sudoku, sudoku_history[0][depth], sizeof(sudoku));
return false;
}
while (locked)
{
int temp = locked & -locked;
if (!(used & temp))
{
for (int j = 0; j < 16; j++)
{
int block_x = i / 4 * 4, block_y = i % 4 * 4,
delta_x = j / 4, delta_y = j % 4;
if (state[block_x + delta_x][block_y + delta_y] & temp)
{
update_state(block_x + delta_x, block_y + delta_y, int(log2(temp)));
n--;
break;
}
}
}
locked -= temp;
}
}
if (n == 0) { return true; }
int x, y, min_ = INT_MAX, min_state;
for (int i = 0; i < 16; i++)
{
for (int j = 0; j < 16; j++)
{
if (sudoku[i][j] != '-') { continue; }
if (ones[state[i][j]] < min_)
{
min_ = ones[state[i][j]];
x = i;
y = j;
min_state = state[i][j];
}
}
}
memcpy(state_history[1][depth], state, sizeof(state));
memcpy(sudoku_history[1][depth], sudoku, sizeof(sudoku));
while (min_state)
{
int temp = min_state & -min_state, num = int(log2(temp));
update_state(x, y, num);
if (dfs(n - 1)) { return true; }
memcpy(state, state_history[1][depth], sizeof(state));
memcpy(sudoku, sudoku_history[1][depth], sizeof(sudoku));
min_state -= temp;
}
memcpy(state, state_history[0][depth], sizeof(state));
memcpy(sudoku, sudoku_history[0][depth], sizeof(sudoku));
return false;
}
void show()
{
for (int i = 0; i < 16; i++)
{
for (int j = 0; j < 16; j++) { cout << sudoku[i][j]; }
cout << endl;
}
}
如果想要找简单一点的练手题, 那么推荐 ( 还是数独 ) P3032 Binary Sudoku G , 只需要把每一行, 每一列, 每一宫压成一个状态就可以了
朴素 BFS
BFS , 全称 Breadth-First Search , 即广度优先搜索, 在无权图最短路中有广泛的应用, 它的三个部分与 DFS 是相同的, 只需要手动维护一个队列
BFS 有两个性质:
- 两段性: BFS 队列中同时只能存在两种不同阶段的状态
- 单调性: 简单来说, 即相同状态都在一段中
P1332 血色先锋队是多源 BFS 模版题, 与普通的 BFS 区别不大, 只需要在开始 BFS 前, 在队列中将多个起点全部推进去即可, 是很灵活的一种变体
我们可以使用 distance_ 数组代替标记数组, 将初始的距离设为 1 , 最后输出时再减去 1 即可, 代码如下:
int main()
{
cin >> n >> m >> a >> b;
for (int i = 1; i <= a; i++)
{
cin >> x >> y;
q.emplace(x, y);
distance_[x][y] = 1;
}
while (!q.empty())
{
auto temp = q.front();
q.pop();
for (auto offset : offsets)
{
int next_x = temp.first + offset.first, next_y = temp.second + offset.second;
if (next_x > n || next_x < 1 || next_y > m || next_y < 1 || distance_[next_x][next_y]) { continue; }
distance_[next_x][next_y] = distance_[temp.first][temp.second] + 1;
q.emplace(next_x, next_y);
}
}
for (int i = 1; i <= b; i++)
{
cin >> x >> y;
cout << distance_[x][y] - 1 << endl;
}
return 0;
}
A*
虽然都冠以 A*之名, 但是它实际与 IDA*并无太大的关联, 只是都有一个估值函数
A* 的主要优化方式是, 估值函数和对应状态离目标状态的步数呈正相关, 因此先遍历估值函数小的状态, 这也可以算是一种对遍历顺序的优化, 所以我们可以将 BFS 的队列改成优先队列 ( 小根堆 ) , 将估值作为第一关键字即可, 正确性显然
要注意的是, A* 的估值函数无需保证大于真实值, 但是如果设计不得当会影响复杂度
接下来看一道例题: UVA11367 Full Tank?
首先考虑估值函数的建立, 比较显然的, 直接以最小可能价格作为估值即可
为了确保 BFS 的两段性, 我们可以用类似多重背包转 01 背包的方式, 将每次加 k 单位的油转化成加 k 次 1 单位油, 这样做需要注意, 可能会多次到达一个加油站 ( 或者根本没走就进入下一次循环 ) , 因此标记是否走过的数组和距离数组需要额外开一维
同时我们显然还要存储油箱中剩余的油, 和我们所处的位置, 但是这两个关键字的顺序并不重要, 剩余一些无关紧要的变量含义如下:
vertex和edge分别是顶点数和边数prices是每个加油站每单位油的价格from,to和weight分别是一条边的起点, 终点和耗油量 ( 边权 )tank,start,end是每次询问的油箱最大容量, 起点和终点
得到如下的数组定义:
priority_queue<tuple<int, int, int>, vector<tuple<int, int, int> >, greater<> > q;
vector<pair<int, int> > edges[1001];
bool visited[1001][101];
int vertex, edge, prices[1001], from, to, weight, tank, start, end_, query, distance_[1001][101];
容易得到 BFS 过程如下:
bool bfs(int max_tank, int base, int target)
{
q.emplace(0, base, 0);
distance_[base][0] = 0;
while (!q.empty())
{
int cost = get<0>(q.top()), location = get<1>(q.top()), usage = get<2>(q.top());
q.pop();
if (location == target) { return true; }
if (visited[location][usage]) { continue; }
visited[location][usage] = true;
if (usage < max_tank) // 只有没超过油箱上限才可以加油
{
int next_usage = usage + 1, next_cost = cost + prices[location]; // 加油时位置不变
if (next_cost < distance_[location][next_usage])
{
distance_[location][next_usage] = next_cost;
q.emplace(next_cost, location, next_usage);
}
}
for (auto next : edges[location])
{
if (usage >= next.second) // 油够才可以走这条边
{
int next_usage = usage - next.second;
if (cost < distance_[next.first][next_usage])
{
distance_[next.first][next_usage] = cost;
q.emplace(cost, next.first, next_usage);
}
}
}
}
return false;
}
注意到, 将估值函数设为当前节点到起点的最短路的长度, 这个算法就是 Dijkstra 算法
状态设计的艺术
上面这些优化技巧其实都缺少非常本质的一部分, 如题, 与 DP 类似, 搜索的状态设计也有一定套路, 当然, 一般的思路也是 “不会就加一维” , 下面列举几个我个人认为比较优雅的状态定义, 以期读者能有所启发:
UVA589 Pushing Boxes 非常有趣的一道题 , 比较显然的状态设计是用四元组
表示人和箱子的位置, 但维度太高, 复杂度不能接受, 考虑箱子被推时人一定在箱子旁边, 可将后两维压缩成 “方位” , 即三元组 这题的另一个难点是维护 BFS 过程中的单调性 ( 见 [朴素 BFS](#朴素 BFS) 一节 ) , 解决方案是使用 BFS 套 BFS , 外层搜索箱子的移动, 内层搜索要使箱子做此移动所需的人的移动, 这样相当于维护了二元组
的单调性 UVA1505 Flood-it! 这题的状态是个标记数组, 但有三种类型的标记, 已染色, 紧挨着已染色的未染色, 和其它未染色, 其中第二种是为了每次快速扩展染色块的边界, 填充函数只以有第二种标记的格点为起点; 一个额外的优点是, 这样实现可以不用对原数组进行更改, 当然, 不是必须这样做
状态是二进制串, 即状态压缩, 似乎可以解决类旅行商问题 ( 正常是 DP 可解的问题 )
总结
搜索的本质是遍历, 遍历中籍由的线性数据结构不同, 所表现出来的搜索形式也就不同, 借助于栈 ( 函数调用栈 ) 实现的是 DFS , 依托于普通队列的是 BFS , 而利用双端队列 deque 的则是 01-BFS ( 文中没有介绍, 这是一种在只有两种边权的图上的priority_queue 的是 A* , 诸如此类
因此, 更抽象一些, 我们得到搜索的通用框架:
container<state> c;
c.emplace(first_state);
while (!c.empty())
{
state current_state = c.front();
c.pop_front();
do_task();
for (state next_state : next_states)
{
if (is_valid(next_state)) { c.emplace(next_state); }
}
}
搜索优化的本质是缩小每一步中的 next_states , 或减小 do_task 的复杂度, 但一般前一种效果更明显 ( 指数级增长使得单步的复杂度没那么重要 )