跳转至

IDA*

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

本頁面將簡要介紹 IDA * 算法。

定義

IDA * 為採用了迭代加深算法的 A * 算法。

優點

由於 IDA * 改成了深度優先的方式，相對於 A * 算法，它的優點如下：

  1. 不需要判重，不需要排序，利於深度剪枝。
  2. 空間需求減少：每個深度下實際上是一個深度優先搜索，不過深度有限制，使用 DFS 可以減小空間消耗。

缺點

  1. 重複搜索：即使前後兩次搜索相差微小，回溯過程中每次深度變大都要再次從頭搜索。

實現（偽代碼）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
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;

例題

埃及分數

在古埃及，人們使用單位分數的和（即 \(\frac{1}{a}\)，\(a\in\mathbb{N}^*\)）表示一切有理數。例如，\(\frac{2}{3}=\frac{1}{2}+\frac{1}{6}\)，但不允許 \(\frac{2}{3}=\frac{1}{3}+\frac{1}{3}\)，因為在加數中不允許有相同的。

對於一個分數 \(\frac{a}{b}\)，表示方法有很多種，其中加數少的比加數多的好，如果加數個數相同，則最小的分數越大越好。例如，\(\frac{19}{45}=\frac{1}{5}+\frac{1}{6}+\frac{1}{18}\) 是最優方案。

輸入整數 \(a,b\)（\(0<a<b<500\)），試編程計算最佳表達式。

樣例輸入：

1
495 499

樣例輸出：

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

這道題目理論上可以用回溯法求解，但是解答樹會非常「恐怖」——不僅深度沒有明顯的上界，而且加數的選擇理論上也是無限的。換句話説，如果用寬度優先遍歷，連一層都擴展不完，因為每一層都是 無限大 的。

解決方案是採用迭代加深搜索：從小到大枚舉深度上限 \(\textit{maxd}\)，每次執行只考慮深度不超過 \(\textit{maxd}\) 的節點。這樣，只要解的深度有限，則一定可以在有限時間內枚舉到。

深度上限 \(\mathit{maxd}\) 還可以用來 剪枝。按照分母遞增的順序來進行擴展，如果擴展到 i 層時，前 \(i\) 個分數之和為 \(\frac{c}{d}\)，而第 \(i\) 個分數為 \(\frac{1}{e}\)，則接下來至少還需要 \(\frac{\frac{a}{b}-\frac{c}{d}}{\frac{1}{e}}\) 個分數，總和才能達到 \(\frac{a}{b}\)。例如，當前搜索到 \(\frac{19}{45}=\frac{1}{5}+\frac{1}{100}+\cdots\)，則後面的分數每個最大為 \(\frac{1}{101}\)，至少需要 \(\frac{\frac{19}{45}-\frac{1}{5}}{\frac{1}{101}}=23\) 項總和才能達到 \(\frac{19}{45}\)，因此前 \(22\) 次迭代是根本不會考慮這棵子樹的。這裏的關鍵在於：可以估計至少還要多少步才能出解。

注意，這裏使用 至少 一詞表示估計都是樂觀的。形式化地，設深度上限為 \(\textit{maxd}\)，當前結點 \(n\) 的深度為 \(g(n)\)，樂觀估價函數為 \(h(n)\)，則當 \(g(n)+h(n)>\textit{maxd}\) 時應該剪枝。這樣的算法就是 IDA*。當然，在實戰中不需要嚴格地在代碼裏寫出 \(g(n)\) 和 \(h(n)\)，只需要像剛才那樣設計出樂觀估價函數，想清楚在什麼情況下不可能在當前的深度限制下出解即可。

如果可以設計出一個樂觀估價函數，預測從當前結點至少還需要擴展幾層結點才有可能得到解，則迭代加深搜索變成了 IDA * 算法。

示例代碼 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <bits/stdc++.h>

using namespace std;

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

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

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

  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;
}

習題

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用