IDA*

IDA*算法

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

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

优点

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

缺点

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

伪代码

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;

「一本通 1.3 练习 1」埃及分数

题目描述

在古埃及，人们使用单位分数的和（形如 的， 是自然数）表示一切有理数。如：，但不允许，因为加数中有相同的。对于一个分数 ，表示方法有很多种，但是哪种最好呢？首先，加数少的比加数多的好，其次，加数个数相同的，最小的分数越大越好。如：

最好的是最后一种，因为 比 , , 都大。 注意，可能有多个最优解。如：

由于方法一与方法二中，最小的分数相同，因此二者均是最优解。

给出 ，编程计算最好的表达方式。保证最优解满足：最小的分数 。

输入格式

一行两个整数，分别为 和 的值。

输出格式

输出若干个数，自小到大排列，依次是单位分数的分母。

样例 #1

样例输入 #1

1
19 45

样例输出 #1

1
5 6 18

数据范围与提示

对于 的数据，

题解

  • 采用迭代加深搜索：从小到大枚举深度上限 ，每次执行只考虑深度不超过 的节点。这样，只要解的深度有限，则一定可以在有限时间内枚举到。
  • 深度上限 还可以用来 剪枝。按照分母递增的顺序来进行扩展，如果扩展到 层时，前 个分数之和为 ，而第 个分数为 ，则接下来至少还需要 个分数，总和才能达到 。例如，当前搜索到 ，则后面的分数每个最大为 ，至少需要 项总和才能达到 ，因此前 次迭代是根本不会考虑这棵子树的。这里的关键在于：可以估计至少还要多少步才能出解。
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
69
70
71
72
73
74
75
76
#include <iostream>
#include <algorithm>
#include <vector> 
using namespace std;

const int MAX_E = 1e7;
int a, b;
vector<int> ans; // 存储最佳解 
vector<int> current; // 存储递归路径中的单位分数的分母 

// 判断当前解是否是更优秀  back:最后一位 
inline bool better() { return ans.empty() || current.back() < ans.back(); }

bool dfs(int d, long a, long b, int e) {
	// 深度限制 分子 分母  上一个单位分数的分母 
  if (d == 0) { // a = 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
  // 下一个分母的最小值 e1 应该是 比 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;
  }
  while(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/e1
    solved |= dfs(d - 1, a * e1 - b, b * e1, e1);
    // d - 1：递归深度减一，表示已经使用了一个单位分数，还剩下 d - 1 个单位分数可以继续分解
    // 通分相减 (a * e1 - b) / (be1) 
    // 回头复原 
    current.pop_back();// 删掉最后一个元素 size-1 
    // 下一位 
    e1 ++ ;
  }
  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() {

	cin >> a >> b;
	
    int maxd = solve();

    for (int i = 0; i < maxd; i++) cout << ans[i] << " ";

  return 0;
}