【OI学习笔记】搜索剪枝

• 搜索算法的时间复杂度大多是指数级的，难以满足对程序运行时间的限制要求，为使降低时间复杂度，对深度优先搜索可以进行一种优化的基本方法——剪枝。

• 剪枝，就是减小搜索树的规模、尽早排除搜索树中一些不必要的分支的一种手段技巧。搜索的进程可以看做是从树根出发，遍历一颗倒置树（搜索树）的过程，所谓剪枝，就是通过某些判断，避免一些不必要的遍历过程，形象的说，就好像是减去搜索树中的某些枝条，也顾名思义叫做“剪枝”。

• 显而易见，应用剪枝优化的核心问题是设计剪枝判断方法，即确定哪些枝条舍弃哪些枝条保留，设计出好的剪枝判断方法，可以使得程序运行时间大大缩短，否则会适得其反。

• 剪枝的原则：正确、准确、高效

剪枝优化技巧

1. 优化搜索顺序
   在不同的搜索问题中，搜索树的各个层次、各个分支之间的顺序不是固定的，不同的搜索顺序会产生不同的搜索树形态，其规模大小也相差甚远。

2. 排除等效冗余
   在搜索过程中，若能判断从搜索树当前节点上沿某几条不同分支到达的子树是相同的，那么只需对其中一条分支执行搜索。

3. 可行性剪枝
   可行性剪枝也叫上下界剪枝，其是指在搜索过程中，及时对当前状态进行检查，若发现分支已无法到达递归边界，就执行回溯。这就好比我们在道路上行走时，远远看到前方是一条死胡同，就应该立即折返，重新选择道路，而不是走到头再折返。

4. 最优性剪枝
   在最优化问题的搜索过程中，若当前花费的代价已超过当前搜索到的最优解，那么无论采取多么优秀的策略到达递归边界，都不可能更新答案，此时可以停止对当前分支的搜索进行回溯。

5. 记忆化
   记忆化正如字面意思，记录每个状态的搜索结果，在重复遍历一个状态时直接检索并返回。这就好比我们对图进行深度优先遍历时，标记一个节点时是否已经被访问过，可以直接调用记录的数据，就可以节省再次重复计算的时间。