Table of Contents

  1. 第七章 狄克斯特拉算法
    1. 小结
  2. 贪婪算法/动态规划/k最近邻算法
  3. 其他一些算法
    1. 反向索引
    2. 傅里叶变换
    3. 并行算法
    4. MapReduce
    5. 布隆过滤器和HyperLogLog
    6. SHA算法
    7. Diffie-Hellman 密钥交换
    8. 线性规划

第七章 狄克斯特拉算法

  • 前一章使用了广度优先搜索,它找出的是段数最少的路径(如第一个图所示)。如果你
    要找出最快的路径(如第二个图所示),该如何办呢?为此,可使用另一种算法——狄克斯特拉
    算法(Dijkstra’s algorithm)。

  • 狄克斯特拉算法包含4个步骤。

  1. 找出最便宜的节点,即可在最短时间内前往的节点。
  2. 对于该节点的邻居,检查是否有前往它们的更短路径,如果有,就更新其开销。
  3. 重复这个过程,直到对图中的每个节点都这样做了。
  4. 计算最终路径。(下一节再介绍!)

小结

  • 广度优先搜索用于在非加权图中查找最短路径。
  • 狄克斯特拉算法用于在加权图中查找最短路径。
  • 仅当权重为正时狄克斯特拉算法才管用。
  • 如果图中包含负权边,请使用贝尔曼福德算法。

贪婪算法/动态规划/k最近邻算法

  • 就是你每步都选择局部最优解,最终得到的就是全局最优解
  • 有时候,你只需找到一个能够大致解决问题的算法,此时贪婪算法正好可派上用场,因为它们实现起来很容易,得到的结果又与正确结果相当接近。
  • 贪婪算法寻找局部最优解,企图以这种方式获得全局最优解。
  • 对于NP完全问题,还没有找到快速解决方案。
  • 面临NP完全问题时,最佳的做法是使用近似算法。
  • 贪婪算法易于实现、运行速度快,是不错的近似算法。
  • 需要在给定约束条件下优化某种指标时,动态规划很有用。
  • 问题可分解为离散子问题时,可使用动态规划来解决。
  • 每种动态规划解决方案都涉及网格。
  • 单元格中的值通常就是你要优化的值。
  • 每个单元格都是一个子问题,因此你需要考虑如何将问题分解为子问题。
  • 没有放之四海皆准的计算动态规划解决方案的公式。
  • KNN用于分类和回归,需要考虑最近的邻居。
  • 分类就是编组。
  • 回归就是预测结果(如数字)。
  • 特征抽取意味着将物品(如水果或用户)转换为一系列可比较的数字。
  • 能否挑选合适的特征事关KNN算法的成败。

其他一些算法

反向索引

傅里叶变换

  • Better Explained是一个杰出
    的网站,致力于以通俗易懂的语言阐释数学,它就傅里叶变换做了一个绝佳的比喻:给它一杯冰沙,它能告诉你其中包含哪些成分。换言之,给定一首歌曲,傅里叶变换能够将其中的各种频率分离出来。
    -JPG也是一种压缩格式,也采用了刚才说的工作原理。傅里叶变换还被用来地震预测和DNA分析。

并行算法

MapReduce

  • MapReduce是一种流行的分布式算法,你可通过流行的开源工具Apache Hadoop来
    使用它。
  • 分布式算法非常适合用于在短时间内完成海量工作,其中的MapReduce基于两个简单的理
    念:映射(map)函数和归并(reduce)函数。
  • MapReduce使用这两个简单概念在多台计算机上执行数据查询。数据集很大,包含数十亿行
    时,使用MapReduce只需几分钟就可获得查询结果,而传统数据库可能要耗费数小时。

布隆过滤器和HyperLogLog

SHA算法

-安全散列算法(secure hash algorithm,SHA)函数。

Diffie-Hellman 密钥交换

线性规划