算法|回溯法-总结

该文章阅读需要7分钟,更多文章请点击本人博客halu886

1. 回溯法

回溯法是一种选优搜索解题思路,按照优的解题思路进行向下搜索,当遇到不优的情况会退回去,换一个选择接着向下搜索。判断当前选择不为优时,则称为当前选择为回溯点。

并且回溯法又是一种通用解题思路。

总结来说就是,按一条路往前走,能进则进,不能进则退回来,换一条路走。

2. 解题

2.1. 解数独

2.1.1. 描述

编写一个程序,通过已填充的空格来解决数独问题。

一个数独的解法需遵循如下规则:

  1. 数字 1-9 在每一行只能出现一次。
  2. 数字 1-9 在每一列只能出现一次。
  3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。

空白格用 ‘.’ 表示。

1

一个数独。

2

答案被标成红色。

2.1.2. 解题思路

我们从左往右,从下往下搜索空缺的位置,然后依次将 1-9 放入当前位置,当满足条件(当前行/列/三宫格 不存在)时,进入下一个空缺的位置。
当不存在满足条件的数字(1-9)时,回溯到上一个位置,进行更新选择,继续向下搜索。

2.1.3. 源码

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
class Solution
{

private:
vector<vector<bool>> rows;
vector<vector<bool>> cols;
vector<vector<bool>> boxes;
int n = 0;
int m = 0;

void init(vector<vector<char>> &board)
{
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < n; ++j)
{
char c = board[i][j];
if (c != '.')
{
int box_id = (i / m) * m + j / m;
insert(c, i, j, box_id);
}
}
}
}
void insert(char c, int i, int j, int b)
{
rows[i][c - '0'] = true;
cols[j][c - '0'] = true;
boxes[b][c - '0'] = true;
}
bool core(vector<vector<char>> &board, int i, int j)
{
if (i == n)
{
return true;
}

if (j == n)
{
return core(board, i + 1, 0);
}

if (board[i][j] != '.')
{
return core(board, i, j + 1);
}

int box_id = (i / m) * m + j / m;

for (int k = 1; k <= n; ++k)
{
char c = '0' + k;
if (has(c, i, j, box_id))
{
continue;
}
board[i][j] = c;
insert(c, i, j, box_id);
if (core(board, i, j + 1))
{
return true;
}
erase(c, i, j, box_id);
board[i][j] = '.';
}
return false;
}
bool has(char c, int i, int j, int b)
{
return rows[i][c - '0'] || cols[j][c - '0'] || boxes[b][c - '0'];
}
void erase(char c, int i, int j, int b)
{
rows[i][c - '0'] = false;
cols[j][c - '0'] = false;
boxes[b][c - '0'] = false;
}

public:
void
solveSudoku(vector<vector<char>> &board)
{
n = board.size();
m = sqrt(n);
rows.assign(n, vector<bool>(n + 1));
cols.assign(n, vector<bool>(n + 1));
boxes.assign(n, vector<bool>(n + 1));

init(board);

core(board, 0, 0);
}
};

2.1.4. 分析

2.1.4.1. 时间复杂度

一行不会超过9行,第一个有9种情况,第二个有8种情况…所有一行总共有的(!9)
共9行,所有总共会计算不超过(!9)^9次

2.1.4.2. 空间复杂度

额外多出了col/row/boxes的空间,每一个分别81个元素。

2.2. 组合总和

2.2.1. 描述

给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

说明:

  • 所有数字(包括 target)都是正整数。
  • 解集不能包含重复的组合。

示例 1:

输入: candidates = [2,3,6,7], target = 7,
所求解集为:
[
    [7],
    [2,2,3]
]

示例 2:

输入: candidates = [2,3,5], target = 8,
所求解集为:
[
    [2,2,2,2],
    [2,3,3],
    [3,5]
]

2.2.2. 解题思路

通过将所有可能的组合的第一个数字(所有数字)列出作为根结点,每个可能的节点向下展开,子节点向下展开(所有数字),每个节点依次展开,形成一个树状的结构,直至当前路径大于等于target,停止展开。

3

从左往右,从上往下依次搜索,当前路径等于target时进行记录,并且回溯。当大于target时,不记录当前路径直接回溯。

为了防止重复记录相同路径,需要进行剪枝,当子节点小于父节点时,则当前路径已经存在,进行剪枝。

2.2.3. 源码

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;

class Solution
{

private:
vector<int> candidates;
vector<vector<int>> res;
vector<int> path;

public:
void DFS(int start, int target)
{
if (target == 0)
{
res.push_back(path);
return;
}
for (int i = start;
i < candidates.size() && target - candidates[i] >= 0; i++)
{
path.push_back(candidates[i]);
DFS(i, target - candidates[i]);
path.pop_back();
}
}

vector<vector<int>> combinationSum(vector<int> &candidates, int target)
{
std::sort(candidates.begin(), candidates.end());
this->candidates = candidates;
DFS(0, target);

return res;
}
};

2.2.4. 分析

2.2.4.1. 时间复杂度

回溯法本质上还是枚举,在这题边界过于模糊,并不太好计算。当忽略子节点等于父节点的情况,则为O((!n)^n)。

2.2.4.2. 空间复杂度

多出一个记录路径的额外的数组,数量与n无关

2.3. 通配符匹配

2.3.1. 描述

给定一个字符串 (s) 和一个字符模式 (p) ,实现一个支持 ‘?’ 和 ‘*’ 的通配符匹配。

'?' 可以匹配任何单个字符。
'*' 可以匹配任意字符串(包括空字符串)。

两个字符串完全匹配才算匹配成功。

说明:

  • s 可能为空,且只包含从 a-z 的小写字母。
  • p 可能为空,且只包含从 a-z 的小写字母,以及字符 ? 和 *。

示例 1:

输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。

示例 2:

输入:
s = "aa"
p = "*"
输出: true
解释: '*' 可以匹配任意字符串。

示例 3:

输入:
s = "cb"
p = "?a"
输出: false
解释: '?' 可以匹配 'c', 但第二个 'a' 无法匹配 'b'。

示例 4:

输入:
s = "adceb"
p = "*a*b"
输出: true
解释: 第一个 '*' 可以匹配空字符串, 第二个 '*' 可以匹配字符串 "dce".

示例 5:

输入:
s = "acdcb"
p = "a*c?b"
输入: false

2.3.2. 解题思路

通过递归回溯进行搜索两个字符串,分别两个指针进行向下遍历,当两个指针指向当字符相同或者为?时,两个指针分别进1。

当存在*,对后续的s子串进行遍历且递归。

回溯点为两个指针指向的字符不同时。

当s子串长度为0时,且p长度为0或p子串全为*。

2.3.3. 源码

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
class Solution
{

public:
bool isMatch(string s, string p)
{
int j = 0;
for (int star = 0, i = 0, last = 0; i < s.length();)
{
if (j < p.size() && (s[i] == p[j] || p[j] == '?'))
{
++i;
++j;
}
else if (j < p.size() && p[j] == '*')
{
last = i;
star = ++j;
}
else if (star != 0)
{
i = ++last;
j = star;
}
else
return 0;
}
for (; j < p.size() && p[j] == '*'; ++j)
;
return j == p.size();
}
};

2.3.4. 分析

2.3.4.1. 时间复杂度

最好的情况下就是只需要遍历一次,不存在回溯点,则为O(n)
最差的情况则是每次都是在最后回溯,O(!n)

2.3.4.2. 空间复杂度

只需要两个指针表示子串的位置,则空间复杂度为O(1)

2.4. N皇后

2.4.1. 描述

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。

4

上图为 8 皇后问题的一种解法。

给定一个整数 n,返回所有不同的 n 皇后问题的解决方案。

每一种解法包含一个明确的 n 皇后问题的棋子放置方案,该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。

示例:

输入: 4
输出: [
    [".Q..",  // 解法 1
    "...Q",
    "Q...",
    "..Q."],

    ["..Q.",  // 解法 2
    "Q...",
    "...Q",
    ".Q.."]
]
解释: 4 皇后问题存在两个不同的解法。

2.4.2. 解题思路

当前位置是否能放置Q的约束条件总共有三个,当前行不能存在其余的Q,当前列不能存在其余的Q,当前斜边不能存在其余的Q。

我们可以从左往右,从上往下进行遍历,当满足以上三个条件时进行放置Q且进入下一行,否则跳过。

当一行结束未放置Q时,则视为回溯点,向上回溯。

当遍历到最后一行时,将结果推入结果集中。进行回溯。

当回溯点为第一行最后一个时,则推出遍历,返回结果集。

2.4.3. 源码

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
class Solution
{

public:
bool valid(int n, vector<int> &cols)
{
if (cols.size() <= 1)
return true;
int row = cols.size() - 1;
int col = cols.back();
for (int r = 0; r < row; ++r)
{
int c = cols[r];
if (c == col || abs(c - col) == abs(r - row))
return false;
}
return true;
}
void backtrace(int n, vector<int> &cols, vector<vector<int>> &res)
{
if (!valid(n, cols))
return;
if (cols.size() == n)
{
res.push_back(cols);
return;
}
for (int i = 0; i < n; ++i)
{
cols.push_back(i);
backtrace(n, cols, res);
cols.pop_back();
}
}
vector<vector<string>> solveNQueens(int n)
{
vector<int> cols;
vector<vector<int>> all;
backtrace(n, cols, all);
vector<vector<string>> res;
for (auto &v : all)
{
vector<string> s;
for (auto &c : v)
{
string t(n, '.');
t[c] = 'Q';
s.push_back(t);
}
res.push_back(s);
}
return res;
}
};

2.4.4. 分析

2.4.4.1. 时间复杂度

第一行需要遍历1遍,第二行需要遍历n-1,第三行需要(n-1)(n-2)…所以时间复杂度为 O(1+n-1+(n-1)(n-2)…+!n)=O(!n)

2.4.4.2. 时间复杂度

分别需要N*N当二维数组进行记录数组O(N^2)

leetcode-解数独
leetcode-组合总和
leetcode-通配符匹配
leetcode-N皇后

谢谢老板,老板必发大财!💰💰💰💰💰💰