搜索算法中常见的几种剪枝操作
2022-03-02 本文已影响0人
fatshi
可行性剪枝
所谓可行性剪枝,顾名思义,就是当当前状态和题意不符,并且由于题目可以推出,往后的所有情况和题意都不符,那么就可以进行剪枝,直接把这种情况及后续的所有情况判负,直接返回。
即:不可行,就返回。
排除等效冗余
所谓排除等效冗余,就是当几个枝桠具有完全相同的效果的时候,只选择其中一个走就可以了。
即:都可以,选一个。
最优性剪枝
所谓最优性剪枝,是在我们用搜索方法解决最优化问题的时候的一种常用剪枝。就是当你搜到一半的时候,已经比已经搜到的最优解要不优了,那么这个方案肯定是不行的,即刻停止搜索,进行回溯。
即:有比较,选最优。
顺序剪枝
普遍来讲,搜索的顺序是不固定的,对一个问题来讲,算法可以进入搜索树的任意的一个子节点。但假如我们要搜索一个最小值,而非要从最大值存在的那个节点开搜,就可能存在搜索到最后才出解。而我们从最小的节点开搜很可能马上就出解。这就是顺序剪枝的一个应用。一般来讲,有单调性存在的搜索问题可以和贪心思想结合,进行顺序剪枝。
即:有顺序,按题意。
记忆化
记忆化搜索其实是搜索的另外一个分支。在这里简单介绍一下记忆化的原理:
就是记录搜索的每一个状态,当重复搜索到相同的状态的时候直接返回。
即:搜重了,直接跳。