ID DFS 迭代加深搜索

使用场景:搜索树非常大而答案的深度较浅, 一般在20以内且dfs搜索会超时, bfs的空间会超出

算法原理:

1. 以dfs的形式搜索;

2. 设定搜索的深度限制limit;

3. dfs不能超过limit, 且要恰好遍历所有limit的状态;

4. 若在limit层没有找到答案, limit++, 重新dfs;

Addition Chains 模板题

朴素版

#include <iostream> // POJ 不能用万能头
using namespace std;

const int N = 110;
int g[N], depth;
int n;

bool dfs(int u) // 目前已经在位置1到u找到结果
{
    if (u == depth) return g[u] == n; // 搜索到与当前迭代深度相等

    for (int i = 1; i <= u; i++)
        for (int j = 1; j <= i; j++)
            if (g[i] + g[j] <= n && g[i] + g[j] > g[u]) // i和j可以相等
            {
                g[u + 1] = g[i] + g[j]; // 和

                if (dfs(u + 1)) return true;
                // 回溯
            }

    return false;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    g[1] = 1;

    while (cin >> n, n)
    {
        depth = 1;
        while (!dfs(1)) depth++;

        for (int i = 1; i <= depth; i++) cout << g[i] << ' ';
        cout << '\n';
    }


    return 0;   
}

优化技巧

1. 最优性剪枝(不能, 因为本来就是最优的了)

2. 可行性剪枝

3. 排除等效同余(说的很nb, 就是排序重复状态)

4. 调整搜索顺序

数据范围更大的题目

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 1e4 + 10;
ll g[N], depth;
ll n;

bool dfs(int u)
{
    if (u == depth) return g[u] == n;

    if (g[u] << depth - u < n) return false;

    for (int i = u; i; i--)
        for (int j = i; j; j--)
            if (g[i] + g[j] <= n && g[i] + g[j] > g[u])
            {
                g[u + 1] = g[i] + g[j];

                if (dfs(u + 1)) return true;
            }

    return false;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    g[1] = 1;

    while (cin >> n, n)
    {
        depth = 1;
        while (!dfs(1)) depth++;

        for (int i = 1; i < depth; i++) cout << g[i] << ' ';
        // UVA不能又多余空格

        cout << g[depth] << '\n';
    }


    return 0;   
}

Power Calculus

1. 本质上是指数从1开始, 可以做加法和减法, 最快到达n;

2. 每次只能选择已经求出的中间指数求和或者做差, 可以选多次;

#include <iostream> // POJ 不能用万能头
using namespace std;

typedef long long ll;

const int N = 1e4 + 10;
ll g[N], depth;
ll n;

bool dfs(int u, int k)
{
    if (k > depth) return false;
    if (u == n) return true;

    if (u << depth - k < n) return false;

    g[k] = u;

    for (int i = 0; i <= k; i++)
        if (dfs(u + g[i], k + 1)) return true;
        else if (dfs(u - g[i], k + 1)) return true;

    return false;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    while (cin >> n, n)
    {
        depth = 0;
        while (!dfs(1, 0)) depth++;

        cout << depth << '\n';
    }


    return 0;   
}

[IOI1994] The Buses

题意: 给定n个数, 求最少的等差序列个数, 恰好覆盖n个数一次;

至少两项, 数值在0到59之间;

允许又重复的等差序列;

等差数列必须按规律在[0, 59]之间出现

分析:

1. 考虑到dfds会超时, 而答案在17以内, 尝试IDDFS;

2. 预处理可能的等差序列, 使得等差序列的每一项都在输入中出现;

3. 维护check函数检查第i个等差序列的每一项是否都有出现, 设找到cnt条;

4. 将等差序列按项数从多到少的排序, 贪心选取, 从而使得需要的公交路线最少;

5. 维护cnt[i]表示时间点i出现的车的数量;

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 310, M = 3610;
int st[N];
int n, depth;
int cnt;

struct Cow
{
    int x, d, num;

    bool operator< (const Cow &u) const
    {
        return num > u.num;
    }
} g[M];

bool check(int x, int d)
{
    for (int i = x; i < 60; i += d)
        if (!st[i]) return false;

    return true;
}

bool dfs(int u, int k, int sum)
{
    if (u == depth) return sum == n;

    if (sum + (depth - u) * g[k].num < n) return false;

    for (int i = k; i < cnt; i++)
        if (check(g[i].x, g[i].d))
        {
            for (int j = g[i].x; j < 60; j += g[i].d) st[j]--;

            if (dfs(u + 1, i, sum + g[i].num)) return true;

            for (int j = g[i].x; j < 60; j += g[i].d) st[j]++;
        }

    return false;
}

int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n;

    for (int i = 0, v; i < n; i++)
    {
        cin >> v;

        st[v]++;
    }

    for (int i = 0; i < 60; i++)
        for (int j = i + 1; j + i < 60; j++)
            if (check(i, j))
                g[cnt++] = {i, j, (59 - i) / j + 1};

    sort(g, g + cnt);

    while (!dfs(0, 0, 0)) depth++;

    cout << depth;


    return 0;
}