【核心算法5】回溯算法

ustbfym 2020-06-17

回溯算法可以看成走迷宫,不知道出口在哪,所以只能不断深入,尝试不同的路线。但一旦找到出口便可以回溯到起点,辩清路线。

  • 回溯算法
  • 遍历所有排序方式
  • 经典问题的组合
  • 查找单词问题
  • 八皇后问题
  • 解数独

回溯算法

简单来说,回溯采用试错的方法解决问题。一旦发现当前步骤失败,回溯方法就返回一个步骤,选择另一种方案继续试错。当没有尝试所有路线时,就找到正确路线,可见回溯算法是一个优点是搜索速度快。当然,如果恰好在最后一个分支的低端,那么该方案就没有特别的优势了。

回溯算法又称为试探法,其特点:

  • 问题的答案有多个元素
  • 答案需要满足的约束条件
  • 寻找答案的方式在每一步骤相同
  • 逐步构建答案

遍历所有排序方式

现有要读的4本书,《Gevent指南》,《PythonCookBook》,《高性能MySql》,《编程珠玑》,每次只能从图书馆借一本,一共有多少中借书的顺序呢,若学过统计学,会有 4!= 24 种不同的排序方式。但,要的到的不只是总数,还想一一输出所有的排序方式

问题求解

  1. 首先,有四个空位,第一个空位有4中选择,假设第一个位置为《编程珠玑》,那么第二个空位就有3个选择,假设第二个位置为《PythonCookBook》,那么第三个空位就有2个选择,假设第三个位置为《Gevent指南》,最后第四个空位就只能是《高性能Mysql》

    def solve_permutataion_bad_way(array):
        solution = []
        for i in range(len(array)):
            ...
            for j in range(len(array1)):
                ...
                for x in range(len(array2)):
                    ...
                    for y in range(len(array3)):
                        ...
  2. 若这个构思,要提前知道数组的长度,代码十分累赘。如果,在排第一本书到 时候,有4种选择,答案集合就在这4中选择在各结尾增加剩下的三本书的排序集合,那么,只需要得出剩余的三本书的排序集合就可以了。

  3. 同样,排着三本书时第一本数有三种选择,所以只需要得出剩余的两本书的排序集合就可以了,那么,推到最后,排两本书时,只需要知道最后一本是什么就可以了。

  4. 定义一个方法来帮助概括重复代码

代码实现

class Solution(object):
    
    def helper(self, array, solution):
        # 如果没有剩余书籍
        if len(array) == 0:
            # 输出结果
            print(solution)
            # 返回上一级
            return
        # 遍历书籍
        for i in range(len(array)):
            # 新建排序列表
            solution_new = solution + [array[i]]
            # 新建书籍列表
            array_new = array[:i] + array[i+1: ]
            # 回溯
            self.helper(array_new, solution_new)
    
    def solve_permutation(self, array):
        self.helper(array, [])

book_li = [
    ‘《Gevent指南》‘,
    ‘《PythonCookBook》‘,
    ‘《高性能MySql》‘,
    ‘《编程珠玑》‘,
]

print(type(book_li))
so = Solution()
so.solve_permutation(book_li)

# >>>

经典问题的组合

现要选择两种水果,有四种选择:A.香蕉,B.橙子, C.葡萄,D.荔枝。一共有多少种选择呢?用数学的方法容易得出C4^2 = 6种不同的选课组合,不过,现在要将这些组合一一输出。

问题求解

  1. 首先有两个空位,第一次选择时有4中选择,A,B,C,D。
  2. 假设选择A,那么第二次选择就有3种选择。
  3. 假设选择B,得出的是AB这个组合

代码实现

class Solution(object):

    def helper(self, array, n, solution):
        # 如果 solution中有n门课程
        if len(solution) == n:
            # 输出结果
            print(solution)
            # 返回被调用的地方
            return

        # 遍历每一种水果
        for i in range(len(array)):
            # 把水果加入新的组合列表
            solution_new = solution + [array[i]]
            # 创建新水果列表,更新列表
            array_new = array[i+1: ]
            # 调用重复方法选择剩余课程
            self.helper(array_new, n, solution_new)

    def solve_combination(self, array, n):
        self.helper(array, n, [])


fruits = [‘A.香蕉‘, ‘B.橙子,‘, ‘C.葡萄‘, ‘D.荔枝‘]

so = Solution()
so.solve_combination(fruits, 2)
### >>>
‘‘‘
[‘A.香蕉‘, ‘B.橙子,‘]
[‘A.香蕉‘, ‘C.葡萄‘]
[‘A.香蕉‘, ‘D.荔枝‘]
[‘B.橙子,‘, ‘C.葡萄‘]
[‘B.橙子,‘, ‘D.荔枝‘]
[‘C.葡萄‘, ‘D.荔枝‘]
‘‘‘

相关推荐