算法【双向广搜】
双向广搜常见用途
1：小优化。bfs的剪枝策略，分两侧展开分支，哪侧数量少就从哪侧展开。
2：用于解决特征很明显的一类问题。特征：全量样本不允许递归完全展开，但是半量样本可以完全展开。过程：把数据分成两部分，每部分各自展开计算结果，然后设计两部分结果的整合逻辑。
下面通过几个题目加深理解。
题目一
测试链接：https://leetcode.cn/problems/word-ladder
分析：这个就是双向广搜的第一个用途。分别从beginWord和endWord开始广度优先遍历，得到转换成的单词序列，对于得到的两个单词序列，选择单词数较少的，再次使用广度优先遍历。当得到的单词序列中，有和另一序列中重复的单词，代表beginWord可以转化成endWord。如果广度优先遍历的次数大于wordList的长度加1则代表不能转换。代码如下。
class Solution {
public:
set<string> beginLevel;
set<string> endLevel;
set<string> nextLevel;
set<string> dict;
void build(string beginWord, string endWord, vector<string>& wordList){
int length = wordList.size();
for(int i = 0;i < length;++i){
dict.insert(wordList[i]);
}
beginLevel.insert(beginWord);
endLevel.insert(endWord);
}
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
build(beginWord, endWord, wordList);
set<string> temp;
int ans = 0;
string cur;
char cur_char;
int cur_length;
if(dict.count(endWord) == 0){
return ans;
}
ans += 2;
while (true)
{
if(beginLevel.size() <= endLevel.size()){
for(set<string>::iterator it = beginLevel.begin();it != beginLevel.end();++it){
cur = *it;
cur_length = cur.size();
for(int i = 0;i < cur_length;++i){
cur_char = cur[i];
for(char j = 'a';j <= 'z';++j){
cur[i] = j;
if(dict.count(cur) != 0 && j != cur_char){
if(endLevel.count(cur) != 0){
return ans;
}else{
nextLevel.insert(cur);
}
}
}
cur[i] = cur_char;
}
}
temp = beginLevel;
beginLevel = nextLevel;
nextLevel = temp;
nextLevel.clear();
++ans;
}else{
for(set<string>::iterator it = endLevel.begin();it != endLevel.end();++it){
cur = *it;
cur_length = cur.size();
for(int i = 0;i < cur_length;++i){
cur_char = cur[i];
for(char j = 'a';j <= 'z';++j){
cur[i] = j;
if(dict.count(cur) != 0 && j != cur_char){
if(beginLevel.count(cur) != 0){
return ans;
}else{
nextLevel.insert(cur);
}
}
}
cur[i] = cur_char;
}
}
temp = endLevel;
endLevel = nextLevel;
nextLevel = temp;
nextLevel.clear();
++ans;
}
if(ans > wordList.size()+1){
break;
}
}
return 0;
}
};其中，采用哈希表来快速判断是否有重复单词。
题目二
测试链接：https://www.luogu.com.cn/problem/P4799
分析：这个就是双向广搜的第二个用途。刚拿到这个题，会很容易地想到使用动态规划，但是一看到数据量就知道一定会超时。而将每场门票分成两部分，分别使用广度优先搜索，得到每一种搭配的花费。对这两部分使用广度优先搜索得到的搭配，从小到大排序后使用双指针即可得到所有方案的个数。代码如下。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int N;
long long M;
long long price[40];
vector<long long> l;
vector<long long> r;
void f(int i, int e, long long sum, long long bound, vector<long long> &ans){
if(sum > bound){
return ;
}
if(i == e){
ans.push_back(sum);
}else{
f(i+1, e, sum, bound, ans);
f(i+1, e, sum+price[i], bound, ans);
}
}
int main(void){
int middle;
long long left, right;
long long l_length, r_length;
long long ans = 0;
scanf("%d%ld", &N, &M);
for(int i = 0;i < N;++i){
scanf("%ld", &price[i]);
}
middle = N / 2;
f(0, middle, 0, M, l);
f(middle, N, 0, M, r);
sort(l.begin(), l.end());
sort(r.begin(), r.end());
l_length = l.size();
r_length = r.size();
left = 0;
right = r_length-1;
for(;left < l_length && right >= 0;++left){
while (right >= 0 && l[left] + r[right] > M)
{
--right;
}
if(right >= 0){
ans += (right + 1);
}
}
printf("%ld", ans);
}其中，f函数是一个递归函数，代表下标从i到e，当前和为sum，不能超过bound的搭配的花费，将花费存储在ans数组中；得到了l和r两个花费数组后排序，然后利用双指针，搭配数组两边之和不超过bound就代表是一种方案。
题目三
测试链接：https://leetcode.cn/problems/closest-subsequence-sum
分析：这道题和题目二基本一致。主体代码相同，只是求的东西不一样。代码如下。
class Solution {
public:
vector<int> l;
vector<int> r;
void f(int i, int e, int sum, int bound, vector<int> &ans, vector<int>& nums){
if(i == e){
ans.push_back(sum);
}else{
f(i+1, e, sum, bound, ans, nums);
f(i+1, e, sum+nums[i], bound, ans, nums);
}
}
int minAbsDifference(vector<int>& nums, int goal) {
int length = nums.size();
int ans = -((1 << 31) + 1);
f(0, length/2, 0, goal, l, nums);
f(length/2, length, 0, goal, r, nums);
sort(l.begin(), l.end());
sort(r.begin(), r.end());
int l_length = l.size();
int r_length = r.size();
int left = 0, right = r_length-1;
for(;left < l_length && right >= 0;++left){
while (right >= 0 && l[left] + r[right] > goal)
{
--right;
}
if(right >= 0){
ans = ans < abs(l[left] + r[right] - goal) ? ans : abs(l[left] + r[right] - goal);
if(right < r_length-1){
ans = ans < abs(l[left] + r[right+1] - goal) ? ans : abs(l[left] + r[right+1] - goal);
}
}else{
ans = ans < abs(l[left] + r[0] - goal) ? ans : abs(l[left] + r[0] - goal);
}
}
return ans;
}
};其中，主体代码也是利用f函数得到搭配序列，然后排序，使用双指针得到结果。