引言
简单介绍一些基本算法，包括：搜索、贪心、二分查找与三分查找、序列分治以及排序。
搜索
什么是搜索
搜索树
- 以起始状态为根，每个状态向其后继状态连有向边，可以得到一棵有根树
- 终止状态对应这棵树的叶子
- 搜索过程可以被抽象成遍历这棵搜索树的过程
- 如果需要遍历整棵搜索树，则复杂度至少正比于搜索树的结点数量
- 如果除叶结点外的结点都有至少两个叶结点，则可以用叶结点的数量估计有根树的大小
- 为什么?
- 如果除终止状态之外的状态都至少有两个后继状态，则可以用终止状态的数量估计搜索的复杂度
- 如果除终止状态之外的状态的后继状态数量是有下限的，则可以用层数估计终止状态的数量
搜索复杂度
深度优先与广度优先
深度优先搜索(Depth-First Search)优先遍历一个后继结点的子树内所有结点
- 先一条路走到黑，再返回上一个分岔点
广度优先搜索(Breadth-First Search)先遍历所有后继结点，再遍历后继结点的后继
- 在分岔点分身，最终每个终止结点都有一个分身
深度优先搜索 Depth-First Search
广度优先搜索 Breadth-First Search
搜索策略的选择
深度优先搜索 DFS
- 只需储存从初始状态到当前状态的一条路径
- 当递归层数较深时可能会爆栈
- 需要考虑回溯撤销的问题，细节可能比较麻烦
- 搜索层数不确定时可能会带来问题:无限拓展
- 移动棋子，绕了一大圈返回起点
- 子树中结点编号是连续的
广度优先搜索 BFS
- 需要储存所有尚待拓展的状态，空间开销大
- 可以动态使用堆内存
- 状态单向拓展，实现较为简单
- 可以知道从初始状态到每个状态的最少步数
- 适用于边权都为 1 的最短路
- 同一层的结点编号是连续的
扩展阅读:迭代加深搜索
搜索剪枝 Pruning
果树剪枝是为了让树长得更好看，结出的水果质量更高
搜索树也可以剪枝，让搜索效率更高;注意不要把最优解给剪枝掉了
可行性剪枝
- 如果当前状态已经不满足题目的要求，则不继续拓展
- 可以用于最优化问题，也可以用于统计解
最优性剪枝
- 只能用于最优化问题
- 如果从当前状态出发，可以得到的最优解一定不比已经得到的最优解优，则不继续拓展
此外还有其它剪枝思路，例如在双人游戏中有 Alpha-beta 剪枝等，在这里不详细展开
经典问题
八皇后
埃及分数
剪枝思路
- 放缩!
- 如果怎么救都救不回来，那就应该放弃
- 如果后续状态一定不合法，则不继续深入搜索
- 以最小化问题为例
- 为当前状态的所有后继估计解的下界，如果下界大于(或大等于，取决于具体题目)当前最小值则剪枝
- 扩展阅读:分支定界法求解
启发式搜索
贪心
贪心 Greedy Algorithm
贪心与动态规划的区别
找零钱问题
- 假设你有面值为 1 元，5 元，10 元，20 元，50 元和 100 元的纸币各若干张
- 用这些纸币表示出给定的正整数金额，使得用的纸币数量最少
- 贪心做法:每次选取不超过尚未被表示的金额的面值最大的纸币
- 127 → 100 + 20 + 5 + 1 + 1
- 正确性?
- 假设纸币的面值是 1 元，2 元，4 元，8 元，16 元，……，贪心做法还是正确的吗?
- 假设纸币的面值是 1 元，5 元，10 元，20 元和 25 元，贪心做法还是正确的吗?
- 反例:40 → 25 + 10 + 5，但是 20 + 20 更优
证明贪心正确性的常见思路
Huffman编码
二分与三分
二分查找 Binary Search
一个小故事
三分
递归与分治
递归
分治
排序
排序
冒泡排序
插入排序
选择排序
归并排序
快速排序