Skip to content

IDA*

Prerequisite knowledge: A* algorithm, Iterative deepening search

This page briefly introduces the IDA algorithm. IDA is essentially the A* algorithm combined with iterative deepening.

Process

The IDA algorithm is a variant of iterative deepening search. Iterative deepening search limits the search depth in each DFS, while IDA limits the path cost in a single DFS.

In one iteration, the algorithm performs DFS starting from the source node \(s\), records the actual cost \(g(x)\) to reach the current node \(x\), and uses the estimated minimum cost \(h(x)\) from \(x\) to the target for pruning. If the estimated total cost to reach the target along the current path

\[ f(x) = g(x) + h(x) \]

exceeds a threshold \(C\), the search on this branch is stopped.

The threshold \(C\) is updated dynamically between iterations. The initial threshold is set to the estimated total cost \(h(s)\) of the source node. During an iteration, whenever the search stops due to exceeding the threshold, the minimum estimated total cost among all unvisited successor nodes is recorded. After the iteration ends, the threshold is updated to this minimum value, and the next round of search begins.

Properties

Since IDA uses the same pruning strategy as the A algorithm, the discussion of A's properties also applies to IDA.

Compared to A, IDA has the following advantages:

  • No need for duplicate detection or sorting, which facilitates depth pruning.
  • Reduced space requirements. Each iteration is a depth-first search but with a limit on the path cost, allowing DFS to reduce space consumption.

However, it also has disadvantages:

  • Repeated search. Even if the difference between two consecutive searches is minimal, each relaxation of the limit requires starting the search from scratch.

Implementation

Let \(h\) be a suitable heuristic function, and \(s\) be the search starting point. The complete algorithm flow is roughly as follows:

\[ \begin{array}{l} \textbf{Algorithm. }\textrm{IdaStar}():\\ \textbf{Output. }\text{The shortest path, }\textit{path}\text{, and its cost, }C\text{, if a path exists,}\\ \quad \text{and }\textrm{NOT}\_\textrm{FOUND}\text{, otherwise.}\\ \textbf{Method.}\\ \begin{array}{ll} 1 & C \gets h(s) \\ 2 & path \gets [s] \\ 3 & \textbf{while }\text{true}\\ 4 & \quad t \gets \textrm{Search}(\textit{path},0,C)\\ 5 & \quad \textbf{if } t=\text{FOUND}\textbf{ then return }(\textit{path},C) \\ 6 & \quad \textbf{if } t=\infty\textbf{ then return }\textrm{NOT}\_\textrm{FOUND} \\ 7 & \quad C \gets t \end{array}\\ \\ \textbf{Sub-Algorithm. }\textrm{Search}(\textit{path},g,C):\\ \textbf{Input. }\text{The current path, }\textit{path}\text{, its cost, }g\text{, and search limit }C.\\ \textbf{Output. }\text{FOUND, if the target node has been reached; }\infty\text{, if all}\\ \quad \text{reachable nodes have been explored; otherwise, the minimum}\\ \quad \text{total cost, }t\text{, among nodes not yet explored.}\\ \textbf{Method.}\\ \begin{array}{ll} 1 & \textit{node} \gets \text{the last element in }\textit{path}\\ 2 & f \gets g + h(\textit{node}) \\ 3 & \textbf{if } f > C \textbf{ then return } f \\ 4 & \textbf{if }\textit{node}\text{ is the target }\textbf{then return }\text{FOUND}\\ 5 & \textit{min} \gets \infty \\ 6 & \textbf{for }\text{each }\textit{child}\text{ of }\textit{node }\textbf{do}\\ 7 & \quad \textbf{if }\textit{child}\text{ not in }\textit{path}\textbf{ then}\\ 8 & \quad \quad \text{append }\textit{child}\text{ to }\textit{path}\\ 9 & \quad \quad t \gets \text{Search}(\textit{path}, g + \text{Cost}(\textit{node},\textit{child}), C)\\ 10 & \quad \quad \textbf{if }t = \text{FOUND}\textbf{ then return }\text{FOUND}\\ 11 & \quad \quad \textbf{if }t < \textit{min}\textbf{ then }\textit{min}\gets t\\ 12 & \quad \quad \text{remove the last element of }\textit{path}\\ 13 & \textbf{return }\textit{min} \end{array} \end{array} \]

Example Problems

Egyptian Fraction

In ancient Egypt, people used sums of distinct unit fractions (i.e., \(1/a\), \(a\in\mathbf{N}_+\)) to represent all rational numbers. For example, \(\dfrac{2}{3}=\dfrac{1}{2}+\dfrac{1}{6}\), but \(\dfrac{2}{3}=\dfrac{1}{3}+\dfrac{1}{3}\) is not allowed because identical unit fractions are not permitted among the addends.

For a fraction \(\dfrac{a}{b}\), there are many representation methods. The rule is: among different representations of the same fraction, the one with fewer addends is better; if the number of addends is the same, the one with the largest smallest fraction is better. For example, \(\dfrac{19}{45}=\dfrac{1}{5}+\dfrac{1}{6}+\dfrac{1}{18}\) is the optimal solution.

Given integers \(a,b\) (\(0<a<b<1000\)), write a program to compute the optimal expression.

Solution Idea

This problem can theoretically be solved by backtracking, but the search tree would be "terrifying"—not only is the depth unbounded, but the choice of addends is also theoretically infinite. In other words, if using breadth-first search, even one layer cannot be fully expanded because each layer is infinitely large.

The solution is to use iterative deepening search: enumerate the depth limit \(C\) from small to large, and each search only considers nodes with depth not exceeding \(C\). This way, as long as the solution depth is finite, it will be enumerated within finite time.

The depth limit \(C\) can also be used for pruning. Expand in order of increasing denominators. If at the \(i\)-th layer, the sum of the first \(i\) fractions is \(\dfrac{c}{d}\), and the \(i\)-th fraction is \(\dfrac{1}{e}\), then at least

\[ h = \left(\dfrac{a}{b}-\dfrac{c}{d}\right)/\left(\dfrac{1}{e+1}\right) \]

more fractions are needed for the total sum to reach \(\dfrac{a}{b}\). For example, if currently searching \(\dfrac{19}{45}=\dfrac{1}{5}+\dfrac{1}{100}+\cdots\), then each subsequent fraction is at most \(\dfrac{1}{101}\), and at least \(\left({\dfrac{19}{45}-\dfrac{1}{5}}\right)/\left({\dfrac{1}{101}}\right)=23\) terms are needed for the sum to reach \(\dfrac{19}{45}\). Therefore, the first \(22\) iterations will not consider this subtree at all. The key here is that we can estimate how many more steps are needed to reach a solution.

Note that the word "at least" indicates the estimate is "optimistic". As with the A algorithm, a good heuristic function must be "optimistic", meaning it must not overestimate the actual cost. Replacing the depth limit \(g\le C\) in iterative deepening search with the stricter limit \(g + h \le C\) yields the IDA algorithm discussed on this page. Since the path cost here is its length, IDA* also limits the path length but adds an estimate of how many more steps are needed. In more general problems, depending on the specific cost to minimize, other heuristic functions can be designed.

In implementation, further pruning optimizations for IDA*:

  1. When expanding a node, the next denominator to consider is at least \(\left(\dfrac{a}{b}-\dfrac{c}{d}\right)^{-1}\), which can be used to improve the starting point for enumerating \(e\).

  2. The path cost limit in IDA* can be transformed into

    \[ e \le \left(\dfrac{a}{b}-\dfrac{c}{d}\right)^{-1}(C-g) - 1. \]

    Therefore, instead of enumerating all subsequent denominators and checking one by one, it suffices to enumerate up to this upper bound.

  3. When searching for the last two fractions, directly use a quadratic equation to check feasibility instead of continuing the search. Specifically, to find \(e<x<y\le E_\text{max}\) such that

    \[ \dfrac{1}{x} + \dfrac{1}{y} = \dfrac{p}{q} := \dfrac{a}{b}-\dfrac{c}{d}, \]

    we only need to solve the system of quadratic equations

    \[ \begin{cases} x + y = kp,\\ xy = kq \end{cases} \]

    where \(k\in\mathbf N_+\). From quadratic equation knowledge, the system has two distinct real roots

    \[ x = \dfrac{kp - \sqrt{\Delta}}{2},~ y = \dfrac{kp + \sqrt{\Delta}}{2}. \]

    when

    \[ \Delta = k^2p^2-4kq > 0 \iff k > \dfrac{4q}{p^2}. \]

    Therefore, we can directly enumerate all feasible \(k\) and check if such an integer solution exists. When enumerating \(k\), the upper bound is determined by \(y < E_\text{max}\).

  4. Each time an answer is found, adjust the denominator upper bound \(M_e\) to the largest denominator in the current answer minus one.

Additionally, in implementation, the values of \(\dfrac{a}{b}-\dfrac{c}{d}\) and \(C-g\) are directly recorded. The numerator and denominator of the former are stored in variables a and b, respectively, while the latter is stored as variable d.

Example Code 
 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
#include <cmath>
#include <iostream>
#include <numeric>
#include <vector>

int max_e = 1e7;
std::vector<int> ans;
std::vector<int> current;

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) {
  long long _gcd = gcd(a, b);
  a /= _gcd;
  b /= _gcd;

  bool solved = false;
  if (d == 2) {
    for (int k = 4 * b / (a * a) + 1;; ++k) {
      long long delta = a * a * k * k - 4 * b * k;
      long long t = std::sqrt(delta + 0.5l);
      long long x = (a * k - t) / 2;
      long long y = (a * k + t) / 2;
      if (y > max_e) break;
      if (!t || t * t != delta || (a * k - t) % 2 != 0) continue;
      ans = current;
      ans.push_back(x);
      ans.push_back(y);
      max_e = y - 1;
      solved = true;
    }
  } else {
    int e1 = std::max(e + 1, int((b + a - 1) / a));
    for (; e1 <= d * b / a && e1 <= max_e; e1++) {
      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(int a, int b) {
  if (b % a == 0) {
    ans.push_back(b / a);
    return 1;
  }
  for (int lim = 2; lim <= 100; lim++)
    if (dfs(lim, a, b, 1)) return lim;
  return -1;
}

int main() {
  int a, b;
  std::cin >> a >> b;
  solve(a, b);
  for (auto x : ans) std::cout << x << ' ';
  std::cout << std::endl;
  return 0;
}

Exercises

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