IDA* 算法

概念讲解

什么是 IDA*？

IDA* 是迭代加深搜索 + A 启发函数*的结合。

核心思想

限制搜索深度，用启发函数剪枝。

实现

123456789101112131415161718192021int limit;
bool found;

void dfs(int u, int depth) {
    if (found) return;
    if (depth + h(u) > limit) return;  // 剪枝
    if (u == end) { found = true; return; }
    
    for (int v : graph[u]) {
        dfs(v, depth + 1);
    }
}

int idaStar(int start) {
    limit = h(start);
    while (!found) {
        dfs(start, 0);
        limit++;
    }
    return limit;
}

考点分析

初赛考查方式

  1. 程序阅读： IDA*
  2. 编程题： 启发式搜索

常见考点

  • IDA* 原理
  • 启发函数
  • 剪枝

练习题

  1. IDA* 和 A* 的区别？
查看答案
特性 IDA* A*
数据结构 栈（DFS） 优先队列
空间复杂度 O(d) O(b^d)
实现难度 简单 较复杂
适用场景 深度较小 通用
  1. IDA* 的优势？
查看答案

IDA* 的优势：

  1. 空间复杂度低：O(d)O(d)，d 是深度
  2. 实现简单：只需 DFS + 剪枝
  3. 不需要状态去重：避免了 A* 中的 open/closed 表
  1. 什么时候用 IDA*？
查看答案

IDA* 适用于：

  1. 深度较小的问题：解的深度不大
  2. 内存有限：空间复杂度要求低
  3. 启发函数有效：能够有效剪枝

例如：八数码问题、十五数码问题。

易错点

⚠️ 注意：

  1. IDA* 空间复杂度低
  2. 要设计好的启发函数
  3. limit 逐步增加
  4. 适用于深度较小的问题