本篇博客是《算法图解》读书笔记的第二篇。
这本书的前半部分，主要是对算法中的一些基础知识和思想的解读。进入后半部分，则开始相对深入的介绍了一些比较复杂问题的算法解决方案，例如图和树等。
对于我来说，这本书后半部分的阅读，主要是抱着拓展视野，知其大概的想法，真想解决什么问题，我估摸着得先去把那本《算法导论》啃两遍才行。因此，我并没有详细的研究算法如何具体实现，只要能简单的理解算法的思路和策略，我也就比较满意了。
第六章：广度优先搜索
图
图，由节点(node)和边(edge)组成。相邻的节点成为邻居。
如果边带有方向，即相邻节点关系为单向的，称为有向图。
如果边不带方向，即相邻节点关系为双向的，称为无向图。
有向图中，如果所有边的方向都是一致的，又称为树。
如果有向图中，没有相邻节点互相双重连接，也就是没有环形结构，又称为有向无环图。
数据结构之队列
队列，是一种先进先出(FIFO–first-in/first-out)的数据结构。类似栈的压入和弹出，队列支持两种操作，入队和出队。
广度优先搜索
广度优先搜索主要用于解决两类问题：
- 路径是否存在问题。即从一个节点到另一个节点，是否存在路径
- 路径最短问题。从一个节点到另一个节点，最短路径是哪条。
广度优先搜索的具体步骤如下：
- 将起始节点的所有相邻节点加入队列
- 取出队列中一个节点，检查是否为目标节点，如果是，目的达成。
- 如果不是，将此节点的所有邻居入队
- 重复步骤2
需要注意的是，在广度优先搜索中，需要记录检查过的节点，避免因为存在环形结构而导致无限循环。
从上面的步骤介绍中，我们知道我们需要遍历所有的边，从而将所有节点加入队列，同时遍历队列，找出目标节点。因此，广度优先搜索的时间复杂度为O(V+E)，其中V为顶点数(vertice)，E为边数。
第七章：狄克斯特拉算法
加权图
当图的边具有相应权重时，称为加权图。
对于加权图，要找出权重之和最低的路径，可以使用狄克斯特拉算法。
狄克斯特拉算法
狄克斯特拉算法适用于有向无环，且不存在负权边的图。
它通过不断找出到达每一节点层级的最短路径节点，从而找到到达目标节点的最短路径。步骤如下：
- 列出到达所有节点的开销权重表（若目前无法到达，可暂设为无穷大
- 找出目前能到达的节点中路径最短的节点，遍历其邻居，更新开销表
- 找出目前能到达的节点中路径第二短的节点，遍历其邻居，更新开销表
- 直到遍历完所有节点，开销表中到达目标节点的开销，即为最短路径的长短
狄克斯特拉算法，通过保证到达遍历节点过程中，每个节点的开销都为最小的，从而一步步找到最终所需的最短路径。也因为如此，狄克斯特拉算法只适用于无负权边的图，因为在存在负权边时，是无法根据已知开销，就确定到目前节点的路径为最短的。对于负权边的情况，可以使用贝尔曼-福德算法。（书中也只是提了个名字，我也不知道是个啥。
同时需要注意，每一步更新节点开销时，都要记录更新开销时的父节点，从而在最终根据父节点回朔得到具体的最短路径。
第八章：贪婪算法
贪婪算法，是指每一步都采取局部最优解的算法。
贪婪算法在某些情况下，获得的结果与全局最优解完全一致。但在某些情况下，并不是全局最优解，但也非常接近。
NP完全问题
NP完全问题，是指形如你需要列出所有的解，并从中选出最大或最小的那个这类问题。前文提过的旅行最短路径问题，就是NP完全问题。
集合覆盖问题，即存在若干个元素和若干个集合，每个集合中都包含有数个元素，选出最少的集合数，能够包含所有元素，也是一个NP完全问题。
在大部分情况下，NP完全问题是无法得出最优解的，只能求出与最优解近似的近似解。
不存在比较好的方法来确定一个问题是不是NP完全问题，但可以通过以下几个特征来进行一些辅助推断：
- 随着元素的增加，时间复杂度近乎阶乘阶。
- 涉及 元素的所有组合类的问题
- 无法分解降低问题规模
- 涉及所有可能顺序的问题。
- 可以转化为旅行商和集合覆盖问题的问题，可以确定是NP完全问题。
第九章：动态规划
动态规划，是指将一个问题分解为多个子问题问题，求出每个子问题的局部最优解，最终得到全局最优解。
动态规划在局部最优解也是全局最优解，且局部最优解的决策在后续决策中会不断被用到的情况下非常有效。
书中举例是有一个小偷，去商场偷东西，有各种商品，价格不同，体积也不同，有一磅，二磅，三磅等等。小偷的背包体积确定为4磅，现在需要确定小偷偷哪些商品，才能在本次偷窃中赚的最多。
这是一个十分适合使用动态规划解决的问题，首先计算，当背包为一磅时，偷哪些商品价值最高，再计算背包为两磅时，偷哪些商品，最终，我们就可以确定，背包为4磅时，偷哪些商品可以获得最多的价值。
动态规划将一个多阶段决策分解为多个局部的小决策，这就必须保证问题的粒度是可分的。如果上面的可偷商品可以只偷一部分的话，例如大米有三磅，但可以只拿一磅，这种时候动态规划就无能为力了。可以考虑使用贪婪算法。
对于动态规划来说，必须保证更细粒度的子问题是离散的，也就是某个局部最优解确定后，后续的决策不会影响到这个最优解。
动态规划问题，常见于求最长公共子序列问题。
费曼算法
费曼算法是计算机领域的一个著名算法，它的步骤如下：
- 把问题写到纸上
- 思考
- 将答案写到纸上
第十章： K最近邻算法（k-nearest-neighbours-KNN）
K最近邻算法，通常用于进行分类和回归。
它将具体对象的一些特征值提取为一个N维数组，通过计算相互对象的特征值在N维坐标系中的距离，来确定对象之间的相似度，从而将相似度较高的对象以邻居归类。
书中举例一个电影推荐系统，每个用户都为很多电影打分，将用户对特定电影的打分值作为特征值，得出一个特征值数组，通过计算两组特征值的距离远近，来确定两个用户的相似度，从而将一个用户比较喜欢的电影推荐给另一个与他品味相似的用户，或者根据近邻用户为某部电影的打分，来预测当前用户的打分大概会是多少，也就是上面所说的回归。
当然，判断两个对象是否是邻居要根据特征值的选取和具体问题确定，不一定是坐标系中的距离，也可能是余弦相似度等。
KNN算法，是机器学习中的一个重要算法。
通过对大量相关对象提取特征值，也就是机器学习中的训练，来组成一个特征值库，通过KNN算法配合特征库，使机器具有识别和预测的能力，也就是我们常说的人工智能。当然，这里只是对人工智能粗浅的一个认识，真正的人工智能领域，是相当复杂和多变的。
KNN算法，比较常见的应用就是图像识别，人脸识别，语音识别，推荐系统等等。
另外，各论坛常见的关键字过滤系统，其中也有KNN算法的功劳。
第十一章：其他常见算法
二叉查找树
在前面的二分法介绍中，我们提到了二分法查找有序数组时效率很高。但是数组的插入和删除效率十分低，因此不适合存储用来查找的数据。
这时就需要二叉查找树来发挥作用了。
二叉查找树是一种左边的子节点始终小于父节点，右边的子节点始终大于父节点的数据结构。
当查找某个节点时，就沿着树形结构一路比较下去，直到找到目标节点。
处于平衡状态时，二叉查找树的查找时间复杂度为O(logn)，但不平衡时，查找的时间复杂度可能达到O(n)，是弱于二分查找的。
但二叉树相比数组的二分查找的优点在于，它的插入和删除的时间复杂度也平均为O(logn)，是优于数组的。但相比数组，它又有不能随机访问的缺点。
傅里叶变换
傅里叶变换，用于分离信号。例如常见的音频信号，傅里叶变换能将其中的各个频率音符分离出来。
它常用于压缩音频文件，进行信号处理等。
并行算法
并行算法用于处理海量数据，通过多核处理器，来对问题进行同时的多重计算。
并行算法对问题解决的速度提升并不是线性的，主要是因为下面两个原因：
- 并行管理开销 例如两个内核的任务分配和结构处理等。
- 负载均衡 平衡各内核间的工作量，从而达到均匀的负载。
分布式算法
分布式算法是一种特殊的并行算法，它并不是在多核上运行，而是在多台计算机上运行。
SHA算法
SHA算法，是一个散列函数，可以根据一个字符串生成另一串唯一的字符串。但你并不能根据这一个唯一的字符串得到它的原始字符串。
它通常用于文件比较，存储密码等。
SHA算法包括SHA-0，SHA-1，SHA-2，SHA-3。SHA-0和 SHA-1 已经被确定为不安全的了。
SHA算法是局部不敏感的，也就是说，原始字符串的一个小小改动，就会导致SHA算法生成的唯一字符串完全不同。
SimHash
SimHash 与 SHA算法类似，不同之处在于，SimHash 算法是局部敏感的，因此常用于比较两个文件的相似程度，判断文件是否存在等。
Diff-Hellman密匙交换
Diff-Hellman是一种加密方式。它提供一个公开的公钥，所有人都可以用此公钥来对数据进行加密，但只有私钥可以对这些加密的数据解密。你可以将公钥发放给需要进行信息传递的一方，从而达到与对方加密通信的效果。