跳转至

雙向搜索

本頁面將簡要介紹兩種雙向搜索算法：「雙向同時搜索」和「Meet in the middle」。

雙向同時搜索

定義

雙向同時搜索的基本思路是從狀態圖上的起點和終點同時開始進行 廣搜 或 深搜。

如果發現搜索的兩端相遇了，那麼可以認為是獲得了可行解。

過程

雙向廣搜的步驟：

 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
}

Meet in the middle

Warning

本節要介紹的不是 二分搜索（二分搜索的另外一個譯名為「折半搜索」）。

引入

Meet in the middle 算法沒有正式譯名，常見的翻譯為「折半搜索」、「雙向搜索」或「中途相遇」。

它適用於輸入數據較小，但還沒小到能直接使用暴力搜索的情況。

過程

Meet in the middle 算法的主要思想是將整個搜索過程分成兩半，分別搜索，最後將兩半的結果合併。

性質

暴力搜索的複雜度往往是指數級的，而改用 meet in the middle 算法後複雜度的指數可以減半，即讓複雜度從 \(O(a^b)\) 降到 \(O(a^{b/2})\)。

例題

例題 「USACO09NOV」燈 Lights

有 \(n\) 盞燈，每盞燈與若干盞燈相連，每盞燈上都有一個開關，如果按下一盞燈上的開關，這盞燈以及與之相連的所有燈的開關狀態都會改變。一開始所有燈都是關着的，你需要將所有燈打開，求最小的按開關次數。

\(1\le n\le 35\)。

解題思路

如果這道題暴力 DFS 找開關燈的狀態，時間複雜度就是 \(O(2^{n})\), 顯然超時。不過，如果我們用 meet in middle 的話，時間複雜度可以優化至 \(O(n2^{n/2})\)。meet in middle 就是讓我們先找一半的狀態，也就是找出只使用編號為 \(1\) 到 \(\mathrm{mid}\) 的開關能夠到達的狀態，再找出只使用另一半開關能到達的狀態。如果前半段和後半段開啓的燈互補，將這兩段合併起來就得到了一種將所有燈打開的方案。具體實現時，可以把前半段的狀態以及達到每種狀態的最少按開關次數存儲在 map 裏面，搜索後半段時，每搜出一種方案，就把它與互補的第一段方案合併來更新答案。

參考代碼 
 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
54
55
56
57
#include <algorithm>
#include <cstdio>
#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] |= ((long long)1 << v);
    a[v] |= ((long long)1 << 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((((long long)1 << n) - 1) ^ t))
      ans = min(ans, cnt + f[(((long long)1 << n) - 1) ^ t]);
  }

  cout << ans;

  return 0;
}

外部鏈接

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：FFjet, ChungZH, frank-xjh, hsfzLZH1, Xarfa, AndrewWayne
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用