双向搜索
双向同时搜索
即从起点与终点同时进行bfs或dfs，如果发现搜索两端相遇，则可以认为是获得了可行解
双向广搜
双向广搜维护两个队列，并轮流拓展；或者维护一个并给不同标记
同时用数组或哈希表记录搜索情况，给从两个方向拓展的节点以不同标记，当某点被两种标记同时标记时，搜索结束
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
将开始结点和目标结点加入队列 q
标记开始结点为 1
标记目标结点为 2
while (队列 q 不为空)
{
从 q.front() 扩展出新的 s 个结点
如果 新扩展出的结点已经被其他数字标记过
那么 表示搜索的两端碰撞
那么 循环结束
如果 新的 s 个结点是从开始结点扩展来的
那么 将这个 s 个结点标记为 1 并且入队 q
如果 新的 s 个结点是从目标结点扩展来的
那么 将这个 s 个结点标记为 2 并且入队 q
}双向迭代加深
迭代加深：控制dfs的最大深度，若深度超过最大深度就返回，某个深度搜完没得到答案就令最大深度+1，重新开始搜索
双向迭代加深就是从两个方向迭代加深搜索
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int D;
bool found;
template <class T>
void dfs(T x, int d, int dir)
{
if (H[x] + dir == 3)
found = true;
H[x] = dir;
if (d == D)
return;
// 这里需要递归搜索当前状态能够转移到的新状态
}
// 在main函数中...
while (D <= MAXD / 2) // MAXD为题中要求的最大深度
{
dfs(st, 0, 1); // st为起始状态
if (found)
// ...
// 题中所给最大深度为奇数时这里要判断一下
dfs(ed, 0, 2); // ed为终止状态
if (found)
// ...
D++;
}Meet In the Middle
思想：将整个搜索过程分成两半分别搜索，最后合并
方法：分别搜索前一半，把状态放入a数组，搜索后一半，把状态放入b数组，最后统计答案
合并时可以通过排序使一部分有序，再通过二分等合并答案
解决问题：可以解决一些统计方案，但暴搜会TLE的题
模板 P4799 世界冰球锦标赛
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int N = 2e5 + 10;
const int mod = 1e9 + 7;
vector<ll> arr, a, b;
ll n, m;
void dfs(ll l, ll r, ll sum, ll sign){
if(sum>m){
return ;
}
// 搜索到达另一半
if(l>r){
// 结果放入左边
if(sign==0){
a.push_back(sum);
}
// 结果放入右边
else if (sign==1){
b.push_back(sum);
}
return ;
}
dfs(l+1,r,sum+arr[l],sign); // 选
dfs(l+1,r,sum,sign); // 不选
}
void solve() {
cin >> n >> m;
arr = vector<ll> (n+1);
for (int i= 1;i<=n;i++) cin >> arr[i];
dfs(1, n/2, 0, 0); // 搜前半
dfs(n/2+1, n, 0, 1); // 搜后半
sort(a.begin(), a.end()); // 对前半排序，以便后面的upperbound
ll ans = 0;
// 按一边的状态进行二分，找减去的另一半，由于相等也取，故upperbound
for (int i = 0;i<b.size();i++){
ans += upper_bound(a.begin(), a.end(), m-b[i]) - a.begin();
}
cout << ans;
}
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int tomorin=1;
//cin >> tomorin;
while (tomorin--) solve();
return 0;
}