剪枝算法(算法优化)

一：剪枝策略的寻找的方法

1）微观方法：从问题本身出发，发现剪枝条件

2）宏观方法：从整体出发，发现剪枝条件。

3）注意提高效率，这是关键，最重要的。

总之，剪枝策略，属于算法优化范畴；通常应用在DFS 和 BFS 搜索算法中；剪枝策略就是寻找过滤条件，提前减少不必要的搜索路径。

二：剪枝算法(算法优化)

1、简介

? 在搜索算法中优化中，剪枝，就是通过某种判断，避免一些不必要的遍历过程，形象的说，就是剪去了搜索树中的某些“枝条”，故称剪枝。应用剪枝优化的核心问题是设计剪枝判断方法，即确定哪些枝条应当舍弃，哪些枝条应当保留的方法。

2、剪枝优化三原则: 正确、准确、高效.原则

搜索算法,绝大部分需要用到剪枝.然而,不是所有的枝条都可以剪掉,这就需要通过设计出合理的判断方法,以决定某一分支的取舍. 在设计判断方法的时候,需要遵循一定的原则.

剪枝的原则

? 1） 正确性

? 正如上文所述,枝条不是爱剪就能剪的. 如果随便剪枝,把带有最优解的那一分支也剪掉了的话,剪枝也就失去了意义. 所以,剪枝的前提是一定要保证不丢失正确的结果.

? 2）准确性

? 在保证了正确性的基础上,我们应该根据具体问题具体分析,采用合适的判断手段,使不包含最优解的枝条尽可能多的被剪去,以达到程序“最优化”的目的. 可以说,剪枝的准确性,是衡量一个优化算法好坏的标准.

?3）高效性

设计优化程序的根本目的,是要减少搜索的次数,使程序运行的时间减少. 但为了使搜索次数尽可能的减少,我们又必须花工夫设计出一个准确性较高的优化算法,而当算法的准确性升高,其判断的次数必定增多,从而又导致耗时的增多,这便引出了矛盾. 因此,如何在优化与效率之间寻找一个平衡点,使得程序的时间复杂度尽可能降低,同样是非常重要的. 倘若一个剪枝的判断效果非常好,但是它却需要耗费大量的时间来判断、比较,结果整个程序运行起来也跟没有优化过的没什么区别,这样就太得不偿失了.

3、分类

剪枝算法按照其判断思路可大致分成两类:可行性剪枝及最优性剪枝.

3.1 可行性剪枝 —— 该方法判断继续搜索能否得出答案，如果不能直接回溯。

3.2 最优性剪枝

?最优性剪枝，又称为上下界剪枝，是一种重要的搜索剪枝策略。它记录当前得到的最优值，如果当前结点已经无法产生比当前最优解更优的解时，可以提前回溯。

三：示例分析

题目来源于poj 3900?The Robbery?(类似于背包问题，但是不能够用背包求解)

1 分析：W，C值很大，数组开不下（所以，不能用背包处理），但是发现N值很小，(1+15)*15/2=120，所以可以考虑dfs+剪枝。

首先利用贪心的思想我们对箱子进行排序，关键字为性价比（参考了poj里的discuss）。也就是单位重量的价值最高的排第一，搜索的时候枚举顺序注意一定要从满到空，这样才能最快的找到一个可行解然后利用它进行接下来的剪枝。

剪枝1. 之后所有的钻石价值+目前已经得到的价值<=ans 则剪枝。

剪枝2. 剩下的重量全部装目前最高性价比的钻石+目前已经得到的价值<=ans 则剪枝（非常重要的剪枝）。

2 程序代码