11、回溯算法详解

​ 回溯算法是一种经常用于解决优化问题（如寻找最短路径、最小生成树、最优布局等）和可满足性问题（如数独、八皇后问题、图的着色问题等）的方法。回溯算法的基本思想是从问题的某一种状态（即解决方案的某一部分）出发，通过尝试各种可能的移动，逐步扩大问题的解决方案。当某一步的尝试没有找到解决方案时，就“回溯”到上一步，尝试其他的移动。

以下是回溯算法的基本步骤：

  1. 选择：在当前的解决方案中，对于所有可能的选择，尝试选择一个。每一步都会产生一个新的部分解决方案。
  2. 约束：检查已选择的部分解决方案是否满足所有约束条件。如果不满足，那么舍弃该解决方案，返回上一步（即“回溯”）。
  3. 目标：检查已选择的部分解决方案是否解决了整个问题。如果已经解决了整个问题，那么这个解决方案就是一个完整的解决方案，可以被输出或记录下来。

重复这些步骤，直到找到所有解决方案，或者已经尝试了所有可能的选择都无法找到解决方案。

​ 一个关键的理念是，回溯算法利用了问题解决方案的“部分-候选”特性，即解决方案可以是逐步构造的，并且每一步都可以检查是否有解。因此，如果一个部分解决方案不能导致一个有效的解决方案，那么任何扩展这个部分解决方案的尝试都是无用的，可以立即停止这个方向的尝试，大大减少搜索的空间和时间。

回溯算法在各种问题中都有应用。下面是一些常见的使用回溯算法的案例：

  1. 八皇后问题：在 8×8 的棋盘上放置 8 个皇后，使得任何一个皇后都不能攻击到其他皇后。这意味着在任何一行、一列和对角线上都不能有两个皇后。
C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

vector<vector<string>> solutions;

bool is_valid(vector<string> &queen, int row, int col) {
    for (int i = 0; i < row; ++i) {
        if (queen[i][col] == 'Q')
            return false;
    }
    for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; --i, --j) {
        if (queen[i][j] == 'Q')
            return false;
    }
    for (int i = row - 1, j = col + 1; i >= 0 && j < queen.size(); --i, ++j) {
        if (queen[i][j] == 'Q')
            return false;
    }
    return true;
}

void solve(vector<string> &queen, int row) {
    int n = queen.size();
    if (row == n) {
        solutions.push_back(queen);
        return;
    }
    for (int col = 0; col < n; ++col) {
        if (is_valid(queen, row, col)) {
            queen[row][col] = 'Q';
            solve(queen, row + 1);
            queen[row][col] = '.'; // 回溯，撤销上一步的选择
        }
    }
}

int main() {
    int n = 8;
    vector<string> queen(n, string(n, '.'));
    solve(queen, 0);

    // 打印所有解
    for (auto &solution : solutions) {
        for (string &row : solution) {
            cout << row << endl;
        }
        cout << "-----" << endl;
    }

    return 0;
}
  1. 图的着色：给定无向图和 m 种不同的颜色。使用这些颜色为图的顶点着色，使得图的任意两个相邻顶点颜色不同。
C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <iostream>
#include <list>
#define V 4
using namespace std;

// check if it is safe to assign color
bool isSafe (int v, bool graph[V][V], int color[], int c) {
    for (int i = 0; i < V; i++)
        if (graph[v][i] && c == color[i])
            return false;
    return true;
}

//recursive function to solve m coloring problem
bool graphColoringUtil(bool graph[V][V], int m, int color[], int v) {
    if (v == V)
        return true;

    for (int c = 1; c <= m; c++) {
        if (isSafe(v, graph, color, c)) {
            color[v] = c;

            if (graphColoringUtil(graph, m, color, v + 1) == true)
                return true;

            color[v] = 0;
        }
    }

    return false;
}

bool graphColoring(bool graph[V][V], int m) {
    int color[V];
    for (int i = 0; i < V; i++)
        color[i] = 0;

    if (graphColoringUtil(graph, m, color, 0) == false) {
        cout << "Solution does not exist";
        return false;
    }

    printSolution(color);
    return true;
}

void printSolution(int color[]) {
    cout << "Solution Exists:"
            " Following are the assigned colors \n";
    for (int i = 0; i < V; i++)
        cout << " " << color[i] << " ";
    cout << endl;
}

int main() {
    bool graph[V][V] = {
        { 0, 1, 1, 1 },
        { 1, 0, 1, 0 },
        { 1, 1, 0, 1 },
        { 1, 0, 1, 0 },
    };
    int m = 3; 
    graphColoring (graph, m);
    return 0;
}
  1. 旅行商问题：给定一系列城市和每对城市之间的距离，找出一个最短的可能的旅程，使得旅行者访问了每个城市一次并且回到原始的城市。
C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <bits/stdc++.h>
using namespace std;
#define N 4

// Implementation of traveling Salesman Problem.
int travllingSalesmanProblem(int graph[N][N], int s) {
    vector<int> vertex;
    for (int i = 0; i < N; i++)
        if (i != s)
            vertex.push_back(i);

    // store minimum weight Hamiltonian Cycle.
    int min_path = INT_MAX;
    do {
        int current_pathweight = 0;

        // compute current path weight
        int k = s;
        for (int i = 0; i < vertex.size(); i++) {
            current_pathweight += graph[k][vertex[i]];
            k = vertex[i];
        }
        current_pathweight += graph[k][s];

        // update minimum
        min_path = min(min_path, current_pathweight);

    } while (next_permutation(vertex.begin(), vertex.end()));

    return min_path;
}

// Driver code
int main() {
    // matrix representation of graph
    int graph[][N] = { { 0, 10, 15, 20 },
                       { 10, 0, 35, 25 },
                       { 15, 35, 0, 30 },
                       { 20, 25, 30, 0 } };
    int s = 0;
    cout << travllingSalesmanProblem(graph, s) << endl;
    return 0;
}
  1. 数独：数独是一个填数字的游戏。整个游戏包含 9×9 的网格，网格又被分割成了 9 个 3×3 的小网格。要在每一行、每一列的 9 个单元格中填入 1-9 的数字，且在每一个 3×3 的小网格中也填入 1-9 的数字，使得整个数独有唯一解。
C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#define UNASSIGNED 0
#define N 9

bool isSafe(int grid[N][N], int row, int col, int num);

bool solveSudoku(int grid[N][N]) {
    int row, col;

    if (!FindUnassignedLocation(grid, row, col))
        return true;

    for (int num = 1; num <= 9; num++) {
        if (isSafe(grid, row, col, num)) {
            grid[row][col] = num;

            if (solveSudoku(grid))
                return true;

            grid[row][col] = UNASSIGNED;
        }
    }
    return false;
}

bool FindUnassignedLocation(int grid[N][N], int &row, int &col) {
    for (row = 0; row < N; row++)
        for (col = 0; col < N; col++)
            if (grid[row][col] == UNASSIGNED)
                return true;
    return false;
}

bool isSafe(int grid[N][N], int row, int col, int num) {
    return !UsedInRow(grid, row, num) &&
           !UsedInCol(grid, col, num) &&
           !UsedInBox(grid, row - row % 3, col - col % 3, num);
}

bool UsedInRow(int grid[N][N], int row, int num) {
    for (int col = 0; col < N; col++)
        if (grid[row][col] == num)
            return true;
    return false;
}

bool UsedInCol(int grid[N][N], int col, int num) {
    for (int row = 0; row < N; row++)
        if (grid[row][col] == num)
            return true;
    return false;
}

bool UsedInBox(int grid[N][N], int boxStartRow, int boxStartCol, int num) {
    for (int row = 0; row < 3; row++)
        for (int col = 0; col < 3; col++)
            if (grid[row + boxStartRow][col + boxStartCol] == num)
                return true;
    return false;
}
  1. 迷宫问题：在二维网格中寻找从源到目标的路径。
C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <iostream>
#include <vector>

#define N 4

bool isSafe(int maze[N][N], int x, int y) {
    return (x >= 0 && x < N && y >= 0 && y < N && maze[x][y] == 1);
}

bool solveMazeUtil(int maze[N][N], int x, int y, int sol[N][N]) {
    if (x == N - 1 && y == N - 1 && maze[x][y] == 1) {
        sol[x][y] = 1;
        return true;
    }

    if (isSafe(maze, x, y)) {
        if (sol[x][y] == 1)
            return false;

        sol[x][y] = 1;

        if (solveMazeUtil(maze, x + 1, y, sol))
            return true;

        if (solveMazeUtil(maze, x, y + 1, sol))
            return true;

        if (solveMazeUtil(maze, x - 1, y, sol))
            return true;

        if (solveMazeUtil(maze, x, y - 1, sol))
            return true;

        sol[x][y] = 0; // backtrack
        return false;
    }

    return false;
}

void solveMaze(int maze[N][N]) {
    int sol[N][N] = { { 0, 0, 0, 0 },
                      { 0, 0, 0, 0 },
                      { 0, 0, 0, 0 },
                      { 0, 0, 0, 0 } };

    if (!solveMazeUtil(maze, 0, 0, sol)) {
        std::cout << "Solution doesn't exist";
        return;
    }

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++)
            std::cout << sol[i][j] << " ";
        std::cout << std::endl;
    }
}

int main() {
    int maze[N][N] = { { 1, 0, 0, 0 },
                       { 1, 1, 0, 1 },
                       { 0, 1, 0, 0 },
                       { 1, 1, 1, 1 } };

    solveMaze(maze);
    return 0;
}
  1. 分割问题：将一个集合或者一串数字分割成满足特定属性的多个子集，如把一个集合分割成两个子集，使得两个子集的元素之和相等。
C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
//子集分割问题
#include <iostream>
#include <vector>
using namespace std;

void subsetsUtil(vector<int>& A, vector<vector<int> >& res, vector<int>& subset, int index) {
    res.push_back(subset);
    for (int i = index; i < A.size(); i++) {
        subset.push_back(A[i]);
        subsetsUtil(A, res, subset, i + 1);
        subset.pop_back();  // 进行回溯
    }

    return;
}

vector<vector<int> > subsets(vector<int>& A) {
    vector<int> subset;
    vector<vector<int> > res;

    int index = 0;
    subsetsUtil(A, res, subset, index);

    return res;
}

int main() {
    vector<int> A = {1, 2, 3};
    vector<vector<int> > res = subsets(A);

    for (int i = 0; i < res.size(); i++) {
        for (int j = 0; j < res[i].size(); j++)
            cout << res[i][j] << " ";
        cout << endl;
    }

    return 0;
}
  1. 密码生成：生成满足特定规则的所有可能的密码。
C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include <vector>
#include <string>

void generatePasswordsHelper(int length, string password, vector<string>& result) {
    if (password.length() == length) {
        result.push_back(password);
        return;
    }

    for (int i = 0; i <= 9; i++) {
        generatePasswordsHelper(length, password + to_string(i), result);
    }
}

vector<string> generatePasswords(int length) {
    vector<string> result;
    generatePasswordsHelper(length, "", result);
    return result;
}

int main() {
    vector<string> passwords = generatePasswords(4);

    for (string password : passwords) {
        cout << password << "\n";
    }

    return 0;
}
  1. 括号生成：生成所有合法的括号对。
C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <iostream>
#include <vector>
#include <string>

using namespace std;

void generateParenthesisHelper(int left, int right, string parenthesis, vector<string>& result) {
    if (left > right)
        return;

    if (left == 0 && right == 0) {
        result.push_back(parenthesis);
        return;
    }

    if (left > 0) {
        generateParenthesisHelper(left - 1, right, parenthesis + "(", result);
    }

    if (right > 0) {
        generateParenthesisHelper(left, right - 1, parenthesis + ")", result);
    }
}

vector<string> generateParenthesis(int n) {
    vector<string> result;
    generateParenthesisHelper(n, n, "", result);
    return result;
}

int main() {
    vector<string> parenthesis = generateParenthesis(3);

    for (string p : parenthesis) {
        cout << p << "\n";
    }

    return 0;
}
C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
//棋盘分割问题
#include <numeric>
#include <algorithm>
#include <vector>
using namespace std;

bool canPartitionKSubsets(vector<int>& nums, int k) {
    int sum = accumulate(nums.begin(), nums.end(), 0);
    if (sum % k != 0) return false;
    vector<int> visited(nums.size(), 0);
    return canPartition(nums, visited, 0, k, 0, 0, sum / k);
}

bool canPartition(vector<int>& nums, vector<int>& visited, int start_index, int k, int cur_sum, int cur_num, int target) {
    if (k == 1) return true;
    if (cur_sum == target && cur_num > 0) return canPartition(nums, visited, 0, k - 1, 0, 0, target);
    for (int i = start_index; i < nums.size(); i++) {
        if (!visited[i]) {
            visited[i] = 1;
            if (canPartition(nums, visited, i + 1, k, cur_sum + nums[i], cur_num++, target)) return true;
            visited[i] = 0;
        }
    }
    return false;
}
  1. 解决游戏：有些游戏可以通过回溯来找出解决方案，例如跳跳棋、魔方等。
C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
//跳跳棋问题
#include <iostream>
#include <vector>
using namespace std;

#define N 7
int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 上下左右四个移动方向

// 打印棋盘
void print_board(vector<vector<int>> &board) {
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            if (board[i][j] == -1) cout << " ";
            else if (board[i][j] == 0) cout << "O";
            else cout << "X";
            cout << " ";
        }
        cout << endl;
    }
    cout << "----------" << endl;
}

// 检查坐标是否合法
bool in_board(int x, int y) {
    return x >= 0 && x < N && y >= 0 && y < N;
}

bool solitaire(vector<vector<int>> &board, int left) {
    if (left == 1) { // 只剩一个棋子，任务完成
        print_board(board);
        return true;
    }

    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            if (board[i][j] == 1) { // 找到一个棋子
                for (int k = 0; k < 4; ++k) { // 试图在四个方向上跳跃
                    int x = i + 2 * dir[k][0], y = j + 2 * dir[k][1]; // 跳跃后的坐标
                    int mx = i + dir[k][0], my = j + dir[k][1]; // 中间的坐标
                    if (in_board(x, y) && board[x][y] == 0 && board[mx][my] == 1) { // 能跳跃
                        // 执行跳跃
                        board[i][j] = 0;
                        board[mx][my] = 0;
                        board[x][y] = 1;
                        // 递归尝试接下来的步骤
                        if (solitaire(board, left - 1))
                            return true;
                        // 回溯
                        board[i][j] = 1;
                        board[mx][my] = 1;
                        board[x][y] = 0;
                    }
                }
            }
        }
    }
    return false;
}

int main() {
    vector<vector<int>> board(N, vector<int>(N, -1));
    // 初始化棋盘，1代表有棋子，0代表无棋子，-1代表不能放棋子的位置
    for (int i = 2; i < 5; ++i) {
        for (int j = 0; j < N; ++j) {
            board[i][j] = 1;
        }
    }
    for (int j = 2; j < 5; ++j) {
        for (int i = 0; i < N; ++i) {
            board[i][j] = 1;
        }
    }
    // 设置一个初始空位
    board[3][3] = 0;
    // 开始解决问题
    solitaire(board, 32);
    return 0;
}

  1. 生成排列和组合：生成集合的所有排列或组合。

    C++
     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
    #include <iostream>
#include <string>
using namespace std;

void permute(string str, int l, int r) {
    if (l == r)
        cout << str << endl;
    else {
        for (int i = l; i <= r; i++) {
            swap(str[l], str[i]);
            permute(str, l+1, r);
            swap(str[l], str[i]); // 回溯
        }
    }
}

int main() {
    string str = "ABC";
    int n = str.size();
    permute(str, 0, n-1);
    return 0;
}
本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用