欢迎访问我的博客：http://wangnan.tech
第七章 狄克斯特拉算法
前一章使用了广度优先搜索，它找出的是段数最少的路径（如第一个图所示）。如果你
要找出最快的路径（如第二个图所示），该如何办呢？为此，可使用另一种算法——狄克斯特拉
算法（Dijkstra’s algorithm）。狄克斯特拉算法包含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）函数。
