跳转至

IDA*

前置知识：A* 算法、迭代加深搜索。

本页面将简要介绍 IDA * 算法。

定义

IDA * 为采用了迭代加深算法的 A * 算法。

优点

由于 IDA * 改成了深度优先的方式，相对于 A * 算法，它的优点如下：

  1. 不需要判重，不需要排序，利于深度剪枝。
  2. 空间需求减少：每个深度下实际上是一个深度优先搜索，不过深度有限制，使用 DFS 可以减小空间消耗。

缺点

  1. 重复搜索：即使前后两次搜索相差微小，回溯过程中每次深度变大都要再次从头搜索。

实现（伪代码）

Procedure IDA_STAR(StartState)
Begin
  PathLimit := H(StartState) - 1;
  Succes := False;
  Repeat
    inc(PathLimit);
    StartState.g = 0;
    Push(OpenStack, StartState);
    Repeat
      CurrentState := Pop(OpenStack);
      If Solution(CurrentState) then
        Success = True
      Elseif PathLimit >= CurrentState.g + H(CurrentState) then
        For each Child(CurrentState) do
          Push(OpenStack, Child(CurrentState));
    until Success or empty(OpenStack);
  until Success or ResourceLimtsReached;
end;

例题

埃及分数

在古埃及，人们使用单位分数的和（即 ，）表示一切有理数。例如，，但不允许 ，因为在加数中不允许有相同的。

对于一个分数 ，表示方法有很多种，其中加数少的比加数多的好，如果加数个数相同，则最小的分数越大越好。例如， 是最优方案。

输入整数 （），试编程计算最佳表达式。

样例输入：

495 499

样例输出：

Case 1: 495/499=1/2+1/5+1/6+1/8+1/3992+1/14970
解题思路

这道题目理论上可以用回溯法求解，但是解答树会非常「恐怖」——不仅深度没有明显的上界，而且加数的选择理论上也是无限的。换句话说，如果用宽度优先遍历，连一层都扩展不完，因为每一层都是 无限大 的。

解决方案是采用迭代加深搜索：从小到大枚举深度上限 ，每次执行只考虑深度不超过 的节点。这样，只要解的深度有限，则一定可以在有限时间内枚举到。

深度上限 还可以用来 剪枝。按照分母递增的顺序来进行扩展，如果扩展到 i 层时，前 个分数之和为 ，而第 个分数为 ，则接下来至少还需要 个分数，总和才能达到 。例如，当前搜索到 ，则后面的分数每个最大为 ，至少需要 项总和才能达到 ，因此前 次迭代是根本不会考虑这棵子树的。这里的关键在于：可以估计至少还要多少步才能出解。

注意，这里使用 至少 一词表示估计都是乐观的。形式化地，设深度上限为 ，当前结点 的深度为 ，乐观估价函数为 ，则当 时应该剪枝。这样的算法就是 IDA*。当然，在实战中不需要严格地在代码里写出 和 ，只需要像刚才那样设计出乐观估价函数，想清楚在什么情况下不可能在当前的深度限制下出解即可。

如果可以设计出一个乐观估价函数，预测从当前结点至少还需要扩展几层结点才有可能得到解，则迭代加深搜索变成了 IDA * 算法。

示例代码 
#include <iostream>
#include <vector>

using namespace std;

constexpr int MAX_E = 1e7;
int a, b;
vector<int> ans;
vector<int> current;

bool better() { return ans.empty() || current.back() < ans.back(); }

long long gcd(long long x, long long y) { return y ? gcd(y, x % y) : x; }

bool dfs(int d, long long a, long long b, int e) {
  if (d == 0) {
    if (a == 0 && better()) ans = current;
    return a == 0;
  }

  long long _gcd = gcd(a, b);
  a /= _gcd;
  b /= _gcd;

  bool solved = false;
  // the min value of e:
  // a/b - 1/e >= 0
  // e >= b/a
  int e1 = max(e + 1, int((b + a - 1) / a));
  // b/a <= e <= MAX_E
  // b/a <= MAX_E
  if (b > a * MAX_E) {
    return false;
  }
  for (;; e1++) {
    // the max value of e:
    // d * (1/e) >= a/b
    // d/e >= a/b
    if (d * b < a * e1) {
      return solved;
    }
    current.push_back(e1);
    // a/b - 1/e
    solved |= dfs(d - 1, a * e1 - b, b * e1, e1);
    current.pop_back();
  }
  return solved;
}

int solve() {
  ans.clear();
  current.clear();
  for (int maxd = 1; maxd <= 100; maxd++)
    if (dfs(maxd, a, b, 1)) return maxd;
  return -1;
}

int main() {
  int kase = 0;
  while (cin >> a >> b) {
    int maxd = solve();
    cout << "Case " << ++kase << ": ";
    if (maxd > 0) {
      cout << a << "/" << b << "=";
      for (int i = 0; i < maxd - 1; i++) cout << "1/" << ans[i] << "+";
      cout << "1/" << ans[maxd - 1] << "\n";
    } else
      cout << "No solution.\n";
  }
  return 0;
}

习题

最后更新: 2024年3月26日
创建日期: 2018年7月11日
回到页面顶部