你的位置:首页 > 信息动态 > 新闻中心
信息动态
联系我们

迭代加深搜索 (IDDFS)和IDA算法

2021-12-2 15:13:58

迭代加深搜索 (IDDFS)和IDA算法

IDDFS:

我个人这个搜索的理解就是以BFS的思想写DFS。

具体来说就是,**首先深度优先搜索k层,若没有找到可行解,再深度优先搜索k+1层,直到找到可行解为止。**由于深度是从小到大逐渐增大的,所以当搜索到结果时可以保证搜索深度是最小的。这也是迭代加深搜索在一部分情况下可以代替广度优先搜索的原(还比广搜省空间)。

前提:

题目一定要有解,否则会无限循环下去。

好处:

1.时间复杂度只比BFS稍差一点(虽然搜索k+1层时会重复搜索k层,但是整体而言并不比广搜慢很多)。

2.空间复杂度与深搜相同,却比广搜小很多。

3.利于剪枝。

使用搜索算法的时候,选择正确的搜索方式很重要。当有一类问题需要做广度优先搜索,但却没有足够的空间,而时间却很充裕,碰到这类问题,我们可以选择迭代加深搜索算法。

IDA*算法:

IDA算法能简要概述为:IDA = IDDFS + 乐观估计函数
在这里乐观估计函数的作用是判断在某个深度时问题是否可解,若无解则返回,即IDDFS利用乐观估计函数进行剪枝操作。

使用迭代加深搜素时没有剪枝操作时,时间开销是非常大的(因为迭代加深搜索是通过限制每次dfs的最大深度进行的搜索。令maxd表示最大的搜索深度,那么dfs就只能在0~maxd之间来进行,如果在这个范围内找到了解,就退出大循环,否则maxd++,扩大搜索范围。所以可想而知,倘若没有高效及时的退出无解的情况,那么时间上的开销也是会比较大的。)

如何及时的退出无解情况呢?这里引入乐观估计函数。这时就需要进行“剪枝”操作,及时地判断此时能否找到解。对于迭代加深搜索,经常通过设计合适的“乐观估价函数”来判断能否剪枝。

乐观估计函数:从当前深度到找到最终的解“至少”还需要多少步,或者距离找到最终的解还需要扩展多少层。如果超出了当前限制的深度maxd,说明当前限制的最大深度下是不可能找到解的,直接退出。(这个函数你只需要乐观的去构造就行了)设当前搜索的深度是cur,乐观估价函数是h(),那么当cur+h()>maxd时就需要剪枝。

比如在“埃及分数”问题中要求将一个分数a/b分解成为若干个形如1/d的加数之和,而且加数越少越好,如果加数个数相同,那么最小的分数越大越好。要拆分19/45这样的一个分数,假设当前搜索到了第三层,得到19/45=1/5+1/100…那么根据题意此时最大的分数为1/101,而且如果需要凑够19/45,需要(19/45-1/5-1/100)*101=23个1/101才行。即从第3层还要向下扩展至少大于23层的深度才可能找到所有的解。所以如果此时的maxd<23,就可以直接剪枝了。因此(a/b-c/d)/(1/e)便是本题的乐观估价函数。

注意,使用IDA*算法时要保证一定可以找到解,否则会无限循环下去。

下面给出“埃及分数”问题的代码以便更好地理解IDA*算法的过程:

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
int maxdepth;
int a, b;
const int maxn = 1000;
int ans[maxn], temp[maxn]; //最终结果 临时结果
int gcd(int a, int b)
{
    return b == 0 ? a : gcd(b, a % b);
}

int get_first(int a, int b) //找到1/c≤a/b时最小的c
{
    int c = 1;
    while (b > a * c)
        c++;
    return c;
}

bool better(int depth) //比较深度为depth时,现在找到的解是不是更优的
{
    for (int i = depth; i >= 0; i--)
        if (temp[i] != ans[i])
        {
            return ans[i] == -1 || temp[i] < ans[i]; //两种情况下说明当前更优:(1)此时尚未找到过解;(2)当前的分母小于原来的分母,说明当前的分数比原来的更大,符合题意要求
        }
    return false;
}

bool dfs(int depth, int from, LL aa, LL bb) //当前深度为depth,分母不能小于from,分数之和恰好是aa/bb
{
    if (depth == maxdepth) //到达了最后一层
    {
        if (bb % aa)
            return false; //不能整除,说明最后一项不符合埃及分数的定义,失败退出
        temp[depth] = bb / aa;
        if (better(depth))
            memcpy(ans, temp, sizeof(LL) * (depth + 1)); //当前找到的解是更优的,更新ans
        return true;
    }
    bool flag = false;
    from = max(from, get_first(aa, bb)); //更新from 使1/from尽可能小 和不越界
    for (int i = from;; i++)             //枚举分母
    {
        if (bb * (maxdepth + 1 - depth) <= i * aa)
            break; //利用乐观估价函数来剪枝,从当前深度depth到达maxdepth一共有maxdepth-depth+1项,如果(maxdepth-depth+1)*(1/i)还凑不够aa/bb,需要剪枝
        temp[depth] = i;
        LL b2 = bb * i; //计算aa/bb-1/i,通分后,分母是bb*i,分母是aa*i-bb
        LL a2 = aa * i - bb;
        LL g = gcd(a2, b2); //计算分子,分母的最大公约数,便于约分
        if (dfs(depth + 1, i + 1, a2 / g, b2 / g))
            flag = true;
    }
    return flag;
}

int main()
{
    while (scanf("%d%d", &a, &b)) //输入分数a/b
    {
        for (maxdepth = 1;; maxdepth++)
        {
            memset(ans, -1, sizeof(ans));
            if (dfs(0, get_first(a, b), a, b))
                break;
        }
        printf("%d/%d=", a, b);
        for (int i = 0;; i++)
            if (ans[i] > 0)
                printf("%s1/%d", i == 0 ? "" : "+", ans[i]);
            else
            {
                printf("\n");
                break;
            }
    }
    return 0;
}