IDA*

在古埃及，人们使用单位分数的和（即 ，）表示一切有理数。例如，，但不允许 ，因为在加数中不允许有相同的。

对于一个分数 ，表示方法有很多种，其中加数少的比加数多的好，如果加数个数相同，则最小的分数越大越好。例如， 是最优方案。

输入整数 （），试编程计算最佳表达式。

样例输入：

495 499

样例输出：

Case 1: 495/499=1/2+1/5+1/6+1/8+1/3992+1/14970

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

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

深度上限 还可以用来 剪枝。按照分母递增的顺序来进行扩展，如果扩展到 i 层时，前 个分数之和为 ，而第 个分数为 ，则接下来至少还需要 个分数，总和才能达到 。例如，当前搜索到 ，则后面的分数每个最大为 ，至少需要 项总和才能达到 ，因此前 次迭代是根本不会考虑这棵子树的。这里的关键在于：可以估计至少还要多少步才能出解。

注意，这里使用 至少 一词表示估计都是乐观的。形式化地，设深度上限为 ，当前结点 的深度为 ，乐观估价函数为 ，则当 时应该剪枝。这样的算法就是 IDA*。当然，在实战中不需要严格地在代码里写出 和 ，只需要像刚才那样设计出乐观估价函数，想清楚在什么情况下不可能在当前的深度限制下出解即可。

如果可以设计出一个乐观估价函数，预测从当前结点至少还需要扩展几层结点才有可能得到解，则迭代加深搜索变成了 IDA*算法。