Java教程

【算法框架套路】回溯算法(暴力穷举的艺术)

本文主要是介绍【算法框架套路】回溯算法(暴力穷举的艺术),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

目录
  • 回溯算法介绍
  • 框架套路
  • 算法示例
    • 全组合
    • 全排列
    • 凑零钱
    • N皇后

回溯算法介绍

回溯算法可以搜索一个问题的所有解,本质是用递归代替N层for循环来“暴力穷举”

原理如下:

  1. 从根节点出发深度搜索解空间树
  2. 搜索到有解的分支时,继续向下搜索
  3. 搜索到无解的分支时,回退到上一步,顾名思义“回溯”

框架套路

talk is cheap,show you套路,框架如下

结果集=[]
function dfs(选择列表,已选择的数组)
    if 结束条件
        结果集追加
        return
    for 选择 in 选择列表
        做选择
        dfs(选择列表, 已选择数组) 进入下一次选择
        取消选择
dfs(选择列表,[])
return 结果集

重点:

  1. 选择列表。当前可以做出的选择
  2. 已选择路径。已经做出的选择
  3. 结束条件。无法再做出选择的条件

有了这框架,以后遇到需要穷举的算法,把3个重点想通,直接套用,童叟无欺~

算法示例

以下算法全用python实现,需要注意的是python的数组默认是传递引用,引入了copy包来复制数组

全组合

全组合是穷举的代表了吧,给定指定不重复的字符串,比如给定["a","b"],返回所有的组合结果应该是

aa
ab
ba
bb

我们来套用框架实现一下,代码如下

import copy

# 全组合
def combination(str_list):
    res = []

    max_len = len(str_list)

    def dfs(str_list, track_list):
        if len(track_list) == max_len:  # 满足条件,加入结果集
            res.append(track_list)
            return
        for c in str_list:
            track_list.append(c)  # 选择
            dfs(str_list, copy.copy(track_list))  # 进入下一次选择
            track_list.pop()  # 取消选择

    dfs(str_list, [])
    return res

三个重点:

  1. 选择列表。可以选择的字符串,比如['a','b','c'],对应变量str_list。
  2. 已选择路径。已经做出的选择,比如已经选择了['a'],对应变量track_list。
  3. 结束条件。无法再做出选择的条件,已选择的数组长度等于可选择长度,对应len(track_list) == max_len

我们来测试一下

for v in combination(['a', 'b']):
    print(v)

运行输出

全排列

全排列和全组合差不多,唯一的区别是已经选择过的字符串,不让选择了。
我们只需要在全组合代码的基础上加上限制即可,代码如下

import copy


# 全排列
def permute(str_list):
    res = []

    max_len = len(str_list)

    def dfs(str_list, track_list):

        if len(track_list) == max_len:  # 满足条件,加入结果集
            res.append(track_list)
            return
        for c in str_list:
            if c in track_list:  # 已经存在的不再添加
                continue
            track_list.append(c)  # 选择
            dfs(str_list, copy.copy(track_list))  # 进入下一次选择
            track_list.pop()  # 取消选择

    dfs(str_list, [])
    return res

我们只是改了一下这里

我们用chenqionghe的简称['c','q','h']来测试一下

for v in permute(['c', 'q', 'h']):
    print(v)

运行输出

凑零钱

给定数量N种面值的硬币, 再给定一个金额,返回硬币凑出这个金额的最少数量。
比如,给定硬币1, 2, 5,总额为10,最少需要2枚硬币5+5=10

代码实现如下

def coin_change(coins, amount):
    res_list = []

    def dfs(n, track_list):
        if n == 0:
            res_list.append(track_list)  # 满足条件
            return 0

        if n < 0:
            return -1

        for coin in coins:
            track_list.append(coin)  # 做选择
            dfs(n - coin, copy.copy(track_list))  # 选择一个硬币,目标金额就会减少,解变为1+sub_dp
            track_list.pop()  # 取消选择

    dfs(amount, [])
    return res_list

三个重点:

  1. 选择列表。可以选择的硬币,对应coins数组。
  2. 已选择路径。已经做出的选择,对应track_list数组。
  3. 结束条件。无法再做出选择的条件,金额为0和负的时候。

需要注意的是:df函数代表的是:目标金额是n,需要dfs[n]个硬币,比如给定金额10,这次选择了2,这次选择能达到的金额数量是1+dfs(10 - 2),也就是1+dfs(8)

我们来运行一下:

for v in coin_change([2, 3, 5], 10):
    print(v)

输出如下

给出了所有的方案,如果要最小的硬币只需要统计长度最小的即可。

N皇后

最典型的是八皇后:

在8×8格的国际象棋上摆放8个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。

以4皇后为例,给定数字4,应该给出两种方案如下

第一种方案
. Q . .
. . . Q
Q . . .
. . Q .
第二种方案
. . Q .
Q . . .
. . . Q
. Q . .

套用框架实现如下

# N皇后问题
def solve_n_queens(n):
    # 初始化二维数组
    res = []

    def dfs(board, row):
        if row == n:  # 到达最后一行,追加结果集
            res.append(board)
            return
        for col in range(n):
            # 排除不合法的选择
            if not is_valid(board, row, col, n):
                continue
            board[row][col] = 'Q'  # 选择第row行第col列放Q
            dfs(copy.deepcopy(board), row + 1)  # 进入下一行选择
            board[row][col] = '.'  # 撤销选择

    board = [['.'] * n for _ in range(n)]
    # 从第0行开始做选择
    dfs(board, 0)
    return res


# 判断是否能在board[row][col]放置Q
def is_valid(board, row, col, n):
    # 垂直方向是否有Q
    for v in range(row):
        if board[v][col] == 'Q':
            return False
    # 左上方是否有Q
    i, j = row - 1, col - 1
    while i >= 0 and j >= 0:
        if board[i][j] == 'Q':
            return False
        i = i - 1
        j = j - 1
    # 右上方是否有Q
    i, j = row - 1, col + 1
    while i >= 0 and j <= n - 1:
        if board[i][j] == 'Q':
            return False
        i = i - 1
        j = j + 1
    return True

N皇后的解法是,在每行做选择,选择为N列,做出选择后,进入下一行继续做选择
三个重点:

  1. 选择列表。可以选择的列,对应的是0-n的任意一列。
  2. 已选择路径。已经做出的选择,对应board二维数组。
  3. 结束条件。无法再做出选择的条件,也就是已经到达最后一行的时候。

注意:is_valid的函数,主要是判断检测当前位置是否能放“皇后”,也就是检查垂直、左上方向和右上方是不是都没有“皇后”

我们来测试一下

res = solve_n_queens(8)
for data in res:
    print('-' * 20)
    for v in data:
        print(" ".join(v))

运行输出如下

看到没有,这就是回溯暴力穷举的艺术,最简单的框架,解决最难的问题~

这篇关于【算法框架套路】回溯算法(暴力穷举的艺术)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!