【搜索】—— 迭代加深/双向DFS/IDA*

---

迭代加深 

深度优先搜索每次固定选定一个分支，不断深入，直到达到递归边界才回溯。这种策略带有一定的缺陷，假设有以下情况：搜索树每个结点的分支很多，并且问题的答案在一个较浅的结点上。如果深搜在一开始选错了分支，就很可能在不包含答案的深层子节树上浪费许多时间。

如下图所示，左半部分是问题的状态空间，菱形表示答案，那么深度优先搜索产生的搜索树如下图所示，算法在矩阵圈出的深层子树上浪费了许多时间。

此时，我们可以从小到大限制搜索的深度，如果在当前深度下搜索不到答案，就把深度限制增加，重新进行一次搜索，这就是迭代加深的思想。 

---

虽然该过程在深度限制为 d 的时候，会重复搜索 1~d-1 层的结点，但是当搜索数节点分支数目较多的时，随着层数的深入，每层节点会呈指数级增长，这点重复搜索和深层子树的规模相比，就是小巫见大巫了。 

总而言之，当搜索树规模随着层次的深入增长很快，并且我们能够保证答案在一个较浅层次的节点的时候，就可以采用迭代加深的深度优先搜索算法来解决问题。

---

AcWing 170. 加成序列 

 

输入样例：

5
7
12
15
77
0

输出样例：

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

---

剪枝1：优先枚举较大的数

剪枝2：排除等效冗余

---

#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. 送礼物 （双向DFS）

输入样例：

20 5
7
5
4
18
1

输出样例：

19

---

1. 将所有的物品按照重量从小到大排序
2. 先将前K件物品能凑出的所有重量打表，然后排序并判重
3. 搜索剩下的N-K件物品的选择方式，然后在表中二分出不超过W的最大值

---

#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;  // 防止 n = 1时，出现死循环
    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;
}