1, Question sequence:
1. Consider how to correctly search out all schemes
2. Consider pruning again

1. Optimize search order
In most cases, we should give priority to searching nodes with fewer branches.
2. Eliminate equivalent redundancy
For example, if the order is not considered, search by combination
3. Feasibility pruning
If a scheme is illegal, do not search
4. Optimal pruning
For example, search for the minimum value. If you find more values than the answer, stop
5. Memory search

2, Iteration deepening:
Some search nodes are particularly deep, but its answer is in a relatively short number of layers
Define a max_ Depth, if the number of search layers is greater than this value, return directly;
max_deeepth generally starts from 0 and increases again and again to prevent entering the bottomless hole.
Difference from wide search: the space used is not as large as bfs, and the space complexity is O(h);

Suitable question: some search layers are deep, but the answer is shallow.
Question: the previous nodes will search repeatedly, but the problem is not big, because the number of nodes in layer i+1 is equal to the number of nodes in layer i - 1, which is negligible compared with the answer.

Example: addition sequence
If you want to use 64 layers to search for 128 layers, you can only use the shortest layer to search for 128 layers. Therefore, if you want to use 64 layers to search for 128 layers, you can use the shortest layer to search for 128 layers at most, but if you want to use 64 layers to search for 128 layers.

Add pruning:
1. Optimize search order: search for large values first in each search
2. Eliminate equivalent redundancy: the sum of two different numbers is the same, so 1 + 4 and 2 + 3 are the same. Just enumerate one group of numbers. Open a bool array to determine whether this number has been enumerated.
The code is as follows:

#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int n;
int path[N]; //Store answers
bool dfs(int u,int k)
{
    if(u==k)//Layer k has been searched, and path[0] is the first layer
    {
        return path[u-1] == n;
    }
    bool st[N] = {0};//This is used to prevent repeated search of answers on the same layer. For example, if the front is 1, 2, 3 and the next is 4, you can choose 1, 3 or 2
    for(int i = u-1;i>=0;i--)
    {
        for(int j=i;j>=0;j--)
        {
            //In this step, the search order is optimized. Search from large elements first. The sequence is increasing, so you need to search backwards
            int s = path[i]+path[j];
            if(s>n||s<=path[u-1]||st[s]) continue;
            st[s] = true;
            path[u] = s;
            if(dfs(u+1,k)) return true;
        }
    }
    return false;
}
int main()
{
    path[0] = 1;//Because the first one is 1 anyway
    while(cin>>n,n)
    {
        int maxdepth=1;//Indicates the number of layers that can be searched currently
        while(!dfs(1,maxdepth)) maxdepth++; //If you can't find the answer in the maxdepth layer, the maximum depth is++
        for(int i=0;i<maxdepth;i++)
        {
            cout<<path[i]<<" ";
        }
        cout<<"\n";
        
    }
    return 0;
}

3, Bidirectional dfs

The upper point is the starting point and the lower point is the end point. If it is an ordinary search, you need to search a wide range of points, but if you search from the starting point and the end point at the same time, you only need to search the green part, and cut off the search time of the red part.
Example: giving gifts.
Trade space for time. What is the sum of all the weights from the first n/2 and the item? When searching the second half of the set, you can find the answer with the previous answer.
Pruning: 1 Optimize the search order and search for heavy items first.
Problem solving ideas:
1. Sort all items by weight from large to small
2. Make a list of all the weights of the first k items, and then sort and judge the weight
3. Search the selection method of the remaining N-k items, and then dichotomize the maximum value not exceeding W in the table.

The code is as follows:

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 50;
int n,maxw,k;
int w[N];
int weight[1<<24],cnt;
int ans;
void dfs1(int u,int s)
{
    if(u == k)
    {
        weight[cnt++] = s;
        return;
    }
    if((LL)s + w[u] <= maxw) dfs1(u+1,s+w[u]);
    dfs1(u+1,s);
}
void dfs2(int u,int s)
{
    if(u==n)
    {
        //Match the dichotomy with the previous set to find the maximum value
        int l=0,r = cnt-1;
        while(l<r)
        {
            int mid = l+r+1 >> 1;
            if(weight[mid]+(LL)s <= maxw) l=mid;
            else r = mid-1;
        }
        if((LL)s+weight[l] <= maxw) ans = max(ans,s+weight[l]);
        return;
    }
    if((LL)s+w[u]<=maxw) dfs2(u+1,s+w[u]);
    dfs2(u+1,s);
}
int main()
{
    cin>>maxw>>n;
    for(int i=0;i<n;i++) cin>>w[i];
    sort(w,w+n);
    reverse(w,w+n);//Optimize the search order and start with the big ones
    
    k = n/2;
    dfs1(0,0);
    
    //Perform the second half of the search
    sort(weight,weight+cnt);
    cnt = unique(weight,weight+cnt)-weight;
    
    //cout<<cnt<<endl;
    dfs2(k,0);
    cout<<ans<<endl;
    return 0;
    
}

4, IDA*
Estimate the minimum number of steps required to get the answer to this point. It is also a circle to search. If the minimum number of steps is greater than maxdepth, exit. Valuation function < = true value.
Use with iteration deepening
Example: Book arrangement
Problem solving ideas:
The number of steps in the iterative process needs to be arranged well.

Each operation will change the successor relationship of these three points.
Successor relationship refers to 1-2-3-3-4... This kind of metaphysical valuation function is
(tot+2)/3, tol refers to the number of subsequent errors, such as 1 3 2 4 5, tot = 3
The code is as follows:

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

using namespace std;

const int N = 15;

int n;
int q[N], w[5][N];

int f()
{
    int res = 0;
    for (int i = 0; i + 1 < n; i ++ )
        if (q[i + 1] != q[i] + 1)
            res ++ ;
    return (res + 2) / 3;
}

bool check()
{
    for (int i = 0; i < n; i ++ )
        if (q[i] != i + 1)
            return false;
    return true;
}

bool dfs(int depth, int max_depth)
{
    if (depth + f() > max_depth) return false;
    if (check()) return true;

    for (int l = 0; l < n; l ++ )
        for (int r = l; r < n; r ++ )
            for (int k = r + 1; k < n; k ++ )
            {
                memcpy(w[depth], q, sizeof q);
                int x, y;
                for (x = r + 1, y = l; x <= k; x ++, y ++ ) q[y] = w[depth][x];
                for (x = l; x <= r; x ++, y ++ ) q[y] = w[depth][x];
                if (dfs(depth + 1, max_depth)) return true;
                memcpy(q, w[depth], sizeof q);
            }
    return false;
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T -- )
    {
        scanf("%d", &n);
        for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);

        int depth = 0;
        while (depth < 5 && !dfs(0, depth)) depth ++ ;
        if (depth >= 5) puts("5 or more");
        else printf("%d\n", depth);
    }

    return 0;
}

Author: yxc
 Link: https://www.acwing.com/solution/content/4050/
Source: AcWing
 The copyright belongs to the author. For commercial reprint, please contact the author for authorization. For non-commercial reprint, please indicate the source.