登录以参加训练计划

课件

回溯算法概述

回溯是一种试探性搜索算法，通过尝试各种可能性，如果发现当前路径不可行就回退到之前的状态。

回溯三步法

1. 做出选择 — 选定当前步骤的选项
2. 递归下一步 — 进入下一层搜索
3. 撤销选择（回溯） — 恢复状态，尝试其他选项

适用场景

• 排列组合问题
• 八皇后问题
• 图着色问题
• 数独求解

全排列模板

int n;
bool used[20];
int ans[20];

void dfs(int p) {
    if (p > n) {
        for (int i = 1; i <= n; i++) cout << ans[i] << " ";
        cout << endl;
        return;
    }
    for (int i = 1; i <= n; i++) {
        if (used[i]) continue;
        used[i] = true;     // 做选择
        ans[p] = i;
        dfs(p + 1);         // 递归
        used[i] = false;    // 回溯
    }
}

八皇后模板

使用三个数组分别记录列、主对角线、副对角线的占用情况：

bool col[20], dia1[40], dia2[40];

void dfs(int x) {
    if (x > n) { ans++; return; }
    for (int i = 1; i <= n; i++) {
        if (!col[i] && !dia1[i - x + n] && !dia2[i + x]) {
            col[i] = dia1[i - x + n] = dia2[i + x] = true;
            dfs(x + 1);
            col[i] = dia1[i - x + n] = dia2[i + x] = false;
        }
    }
}

图着色模板

bool check(int p, int c) {
    for (int i = 1; i < p; i++)
        if (g[p][i] && color[i] == c) return false;
    return true;
}

void dfs(int p) {
    if (p > n) { ans++; return; }
    for (int i = 1; i <= m; i++) {
        if (check(p, i)) {
            color[p] = i;
            dfs(p + 1);
            color[p] = 0;
        }
    }
}

素数环

void dfs(int p) {
    if (p > n) {
        if (isprime(ans[1] + ans[n])) { /* 输出 */ }
        return;
    }
    for (int i = 2; i <= n; i++) {
        if (num[i]) continue;
        if (!isprime(i + ans[p-1])) continue;
        ans[p] = i;
        num[i] = true;
        dfs(p + 1);
        num[i] = false;
    }
}

注意事项

1. 回溯的核心在于"恢复状态"，忘记回溯会导致状态污染
2. 八皇后问题中对角线的公式：主对角线 i - x + n，副对角线 i + x
3. 图着色问题是NP完全问题，一般只适用于小规模