算法笔记之回溯算法
Kotori Y 27 Posts

回溯算法 (Backtracking) 是一种经典的算法,它通过对树形或者图形结构执行一次深度优先遍历,实际上类似枚举的搜索尝试过程,在遍历的过程中寻找问题的解。实际上,回溯算法就是暴力搜索算法,它是早期的人工智能里使用的算法,借助计算机强大的计算能力帮助我们找到问题的解。

0. 代码结构

1
2
3
4
5
6
7
8
9
10
result = []
def backtrack(路径, 选择列表):
if 满足结束条件:
result.add(路径)
return

for 选择 in 选择列表:
做选择
backtrack(路径, 选择列表)
撤销选择
  1. 路径:也就是已经做出的选择。

  2. 选择列表:也就是你当前可以做的选择。

  3. 结束条件:也就是到达决策树底层,无法再做选择的条件。

上面为回溯算法的一般框架,其本质还是一个for循环,通过不断的“选择”与“撤销”,迭代自身直至达到某个特定的终点。下面为两个例子。

1. 全排列

给定一个 没有重复 数字的序列,返回其所有可能的全排列。

示例
输入:[1, 2, 3]
输出:[ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]

如果要手动进行排列组合上面的例子,我们一般会进行这样的操作:先选出数字1,再依次选择2和3、3和2,当1开头的数排列完毕后重新选择2为开头,再类似的操作。对应地,每次所选择的数字为路径,待选择的数字为选择列表,当数字全部选择完后即为结束条件

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
/**
* @param {number[]} nums
* @return {number[][]}
*/
var permute = function (nums) {

var backtrack = (depth = 0) => {

if (depth === n) {
res.push(nums.slice())
}

for (let i = depth; i < n; i++) {
[nums[i], nums[depth]] = [nums[depth], nums[i]];
backtrack(depth + 1);
[nums[i], nums[depth]] = [nums[depth], nums[i]];
}

}

var n = nums.length
var res = []
backtrack()
return res
};

其中[nums[i], nums[depth]] = [nums[depth], nums[i]];作用为将第depth个数字依次与第i个数字进行交换($i\in[depth, n]$),即将第i个数字作为第depth层的选择。最后再将交换撤消失。时间复杂度为$O\left ( n\times n! \right )$,空间复杂度为$O\left ( n\times n! \right )$。

图片来自LeetCode(liweiwei1419)

2. N皇后

说到回溯算法就不得不提经典的“八皇后问题”。

如何能够在8×8的国际象棋棋盘上放置八个皇后,使得任何一个皇后都无法直接吃掉其他的皇后?为了达到此目的,任两个皇后都不能处于同一条横行、纵行或斜线上。八皇后问题可以推广为更一般的n皇后摆放问题:这时棋盘的大小变为n×n,而皇后个数也变成n


输入:n = 4

输出:[[“.Q..”,”…Q”,”Q…”,”..Q.”],[“..Q.”,”Q…”,”…Q”,”.Q..”]]

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
/**
* @param {number} n
* @return {string[][]}
*/
var solveNQueens = function (n) {

var backtrack = (line = 0) => {
if (line === n) {
let temp = new Array(n).fill(".").map(elem => new Array(n).fill("."))
temp.forEach((elem, idx) => elem[queensPos[idx]]="Q")
temp = temp.map(elem => elem.join(""))
res.push(temp)
}

for (let i = 0; i < n; i++) {
if (cols.has(i) ||
diagonal1.has(line + i) ||
diagonal2.has(line - i)) {
continue
}
queensPos[line] = i
cols.add(i)
diagonal1.add(line + i)
diagonal2.add(line - i)
backtrack(line + 1)
cols.delete(i)
diagonal1.delete(line + i)
diagonal2.delete(line - i)
}
}

var res = []
var queensPos = new Array(n).fill(-1)
var cols = new Set()
var diagonal1 = new Set()
var diagonal2 = new Set()
backtrack()
return res

};

依次遍历所有组合,如果在某一行没有格子可以放置皇后,则撤销上一步回滚到上一状态。时间复杂度为$O\left ( n! \right )$,空间复杂度为$O\left ( n! \right )$。

3. 参考文献

  1. 全排列

  2. N皇后

  3. 回溯算法入门级详解

  4. 八皇后问题

  • Post title:算法笔记之回溯算法
  • Post author:Kotori Y
  • Create time:2021-01-21 09:31
  • Post link:https://blog.iamkotori.com/2021/01/21/算法笔记之回溯算法/
  • Copyright Notice:All articles in this blog are licensed under BY-NC-SA unless stating additionally.
 Comments