[search] - DFS pruning and optimization

---

prune

prune , To reduce the size of the search tree , A means of eliminating unnecessary branches in the search tree as soon as possible . Image theory , It's like cutting off the branches of the search tree , So it is called “ prune ”. In depth first search , There are several common pruning methods ：

1. Optimize the pruning sequence

In some search questions , Layers of the search tree 、 The order between branches is not fixed . Different search order will produce different search tree forms , Its size is also very different .

Following ：

1. stay “ Kittens climb mountains ” In question , Take the kitten In descending order of weight To search
2. stay “ Sudoku ” In question , Priority search “ Legal figures that can be filled in ” Minimum position

2. Check the equivalent redundancy

During search , If we can judge It is equivalent to reach the subtree along several different branches from the current node of the search tree , that , Just perform a search on one of the branches .

3. Feasibility pruning

During search , Check the current status in time , If it is found that the branch cannot reach the recursive boundary , Just go back 、 It's like walking on the road , From a distance, I can see a dead end ahead , We should turn around immediately , Instead of walking to the end of the road and returning .

The range limit of some topic conditions is an interval , At this time, feasible pruning is also called “ Up and down ” prune .

4. Optimal pruning

In the search process of optimization problem , If the current cost has exceeded the current optimal solution , Then no matter how good the strategy is to reach the recursive boundary , It's impossible to update the answer . At this point, you can stop searching the current branch , Executive backtracking .

5. Memorize

Sure Record search results for each status , Directly retrieve and return when iterating over a state repeatedly . This is like when we traverse the graph depth first , Mark whether a node has been accessed .

---

AcWing 165. Kittens climb mountains

sample input ：

5 1996
1
2
1994
12
29

sample output ：

2

---

source ：AcWing 165. Kittens climb mountains - AcWing

---

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 20;

int n, m;
int w[N];
int sum[N];
int ans = N;

void dfs(int u, int k)
{
    //  Optimal pruning 
    if(k >= ans) return;
    if(u == n) 
    {
        ans = k;
        return ;
    }
    
    for(int i = 0; i < k; i ++ )
        if(sum[i] + w[u] <= m)
        {
            sum[i] += w[u];
            dfs(u + 1, k);
            sum[i] -= w[u];
        }
    
    sum[k] = w[u];
    dfs(u + 1, k + 1);
    sum[k] = 0;
}

int main()
{
    cin >> n >> m;
    for(int i = 0; i < n; i ++ ) cin >> w[i];
    
    //  Optimize search order 
    sort(w, w + n);
    reverse(w, w + n);
    
    dfs(0, 0);
    
    cout << ans << endl;
    
    return 0;
}

---

AcWing 166. Sudoku   

sample input ：

4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......
......52..8.4......3...9...5.1...6..2..7........3.....6...1..........7.4.......3.
end

sample output ：

417369825632158947958724316825437169791586432346912758289643571573291684164875293
416837529982465371735129468571298643293746185864351297647913852359682714128574936

---

 

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

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

int ones[M], map[M];
int row[N], col[N], cell[3][3];
char str[100];

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

    for (int i = 0; i < 3; i ++ )
        for (int j = 0; j < 3; j ++ )
            cell[i][j] = (1 << N) - 1;
}

void draw(int x, int y, int t, bool is_set)
{
    if (is_set) str[x * N + y] = '1' + t;
    else str[x * N + y] = '.';

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

    row[x] -= v;
    col[y] -= v;
    cell[x / 3][y / 3] -= v;
}

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

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

bool dfs(int cnt)
{
    if (!cnt) return true;

    int minv = 10;
    int x, y;
    for (int i = 0; i < N; i ++ )
        for (int j = 0; j < N; j ++ )
            if (str[i * N + j] == '.')
            {
                int state = get(i, j);
                if (ones[state] < minv)
                {
                    minv = ones[state];
                    x = i, y = j;
                }
            }

    int state = get(x, y);
    for (int i = state; i; i -= lowbit(i))
    {
        int t = map[lowbit(i)];
        draw(x, y, t, true);
        if (dfs(cnt - 1)) return true;
        draw(x, y, t, false);
    }

    return false;
}

int main()
{
    for (int i = 0; i < N; i ++ ) map[1 << i] = i;
    for (int i = 0; i < 1 << N; i ++ )
        for (int j = 0; j < N; j ++ )
            ones[i] += i >> j & 1;

    while (cin >> str, str[0] != 'e')
    {
        init();

        int cnt = 0;
        for (int i = 0, k = 0; i < N; i ++ )
            for (int j = 0; j < N; j ++, k ++ )
                if (str[k] != '.')
                {
                    int t = str[k] - '1';
                    draw(i, j, t, true);
                }
                else cnt ++ ;

        dfs(cnt);

        puts(str);
    }

    return 0;
}

---

AcWing 167. stick  

---

sample input ：

9
5 2 1 5 2 1 5 2 1
4
1 2 3 4
0

sample output ：

6
5

---

 

---

AcWing 168. Birthday cake  

sample input ：

100
2

sample output ：

68

---