跳转至

# IDA*

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

本页面将简要介绍 IDA* 算法．IDA* 就是采用了迭代加深算法的 A* 算法．

## 过程

IDA* 算法是迭代加深搜索的一种变形．迭代加深搜索在每次 DFS 中限制搜索深度，而 IDA* 则限制单次 DFS 的路径成本．

在一次迭代中，算法从起点 𝑠 s 开始进行 DFS，记录到达当前结点 𝑥 x 的实际成本 𝑔(𝑥)g(x)，并利用它到终点的最小成本估计 ℎ(𝑥)h(x) 进行剪枝．如果沿着当前路径到达终点的总成本估计

𝑓(𝑥)=𝑔(𝑥)+ℎ(𝑥)f(x)=g(x)+h(x)

超过阈值 𝐶 C，则停止对该分支的搜索．

阈值 𝐶 C 在迭代间动态更新．初始阈值取为起点的总成本估计值 ℎ(𝑠)h(s)．在一次迭代中，每当因超过阈值而停止时，就记录所有尚未访问的后继结点的总成本估计的最小值．迭代结束后，将阈值更新为这一最小值，继续下一轮搜索．

## 性质

由于使用了和 A* 算法一样的剪枝策略，所以对 A* 算法性质的讨论对 IDA* 算法也适用．

和 A* 算法相比，IDA* 算法有如下优点：

- 不需要判重，不需要排序，利于深度剪枝．
- 空间需求减少．每次迭代都是一个深度优先搜索，但是对搜索中的路径成本有限制，使用 DFS 可以减小空间消耗．

同时，它也有缺点：

- 重复搜索．即使前后两次搜索相差微小，每次放宽限制都要再次从头搜索．

## 实现

设 ℎ h 是一个合适的估价函数，𝑠 s 为搜索起点．完整的算法流程大致如下所示：

𝐀 𝐥 𝐠 𝐨 𝐫 𝐢 𝐭 𝐡 𝐦. I d a S t a r():𝐎 𝐮 𝐭 𝐩 𝐮 𝐭. T h e s h o r t e s t p a t h, 𝑝 𝑎 𝑡 ℎ, a n d i t s c o s t, 𝐶, i f a p a t h e x i s t s,a n d N O T_F O U N D, o t h e r w i s e.𝐌 𝐞 𝐭 𝐡 𝐨 𝐝.1 𝐶←ℎ(𝑠)2 𝑝 𝑎 𝑡 ℎ←[𝑠]3 𝐰 𝐡 𝐢 𝐥 𝐞 t r u e 4 𝑡←S e a r c h(𝑝 𝑎 𝑡 ℎ,0,𝐶)5 𝐢 𝐟 𝑡=F O U N D 𝐭 𝐡 𝐞 𝐧 𝐫 𝐞 𝐭 𝐮 𝐫 𝐧 (𝑝 𝑎 𝑡 ℎ,𝐶)6 𝐢 𝐟 𝑡=∞ 𝐭 𝐡 𝐞 𝐧 𝐫 𝐞 𝐭 𝐮 𝐫 𝐧 N O T_F O U N D 7 𝐶←𝑡 𝐒 𝐮 𝐛-𝐀 𝐥 𝐠 𝐨 𝐫 𝐢 𝐭 𝐡 𝐦. S e a r c h(𝑝 𝑎 𝑡 ℎ,𝑔,𝐶):𝐈 𝐧 𝐩 𝐮 𝐭. T h e c u r r e n t p a t h, 𝑝 𝑎 𝑡 ℎ, i t s c o s t, 𝑔, a n d s e a r c h l i m i t 𝐶.𝐎 𝐮 𝐭 𝐩 𝐮 𝐭. F O U N D, i f t h e t a r g e t n o d e h a s b e e n r e a c h e d; ∞, i f a l l r e a c h a b l e n o d e s h a v e b e e n e x p l o r e d; o t h e r w i s e, t h e m i n i m u m t o t a l c o s t, 𝑡, a m o n g n o d e s n o t y e t e x p l o r e d.𝐌 𝐞 𝐭 𝐡 𝐨 𝐝.1 𝑛 𝑜 𝑑 𝑒←t h e l a s t e l e m e n t i n 𝑝 𝑎 𝑡 ℎ 2 𝑓←𝑔+ℎ(𝑛 𝑜 𝑑 𝑒)3 𝐢 𝐟 𝑓>𝐶 𝐭 𝐡 𝐞 𝐧 𝐫 𝐞 𝐭 𝐮 𝐫 𝐧 𝑓 4 𝐢 𝐟 𝑛 𝑜 𝑑 𝑒 i s t h e t a r g e t 𝐭 𝐡 𝐞 𝐧 𝐫 𝐞 𝐭 𝐮 𝐫 𝐧 F O U N D 5 𝑚 𝑖 𝑛←∞6 𝐟 𝐨 𝐫 e a c h 𝑐 ℎ 𝑖 𝑙 𝑑 o f 𝑛 𝑜 𝑑 𝑒 𝐝 𝐨 7 𝐢 𝐟 𝑐 ℎ 𝑖 𝑙 𝑑 n o t i n 𝑝 𝑎 𝑡 ℎ 𝐭 𝐡 𝐞 𝐧 8 a p p e n d 𝑐 ℎ 𝑖 𝑙 𝑑 t o 𝑝 𝑎 𝑡 ℎ 9 𝑡←S e a r c h(𝑝 𝑎 𝑡 ℎ,𝑔+C o s t(𝑛 𝑜 𝑑 𝑒,𝑐 ℎ 𝑖 𝑙 𝑑),𝐶)1 0 𝐢 𝐟 𝑡=F O U N D 𝐭 𝐡 𝐞 𝐧 𝐫 𝐞 𝐭 𝐮 𝐫 𝐧 F O U N D 1 1 𝐢 𝐟 𝑡<𝑚 𝑖 𝑛 𝐭 𝐡 𝐞 𝐧 𝑚 𝑖 𝑛←𝑡 1 2 r e m o v e t h e l a s t e l e m e n t o f 𝑝 𝑎 𝑡 ℎ 1 3 𝐫 𝐞 𝐭 𝐮 𝐫 𝐧 𝑚 𝑖 𝑛 Algorithm. IdaStar():Output. The shortest path, path, and its cost, C, if a path exists,and NOT_FOUND, otherwise.Method.1 C←h(s)2 p a t h←[s]3 while true 4 t←Search(path,0,C)5 if t=FOUND then return (path,C)6 if t=∞ then return NOT_FOUND 7 C←t Sub-Algorithm. Search(path,g,C):Input. The current path, path, its cost, g, and search limit C.Output. FOUND, if the target node has been reached; ∞, if all reachable nodes have been explored; otherwise, the minimum total cost, t, among nodes not yet explored.Method.1 node←the last element in path 2 f←g+h(node)3 if f>C then return f 4 if node is the target then return FOUND 5 min←∞6 for each child of node do 7 if child not in path then 8 append child to path 9 t←Search(path,g+Cost(node,child),C)10 if t=FOUND then return FOUND 11 if t<min then min←t 12 remove the last element of path 13 return min

## 例题

埃及分数

在古埃及，人们使用互不相同的单位分数（即 1/𝑎 1/a，𝑎 ∈𝐍+a∈N+）的和表示一切有理数．例如，2 3 =1 2 +1 6 2 3=1 2+1 6，但不允许 2 3 =1 3 +1 3 2 3=1 3+1 3，因为在加数中不允许有相同的单位分数．

对于一个分数 𝑎 𝑏 a b，表示方法有很多种．规定：同一个分数的不同表示方法中，加数少的比加数多的好；如果加数个数相同，则最小的分数越大越好．例如，1 9 4 5 =1 5 +1 6 +1 1 8 19 45=1 5+1 6+1 18 是最佳方案．

输入整数 𝑎,𝑏 a,b（0 <𝑎 <𝑏 <1 0 0 0 0<a<b<1000），试编程计算最佳表达式．

解题思路

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

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

深度上限 𝐶 C 还可以用来剪枝．按照分母递增的顺序来进行扩展，如果扩展到 𝑖 i 层时，前 𝑖 i 个分数之和为 𝑐 𝑑 c d，而第 𝑖 i 个分数为 1 𝑒 1 e，则接下来至少还需要

ℎ=(𝑎 𝑏−𝑐 𝑑)/(1 𝑒+1)h=(a b−c d)/(1 e+1)

个分数，总和才能达到 𝑎 𝑏 a b．例如，当前搜索到 1 9 4 5 =1 5 +1 1 0 0 +⋯19 45=1 5+1 100+⋯，则后面的分数每个最大为 1 1 0 1 1 101，至少需要 (1 9 4 5−1 5)/(1 1 0 1) =2 3(19 45−1 5)/(1 101)=23 项总和才能达到 1 9 4 5 19 45，因此前 2 2 22 次迭代是根本不会考虑这棵子树的．这里的关键在于：可以估计至少还要多少步才能出解．

注意，这里使用「至少」一词表示估计是「乐观的」．和 A* 算法一样，好的估计函数都需要是「乐观的」，也就是说，它不能高估实际成本．将迭代加深搜索中的深度限制 𝑔 ≤𝐶 g≤C 替换为更严格的限制 𝑔 +ℎ ≤𝐶 g+h≤C，就得到了本页面所讨论的 IDA* 算法．因为本文中的路径成本就是它的长度，所以，IDA* 算法同样是对路径长度进行限制，只是加上了对于还需要多少步的估计．更一般的问题中，根据具体要最小化的成本不同，还可以设计出其他的估计函数．

在实现中，对 IDA* 算法进一步剪枝优化：

1. 扩展结点时，下一个要考虑的分母至少是 (𝑎 𝑏−𝑐 𝑑)−1(a b−c d)−1，可以以此改进枚举 𝑒 e 的起点．

2. IDA* 的路径成本限制可以变形为

   𝑒≤(𝑎 𝑏−𝑐 𝑑)−1(𝐶−𝑔)−1.e≤(a b−c d)−1(C−g)−1.

   所以，不必枚举所有的后续分母再逐个判断，只需要枚举到这个上界即可．

3. 在搜索到最后两个分数时，直接利用二次方程计算是否可行，而非继续搜索．具体地，要找到 𝑒 <𝑥 <𝑦 ≤𝐸 m a x e<x<y≤E max 使得

   1 𝑥+1 𝑦=𝑝 𝑞:=𝑎 𝑏−𝑐 𝑑,1 x+1 y=p q:=a b−c d,

   只需要求解二元二次方程组

   {𝑥+𝑦=𝑘 𝑝,𝑥 𝑦=𝑘 𝑞{x+y=k p,x y=k q

   即可，其中，𝑘 ∈𝐍+k∈N+．由二次方程的知识可知，方程组在

   Δ=𝑘 2 𝑝 2−4 𝑘 𝑞>0⟺𝑘>4 𝑞 𝑝 2 Δ=k 2 p 2−4 k q>0⟺k>4 q p 2

   时，才有两个不同的实根

   𝑥=𝑘 𝑝−√Δ 2, 𝑦=𝑘 𝑝+√Δ 2.x=k p−Δ 2, y=k p+Δ 2.

   因此，可以直接枚举所有可行的 𝑘 k，判断是否存在这样一组整数解．枚举 𝑘 k 时，上界通过 𝑦 <𝐸 m a x y<E max 判断．

4. 每次得到一组答案时，都将分母的上界 𝑀 𝑒 M e 调整到当前答案中的最大分母减一．

另外，实现中，直接记录了 𝑎 𝑏 −𝑐 𝑑 a b−c d 和 𝐶 −𝑔 C−g 的取值，前者的分子和分母分别存储在变量 `a` 和 `b` 中，后者则存储为变量 `d`．

示例代码

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

## 习题

- UVa1343 旋转游戏

> 本页面最近更新：2026/1/7 08:56:54，更新历史
> 发现错误？想一起完善？ 在 GitHub 上编辑此页！
> 本页面贡献者：Ir1d, ksyx, Tiphereth-A, c-forrest, hsfzLZH1, CCXXXI, Chrogeek, ChungZH, Enter-tainer, frank-xjh, greyqz, GreyTigerOIer, Henry-ZHR, HHH2309, iamtwz, kenlig, Kuludu, lct8712, NachtgeistW, ouuan, Phemon, yusancky, ZnPdCo
> 本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用