算法-回溯算法 - 日勿の部落格

n 后问题#

问题定义#

在 $n \times n$ 格的棋盘上放置彼此不受攻击的 $n$ 个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。 $n$ 后问题等价于在 $n \times n$ 格的棋盘上放置 $n$ 个皇后，任何 2 个皇后不放在同一行或同一列或同一斜线上。

算法思想#

用 $n$ 元组 $x[1:n]$ 表示 $n$ 后问题的解。其中， $x[i]$ 表示皇后 $i$ 放在第 $i$ 行的第 $x[i]$ 列，则存在以下要求：

不在同一行： $i$ 不同就可以保证
不在同一列： $x[i]$ 表示第 $x[i]$ 列，因此 $x[i]$ 也互不相同

[!info] 对于不在同一斜线的情况，做出以下论述。

假设 $n \times n$ 格的棋盘的行号从左到右、列号从上到下分别为 $1,2,...,n$ ，则：

斜率为 $-1$ 的直线（有若干条，且互相平行）所对应的格子，例如下图中黄色方格的坐标分别为 $(1,2),\ (2,3)$ ，其横纵坐标的差值都为 $-1$ 。同理，红色、黄色对应方格的坐标差值 $0$ 和 $-2$ ，也是分别相同的。

因此，假设两个皇后放置的位置分别为 $(i,j),\ (k,l)$ ，若 $i-j=k-l$ ，则说明两者同处于斜率为 $-1$ 的斜线上。
斜率为 $+1$ 的直线所对应的格子，例如下图中宇宙超级无敌绝绝魅惑紫色方格的坐标分别为 $(2,1),\ (1,2)$ ，其横纵坐标的和都为 $3$ 。同理，青色与褐色对应的方格的坐标和也是分别相同的。

因此，假设两个皇后放置的位置分别为 $(i,j),\ (k,l)$ ，若 $i+j=k+l$ ，则说明两者同处于斜率为 $+1$ 的斜线上。

综上所述，我们可以给出 N 后问题的所有约束。

代码实现#

[!info] 关于 N 后问题，有一个未按照上述思路优化的原始版本，见仓库代码 NQueen.c

1
/**
2
 * 判断在指定位置放置皇后是否可行
3
 *
4
 * @param solution 存放皇后位置的数组
5
 * @param row      当前行数
6
 * @param col      当前列数
7
 * @return         如果安全放置皇后，则返回 true；否则返回 false
8
 */
9
bool isSafe(int* solution, int row, int col) {
10
    for (int i = 0; i < row; i++) {
11
        // 检查是否在同一列或同一斜线上
12
        if (solution[i] == col || abs(i - row) == abs(solution[i] - col)) {
13
            return false;
14
        }
15
    }
16
    return true;
17
}
18

19
/**
20
 * 解决N皇后问题的辅助函数
21
 *
22
 * @param solution 存放皇后位置的数组
23
 * @param row 当前处理的行
24
 * @param n 皇后的数量
25
 */
26
void solveNQueensUtil(int* solution, int row, int n) {
27
    if (row == n) {
28
        // 处理完最后一行，表示找到一个解
29
        printSolution(solution, n);
30
        return;
31
    }
32

33
    for (int col = 0; col < n; col++) {  // 遍历当前行的每一列
34
        if (isSafe(solution, row, col)) {
35
            // 当前位置安全，将皇后放置在该位置
36
            solution[row] = col;
37

38
            // 递归地尝试放置下一行的皇后
39
            solveNQueensUtil(solution, row + 1, n);
40

41
            // 没有显式地撤销当前皇后的位置，这是因为我们使用了一个一维数组 solution 来存储每行皇后的列位置
42
            // 回溯：当递归返回到当前行时，我们会继续在其他列尝试放置皇后。在这个过程中，solution[row] 的值会被新的列位置覆盖，这实际上就是撤销了之前放置在该行的皇后。
43

44
        }
45
    }
46
}
47

48
/**
49
 * 解决N皇后问题
50
 *
51
 * @param n 皇后的数量
52
 */
53
void solveNQueens(int n) {
54
    int* solution = (int*)malloc(n * sizeof(int));  // 申请分配用于存放皇后位置的数组
55

56
    solveNQueensUtil(solution, 0, n);  // 从第0行开始处理
57

58
    free(solution);  // 释放内存
59
}

[!question] 为什么 isSafe() 中检查冲突时，只需要检查前 row 行？

在 N 后问题中，我们通常会按行顺序，每一次放置一个皇后。也就是说，当我们在检查是否可以在第 row 行和第 col 列放置皇后时，我们知道所有在第 row 行之前的行已经放置了皇后，而所有在第 row 行之后的行还没有放置皇后。

01 背包问题#

问题定义#

01 背包问题是背包问题的一个特例，即装入物品时，不能装入物品的一部分，要么全部装入、要么不装入，因为这种非此即彼的选择方式，得名 01 背包问题。

算法思想#

在背包问题的解决过程中，我们需要尝试所有可能的物品组合，以找到最优解。为了实现这一点，我们对每个物品都有两种选择：选择它或者不选择它，分别对应解空间的左右子树。当我们选择了一个物品（即 selected[index] = true;）并递归地处理了所有后续的物品后，我们需要撤销对当前物品的选择，以便我们可以在不选择当前物品的情况下，尝试所有可能的后续选择。

但是，当不选择当前物品时，我们可以借助剪枝函数提前回溯：若不选择当前物品 index，则假设尽力装入从下一物品 index+1 开始的剩余物品（按背包问题的方式，即可以装入部分），可以求出一个价值上界。那么：

如果这个价值上界小于当前的最高价值，则无需继续考虑从 index+1 开始的该分枝。原因很简单，你 TM 把剩下的破玩意都塞进去也不能达到新的最大价值，那我还装你干什么。
反之，如果这个价值上界大于当前的最高价值，那才有考虑该分枝的价值。

代码实现#

1
// 定义物品结构体
2
typedef struct {
3
    int id;
4
    int weight;
5
    int value;
6
} Item;
7

8
/**
9
 * 计算选择剩余所有物品后的价值上界
10
 *
11
 * @details 用于剪枝，如果价值上界小于当前最大价值，则不再继续搜索
12
 *
13
 * @param items 物品数组
14
 * @param n 物品数量
15
 * @param W 背包容量
16
 * @param index 当前物品索引
17
 * @param currentWeight 当前背包重量
18
 * @param currentValue 当前背包价值
19
 * @return 价值上界
20
 */
21
int upperBound(Item* items, int n, int W, int index, int currentWeight, int currentValue) {
22
    int remainingWeight = W - currentWeight;  // 剩余容量
23
    int upperValue = currentValue;  // 上界价值：初始值为当前已选中物品的总价值
24

25
    // 从index开始，尽可能多地装入物品
26
    while (index < n && items[index].weight <= remainingWeight) {  // 不是最后一个物品，且剩余容量足够装下当前物品
27
        remainingWeight -= items[index].weight;
28
        upperValue += items[index].value;
29
        index++;
30
    }
31

32
    if (index < n) {  // 剩余容量不足以装下当前物品
33
        upperValue += (remainingWeight * (items[index].value/items[index].weight));  // 装入部分当前物品，更新上界价值
34
    }
35

36
    return upperValue;
37
}
38

39
/**
40
 * 回溯搜索函数
41
 *
42
 * @param items 物品数组
43
 * @param n 物品数量
44
 * @param W 背包容量
45
 * @param selected 选中的物品数组
46
 * @param currentWeight 当前背包重量
47
 * @param currentValue 当前背包价值
48
 * @param maxValue 最大背包价值
49
 * @param index 当前物品索引
50
 */
51
void backtrack(Item* items, int n, int W, bool* selected, int* currentWeight, int* currentValue, int* maxValue, int index) {
52
    if (index == n) {  // 处理完所有物品
53
        if (*currentWeight <= W && *currentValue > *maxValue) {  // 找到一个更优解
54
            *maxValue = *currentValue;
55
            printf("The max value is: %d\n", *maxValue);
56
            printf("The best choice is as follows:\n");
57
            for (int i = 0; i < n; i++) {
58
                if (selected[i]) {
59
                    printf("item %d\n", items[i].id);
60
                }
61
            }
62
            printf("----------\n");
63
        }
64
        return;
65
    }
66

67
    if (*currentWeight + items[index].weight <= W) {  // 当前物品可以装入背包
68
        selected[index] = true;  // 选中当前物品
69
        // 更新当前总重量和总价值
70
        *currentWeight += items[index].weight;
71
        *currentValue += items[index].value;
72
        // 选择当前物品的情况下，递归处理下一个物品
73
        backtrack(items, n, W, selected, currentWeight, currentValue, maxValue, index + 1);
74

75
        selected[index] = false;  // 撤销选择当前的物品
76
        // 恢复不选择这个物品时的总重量和总价值
77
        *currentWeight -= items[index].weight;
78
        *currentValue -= items[index].value;
79
    }
80

81
    // 不选择当前物品(从index+1开始)的情况下，尝试所有可能的后续选择
82
    // 如果选择剩余物品的上界价值大于当前最大价值，则递归处理下一个物品
83
    if (upperBound(items, n, W, index + 1, *currentWeight, *currentValue) > *maxValue) {
84
        backtrack(items, n, W, selected, currentWeight, currentValue, maxValue, index + 1);
85
    }
86
}
87

88
/**
89
 * 解决01背包问题
90
 *
91
 * @param items 物品数组
92
 * @param n 物品数量
93
 * @param W 背包容量
94
 */
95
void knapsack(Item* items, int n, int W) {
96
    // 初始化
97
    bool selected[n];
98
    int currentWeight = 0;
99
    int currentValue = 0;
100
    int maxValue = 0;
101
    int index = 0;
102

103
    // 按照单位重量价值进行降序排序
104
    qsort(items, n, sizeof(Item), compare);
105
    printf("Sort by unitValue:\n");
106
    for (int i = 0; i < n; i++)
107
    {
108
        printf("item %d: weight = %d, value = %d, unitValue = %d\n", items[i].id, items[i].weight, items[i].value, items[i].value/items[i].weight);
109
    }
110
    printf("----------\n");
111

112

113
    backtrack(items, n, W, selected, &currentWeight, &currentValue, &maxValue, index);
114

115
    printf("The final best value is: %d\n", maxValue);
116
}

日勿の部落格

n 后问题#

问题定义#

算法思想#

代码实现#

01 背包问题#

问题定义#

算法思想#

代码实现#

目录