众所周知，搜索的时间复杂度大多是指数级的，简单的不加优化的搜索，时间效率低，难以应付信息学竞赛严格的运行时间限制。本章主要讨论在建立搜索的结构之后，对程序进行优化的一种基本方法–剪枝。
搜索的进程可以看作是从树根出发，遍历一棵倒置的树–搜索树的过程。所谓剪枝，就是通过某种判断，避免不必要的遍历过程，形象的说，就是剪去搜索树中的某些“枝条”，故称剪枝。
在编写程序时，一般都要考虑到剪枝。应用剪枝优化的核心是设计剪枝判断方法，即确定哪些枝条应当舍弃，哪些枝条应当保留。好的剪枝判断方法，能使程序的运行时间大大缩短；否则，也可能适得其反。首先分析一下设计剪枝判断方法的时候，需要遵循的一些原则。
剪枝的原则
❶、正确性 剪枝能优化程序的执行效率，是因为它“剪去”搜索树中的一些“枝条”。但如果在剪枝时，将“长有”所需要的解的枝条剪掉，一切优化也就没有意义。所以，剪枝的第一个原则是正确性，即必须保证不丢失正确的结果，这是剪枝优化的前提。
❷、准确性 在保证了正确性的基础上，对剪枝判断的第二个要求就是准确性，即能够尽可能多的剪去不能通向正解的枝条。剪枝方法只有在具有了较高的准确性的时候，才能真正收到优化的效果。
❸、高效性 利用出解的“必要条件”进行判断，会有不含正解的枝条没被剪枝。这些情况下的剪枝判断操作，对程序的效率的提高有副作用。为了减少剪枝判断的副作用，除了要改善判断的准确性外，还需要提高判断操作本身的时间效率。
但这带来了一个矛盾：为了加强优化的效果，必须提高剪枝判断的准确性，因此，不得不提高判断操作的复杂度，也就同时降低了剪枝判断的时间效率；但如果剪枝判断的时间消耗过多，就有可能减小、甚至完全抵消提高判断准确性所能带来的优化效果。能否较好的解决这个矛盾，往往成为搜索算法优化的关键。
综上所述，可以把剪枝优化的主要原则归结为六个字：正确、准确、高效。在应用剪枝优化的时候，仅有上述的原则是不够的，还需要具体研究一些设计剪枝判断方法的思路。
剪枝的优化技巧
◆ 优化搜索顺序 一些搜索问题的搜索树的各个层次、各个分支之间的顺序不固定。不同的搜索顺序产生不同的搜索树形态，规模大小也不同。
◆ 排除等效冗余 在搜索过程中，如果我们能够判定从搜索树的当前节点上沿着某几条不同分支到达的子树是等效的，那么只需要对其中的一条分支执行搜索。
◆ 可行性剪枝 在搜索过程中，及时对当前状态进行检查，如果发现分支已经无法到达递归边界，就执行回溯。这就好比在道路上行走时，远远看到前方是一个死胡同，就应该立即折返绕路，而不是走到路的尽头再返回。某些题目条件的范围限制是一个区间，此时可行性剪枝也被称为“上下界剪枝”。
◆ 最优性剪枝 在最优化问题的搜索过程中，如果当前花费的代价己经超过了当前搜到的最优解，那么无论采取多么优秀的策略到达递归边界，都不可能更新答案。此时可以停止对当前分支的搜索，执行回溯。
◆ 记忆化 可以记录每个状态的搜索结果，在重复遍历一个状态时直接检索并返回。这就好比我们对图进行深度优先遍历时，标记一个节点是否己经被访问过。