回溯算法
1. 什么是回溯算法
回溯可以看作是一个搜索问题解的过程,这个过程分为很多个阶段,每一个阶段我们都有很多个选择,但我们不知道选择哪一个,所以就随机选择一个继续进行下一个阶段,如果发现找不到解,就回退到上一个阶段采取另外的选择再继续搜索。
比如之前图的深度搜索问题,我们就是沿着起始顶点一直向下搜索,发现走不下去了再选择另外一条边继续搜索。
另一个经典的例子则是八皇后问题,我们有一个 8×8 的棋盘,希望在里面放置八个皇后,满足每个皇后所在的行、列和对角线都不能有另外一个皇后。
result = [0] * 8 num = [0] def print_queen(result): for row in range(8): for col in range(8): if result[row] == col: print('Q ', end='') else: print('* ', end='') print() print() def check(row, column): # 检查前面行是否有皇后位于同一列或者对角线上 leftup = column - 1 rightup = column + 1 for i in range(row-1, -1, -1): if result[i] == column: return False if 0 <= leftup == result[i]: return False if 7 >= rightup == result[i]: return False leftup -= 1 rightup += 1 return True def find_eight_queens(row): if row == 8: print_queen(result) num[0] += 1 return for column in range(8): if check(row, column): result[row] = column find_eight_queens(row+1) find_eight_queens(0) print(num[0])
我们从第 0 行开始放置皇后,每一行都有 8 种可能,但是要检查前面的行是否有皇后位于同一列或者对角线上。总共有 92 种解决方案,几个示例如下。
2. 0-1 背包问题
假设我们有一个背包,总的承重量为 W Kg,现在我们有 n 个物品,每个物品的重量不等。要求选择若干个物品,在不超过背包总承重量的前提下,尽可能放最大重量的物体。
这个问题可以看作是一系列的选择,对于 n 个物品,每一个物品我们都可以选择放入背包或者不放入背包,然后就可以用回溯的思想来解决。在这里,当我们发现选择的物品总重量超过 W 之后,我们就停止搜索,返回上一步。
items = [10, 52, 31, 20, 35, 26, 15, 60] biggest_weight = 100 n = 8 max_weight = 0 result = [] def bag(num, current_weight): global max_weight if current_weight == biggest_weight or num == n: if current_weight >= max_weight: max_weight = current_weight print(result, max_weight, num) return # 将当前物品不放入背包 bag(num+1, current_weight) # 不超重的话,将当前物品放入背包 if current_weight + items[num] <= biggest_weight: result.append(items[num]) bag(num+1, current_weight+items[num]) result.pop(-1) bag(0, 0) print(max_weight)
3. 正则表达式匹配
针对这个问题,我们需要重点考虑通配符 \('*'\) 的情况。如果 p 中下一个字符是 \('*'\),我们要分两种情况:
- 如果当前 s 和 p 的两个字符相等或者 p 中的字符为 \('.'\) 且 s 还没到末尾,那么我们有以下几个选择:
- 后面的 \('*'\) 匹配零个元素,也就是 p 跳过两个字符,s 保持当前位置不变
- 后面的 \('*'\) 匹配一个元素,也就是 p 跳过两个字符,s 跳过一个字符
- 后面的 \('*'\) 匹配多个元素,也就是 p 保持当前位置不变,s 跳过一个字符
- 如果当前 s 和 p 的两个字符不相等或者 p 中的字符也不是 \('.'\) 或者 s 还没到末尾,那么后面的 \('*'\) 必须匹配零个元素,也就是 p 跳过两个字符,s 保持当前位置不变
class Solution { public: bool isMatch(string s, string p) { return match(0, 0, s, p); } bool match(int i, int j, string &s, string &p) { // 两个字符串都到结尾了,匹配成功 if (i == s.size() && j == p.size()) return true; // 若 s 没到结尾但 p 到结尾了,匹配失败 if (i != s.size() && j == p.size()) return false; if (p[j+1] == '*') { if (s[i] == p[j] || (p[j] == '.' && i != s.size())) { return match(i, j+2, s, p) || // * 匹配零个元素 match(i+1, j+2, s, p) || // * 匹配一个元素 match(i+1, j, s, p); // * 匹配多个元素 } // 当前两个字符不想等或者 s 到达了末尾 // 则 * 只能匹配零个元素 else { return match(i, j+2, s, p); } } if (s[i] == p[j] || (p[j] == '.' && i != s.size())) { return match(i+1, j+1, s, p); } return false; } };
获取更多精彩,请关注「seniusen」!
相关推荐
hugebawu 2020-10-12
风吹夏天 2020-07-18
莫明天涯 2020-07-05
pengkingli 2020-06-25
ustbfym 2020-06-17
wonner 2020-06-04
SystemArchitect 2020-06-02
dbhllnr 2020-05-15
wonner 2020-04-25
seekerhit 2020-04-20
yedaoxiaodi 2020-04-19
sunjunior 2020-03-08
faiculty 2020-03-03
dushine00 2020-02-18
nurvnurv 2020-02-02
troysps 2020-01-08
rein0 2020-01-01
yishujixiaoxiao 2019-12-30