【概述】

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

搜索的进程可以看做是从树根出发，遍历一颗倒置树（搜索树）的过程，所谓剪枝，就是通过某些判断，避免一些不必要的遍历过程，形象的说，就是减去搜索树中的某些枝条。

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

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

【优化技巧】

1.优化搜索顺序

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

2.排除等效冗余

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

3.可行性剪枝

在搜索过程中，及时对当前状态进行检查，若发现分支已无法到达递归边界，就执行回溯。

4.最优性剪枝

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

5.记忆化搜索

搜索的低效无法很好的处理重叠子问题，动态规划虽然较好的处理了重叠子问题但再一些具拓扑关系的题前较无奈，因此可采用记忆化搜索的方法，通过记忆化记录每个状态的搜索结果，在重复遍历一个状态时直接检索并返回。

简单地说就是：记忆化搜索=搜索的形式+动态规划的思想

【经典剪枝技巧——奇偶剪枝】

1.内容

假设起点为（sx,sy），终点为（ex,ey），给定 t 步恰好走到终点，如图所示（“|”竖走，“—”横走，“+”转弯），易证abs(ex-sx)+abs(ey-sy)为此问题类中任意情况下，起点到终点的最短步数，记做step，此处step1=8；

如图，为一般情况下非最短路径的任意走法举例，step2=14；step2-step1=6，偏移路径为6

推广：若 t-[abs(ex-sx)+abs(ey-sy)] 结果为奇数，则无法在t步恰好到达，返回 false；反之，若结果为偶数，则可以在 t 步恰好到达，返回 true。

2.应用

如图，没障碍物#时，S到E的最短路长为6，但是当有障碍物时，就要绕行了。

如图，黑色为最短路径，当他绕行（红色加蓝色部分）时，其中蓝色部分其实还是最短路径部分平移来的，所以多走的步数也就是红色部分。对于红色部分我们可以分为两部分，一部分是远离最短路径的步数，另一部分是回到最短路径的部分，他们一定是对称的，所以多走的步数一定是偶数。

所以，当问走 x 步能否到达 e，就算出最短路径长 y，如果 x-y 是偶数就能到达，否则不能到达。