算法【双向广搜】

双向广搜常见用途

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函数得到搭配序列，然后排序，使用双指针得到结果。