学习一下剪枝。下面是个人笔记梳理和心得。
1. 概念
剪枝，在机器学习之中的定义是：通过解决决策树过拟合，为了降低模型复杂度的一种手段。在我们的算法学习过程之中，其意义也是相似的，即通过剪枝来删除掉某些不可能成立的情况，从而帮助我们减少时空复杂度。
剪枝的目的：
剪枝就是为了降低算法复杂度，也就是在搜索空间之中剪掉绝对不可能得到解的部分来减小搜索空间。
剪枝的三原则：
- 正确性：剪掉枝桠的前提是其不包括正确的解，不然咔嚓咔嚓全剪掉了图的是个啥呢？
- 准确性：在保证正确性的前提之下，尽量多的剪掉不包含搜寻解的枝叶，也就是剪就剪个干净，剪到最好。
- 高效性：这个就是去衡量某些剪枝算法的标准了，假设我们发现一种剪枝算法，可以将搜索的规模控制在很小的范围之内，但是我们在实施的时候却发现其耗费了大量的时间和空间，那么这种剪枝策略就是得不偿失的。
常用的剪枝策略
- 可行性剪枝：如果当前状态已经不合法了， 那么从这里往下的搜索空间都可以剪掉。也就是直接return
- 记忆化：在dp之中就用到了类似的思想，就是将某些可能会用到的已经计算的答案保存下来，下次遇到就可以直接使用，不需要重复计算
- 搜索顺序剪枝：在我们已经知道了某些有用的可能和顺序相关的前验情况下，定义我们的搜索顺序。比如有时候正序遍历数组会TLE，但是倒着遍历却可以。
- 最优性剪枝：也叫上下边界剪枝，常用在对抗类游戏之中。当算法评估某策略的后续走法比之前的还差，就会直接干掉这个分支的后续发展。
个人认为最常用的还是1和2.
