DFS pruning and searching

The first thing to ensure in designing DFS search is to design a reasonable search order that can cover all States.

However, the number of DFS search States increases exponentially, and some of these states are 'useless'. Therefore, we need to reduce the search states through pruning strategy to improve the efficiency of DFS

The pruning strategies of DFS can be divided into five categories:

Optimize search order
Eliminate equivalent redundancy
Feasible pruning
Optimal pruning
Memory search (DP)

Memory search is mainly used in DP.

For the topic to be searched by DFS, we can explore various properties of the topic from the above angles, so as to reduce the number of search schemes and optimize the complexity of search

Examples

The kitten climbed the mountain

Title Link]

After reading the meaning of the question, we can design the search order in this way:

Each cat is regarded as the number of search layers to see which cable car the cat can put in

For each kitten, there are two placement strategies:

Put the kitten in the rented cable car
Put the kitten in the new cable car

This search order can cover all possibilities. After determining the search order, analyze pruning

prune:

Optimize search order:

Search for large cats first, then the number of cats stored in the cable car will be less, and the search scheme will be less

Eliminate equivalent redundancy:

There is no equivalent redundancy in the search order of this question, so we can't cut in from this angle

Feasible pruning:

Only the free capacity of the current cable car is greater than the volume of a kitten

Optimal pruning:

First of all, the answer will certainly not exceed the number of cats

Secondly, when the search result is greater than the answer, the current scheme will not be the optimal solution, so you can end the search in advance and prune

Finally, we can write the code of this problem according to these analyses

#include <iostream>
#include <algorithm>
using namespace std;

constexpr int N = 20;
int c[N], n, m, res;
int w[N];

void dfs(int u, int cat) {
    // Optimal pruning
    if (u >= res) return;
    // Place the last kitten
    if (cat > n) {
        res = u;
        return;
    }

    for (int i = 1; i <= u; i++) {
        if (w[i] >= c[cat]) { // Feasible pruning
            w[i] -= c[cat];
            dfs(u, cat + 1);
            w[i] += c[cat];
        }
    }
    w[u + 1] -= c[cat];
    dfs(u + 1， cat + 1);
    w[u + 1] += c[cat];
}

int main() {
    cin >> n >> m;
    fill(w, w + N, m);
    res = n;
    for (int i = 1; i <= n; i++) cin >> c[i];
    // Optimize search order
    // Because the larger the size of the cat, the fewer nodes below and the fewer search states
    sort(c + 1, c + n + 1, greater<int>());
    dfs(1, 1);

    cout << res << '\n';

    return 0;
}

Divided into coprime groups

Title Link

There are two possible search sequences for this question:

Fix the group and see what numbers can be put into this group
Fixed number, see which groups this number can be put into

For these two search sequences, it is impossible to start from the perspective of optimizing the search sequence and eliminating equivalent redundancy. Next, we will analyze the pruning strategies of these two search sequences

Sequence 1: fixed group

Search order: enumerate all elements in turn to see if they can join the current group, otherwise open a new group and save this element

prune:

Feasible pruning:

Judge whether the current element can be placed in the group. If so, store the element in the current group and continue to search downward

Optimal pruning:

If the current answer is greater than the optimal answer, there is no need to continue the downward search

#include <iostream>
using namespace std;
constexpr int N = 14;
int a[N], n, ans, group[N][N];
bool st[N]; // Mark whether the i th element belongs to a group

int gcd(int a, int b) {return b ? gcd(b, a % b) : a; }

inline bool check(int g[], int n, int x) {
    for (int i = 0; i < n; i++)
        if (gcd(g[i], x) > 1) return 0;
    return 1;
}

void dfs(int u, int c, int sum, int start) {
    // Optimal pruning
    if (u >= ans) return;
    if (sum == n) {
        ans = u;
        return;
    }

    bool ok = 1;
    for (int i = start; i < n; i++) 
        // Feasible pruning
        if (!st[i] && check(group[u], c, a[i])) {
            st[i] = 1;
            group[u][c] = a[i];
            dfs(u, c + 1, sum + 1, i + 1);
            st[i] = 0;
            ok = 0;
        }
    if (ok) dfs(u + 1, 0, sum, 0);
}


int main() {
    cin >> n;
    ans = n;
    for (int i = 0; i < n; i++) cin >> a[i];
    dfs(1, 0, 0, 0);

    cout << ans << '\n';
    return 0;
}

Sequence 2: fixed elements

Search order: for the current element, see whether it can be put into the existing group, or open a new group to save the element

prune:

Optimize search order:

When working with groups,

Feasible pruning:

If the current element can be stored in the group, save the element to continue the search

Optimal pruning:
If the current answer is greater than the optimal answer, there is no need to continue the downward search
If the current element can be placed in an existing group, there is no need to search for other existing groups

#include <iostream>
#include <vector>
using namespace std;
using VI = vector<int>;

constexpr int N = 11;
int a[N], w[N], n, res;
VI g[N];
bool st[N];

int gcd(int x, int y) { return y ? gcd(y, x % y) : x; }

inline bool check(VI g, int x) {
    for (int i : g)
        if (gcd(i, x) > 1)
            return 0;
    return 1;
}

void dfs(int u, int num) {
    // Optimal pruning
    if (u >= res) return;
    if (num >= n) {
        res = u;
        return;
    }

    int c = a[num];
    for (int i = 1; i <= u; i++) {
        // Feasible pruning
        if (check(g[i], c)) {
            /* If an element can be put into a group, put it directly,
             * There is no need to consider whether it can be put into other groups
             */
            g[i].push_back(c);
            dfs(u, num + 1);
            g[i].pop_back();

            break;
        }
    }

    g[u + 1].push_back(c);
    dfs(u + 1, num + 1);
    g[u + 1].pop_back();
}

int main() {
    scanf("%d", &n);
    // A little pruning
    res = n;
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    dfs(1, 0);

    cout << res << '\n';

    return 0;
}

Summary of this topic

Although the pruning strategies of the two search orders are not much different, the speed of order 2 is more than \ (30 \) times that of order 1. It can also be seen that the selection of search order is also extremely important to the speed of DFS

Sudoku

Title Link

This problem not only needs pruning, but also needs small skills such as binary state representation

Search order:

Select one of the nine palaces and fill it up. Then select another one to fill it up

prune:

Optimize search order:

Select the most filled grid each time, because the more grids you have selected, the less you may enumerate later

Feasible pruning:

The number \ (x \) has not been filled in the column, row and Jiugong grid of the current position, so this number can be filled in

Other optimizations:

For each column, row, and Jiugong grid filled with numbers, we can use binary to represent it. 1 represents every day, and 0 represents filled
For finding the number of unfilled numbers in a nine house lattice, we can preprocess all binary states in advance and count the number of 1s in each state
To judge whether the current grid can be filled in, we can go to the state of the row, column and Jiugong grid where the grid is located, and get the number with only one 1 in the binary. Find the position where 1 appears and add 1. The result is the number that can be filled in. Similarly, the position of 1 in this state can also be preprocessed in advance
lowbit can be used to quickly calculate the position of numbers that can be filled in a state

#include <bits/stdc++.h>
using namespace std;

constexpr int N = 9, M = 1 << N;

int row[N], col[N], f[3][3];
char s[N * N + 5];
int loc[M], Count[M];

inline int lowbit(int x) { return x & -x; }

inline void init() {
  for (int i = 0; i < N; i++) col[i] = row[i] = (1 << N) - 1;
  for (int i = 0; i < 3; i++)
    for (int j = 0; j < 3; j++) f[i][j] = (1 << N) - 1;
}

int get(int x, int y) { return row[x] & col[y] & f[x / 3][y / 3]; }

inline void update(int x, int y, int v, bool type) {
  if (type) {
    s[x * N + y] = '1' + v;
  } else s[x * N + y] = '.';

  int t = 1 << v;
  if (!type) t = -t;

  row[x] -= t;
  col[y] -= t;
  f[x / 3][y / 3] -= t;
}

bool dfs(int cnt) {
  if (!cnt) return 1;
  int x, y, maxv = 12;
  for (int i = 0; i < N; i++)
    for (int j = 0; j < N; j++) {
      if (s[i * N + j] != '.') continue;
      int n = Count[get(i, j)];
      if (n < maxv) maxv = n, x = i, y = j;
    }

  for (int i = get(x, y); i; i -= lowbit(i)) {
    int c = loc[lowbit(i)];
    update(x, y, c, 1);
    if (dfs(cnt - 1)) return 1;
    update(x, y, c, 0);
  }

  return 0;
}

int main() {
  for (int i = 0; i < N; i++) loc[1 << i] = i;
  for (int i = 0; i < 1 << N; i++)
    for (int j = i; j; j -= lowbit(j)) Count[i]++;

  while(cin >> s && s[0] != 'e') {
    init();
    int cnt = 0;
    for (int i = 0; i < N; i++)
      for (int j = 0; j < N; j++) if (s[i * N + j] != '.') {
        update(i, j, s[i * N + j] - '1', 1);
      } else cnt++;
    dfs(cnt);

    puts(s);
  }

  return 0;
}

stick

Title Link

Here, the short one is called a wooden stick, and the long one after composition is called a wooden stick

Search order:

First, the length of the search stick must be the factor of the length of all sticks, so we can enumerate the factor of the total length of sticks as the length of sticks to search. The problem is to let different groups of sticks weigh several groups of the same length

We can enumerate all the sticks in turn. If the current stick can be put into the current stick group, put it into the group and continue to search for the next stick; Otherwise, put it in the next group and search from the beginning for the sticks that have not been put in.

Search order:

Optimize search order:

When searching, start searching according to the length of the stick from large to small, then the available space of the stick will be less, and the corresponding search status will be reduced

Eliminate equivalent redundancy:

Search from small to large according to the subscript of the stick, so as to avoid equivalent redundancy (enumeration by combination)

Feasible pruning:
Set the length of enumeration sticks as \ (len \) and the number of groups of sticks as \ (n \). If there is \ (n \ times len > sum \), the status must be illegal
If a stick of a certain length cannot be put in, then the stick of the same length behind it cannot be put in
If the length of the first stick is greater than the length of the stick, the scheme must be illegal
If the placement of the last stick \ (x \) fails, the scheme must also be illegal (counter evidence: if there are other groups that can make the placement of \ (x \) successful, change the placement order of the sticks and make \ (x \) the last stick, which is inconsistent with the previous conclusion)

#include <iostream>
#include <algorithm>
using namespace std;
constexpr int N = 210;

int n, a[N], sum, len;
bool st[N];

bool dfs(int u, int start, int size) {
    if (len * u == sum) return 1;
    if (size == len) return dfs(u + 1, 0, 0);

    for (int i = start; i < n; i++) {
        // Feasible pruning
        if (st[i] || a[i] + size > len) continue;
        st[i] = 1;
        if (dfs(u, start + 1, size + a[i])) return 1;
        st[i] = 0;
        if (!size || size + a[i] == len) return 0;
        int j = i;
        while (j < n && a[i] == a[j]) j++;
        i = j - 1;
    }
    return 0;
}

int main() {
    while (scanf("%d", &n) != EOF && n) {
        // init
        fill(st, st + n + 1, 0);
        sum = 0, len = 0;
        for (int i = 0; i < n; i++) cin >> a[i], sum += a[i];
        // Optimize search order
        sort(a, a + n, greater<int>());

        while (++len <= sum) {
            if (sum % len == 0 && dfs(1, 0, 0)) {
                printf("%d\n", len);
                break;
            }
        }
    }

    return 0;
}

birthday cake

Original question link

Topic analysis:

There are two search orders for cakes: top-down and bottom-up. Since the given volume is fixed and the volume is reduced from bottom to top, we should select the second search order to reduce the enumeration state, so as to optimize the search order

First, we need to analyze the cake to see what information can be obtained according to the information in the title:

According to the information in the title, we can write the formula of the area and volume of the cake

$n=\sum^m_{i=1}{R_i^2H_i}$，$Ans=\sum_{i=1}^m2R_iH_i+R_m^2$

For the \ (u \) layer cake, we can determine the value range of radius and height: \ (u \ Le r_ < R {u + 1} - 1 \), \ (u \ Le h_ < h {u + 1} - 1 \). Similarly, we can also infer the volume and surface area of the front \ (u \) layer when both \ (R \) and \ (H \) go to the minimum
For the \ (u \) layer, if the volume of the previous layer is \ (v \), there is \ (n-v\ge \sum R_i^2H_i\ge R_i^2 \), and you can get \ (R_i\le \sqrt{n-v} \), \ (H_i\le \frac{n-v}{R_i^2} \). Therefore, the area of each layer is \ (u \ Le R _ < \ min ({R {u + 1}-1, \ sqrt {N-v}) \), and the volume is \ (u \ Le h _ < \ min (H {u + 1}-1, \ frac {N-v} {R _i ^ 2}) \)
Find the relationship between volume and area:
First scale the area:

$$
Ans = R^2_m+2\sum_{i=1}^uR_iH_i\\
=R_m^2+\frac{2}{R_{u+1}}R_iR_uH_i\\
\because \frac{2}{R_{u+1}}R_iR_uH_i<\frac{2}{R_{u+1}}R_i^2H_i
=\frac{2}{R_{u+1}}n-v\\
\therefore Ans<\frac{2(n-v)}{R_{u+1}}
$$

So we can get the pruning scheme:

Optimize search order: search from bottom to top
Feasible pruning:
If the current area \ volume plus the minimum volume \ area of the front \ (u \) layer is greater than \ (n\)\ $Ans $, the scheme is not feasible
The value of the area of each layer is $$u \ Le R_ U < \ min ({R {U + 1} - 1, \ sqrt {N-V}}) \ (, the value of volume is \) u \ Le H_ u< \min(H_{u+1}-1,\frac{n-v}{R_i^2})$
Ans must meet \ (ANS < \ frac {2 (N-V)} {R {U + 1} \)

#include <bits/stdc++.h>
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
using namespace std;

constexpr int N = 22, INF = 0x3f3f3f3f;

int n, m, ans = INF;
int mins[N], minv[N], R[N], H[N];

void dfs(int u, int s, int v) {
  if (v + minv[u] > n) return;
  if (s + mins[u] >= ans) return;
  if (s + 2 * (n - v) / R[u + 1] >= ans) return;
  if (!u) {
    if (v == n) ans = s;
    return;
  }

  for (int r = min(R[u + 1] - 1, (int)sqrt(n - v)); >= u; r--)
    for (int h = min(H[u + 1] - 1, (n - v) / r / r); h >= u; h--) {
      int t = 0;
      if (u == m) t = r * r;
      R[u] = r, H[u] = h;
      dfs(u - 1, s + t + 2 * r * h, v + r * r * h);
    }
}

int main() {
  io;
  cin >> n >> m;
  for (int i = 1; i <= m; i++) {
    mins[i] = mins[i - 1] + 2 * i * i;
    minv[i] = minv[i - 1] + i * i * i;
  }

  R[m + 1] = H[m + 1] = INF;

  dfs(m, 0, 0);
  
  if (ans == INF) ans = 0;
  cout << ans << '\n';

  return 0;
}

It can be seen that the pruning strategy of this problem mainly comes from the derivation of the formula

Keywords: Algorithm search engine dfs

Added by derrtyones on Sun, 05 Dec 2021 03:26:52 +0200

Programming VIP

DFS pruning and searching

DFS pruning and searching

Examples

The kitten climbed the mountain

Divided into coprime groups

Sequence 1: fixed group

Sequence 2: fixed elements

Summary of this topic

Sudoku

stick

birthday cake

Popular Keywords