LJOJ1244 - 埃及分数

您可以去 Vijos 上搜索此题,不过温馨提示, Vijos 的数据是错的,详情可以参考那题的讨论。

这是一道IDA*经典题,集成了启发式搜索迭代加深的特点进行剪枝。

  • 迭代加深
    本题中,我们限定DFS搜索的层数,如果超过这个层数,就进行剪枝。

  • 启发式搜索
    我们设立一个估价函数,考虑最优情况下的步数。
    本题中我们按照分母从小到大的顺序来DFS埃及分母,所以之后遇到的值就必定大于当前取到的值。
    我们可以通过这个特性来写估价函数,即(a / b) / (1 / u)(其中a / b表示当前的值,u表示剩下能够取到的最小分母)
    做其他题目时一定要注意估价函数所估计的值之多劣于实际情况,而不能比实际情况更优

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×