pydata

Keep Looking, Don't Settle

深度搜索,回溯法和递归

通常如果需要列出所有的结果的时候,就需要使用回溯法(backtracking)。当然通过暴力解法(brute force)也是可以,但是暴力解法会浪费太多的时间和空间。两点区别

  1. 回溯法会回头,把路径pop出来,而暴力解法是走所有的解
  2. 回溯法会剪枝,比如通过某些if条件滑过某些路径,减少很多不必要走的路

识别回溯

判断回溯很简单,拿到一个问题,你感觉如果不穷举一下就没法知道答案,那就可以开始回溯了。 一般回溯的问题有三种:

  1. 有没有解:Find a path to success
  2. 求所有解:Find all paths to success 求所有解的个数 求所有解的具体信息
  3. 求最优解:Find the best path to success

backtracking代码模板

'''
backtracking使用dfs的模板,基本跟dfs的模板一模一样
'''
class Backtracking(object):

    def backtracking(self, input):

        self.res = []

        def dfs(input, temp, [index]):
            # 边界
            if 非法数据:
                return

            # 终止条件
            if len(input) == len(temp)
                self.res.append(temp[:])
                return

            # for循环
            for i range(len(input)):
                ##1. 修改path
                temp.append(input[i])
                ##2. backtracking
                dfs(input, temp, [index])
                ##3. 退回原来状态,恢复path
                temp.pop()
        # 执行
        dfs(input, [], 0)
        return self.res

深度搜索与回溯法的区别

简单一点可以认为 回溯法 = 深度搜索 + 剪枝。一般大家用深度搜索时,或多或少会剪枝,因此深度搜索与回溯法没有什么不同,可以在它们之间画上一个等号。简单的可以认为二者等价。

深度搜索一般用递归(recursion)来实现,这样比较简洁。

深度搜索能够在候选答案生成到一半时,就进行判断,抛弃不满足要求的答案,所以深度搜索比暴力搜索法要快。

深度搜索与递归的区别

深度搜索经常用递归(recursion)来实现,二者常常同时出现。深度搜索,是逻辑意义上的算法,递归,是一种物理意义上的实现,它和迭代(iteration)是对应的。深度搜索,可以用递归来实现,也可以用栈来实现;而递归,一般总是用来实现深度搜索。可以说,递归一定是深度搜索,深度搜索不一定用递归。