[search] - iteration deepening / bidirectional dfs/ida*

---

Iteration deepening  

Depth first search selects one branch at a time , Keep going deep , Do not backtrack until you reach the recursive boundary . There is a certain flaw in this strategy , Suppose that ： Each node of the search tree has many branches , And the answer to the question is on a shallow node . If deep search chooses the wrong branch at the beginning , It is likely to waste a lot of time on the deep sub section tree that does not contain answers .

As shown in the figure below , The left half is the state space of the problem , The diamond represents the answer , Then the search tree generated by depth first search is shown in the following figure , The algorithm wastes a lot of time on the deep subtree circled by the matrix .

here , We can Limit the depth of search from small to large , If you can't find the answer at the current depth , Just increase the depth limit , Do a new search , This is it. Iteration deepening Thought . 

---

Although the process is limited in depth to d When , Will repeat the search 1~d-1 The node of the layer , But when the number of search nodes and branches is large , As the number of layers goes deeper , Nodes of each layer will Exponential growth , This repeated search is compared with the scale of deep subtree , It's the little wizard who sees the big one . 

To make a long story short , When the size of the search tree grows rapidly with the depth of the hierarchy , And we can ensure that the answer is at a shallow node , We can use depth first search algorithm to solve the problem .

---

AcWing 170. Addition sequence  

 

sample input ：

5
7
12
15
77
0

sample output ：

1 2 4 5
1 2 4 6 7
1 2 4 8 12
1 2 4 5 10 15
1 2 4 8 9 17 34 68 77

---

prune 1： Give priority to enumerating larger numbers

prune 2： Eliminate equivalent redundancy

---

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

using namespace std;

const int N = 110;

int n;
int path[N];

bool dfs(int u, int depth)
{
    if(u > depth) return false;
    if(path[u - 1] == n) return true;
    
    bool st[N] = {0};
    for(int i = u - 1; i >= 0; i -- )
        for(int j = i; j >= 0; j --)
        {
            int s = path[i] + path[j];
            if(s > n || s <= path[u - 1] || st[u]) continue;
            
            st[s] = true;
            path[u] = s;
            if(dfs(u + 1, depth)) return true;
        }
    return false;
}

int main()
{
    path[0] = 1; 
    while(cin >> n, n)
    {
        int depth = 1;
        while(!dfs(1, depth)) depth ++ ;
        for(int i = 0; i < depth ; i ++ ) cout << path[i] << ' ';
        cout << endl;
    }
    return 0;
}

---

AcWing 171. giving gifts  （ two-way DFS）

sample input ：

20 5
7
5
4
18
1

sample output ：

19

---

1. Sort all items according to their weight from small to large
2. Before K Make a list of all the weights that can be put together by an item , Then sort and weigh
3. Search for the rest N-K How to choose an item , Then dichotomize no more than in the table W The maximum of

---

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

typedef long long LL;

const int N = 1 << 24;

int n, m, k;
int g[50], weights[N];
int cnt = 0;
int ans;


void dfs(int u, int s)
{
    if (u == k)
    {
        weights[cnt ++ ] = s;
        return;
    }

    if ((LL)s + g[u] <= m) dfs(u + 1, s + g[u]);
    dfs(u + 1, s);
}


void dfs2(int u, int s)
{
    if (u == n)
    {
        int l = 0, r = cnt - 1;
        while (l < r)
        {
            int mid = l + r + 1 >> 1;
            if (weights[mid] + (LL)s <= m) l = mid;
            else r = mid - 1;
        }
        if (weights[l] + (LL)s <= m) ans = max(ans, weights[l] + s);

        return;
    }

    if ((LL)s + g[u] <= m) dfs2(u + 1, s + g[u]);
    dfs2(u + 1, s);
}


int main()
{
    cin >> m >> n;
    for (int i = 0; i < n; i ++ ) cin >> g[i];

    sort(g, g + n);
    reverse(g, g + n);

    k = n / 2;  //  prevent  n = 1 when , There's a dead cycle 
    dfs(0, 0);

    sort(weights, weights + cnt);
    int t = 1;
    for (int i = 1; i < cnt; i ++ )
        if (weights[i] != weights[i - 1])
            weights[t ++ ] = weights[i];
    cnt = t;

    dfs2(k, 0);

    cout << ans << endl;

    return 0;
}