IDA*


前置知识:

A* 算法、
迭代加深搜索

本页面将简要介绍 IDA*算法。

定义

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

优点

由于 IDA*改成了深度优先的方式,相对于 A*算法,它的优点如下:

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

缺点

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

实现(伪代码)

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;

例题

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

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

输入整数 ),试编程计算最佳表达式。

样例输入:

495 499

样例输出:

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

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

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

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

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

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

习题

贡献者:@WenzelTian@kenlig@夜轮_NachtgeistW@mgt@ksyx@Chrogeek@Henry-ZHR@ouuan@Phemon@Ir1d@雷蒻@MrFoodinChina@Haoshen@Kuludu@心旷神怡@frank

本页面最近更新:2/3/2023, 12:00:00 AM更新历史

发现错误?想一起完善? 在 GitHub 上编辑此页!

本页面的全部内容在 CC BY-SA 4.0SATA 协议之条款下提供,附加条款亦可能应用

评论

0 条评论
未登录用户


Copyright © 2016 - 2023 OI Wiki Team

最近更新:fd2ec2c, 2023-02-03

联系方式:Telegram 群组 / QQ 群组