迭代加深搜索 IDS (Iterative Deepening Search)

📖 算法原理：限深搜索与时空折中

宽度优先搜索 (BFS) 占用内存极大 $O(b^d)$，容易发生内存溢出 (MLE)；深度优先搜索 (DFS) 内存极小 $O(d)$ 但容易深陷无穷分支，且找到的解不一定是最短路径。迭代加深搜索 (IDS) 完美吸取了两者的所有优势。

📐 迭代加深搜索 IDS 算法步骤

IDS 本质上是带有深度限制的 DFS，通过不断放宽搜索深度限制 $D$ 来层层探寻：

设置限制 $D = 0$：只搜索深度为 0 的根节点，若未找到目标，则清空状态，放宽限制。
递增放宽 $D = 1, 2, 3, \dots$：每一次都重新从根节点开始进行一次完整的 DFS 限制搜索。在 DFS 递归中，一旦发现 current_depth > D，立刻进行剪枝强制回溯。
优越性分析：
- 完备最短路：由于深度限制是由小到大逐层递增的，IDS 第一次发现的目标解必定是深度最小（即最短路径）的完备解！
- 空间奇迹 $O(D)$：它不需要像 BFS 那样缓存整层的节点，每一时刻的内存中仅保存一条深度优先的递归调用单链，空间复杂度退化为完美的线性 $O(D)$！
- 时间没有浪费：虽然前面层会被重复扫描，但由于树结构中底层节点数占绝对统治地位，重复扫描上层的时间代价仅为 $O(N)$ 常数级别，时间复杂度依然是完备的 $O(b^D)$！

演示速度：

点击"开始演示"观察深度限制 D 逐步从 0 递增到 3 的 DFS 回溯与限深阻断墙。

当前深度限制 D (Limit) 0

当前遍历点深度 (Depth) 0

本轮扫描次数 (Scanned) 0

空间开销对比 (IDS vs BFS) O(d) vs O(b^d)

🌲 树状决策空间限制深度 DFS 轨迹 (限制深度的红色隔离线)

bool dfs(int u, int depth, int limit) {
    if (depth > limit) {
        return false; // 💥 触及当前层深度限制，强制返回！
    }
    if (u == target) return true; // 寻获目标！
    
    for (int v : adj[u]) {
        if (dfs(v, depth + 1, limit)) return true;
    }
    return false;
}

void solve() {
    // 迭代加深：逐层递增搜索深度上限
    for (int limit = 0; limit <= max_depth; limit++) {
        if (dfs(root, 0, limit)) {
            cout << "Goal Found at limit: " << limit;
            return;
        }
    }
}

📋 迭代加深 DFS 限深回溯日志