搜索与回溯算法

搜索与回溯算法是一种遍历算法。它区别与利用循环无脑的遍历。相比较利用for循环遍历，搜索与回溯算法是可以有目的筛选遍历（也就是说可以进行剪枝）。进行搜索遍历之后，可以恢复原来的遍历初始条件（也就是回溯）。

（1）搜索与回溯算法中的搜索

不同与循环进行全遍历搜索（这是一种全遍历方法。是将所有可能进行遍历），在搜索与回溯算法中使用搜索是按照一定的条件进行搜索遍历，当满足搜索条件之后进行递归操作。

（2）搜索与回溯算法中的回溯

当开始进行搜索，满足条件之后会进行下一轮的搜索，也就是递归操作。这时操作也就将初始化的条件破坏，因此搜索会改变初始的条件，这是就要回溯变回原来的初始条件。

（3）搜索与回溯算法的案例

搜索与回溯算法的迷宫问题，当从入口到达出口时，想要找到所有的路径。利用搜索与回溯的思想就可以解决。搜索与回溯思想的解决方式如下述：当从出发开始，出发点有多种路径选择，则选任意一条路径进行搜索，并且标记当前路径（表示此路径不能回头），若到达一个死角，则进行回溯将标记的路径取消（取消的意义在于不影响其他路径进行遍历搜索，此操作也就是回溯），若到达下一个路口则进行递归操作。

（4）搜索与回溯算法的模板

搜索与回溯算法一般是先判断是否结束当前路径，若满足则结束当前路径的搜索，若不满足则进入for循环，进入循环之后判断是否要进行递归操作。

#搜索回溯算法模板
    def (x :int):
        if 到达目的地:
            输出解
            return
        for i in range(方案数):
            if 方案可行:
                保存路径
                dfs(x+1)
                恢复保存前的状态

但是在具体问题中还需要具体的设计算法。

(5)搜索与回溯算法例题

1. 全排列问题：如一个集合{1，2，3}请输出他所有的全排列数组。
   这个问题可以套用模板进行解决！