AIOJ

Prerequisites: A* algorithm, iterative deepening search

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

Process

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

In one iteration, the algorithm starts at the starting point $s$ and performs DFS, recording the actual cost $g(x)$ of reaching the current node $x$ , and uses the minimum estimated cost $h(x)$ from it to the destination for pruning. If the estimated total cost of reaching the destination along the current path

f(x) = g(x) + h(x)

exceeds the threshold $C$ , the search of that branch is stopped.

The threshold $C$ is updated dynamically between iterations. Initially, the threshold is set to the estimated total cost $h(s)$ at the starting point. During an iteration, whenever the search is stopped because the threshold is exceeded, the minimum estimated total cost among all not-yet-visited successor nodes is recorded. After the iteration ends, the threshold is updated to this minimum, and the next round of search continues.

Properties

Because it uses the same pruning strategy as the A* algorithm, the discussion of the properties of A* also applies to IDA*.

Compared with A*, IDA* has the following advantages:

Duplicate detection and sorting are unnecessary, which is favorable for depth pruning.
Reduced space requirements. Each iteration is a depth-first search, but the path cost during the search is limited; using DFS reduces space consumption.

At the same time, it has a disadvantage:

Repeated searches. Even if two successive searches differ only slightly, the search must start over from the beginning whenever the limit is relaxed.

Implementation

Let $h$ be a suitable heuristic function and $s$ be the starting point of the search. The complete algorithm 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}

Examples

Egyptian Fractions

In ancient Egypt, people represented every rational number as a sum of distinct unit fractions (that is, $1/a$ , $a\in\mathbf{N}_+$ ). 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 the summands may not contain identical unit fractions.

A fraction $\dfrac{a}{b}$ has many representations. Among different representations of the same fraction, the one with fewer summands is considered better; if the number of summands is the same, the one with the larger smallest fraction is better. For example, $\dfrac{19}{45}=\dfrac{1}{5}+\dfrac{1}{6}+\dfrac{1}{18}$ is optimal.

Given integers $a,b$ ($0 [!note]- Solution Approach

This problem can theoretically be solved with backtracking, but the solution tree would be extremely “terrifying”—not only is there no obvious upper bound on its depth, the choices of summands are theoretically infinite. In other words, if breadth-first traversal were used, not even one level could be fully expanded, because every level would be infinite.

The solution is to use iterative deepening search: enumerate the depth limit $C$ from small to large, and in each search consider only nodes whose depth does not exceed $C$ . Thus, as long as the solution has finite depth, it will be enumerated in finite time.

The depth limit $C$ can also be used for pruning. Expand in increasing order of denominators. If, after expanding to level $i$ , 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 to reach $\dfrac{a}{b}$ . For example, suppose the current search has reached $\dfrac{19}{45}=\dfrac{1}{5}+\dfrac{1}{100}+\cdots$ . Each later fraction is at most $\dfrac{1}{101}$ , so at least $\left({\dfrac{19}{45}-\dfrac{1}{5}}\right)/\left({\dfrac{1}{101}}\right)=23$ terms are needed for the total to reach $\dfrac{19}{45}$ . Therefore, the first $22$ iterations will not consider this subtree at all. The key point is that we can estimate how many steps are needed at minimum before a solution can be found.

Here, the word “at least” means that the estimate is “optimistic”. As with the A* algorithm, a good heuristic function must be “optimistic”; that is, it must not overestimate the actual cost. Replacing the depth constraint $g\le C$ in iterative deepening search with the stricter constraint $g + h \le C$ yields the IDA* algorithm discussed on this page. Because the path cost in this article is its length, IDA* likewise limits the path length, while adding an estimate of how many more steps are needed. For more general problems, other heuristic functions can be designed depending on the specific cost to be minimized.

In the implementation, IDA* is further optimized by pruning:

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$ .
The path-cost limit of IDA* can be transformed into
$e \le \left(\dfrac{a}{b}-\dfrac{c}{d}\right)^{-1}(C-g) - 1.$
Therefore, it is unnecessary to enumerate all subsequent denominators and check them one by one; it is enough to enumerate up to this upper bound.
When searching for the last two fractions, directly use a quadratic equation to determine 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},$
it is enough to solve the binary quadratic system
$\begin{cases} x + y = kp,\\ xy = kq \end{cases}$
where $k\in\mathbf N_+$ . From the theory of quadratic equations, the system has two distinct real roots when
$\Delta = k^2p^2-4kq > 0 \iff k > \dfrac{4q}{p^2}$
and the roots are
$x = \dfrac{kp - \sqrt{\Delta}}{2},~ y = \dfrac{kp + \sqrt{\Delta}}{2}.$
Therefore, enumerate all feasible $k$ directly and determine whether such a pair of integer solutions exists. When enumerating $k$ , determine its upper bound using $y < E_\text{max}$ .
Whenever a solution is found, adjust the upper bound $M_e$ of the denominators to one less than the largest denominator in the current solution.

In addition, the implementation directly records the values of $\dfrac{a}{b}-\dfrac{c}{d}$ and $C-g$ ; the numerator and denominator of the former are stored in variables a and b, respectively, while the latter is stored in variable d.

Example Code

#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

UVa1343 Rotating Game