迭代加深搜索（IDDFS）CSP-S

💡 核心思想

迭代加深搜索（IDDFS）是一种限制搜索深度的 DFS：从深度 1 开始，逐步增加深度限制，每次在限制深度内做 DFS。它结合了 DFS 的空间优势和 BFS 的最优性保证，特别适合状态空间巨大但最优解深度不大的问题。

🎯 直觉理解

想象你在一个巨大的迷宫里找出口。BFS 会同时探索所有方向，内存可能爆炸；DFS 可能一条路走到黑永远回不来。IDDFS 的策略是：先只探索深度 1 的范围，找不到再探索深度 2，然后深度 3... 就像你决定"这次最多走 10 步"，走不到就回头，下次允许走 11 步。

📝 算法流程

1. 设定初始深度限制 maxDepth = 1
2. 在 maxDepth 限制下做 DFS
3. 如果找到解，返回
4. 否则 maxDepth++，重复步骤 2
5. DFS 中：如果当前深度 > maxDepth，剪枝返回

$$\text{总节点数} \approx O(b^d) \text{，其中 }b\text{ 为分支因子，}d\text{ 为解深度}$$

📊 复杂度分析

💻 参考实现（C++）

#include 
using namespace std;

bool found;
int maxDepth;

// 示例：在数字 1~n 中找和为 target 的最少个数（IDDFS 模板）
void dfs(int cur, int depth, int target) {
    if (found) return;
    if (cur == target) { found = true; return; }
    if (depth >= maxDepth) return; // 超过深度限制，剪枝
    if (cur > target) return;      // 剪枝：已经超过目标
    
    // 尝试加下一个数（分支）
    for (int i = 1; i <= 3 && !found; i++) // 每次可以 +1, +2, +3
        dfs(cur + i, depth + 1, target);
}

int iddfs(int target) {
    for (maxDepth = 1; ; maxDepth++) {
        found = false;
        dfs(0, 0, target);
        if (found) return maxDepth;
    }
}

int main() {
    cout << iddfs(10) << endl; // 最少 4 步：3+3+3+1
    return 0;
}

⚠️ 常见坑点

📚 相关题目