【python算法基础】回溯算法

意义

一种系统地搜索问题的解
回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。

与优化搜索区别

深度度优先搜索的能够在图结构里搜索到通往特定终点的一条或者多条特定路径。每条路深入到不能再深入，并且每条个点只访问一次;属于盲目搜索,最糟糕的情况算法时间复杂度为O(n!)。

可以浅显地认为回溯=深度优先+剪枝函数

深度优先搜索： 可以理解为暴力法遍历矩阵中所有字符串可能性。DFS 通过递归，先朝一个方向搜到底，再回溯至上个节点，沿另一个方向搜索，以此类推。
剪枝： 在搜索中，遇到 这条路不可能和目标字符串匹配成功 的情况（例如：此矩阵元素和目标字符不同、此元素已被访问），则应立即返回，称之为 可行性剪枝 。

但是两者却又存在不同，就是深度优先算法适用于所有的图但是回溯只适合于树结构

回溯法的核心为试探和复原。整个过程利用递归去执行，在递归函数执行前取修改尝试，满足条件后下沉到下一层，试探完成后将数值复原。在整个试探和复原的过程中找到最终需要的一个或所有解。

回溯函数的三个组成部分：
1.回溯出口：当找到了一个问题的解时，存储该解。
2.回溯主体：就是遍历当前的状态的所有子节点，并判断下一个状态是否是满足问题条件的，如果满足问题条件，那么进入下一个状态。
3.状态返回：如果当前状态不满足条件，那么返回到前一个状态。

python 模板：

def backtrack ( 参数 ):
    #回溯出口
    if ( 满足题意了 ):
        计数或进行其他操作
        return True   #有时可以省略
    
    #回溯主体
    for( 查找当前节点的周围的节点 )
        进行其他的操作;
        标记已经搜索过的节点
        backtrack( 下一次搜索的节点 )
    #状态返回
        取消标记;
    return False    #有时可以省略
1
2
3
4
5
6
7
8
9
10
11
12
13
14