【OI学习笔记】迭代加深搜索

迭代加深搜索

• 在我们切了很多搜索题后，相信大家会发现有些问题，它们的搜索树很特别，不仅很深并且很宽。此时，如果我们采用一般的DFS会陷入递归而无法返回，如果我们采用一般的BFS，队列可能会炸掉。对于这些问题，它的答案可能在某个较浅的节点上，但如果一开始就选错了分支，那么就很可能在不包含答案的深层子树上浪费许多时间。

• 迭代加深搜索通俗讲可以理解为“DFS + BFS”，具体操作方法如下：

1. 我们先设定搜索深度为1，用DFS搜索到第1层即停止。也就是说，用DFS搜索一个深度为1 的搜索树。

2. 如果没有找到答案，再将搜索深度增加2，用DFS搜索前2层即停止。也就是说，用DFS搜索一个深度为2的搜索树。

3. 同理，我们每次增加搜索的深度，直到搜索到答案。

• 这整个迭代的过程，再每一层的广度上采用的是BFS的思想，但是在实现搜索的过程中采用的是DFS，只是控制了DFS搜索根节点的每个子树的深度。

• 那么就会有同学想说，假设搜索限制为d，每次需要重复跑1~d-1层上的节点，不是更耗费时间吗？但是我们知道当搜索树的节点分支很多时，层上的节点会以指数级增长，那么对于我们重复搜索的点就不值一提了。并且在搜索过程中我们采用记忆化搜索也可以很有效 地避免这个问题。

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

【例题】巴士

题解

//DC Songxingan
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
#define PII pair<int, int>
using namespace std;
const int N = 2000, M = 60;
int n, bus[M];
vector<pair<int, PII>> routes;

bool is_route(int a, int d)
{
    for (int i = a; i < 60; i += d)
        if (!bus[i])
            return false;
    return true;
}

bool DFS(int depth, int u, int sum, int start)
{
    if (u == depth)
        return sum == n;
    if (routes[start].first * (depth - u) + sum < n)
        return false;
    for (int i = start; i < routes.size(); i++)
    {
        auto r = routes[i];
        int a = r.second.first, d = r.second.second;
        if (!is_route(a, d))
            continue;
        for (int j = a; j < 60; j += d)
            bus[j]--;
        if (DFS(depth, u + 1, sum + r.first, i))
            return true;
        for (int j = a; j < 60; j += d)
            bus[j]++;
    }
    return false;
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        int t;
        scanf("%d", &t);
        bus[t]++;
    }

    for (int i = 0; i < 60; i++)
        for (int j = i + 1; i + j < 60; j++)
            if (is_route(i, j))
                routes.push_back({(59 - i) / j + 1, {i, j}});

    sort(routes.begin(), routes.end(), greater<pair<int, PII>>());

    int depth = 0;
    while (!DFS(depth, 0, 0, 0))
        depth++;

    printf("%d\n", depth);
    return 0;
}