返回

常见算法类型(九)基本算法思想

贪心算法 Greedy Algorithm

  1. 适用场景明确包含期望值和限制值
    • 一组数据中定义了限制值和期望值,求满足限制值的情况下,令期望值最大
  2. 确定是否可以使用贪心算法
    • 每次选择当前情况下,在对限制值同等贡献量的情况下,对期望值贡献最大
  3. 初步验证贪心算法求得的结果是否是最优
    • 尝试举几个例子
  4. 不能使用贪心算法的问题的特征
    • 前面的选择,会影响后面的选择,例如 地图的最短路径

贪心算法的常见示例

  1. 霍夫曼编码 Huffman Coding
    • 给字符进行编码,字符出现的频率越高,则编码后的符号越短
      • 任何字符的编码都不是另一个的前缀
      • 解压缩时,尽可能长地读取二进制串
    • 按照字符出现的频率,放入优先级队列中从小到大排列,若频率相同则按照出现次序排列
    • 构建霍夫曼树
      • 每次从队列中取出前两个元素(最小的两个元素),将它们的频率相加后,放入优先级队列中,仍旧保证优先级队列是有序的
    • 根据霍夫曼树进行编码
      • 给霍夫曼树中的所有左链接 0,右链接 1
      • 从根结点开始,依次记录所有字母的编码
  2. Prim 最小生成树算法、Kruskal 最小生成树算法
  3. Dijkstra 单源最短路径算法
  4. 分糖果
    • 每次从剩下的孩子中找到需求最小的孩子
    • 从剩下的糖果中找到能满足他的最小的糖果
  5. 钱币找零
    • 如果钱币的面额分布较为均匀,如 100、50、20,则可以使用贪心算法。每次找出最大面额的钱币支付
    • 如果钱币的面额分布不均匀,如 100、99、1,则贪心算法不再适用,需要使用动态规划 6.区间覆盖
    • n 个区间的最左端点为 lmin,最右端点为 rmax
    • n 个区间按照起始端点从小到大排序
    • 每次选择左端点和已经覆盖的区间不重合,右端点尽量小的

分治算法 Divide and Conquer

  1. 原问题可以分解成一系列的子问题,且原问题与分解成的小问题有相同的模式
  2. 原问题分解成的子问题可以独立求解,子问题之间没有相关性
  3. 具有分解终止条件,在问题足够小时,可以直接求解
  4. 可以将子问题合并成原问题,合并操作的复杂度不高

分治算法-递归操作

  1. 分解,将原问题分解成一系列子问题
  2. 解决,递归地求解各个子问题,若子问题足够小,则直接求解
  3. 合并,将子问题的结果合并成原问题

分治算法的常见示例

  1. 一组数据的有序对个数或者逆序对个数
    • 将数组分成前后两段 A1、A2,则数组的逆序对个数等于 A1 的逆序对个数 K1 与 A2 的逆序对个数 K2、A1 A2 的逆序对个数 K3 之和,即 K1 + K2 + K3
    • 借助归并排序,当 A1、A2 两个有序数组合并时,找出 A1 中比 A2 大的元素个数
    • 最后将结果全部相加,得到总的逆序对个数
  2. 求平面内的最近点对
  3. 矩阵计算

回溯算法 Backtracking Algorithm

枚举搜索的思想,有规律地枚举所有可能的解

回溯算法的常见示例

  1. 八皇后
  2. 0 - 1 背包
  3. 正则表达式
  4. 图的着色
  5. 旅行商问题
  6. 数独
  7. 全排列

动态规划 Dynamic Programming

  1. 适用场景
    • 用于求解最优问题,如最大值、最小值等
  2. 思路
    • 把问题分解为多个阶段,每个阶段对应一个决策
    • 记录每个阶段可达的状态集合(去掉重复的)
    • 通过当前阶段的状态集合,来推导下一个阶段的状态集合,动态地向前推进

动态规划适用的问题

  1. 动态规划适合解决的问题的模型(一个模型),即多阶段决策最优解模型
    1. 解决问题的过程中,需要经历多个决策阶段
    2. 每个决策阶段都对应着一组状态
    3. 求解最优解时,可以经过某组决策序列来找到
  2. 三个特征
    • 最优子结构
      • 问题的最优解包含子问题的最优解,即可以通过子问题的最优解,推导出问题的最优解
      • 后面阶段的状态可以通过前面阶段的状态推导出来
    • 无后效性
      • 推到后面阶段的状态时,只需要关心前面阶段的状态值,而不需要关心这个状态值是怎么得到的
      • 某阶段的状态确定后,不受后面阶段的决策影响
    • 重复子问题
      • 不同的决策序列,到达某个相同的阶段时,可能会产生重复的状态

动态规划解决思路

  1. 状态转移表法
    • 先建立一个状态表(一般都是二维的,如果问题的状态比较复杂的话,可能是多维)
    • 状态表的每个状态包含三个变量,行、列、数组值
    • 根据决策的过程,从前往后递推地填充状态表
  2. 状态转移方程法
    • 递归 + 缓存、迭代递推
    • 找到最优子结构
    • 推导出状态转移方程

动态规划 和 回溯算法 的关系

  1. 根据回溯算法画出递归树
  2. 如果存在子问题,则可以考虑是否能用动态规划实现
  3. 如果不存在子问题,则回溯算法就是最优解

并行算法

并行处理的常见示例

  1. 并行排序
    • 处理思想:先将数据进行分片,然后并行处理
    • 并行执行归并排序,先随意地对数据分片,排序之后再合并
    • 并行执行快速排序,先对数据按照大小划分区间,然后再排序,排完序后不需要合并
  2. 并行查找
    • 使用散列表存储一定量的数据,当需要对散列表动态扩容时,会耗费很多不必要的内存
    • 将数据随机分割成 k 份,每份中的数据只有原来的 1/k,针对这 k 个小数据集合分别构建散列表
    • 当某个散列表的装载因子过大时,可以单独对这个小散列表进行扩容,这样不仅从内存的利用率或扩容的执行效率上,都比只使用一个大的散列表高效
  3. 并行匹配字符串
    • 将一个大文本分割成 k 个小文本,并行地在这些小文本中查找关键词
    • 在相邻的两个小文本中,将前一个小文本的结尾取 m 个字符,后一个小文本的开始取 m 个字符,在这个 2m 的字符串中再查找一遍需要匹配的字符串
  4. 并行搜索
    • 并行化广度优先搜索算法
    • 广度优先搜索是一种逐层搜索的搜索策略,可以基于当前结点,启动多个线程并行地搜索下一个层的顶点
    • 使用两个队列 A、B,多个线程并行地处理队列 A 中的顶点,并将扩展得到的顶点存储在队列 B 中。队列 A 中的顶点都遍历过之后,队列 A 被清空。再遍历队列 B 中的顶点,将扩展得到的顶点存储在队列 A 中。A、B 循环使用。
© Licensed Under CC BY-NC-SA 4.0