迭代加深搜索（IDDFS）

概念讲解

什么是 IDDFS？

IDDFS 是一种限制搜索深度的 DFS，逐步增加深度限制。

核心思想

结合了 DFS 的空间优势和 BFS 的最优性。

实现

123456789101112131415161718192021222324bool found;

void dfs(int state, int depth, int limit) {
    if (found) return;
    if (depth > limit) return;
    if (isGoal(state)) {
        found = true;
        return;
    }
    
    for (int nextState : getNeighbors(state)) {
        dfs(nextState, depth + 1, limit);
    }
}

int iddfs(int start, int maxDepth) {
    for (int limit = 0; limit <= maxDepth; limit++) {
        found = false;
        dfs(start, 0, limit);
        if (found) return limit;
    }
    
    return -1;
}

适用场景

  1. 搜索空间很大
  2. 最优解深度较浅
  3. 内存有限

考点分析

初赛考查方式

  1. 选择题： IDDFS 的概念
  2. 程序阅读： 理解 IDDFS
  3. 编程题： IDDFS 应用

常见题型

  • 最优解搜索
  • 深度限制搜索

例题精讲

例题 1：IDDFS

题目： 使用 IDDFS 求解问题。

解答：

123456789101112131415161718192021222324252627282930313233343536373839404142#include <iostream>
using namespace std;

bool found;

bool isGoal(int state) {
    // 判断是否是目标状态
    return false;
}

void dfs(int state, int depth, int limit) {
    if (found) return;
    if (depth > limit) return;
    if (isGoal(state)) {
        found = true;
        return;
    }
    
    // 扩展邻居状态
    for (int i = 0; i < 4; i++) {
        int nextState = state; // 根据操作生成新状态
        dfs(nextState, depth + 1, limit);
    }
}

int main() {
    int start, maxDepth;
    cin >> start >> maxDepth;
    
    for (int limit = 0; limit <= maxDepth; limit++) {
        found = false;
        dfs(start, 0, limit);
        if (found) {
            cout << limit << endl;
            return 0;
        }
    }
    
    cout << -1 << endl;
    
    return 0;
}

练习题

  1. 洛谷 P1379 八数码难题
查看答案

思路：IDA* 算法，使用启发式函数剪枝。

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768#include <iostream>
#include <cmath>
using namespace std;

int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int target[3][3] = {{1, 2, 3}, {8, 0, 4}, {7, 6, 5}};
int a[3][3];
int maxDepth;

int heuristic() {
    int dist = 0;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            if (a[i][j] != 0) {
                int val = a[i][j] - 1;
                dist += abs(i - val / 3) + abs(j - val % 3);
            }
        }
    }
    return dist;
}

bool dfs(int x, int y, int depth, int last) {
    int h = heuristic();
    if (h == 0) return true;
    if (depth + h > maxDepth) return false;
    
    for (int i = 0; i < 4; i++) {
        if (i == (last ^ 1)) continue;
        
        int nx = x + dx[i], ny = y + dy[i];
        if (nx < 0 || nx >= 3 || ny < 0 || ny >= 3) continue;
        
        swap(a[x][y], a[nx][ny]);
        if (dfs(nx, ny, depth + 1, i)) return true;
        swap(a[x][y], a[nx][ny]);
    }
    
    return false;
}

int main() {
    int sx, sy;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            char c;
            cin >> c;
            if (c == 'x') {
                a[i][j] = 0;
                sx = i;
                sy = j;
            } else {
                a[i][j] = c - '0';
            }
        }
    }
    
    for (maxDepth = 0; maxDepth <= 30; maxDepth++) {
        if (dfs(sx, sy, 0, -1)) {
            cout << maxDepth << endl;
            return 0;
        }
    }
    
    cout << -1 << endl;
    return 0;
}
  1. 洛谷 P2324 [SCOI2005] 骑士精神
查看答案

思路：IDA* 算法。

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677#include <iostream>
using namespace std;

int target[5][5] = {
    {1, 1, 1, 1, 1},
    {0, 1, 1, 1, 1},
    {0, 0, 2, 1, 1},
    {0, 0, 0, 0, 1},
    {0, 0, 0, 0, 0}
};

int a[5][5];
int maxDepth;
int dx[] = {-2, -2, -1, -1, 1, 1, 2, 2};
int dy[] = {-1, 1, -2, 2, -2, 2, -1, 1};

int heuristic() {
    int cnt = 0;
    for (int i = 0; i < 5; i++) {
        for (int j = 0; j < 5; j++) {
            if (a[i][j] != target[i][j]) cnt++;
        }
    }
    return cnt;
}

bool dfs(int x, int y, int depth) {
    int h = heuristic();
    if (h == 0) return true;
    if (depth + h > maxDepth) return false;
    
    for (int i = 0; i < 8; i++) {
        int nx = x + dx[i], ny = y + dy[i];
        if (nx < 0 || nx >= 5 || ny < 0 || ny >= 5) continue;
        
        swap(a[x][y], a[nx][ny]);
        if (dfs(nx, ny, depth + 1)) return true;
        swap(a[x][y], a[nx][ny]);
    }
    
    return false;
}

int main() {
    int T;
    cin >> T;
    
    while (T--) {
        int sx, sy;
        for (int i = 0; i < 5; i++) {
            string s;
            cin >> s;
            for (int j = 0; j < 5; j++) {
                if (s[j] == '*') {
                    a[i][j] = 2;
                    sx = i;
                    sy = j;
                } else {
                    a[i][j] = s[j] - '0';
                }
            }
        }
        
        bool found = false;
        for (maxDepth = 0; maxDepth <= 15; maxDepth++) {
            if (dfs(sx, sy, 0)) {
                cout << maxDepth << endl;
                found = true;
                break;
            }
        }
        
        if (!found) cout << -1 << endl;
    }
    
    return 0;
}
  1. 洛谷 P1441 砝码称重
查看答案

思路：枚举去掉的砝码，然后 DP 求解。

12345678910111213141516171819202122232425262728293031323334353637#include <iostream>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    
    int a[n];
    for (int i = 0; i < n; i++) cin >> a[i];
    
    int ans = 0;
    
    for (int mask = 0; mask < (1 << n); mask++) {
        if (__builtin_popcount(mask) != n - m) continue;
        
        bool dp[2005] = {false};
        dp[0] = true;
        
        for (int i = 0; i < n; i++) {
            if (mask & (1 << i)) continue;
            
            for (int j = 2000; j >= a[i]; j--) {
                if (dp[j - a[i]]) dp[j] = true;
            }
        }
        
        int cnt = 0;
        for (int i = 1; i <= 2000; i++) {
            if (dp[i]) cnt++;
        }
        
        ans = max(ans, cnt);
    }
    
    cout << ans << endl;
    return 0;
}

易错点

⚠️ 注意：

  1. IDDFS 是 DFS 和 BFS 的结合
  2. 逐步增加深度限制
  3. IDDFS 通常比 BFS 更省内存
  4. 适用场景有限