算法导论笔记

Algorithm
留言

算法导论记录：动态规划、贪心算法与图

一、动态规划

概念：动态规划（dynamic programming/DP）中的programming指的是一种表格法，并非编写计算机程序 动态规划应用于子问题重叠的情况，即不同的子问题有公共的子子问题

动态规划的设计：

  • 1.刻画最优解的结构特征
  • 2.递归地定义最优解的值
  • 3.计算最优解的值（通常采用自底向上的方法）
  • 4.利用计算出的信息构造一个最优解

朴素的递归算法由于反复求解相同的子问题而效率低下；动态规划对每个子问题只求解一次，，并将其保存下来，如果再次需要这个子问题的解，只需要查找保存的结果

动态规划两种等价的实现方法：

  • 1.带备忘的自顶向下法 仍然按自然递归的形式编写过程，但是过程会保存每个子问题的解，当需要某个子问题的解时，会先进行查找是否有这个解，否则会计算这个解，并保存
  • 2.自低向上法（按照逆拓扑排序，反序的拓扑排序）（自底向上表格法） 当求解某个子问题时，它所依赖的那些更小的子问题都已经求解完毕

动态规划的标识：

  • 1.最优子结构
  • 2.子问题重叠

剪切-粘贴：假定子问题的解不是其自身的最优解，那么我们可以剪切掉这些非最优解，将最优解粘贴进去，从而可以得到原问题的一个更优的解，这与原问题是最优解的假设是矛盾的

子问题无关：同一个原问题的一个子问题的解不影响另一个子问题的解

重叠子问题的性质：递归算法反复求解相同的子问题 如果每个子问题必须求解一次，自底向上动态规划算法会比自顶向下备忘算法快，因为自底向上算法没有递归调用的开销；如果子问题中的某些子问题不需要求解，自顶向下备忘算法就比较快

动态规划求解：找到状态转移方程和状态

二、贪心算法

概念：贪心算法每一步在当时看起来是最佳的选择，总是做出局部最优的选择 贪心算法并不保证得到最优解，但对于很多问题可以得到最优解 首先考虑用动态规划算法，然后证明一直做贪心的选择可以得到最优解，从而得到一个贪心算法

贪心算法步骤：

  • 确定问题的最优子结构
  • 将最优化问题转化为对其做出一次选择之后，只剩下一个子问题需要求解的形式
  • 证明做出贪心选择之后，原问题总是存在最优解，即贪心选择总是安全的

证明做出贪心选择之后，剩余的子问题满足性质：

  • 最优解和贪心选择组合即可得到原问题的最优解，这样就得到了最优子结构
  • 贪心算法进行选择时可能依赖之前做出的选择，但是不会依赖将来的选择或者是子问题的解

三、图

3.1 图的表示

  • 邻接链表：适用于稀疏图
  • 邻接矩阵：适用于稠密图

邻接链表无法迅速判断一条边是否是图中的一条边（邻接矩阵则可以，但是消耗了更多的内存空间），如果使用邻接链表来表示图，一种可能的方法是用额外的数组来表示节点属性

3.2 图的遍历

3.2.1 广度优先搜索：

广度优先搜索树中两个节点的简单路径就是这两个节点间的最短路径 用队列来实现广度优先搜索 广度优先搜索将每个节点涂上黑色/灰色/白色，遇到白色节点为发现，对于灰色节点，该节点周围肯能存在尚未发现的节点，对于黑色节点，该节点周围所有的节点都已经被发现 队列里面的距离差值最大为一 对图进行广度优先搜索的过程中将创建一棵广度优先搜索树

3.2.2 深度优先搜索：

深度优先搜索的前驱子图形成一个由多棵深度优先树构成的深度优先森林 若深度优先搜索中一个节点周围没有节点，则会回退到上一个节点，然后发现该节点周围的节点 发现时间和完成时间具有括号化结构（即嵌套）： 深度优先搜索在每个节点上面盖一个时间戳，一个是发现时间，第二个是搜索完成时间，对两个节点的时间戳，若重叠则必定是包含关系 边的分类： 树边/后向边/前向边/横向边 对无向图，从来不会出现前向边和横向边 拓扑排序： 拓扑排序是图中节点的一种线性排序，其次若图中有环路则无法排出一个线性次序 与深度优先搜索有关

强连通分量：

深度优先搜索的应用：将有向图分解为强连通分量 将图分解成强连通分量之后，这些算法将运行在每个连通分量上，然后根据连通分量之间的结构将各个结果组合起来，从而得到最终结果 强连通分量就是将环收缩，形成一个有向无环图 寻找强连通分量，图和改图的转置的强连通分量完全相同 分量图是一个有向无环图

单源最短路径

单源最短路径的子路径也是最短路径 单源最短路径包含着其它的最短路径（最优子结构） 求解最短路径的图中不能包含权值为负值的环路 事实上，最短路径也不能包含权重为正值的环路（无效环路），只要删去该环路，就可以得到一个更短的路径 松弛： 维持节点的最短路径估计属性 过程：首先测试是否可以对两个节点的最短路径进行改善，测试方法是：将一个节点到中间节点加上中间节点到另一个节点的值与当前值进行比较，如果更小则更新节点的该属性值 Dijkstra算法和用于有向无环图的最短路径算法对每条边仅仅松弛一次，Bellman——Ford算法对每条边松弛节点数减一次 Bellman——Ford算法： Bellman——Ford算法通过对边进行松弛操作，来渐进的降低从源节点到每个节点的最短路径的估计值， 先对图进行拓扑排序。。降低时间复杂度 Dijkstra算法：（贪心算法） Dijkstra算法要求所有的边的权重是非负 Dijkstra算法在运行过程中维持的关键信息是一组节点集合，从源节点到该集合中的每个节点之间的最短路径都已经找到，使用一个最小优先队列来保存节点集合

四、树

4.1 最小生成树

最小生成树问题： 对于带有权重的图，找到一个无环子集，既能够将所有的节点连接起来，又使其具有最小的权重 两种最小生成树算法：（贪心算法） kruskal算法 prim算法 kruskal算法： 集合a是一个森林，每次加入到集合a中的安全边永远是权重最小的连接两个不同分量的边 prim算法： 集合a是一棵树，每次加入a中的安全边是连接a与a之外的某个节点的边权重最小的 使用一个最小优先队列，算法结束时，最小优先队列为空

4.2二叉树

二叉搜索树上所花费的时间与这棵树的高度成正比 区分树的高度和深度 二叉搜索树： 左子树中的关键字的值小于根节点中关键字的值，右子树中关键字的值大于根节点中关键字的值 二叉搜索树的遍历： 先序遍历 中序遍历 后序遍历 其中序是指根节点的位置 二叉搜索树的查找 迭代比递归更加高效 比较关键字的值，大于向右，小于向左 插入和删除： 插入类似于查找，即查找到一个空的合适的位置，将该节点插入 删除则分为三种情况 将删除的节点没有孩子节点，直接删除 将删除的节点只有一个孩子节点，将这个孩子提升到将删除节点的位置，并修改将删除节点的父节点， 将删除的节点有两个孩子节点，查找将要删除节点的后继，并让该后继占据将要删除的节点的位置，让将删除节点的右子树部分成为那个后继的新的右子树，并且将删除节点的左子树成为那个后继的新的左子树 红黑树： 红黑树保证没有一条路径会比其它路径长出两倍，是近似平衡的，平衡二叉树是绝对平衡的 红黑树性质： 每个节点是红色的或者是黑色的 根节点是黑色的 每个叶节点是黑色的 如果一个节点是红色的，那么它的两个子节点是黑色的 对于每个节点，从该节点到其所有后代叶节点的简单路径上，均包含数目相同的黑色节点数，成为黑高 红黑树的旋转： 左旋和右旋 左旋是靠左边的节点下滑，夺取右子树的左子树作为自己的右子树，同时自己从新成为右子树的左子树 右旋是靠右边的节点下滑，夺取左子树的右子树作为自己的左子树，同事自己从新成为左子树的右子树 红黑树的插入： 红黑树的性质2或者4被破坏 插入的节点首先着色为红色 为保持红黑树的性质，调用辅助程序对红黑树的节点重新着色并进行旋转 红黑树的删除： 删除节点之后，调用辅助程序通过改变颜色和执行旋转来恢复红黑树性质 如果删除的节点是红色，则不需要对树进行恢复