贪心算法 Greedy Algorithm
- 适用场景明确包含期望值和限制值
- 一组数据中定义了限制值和期望值,求满足限制值的情况下,令期望值最大
- 确定是否可以使用贪心算法
- 每次选择当前情况下,在对限制值同等贡献量的情况下,对期望值贡献最大
- 初步验证贪心算法求得的结果是否是最优
- 尝试举几个例子
- 不能使用贪心算法的问题的特征
- 前面的选择,会影响后面的选择,例如 地图的最短路径
贪心算法的常见示例
- 霍夫曼编码 Huffman Coding
- 给字符进行编码,字符出现的频率越高,则编码后的符号越短
- 任何字符的编码都不是另一个的前缀
- 解压缩时,尽可能长地读取二进制串
- 按照字符出现的频率,放入优先级队列中从小到大排列,若频率相同则按照出现次序排列
- 构建霍夫曼树
- 每次从队列中取出前两个元素(最小的两个元素),将它们的频率相加后,放入优先级队列中,仍旧保证优先级队列是有序的
- 根据霍夫曼树进行编码
- 给霍夫曼树中的所有左链接 0,右链接 1
- 从根结点开始,依次记录所有字母的编码
- 给字符进行编码,字符出现的频率越高,则编码后的符号越短
- Prim 最小生成树算法、Kruskal 最小生成树算法
- Dijkstra 单源最短路径算法
- 分糖果
- 每次从剩下的孩子中找到需求最小的孩子
- 从剩下的糖果中找到能满足他的最小的糖果
- 钱币找零
- 如果钱币的面额分布较为均匀,如 100、50、20,则可以使用贪心算法。每次找出最大面额的钱币支付
- 如果钱币的面额分布不均匀,如 100、99、1,则贪心算法不再适用,需要使用动态规划 6.区间覆盖
- n 个区间的最左端点为 lmin,最右端点为 rmax
- n 个区间按照起始端点从小到大排序
- 每次选择左端点和已经覆盖的区间不重合,右端点尽量小的
分治算法 Divide and Conquer
- 原问题可以分解成一系列的子问题,且原问题与分解成的小问题有相同的模式
- 原问题分解成的子问题可以独立求解,子问题之间没有相关性
- 具有分解终止条件,在问题足够小时,可以直接求解
- 可以将子问题合并成原问题,合并操作的复杂度不高
分治算法-递归操作
- 分解,将原问题分解成一系列子问题
- 解决,递归地求解各个子问题,若子问题足够小,则直接求解
- 合并,将子问题的结果合并成原问题
分治算法的常见示例
- 一组数据的有序对个数或者逆序对个数
- 将数组分成前后两段 A1、A2,则数组的逆序对个数等于 A1 的逆序对个数 K1 与 A2 的逆序对个数 K2、A1 A2 的逆序对个数 K3 之和,即 K1 + K2 + K3
- 借助归并排序,当 A1、A2 两个有序数组合并时,找出 A1 中比 A2 大的元素个数
- 最后将结果全部相加,得到总的逆序对个数
- 求平面内的最近点对
- 矩阵计算
回溯算法 Backtracking Algorithm
枚举搜索的思想,有规律地枚举所有可能的解
回溯算法的常见示例
- 八皇后
- 0 - 1 背包
- 正则表达式
- 图的着色
- 旅行商问题
- 数独
- 全排列
动态规划 Dynamic Programming
- 适用场景
- 用于求解最优问题,如最大值、最小值等
- 思路
- 把问题分解为多个阶段,每个阶段对应一个决策
- 记录每个阶段可达的状态集合(去掉重复的)
- 通过当前阶段的状态集合,来推导下一个阶段的状态集合,动态地向前推进
动态规划适用的问题
- 动态规划适合解决的问题的模型(一个模型),即多阶段决策最优解模型
- 解决问题的过程中,需要经历多个决策阶段
- 每个决策阶段都对应着一组状态
- 求解最优解时,可以经过某组决策序列来找到
- 三个特征
- 最优子结构
- 问题的最优解包含子问题的最优解,即可以通过子问题的最优解,推导出问题的最优解
- 后面阶段的状态可以通过前面阶段的状态推导出来
- 无后效性
- 推到后面阶段的状态时,只需要关心前面阶段的状态值,而不需要关心这个状态值是怎么得到的
- 某阶段的状态确定后,不受后面阶段的决策影响
- 重复子问题
- 不同的决策序列,到达某个相同的阶段时,可能会产生重复的状态
- 最优子结构
动态规划解决思路
- 状态转移表法
- 先建立一个状态表(一般都是二维的,如果问题的状态比较复杂的话,可能是多维)
- 状态表的每个状态包含三个变量,行、列、数组值
- 根据决策的过程,从前往后递推地填充状态表
- 状态转移方程法
- 递归 + 缓存、迭代递推
- 找到最优子结构
- 推导出状态转移方程
动态规划 和 回溯算法 的关系
- 根据回溯算法画出递归树
- 如果存在子问题,则可以考虑是否能用动态规划实现
- 如果不存在子问题,则回溯算法就是最优解
并行算法
并行处理的常见示例
- 并行排序
- 处理思想:先将数据进行分片,然后并行处理
- 并行执行归并排序,先随意地对数据分片,排序之后再合并
- 并行执行快速排序,先对数据按照大小划分区间,然后再排序,排完序后不需要合并
- 并行查找
- 使用散列表存储一定量的数据,当需要对散列表动态扩容时,会耗费很多不必要的内存
- 将数据随机分割成 k 份,每份中的数据只有原来的 1/k,针对这 k 个小数据集合分别构建散列表
- 当某个散列表的装载因子过大时,可以单独对这个小散列表进行扩容,这样不仅从内存的利用率或扩容的执行效率上,都比只使用一个大的散列表高效
- 并行匹配字符串
- 将一个大文本分割成 k 个小文本,并行地在这些小文本中查找关键词
- 在相邻的两个小文本中,将前一个小文本的结尾取 m 个字符,后一个小文本的开始取 m 个字符,在这个 2m 的字符串中再查找一遍需要匹配的字符串
- 并行搜索
- 并行化广度优先搜索算法
- 广度优先搜索是一种逐层搜索的搜索策略,可以基于当前结点,启动多个线程并行地搜索下一个层的顶点
- 使用两个队列 A、B,多个线程并行地处理队列 A 中的顶点,并将扩展得到的顶点存储在队列 B 中。队列 A 中的顶点都遍历过之后,队列 A 被清空。再遍历队列 B 中的顶点,将扩展得到的顶点存储在队列 A 中。A、B 循环使用。