Skip to content

Bidirectional Search

This page briefly introduces two bidirectional search algorithms: "Bidirectional Simultaneous Search" and "Meet in the Middle".

Definition

The basic idea of bidirectional simultaneous search is to perform BFS or DFS simultaneously from both the start and end points in the state graph.

If the two search frontiers meet, a feasible solution is considered to have been found.

Process

Steps for bidirectional BFS:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
Add the start node and target node to queue q
Mark the start node as 1
Mark the target node as 2
while (queue q is not empty)
{
  Expand new s nodes from q.front()

  If the newly expanded nodes have already been marked by the other number
    Then the two search frontiers have collided
    Then end the loop

  If the new s nodes are expanded from the start node
    Then mark these s nodes as 1 and enqueue them into q

  If the new s nodes are expanded from the target node
    Then mark these s nodes as 2 and enqueue them into q
}

Example Problem

Example Eight Digits Puzzle

On a \(3\times 3\) board, there are eight pieces, each marked with a number from \(1\) to \(8\). There is one empty space on the board, represented by \(0\). Pieces adjacent to the empty space can be moved into it. The problem is: given an initial layout (initial state) and a target layout (for simplicity, let the target state be \(123804765\)), find a method to move from the initial layout to the target layout with the minimum number of steps.

Solution Idea

It is easy to think of a brute-force BFS. Using brute-force BFS for this problem will not time out. However, it is used here as an example of bidirectional simultaneous search. We can use two BFS: one starting from the initial state and searching forward, and the other starting from the target state and searching backward. Alternating between the two BFS significantly reduces the size of the search tree. When one BFS finds a state already discovered by the other BFS, the answer is obtained.

Reference Code 
 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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <iostream>
#include <map>
#include <queue>
#include <string>
using namespace std;

struct State {
  int A[3][3];
  State() = default;

  State(string s) {
    for (int i = 0; i < 3; i++) {
      for (int j = 0; j < 3; j++) {
        A[i][j] = s[i * 3 + j] - '0';
      }
    }
  }

  friend bool operator<(const State &a, const State &b) {
    for (int i = 0; i < 3; i++) {
      for (int j = 0; j < 3; j++) {
        if (a.A[i][j] != b.A[i][j]) {
          return a.A[i][j] < b.A[i][j];
        }
      }
    }
    return false;
  }
};

int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

void bfs(queue<State> &q, map<State, int> &m1, map<State, int> &m2) {
  auto u = q.front();
  q.pop();
  int xx, yy;
  for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 3; j++) {
      if (u.A[i][j] == 0) {
        xx = i;
        yy = j;
      }
    }
  }
  for (int i = 0; i < 4; i++) {
    int tx = dir[i][0] + xx, ty = dir[i][1] + yy;
    if (tx >= 0 && tx < 3 && ty >= 0 && ty < 3) {
      auto v = u;
      swap(v.A[xx][yy], v.A[tx][ty]);
      if (m2.count(v)) {
        cout << m1[u] + m2[v] << endl;
        exit(0);
      }
      if (!m1.count(v)) {
        m1[v] = m1[u] + 1;
        q.push(v);
      }
    }
  }
}

int main() {
  string I, O;
  cin >> I;
  O = "123804765";
  State in = I, ou = O;
  queue<State> q1, q2;
  map<State, int> mp1, mp2;
  q1.push(in);
  mp1[in] = 0;
  q2.push(ou);
  mp2[ou] = 1;
  if (I == O) {
    cout << 0;
    return 0;
  }
  while (1) {
    bfs(q1, mp1, mp2);
    bfs(q2, mp2, mp1);
  }
  return 0;
}

Meet in the Middle

Warning

This section does not introduce Binary Search (another translation for binary search is "half-interval search").

Introduction

The Meet in the Middle algorithm has no formal translation; common translations include "half-interval search", "bidirectional search", or "meet in the middle".

It is suitable when the input data is relatively small but not small enough to allow direct brute-force search.

Process

The main idea of the Meet in the Middle algorithm is to split the entire search process into two halves, search each half separately, and finally merge the results from both halves.

Properties

The complexity of brute-force search is often exponential. By using the meet in the middle algorithm, the exponent can be halved, reducing the complexity from \(O(a^b)\) to \(O(a^{b/2})\).

Example Problem

Example 「USACO09NOV」Lights

There are \(n\) lights, each connected to several other lights. Each light has a switch. Pressing the switch on a light will toggle the state of that light and all lights connected to it. Initially, all lights are off. You need to turn on all lights. Find the minimum number of switch presses required.

\(1\le n\le 35\).

Solution Idea

If we use brute-force DFS to search for the switch states, the time complexity would be \(O(2^{n})\), which is clearly too slow. However, if we use meet in the middle, the time complexity can be optimized to \(O(n2^{n/2})\). Meet in the middle involves first finding the states achievable using only the switches numbered from \(1\) to \(\mathrm{mid}\), and then finding the states achievable using only the other half of the switches. If the lights turned on in the first half and the second half are complementary, merging these two halves gives a solution to turn on all lights. In implementation, we can store the states from the first half and the minimum number of switch presses to reach each state in a map. When searching the second half, for each state found, we merge it with the complementary state from the first half to update the answer.

Reference Code 
 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
#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;  // Perform preprocessing

  for (int i = 1; i <= m; ++i) {  // Process the input edges
    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) {  // Search the first half
    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) {  // Search the second half
    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 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用