双向搜索

双向搜索 (Meet in the Middle / Bidirectional BFS)

核心思想

双向同时搜索：从起点和终点同时 BFS/DFS，两端相遇时即得可行解，搜索树大小大幅减小。

Meet in the Middle（折半搜索 / 中途相遇）：将搜索过程分成两半，分别搜索，最后合并结果。适用于输入数据较小但不足以直接暴力的场景（如 $n\le 40$）。

复杂度

暴力 $O(a^b)$ → Meet in the Middle $O(a^{b/2})$。

实现（折半枚举 — P2962 开关灯）

#include <algorithm>
#include <iostream>
#include <map>
using namespace std;
 
int n, m, ans = 0x7fffffff;
map<long long, int> f;
long long a[40];
 
int main() {
  cin >> n >> m;
  a[0] = 1;
  for (int i = 1; i < n; ++i) a[i] = a[i - 1] * 2;
  for (int i = 1; i <= m; ++i) {
    int u, v; cin >> u >> v;
    --u; --v;
    a[u] |= (1ll << v);
    a[v] |= (1ll << u);
  }
  // 前半
  for (int i = 0; i < (1 << (n / 2)); ++i) {
    long long t = 0; int cnt = 0;
    for (int j = 0; j < n / 2; ++j)
      if ((i >> j) & 1) t ^= a[j], ++cnt;
    if (!f.count(t)) f[t] = cnt;
    else f[t] = min(f[t], cnt);
  }
  // 后半
  for (int i = 0; i < (1 << (n - n / 2)); ++i) {
    long long t = 0; int cnt = 0;
    for (int j = 0; j < (n - n / 2); ++j)
      if ((i >> j) & 1) t ^= a[n / 2 + j], ++cnt;
    if (f.count(((1ll << n) - 1) ^ t))
      ans = min(ans, cnt + f[((1ll << n) - 1) ^ t]);
  }
  cout << ans;
  return 0;
}

练习

题目	说明
P2962 USACO 灯 Lights	折半枚举，$n\le 35$
P4799 冰球	meet in the middle 经典

相关链接

路径D-DSA算法刷题 | A星算法 | IDA星算法

来源：OI-wiki 双向搜索

多平台练习

| 洛谷 | 本题单 | 竞赛基础 |
| POJ (北大) | PKU JudgeOnline | 经典题目，适合巩固 |
| HDU (杭电) | HDU OJ | 暑期多校训练 |
| Codeforces | Codeforces | 国际竞赛，适合提升 |