算法思想 - 回溯算法
2020-04-07 本文已影响0人
天命_风流
回溯思想
回溯算法的思想非常好理解，之前我们也使用回溯的思想完成了图的深度优先搜索。简单来说，回溯的思想是这样的：假设你在走迷宫，现在你站在一个分岔口，你不知道该向哪里走，所以你随机选择一个路口向前走，当你走到死胡同（或者已经走过的路）的时候，你知道这条路不对，于是你退回到上一个路口，选择另一条路再走。这样往复，直到找到出口。
适合使用回溯的问题
回溯算法适合解决这样一类问题：在一组数据中，我们有一个期望得到的解，在求解的过程中，我们可以有规律的枚举所有的解，过程中通过不断地回溯、剪枝，最终得到一个与条件最接近的解。
你能发现，回溯算法的应用场景和贪婪算法的应用场景很像，但是贪婪算法并不一定能求得最优解，而回溯虽然要枚举的量很大，但是可以找到最接近期待的解。
回溯的例子
八皇后（n皇后）问题
八皇后是回溯算法的招牌案例，它的描述如下：
八皇后.jpg
如何利用回溯思想扎到棋盘上的皇后排列呢？
我们把这个问题划分成 8 个阶段，依次将 8 个棋子放到第一行、第二行...第八行中。在放置的过程中，我们不停地检查当前的放法。如果满足要求，进入下一行的放置；如果不满足要求，就换一种放法，继续尝试。
下面是专栏老师给出的代码：
int[] result = new int[8];//全局或成员变量,下标表示行,值表示queen存储在哪一列
public void cal8queens(int row) { // 调用方式：cal8queens(0);
if (row == 8) { // 8个棋子都放置好了，打印结果
printQueens(result);
return; // 8行棋子都放好了，已经没法再往下递归了，所以就return
}
for (int column = 0; column < 8; ++column) { // 每一行都有8中放法
if (isOk(row, column)) { // 有些放法不满足要求
result[row] = column; // 第row行的棋子放到了column列
cal8queens(row+1); // 考察下一行
}
}
}
private boolean isOk(int row, int column) {//判断row行column列放置是否合适
int leftup = column - 1, rightup = column + 1;
for (int i = row-1; i >= 0; --i) { // 逐行往上考察每一行
if (result[i] == column) return false; // 第i行的column列有棋子吗？
if (leftup >= 0) { // 考察左上对角线：第i行leftup列有棋子吗？
if (result[i] == leftup) return false;
}
if (rightup < 8) { // 考察右上对角线：第i行rightup列有棋子吗？
if (result[i] == rightup) return false;
}
--leftup; ++rightup;
}
return true;
}
private void printQueens(int[] result) { // 打印出一个二维矩阵
for (int row = 0; row < 8; ++row) {
for (int column = 0; column < 8; ++column) {
if (result[row] == column) System.out.print("Q ");
else System.out.print("* ");
}
System.out.println();
}
System.out.println();
}
我自己使用python实现了这个功能，同时我还添加了一个扩展功能：将 八皇后 扩展为 n皇后的求解：
def queens(row, n=8, res=None):
'''
进行 n 皇后的求解，之后的注释默认 n = 8
:param row: 当前所在行
:param n: 输入 n 可求解 n皇后 问题，如果不输入，默认为 8皇后
:param res: 当前 n皇后的保存，如果不输入，默认构造 8皇后的数组
:return: None
'''
if res == None:
res = [None for i in range(n)] # 如果没有参数，默认构造 res[n] 的数组
if row == n: # 求解完成
print_queens(res, n=n) # 输出棋盘
return
for column in range(n): # 求解没有完成，进行求解，对每个 row 进行 8 次迭代尝试
if isOK(row, column, res, n=n): # 如果放置的棋子符合规则，继续进行尝试，如果不符合规则，回溯（在这里是什么也不做）
res[row] = column
queens(row + 1, n=n, res=res)
def print_queens(res, n=8): # 输出棋盘
for i in res:
p = [1 if i == j else 0 for j in range(n)]
print(p)
print('---------------------------------------------------')
def isOK(row, column, res, n=8): # 判断当前棋子是否符合规则
l = column - 1 # 用于判断左上方有没有棋子
r = column + 1 # 判断右上方
i = row - 1 # 判断上方
while i >= 0:
if res[i] == column: # 上方有棋子
return False
if l >= 0:
if res[i] == l: # 左上方有棋子
return False
if r < n:
if res[i] == r: # 右上方有棋子
return False
l -= 1
r += 1
i -= 1
return True
if __name__ == "__main__":
r = queens(0, n=5) # 默认进行 8皇后求解，你可以输入任意一个数 n
如果不理解计算机的工作过程，你很难理解回溯算法在计算机中的执行过程。如果你看不明白这段代码，那你最好自己复制这段代码到 pycharm 中设置程序断点自己看一看程序的函数调用栈。
0-1背包问题
我们有一个背包，背包总的承载重量是 Wkg。现在我们有 n 个物品，每个物品的重量不等，并且不可分割。我们现在期望选择几件物品，装载到背包中。在不超过背包所能装载重量的前提下，如何让背包中物品的总重量最大？
思路：我们可以将这个问题抽象化：总共有 n 个物品，面对每个物品我们有两个选择：放入背包 或者 不放入背包。这样，整个问题的所有可能性就是 2n（也就是这个问题的解空间）。我们尝试将某个物品放入背包：如果背包没有超重，就可以尝试再放一个物品；如果背包超重，就放弃这种操作。（实际上，在放弃这种操作的同时，你一并放弃了在执行这种操作之后的其它各种操作，这种方式叫做剪枝，剪枝是个非常有意思的东西，有机会我会写一下这个操作的含义）
专栏作者给出了如下的代码：
public int maxW = Integer.MIN_VALUE; //存储背包中物品总重量的最大值
// cw表示当前已经装进去的物品的重量和；i表示考察到哪个物品了；
// w背包重量；items表示每个物品的重量；n表示物品个数
// 假设背包可承受重量100，物品个数10，物品重量存储在数组a中，那可以这样调用函数：
// f(0, 0, a, 10, 100)
public void f(int i, int cw, int[] items, int n, int w) {
if (cw == w || i == n) { // cw==w表示装满了;i==n表示已经考察完所有的物品
if (cw > maxW) maxW = cw;
return;
}
f(i+1, cw, items, n, w);
if (cw + items[i] <= w) {// 已经超过可以背包承受的重量的时候，就不要再装了
f(i+1,cw + items[i], items, n, w);
}
}
我的python代码：
import random
def bag(cur_index, already_weight, weight, goods, goods_len,res):
'''
放物品函数，在这个函数中，会更改 max_w 的值，
:param cur_index:当前物品的序号
:param already_weight: 当前背包已经装装载的重量，注意，是已经装载的重量，也就是说不包括下标为 cur_index 的物品
:param weight: 背包承重
:param goods:所有物品的重量
:param goods_len: 物品的数量
:param res: 记录被放入背包的物品的重量
:return:
'''
global max_w
if already_weight == weight or cur_index == goods_len:#背包当前重量真好满足条件 或 已经取到了最后一个物品
if already_weight > max_w :
max_w = already_weight
print('背包内有{}，重量为{}'.format(res,sum(res)))
return
bag(cur_index + 1,already_weight,weight,goods,goods_len,res)#不装当前物品，already_weight不增大
if already_weight + goods[cur_index] <= weight:#装当前物品，already_weight增加当前物品的重量
x = res.copy()#记录背包里的物品
x.append(goods[cur_index])
bag(cur_index + 1,already_weight+goods[cur_index],weight,goods,goods_len,x)
if __name__ =='__main__':
goods = [random.randint(0,50) for i in range(10)]
print('所有物品的重量如下：',goods)
max_w = max(goods)
bag(0,0,145,goods,len(goods),[])
print('背包最多可以装：',max_w)
正则匹配
正则表达式中，最重要的就是通配符，通配符结合在一起，可以表达非常丰富的语义。为了方便讲解，我假设正则表达式中只包含“”和“?”这两种通配符，并且对这两个通配符的语义稍微做些改变，其中，“”匹配任意多个（大于等于 0 个）任意字符，“?”匹配零个或者一个任意字符。基于以上背景假设，我们看下，如何用回溯算法，判断一个给定的文本，能否跟给定的正则表达式匹配？
我们依次考察正则表达式中的每个字符，当是非通配符时，我们就直接跟文本的字符进行匹配，如果相同，则继续往下处理；如果不同，则回溯。
如果遇到特殊字符的时候，我们就有多种处理方式了，也就是所谓的岔路口，比如“*”有多种匹配方案，可以匹配任意个文本串中的字符，我们就先随意的选择一种匹配方案，然后继续考察剩下的字符。如果中途发现无法继续匹配下去了，我们就回到这个岔路口，重新选择一种匹配方案，然后再继续匹配剩下的字符。
专栏作者的代码如下：
public class Pattern {
private boolean matched = false;
private char[] pattern; // 正则表达式
private int plen; // 正则表达式长度
public Pattern(char[] pattern, int plen) {
this.pattern = pattern;
this.plen = plen;
}
public boolean match(char[] text, int tlen) { // 文本串及长度
matched = false;
rmatch(0, 0, text, tlen);
return matched;
}
private void rmatch(int ti, int pj, char[] text, int tlen) {
if (matched) return; // 如果已经匹配了，就不要继续递归了
if (pj == plen) { // 正则表达式到结尾了
if (ti == tlen) matched = true; // 文本串也到结尾了
return;
}
if (pattern[pj] == '*') { // *匹配任意个字符
for (int k = 0; k <= tlen-ti; ++k) {
rmatch(ti+k, pj+1, text, tlen);
}
} else if (pattern[pj] == '?') { // ?匹配0个或者1个字符
rmatch(ti, pj+1, text, tlen);
rmatch(ti+1, pj+1, text, tlen);
} else if (ti < tlen && pattern[pj] == text[ti]) { // 纯字符匹配才行
rmatch(ti+1, pj+1, text, tlen);
}
}
}
我的python代码：
class Pattern:
def __init__(self, pattern):
'''
初始化模式串
:param pattern: 模式串
'''
self.pattern = pattern
self.plen = len(pattern)
def match(self, text):
'''
匹配接口
:param text: 主串
:return:
'''
print('模式串为：{}，等待匹配的字符串为{}'.format(self.pattern,text))
self.matched = False
self.rmatch(0, 0, text, len(text))
return self.matched
def rmatch(self, cur_text, cur_pattern, text, tlen):
'''
进行匹配
:param cur_text: 当前主串的下标
:param cur_pattern: 当前模式串的下标
:param text: 主串
:param tlen: 主串长度
:return:
'''
# print('匹配中，主串：{},模式串：{}'.format(text[cur_text],self.pattern[cur_pattern]))
# print(cur_text,cur_pattern,'-----',tlen,self.plen)
if self.matched == True:#匹配已经完成，跳出函数
return
if cur_pattern == self.plen:#模式串匹配结束，注意这段代码需要放在匹配行为之前，因为此时的 cur_pattern 已经溢出了字符串
if cur_text == tlen:#如果此时主串也匹配结束，匹配成功
self.matched = True
return
if self.pattern[cur_pattern] == '*':#匹配到 * ：把之后所有的主串位置都匹配一遍
for i in range(tlen - cur_text):
print(cur_text + i,cur_pattern + 1)
self.rmatch(cur_text + i, cur_pattern + 1, text, tlen)
elif self.pattern[cur_pattern] == '?':#匹配到 ？：主串移动 一步 或 零步
self.rmatch(cur_text + 1, cur_pattern+1, text, tlen)
self.rmatch(cur_text, cur_pattern+1, text, tlen)
elif self.pattern[cur_pattern] == text[cur_text] and cur_text < tlen:#匹配到非通配符：向后移动
self.rmatch(cur_text + 1, cur_pattern+1, text, tlen)
if __name__ == '__main__':
x = Pattern('???b?d')
r1 = x.match('aaabcd')
print(r1)
r2 = x.match('abcd')
print(r2)
走迷宫问题
下面有一段代码，是我在以前学习中使用栈完成的深度优先走迷宫，由于年代久远，我就不做解释，想要了解的朋友可以自行百度。
注意，这段代码没有使用递归，如果你不理解，直接跳过也无妨。
maze = [
[1,1,1,1,1,1,1,1,1,1],
[1,0,0,1,0,0,0,1,0,1],
[1,0,0,1,0,0,0,1,0,1],
[1,0,0,0,0,1,1,0,0,1],
[1,0,1,1,1,0,0,0,0,1],
[1,0,0,0,1,0,0,0,0,1],
[1,0,1,0,0,0,1,0,0,1],
[1,0,1,1,1,0,1,1,0,1],
[1,1,0,0,0,0,0,1,0,1],
[1,1,1,1,1,1,1,1,1,1]
]
dirs = [lambda x, y: (x + 1, y),
lambda x, y: (x - 1, y),
lambda x, y: (x, y - 1),
lambda x, y: (x, y + 1)]
def mpath(x1, y1, x2, y2):
stack = []
stack.append((x1, y1))
while len(stack) > 0:
curNode = stack[-1]
if curNode[0] == x2 and curNode[1] == y2:
#到达终点
for p in stack:
print(p)
return True
for dir in dirs:
nextNode = dir(curNode[0], curNode[1])
if maze[nextNode[0]][nextNode[1]] == 0:
#找到了下一个
stack.append(nextNode)
maze[nextNode[0]][nextNode[1]] = -1 # 标记为已经走过，防止死循环
break
else:#四个方向都没找到
maze[curNode[0]][curNode[1]] = -1 # 死路一条,下次别走了
stack.pop() #回溯
print("没有路")
return False
mpath(1,1,8,8)
总结
回溯算法的思想非常简单，在大部分情况下，可以用来解决广义的搜索问题。即从一组可能的解中，找到一个最免租要求的解。
回溯算法有一个 探索-碰壁-回溯 的过程，所以可以利用栈实现，但是最简版的方法还是使用递归。
在回溯过程中，对解空间进行剪枝操作是一个非常有趣的操作，它可以提高搜索效率。
我们在上面已经举了多个利用回溯完成的代码，你可以细细琢磨一下。
以上就是回溯算法的全部内容
注：本文章的主要内容来自我对极客时间app的《数据结构与算法之美》专栏的总结，我使用了大量的原文、代码和截图，如果想要了解具体内容，可以前往极客时间
