算法笔记-贪婪技术

Posted by MaggicQ on February 8, 2017

贪婪技术

贪婪法通过一系列的步骤来构造问题的解,每一步对目前构造的部分解一个拓展,直到获得问题的完整解为止,这个技术的核心是,所做的每一步选择都必须满足以下条件:

  • 可行的(feasible),即它必须满足问题的约束。
  • 局部最优(locally optimal):它是当前步骤中所有可选选择中的最佳局部选择
  • 不可取消(irrevocable):即选择一旦做出,在算法的后面步骤中就无法改变了

贪婪算法既直观又简单。通常最困难的是如何证明某一个贪婪算法能获得最优解。

有以下几种证明方法:

  • 使用数学归纳法,证明贪婪算法在每一步获得的部分解能够拓展到全局最优解。
  • 证明在接近问题的目标过程中,贪婪算法每一步的选择至少不比任何其他算法差。
  • 基于算法的输出来证明贪婪算法获得的最终解的最优性。

Prim算法

最小生成树问题:连通图的一棵生成树(spanning tree)是包含图的所有顶点的连通无环子图。

加权连通图的一颗最小生成树是图的一棵权重最小的生成树,其中,树的权重定义为所有边的权重之和。

Prim算法通过一系列不断扩张的子树来构造一棵最小生成树。首先选择任意一个单顶点作为初始子树,每次迭代

的时候,把不再树中的最近顶点添加到树中。

Prim算法

效率跟图的数据结构有关,

如果图是由权重矩阵实现的,优先队列是无序数组实现的,该算法的效率为$\Theta( V ^2)$

如果优先队列是由最小堆实现的,最小堆是一个完全二叉树,其中每个元素都小于等于它的子女,

这是效率为$O( E log V )$

Kruskal算法

最小生成树的另外一个贪婪解法

该算法先按照权重的非递减顺序对图中的边进行排序,然后从一个空子图开始,扫描这个有序列表,

并试图把列表中的下一条边加到当前子图。(如果这个添加产生了回路,那么跳过这条边)

Kruskal算法

Dijkstra算法

单起点最短路径问题(single-source shortest-paths problem):对于加权连通图的一个称为起点的

给定顶点,求出它到所有其他顶点之间的一系列最短路径。

Dijkstra算法按照从给定起点到图中顶点的距离,顺序求出最短的路径,首先求出从起点到最接近起点的顶点之间的最短路径,然后求出第二近的,以此类推。

为了使算法的操作更加容易,给每一个顶点附加两个标记:

  • 数字标记$d$指出到目前为止该算法求出的从起点到该顶点之间最短路径的长度
  • $p$指出这条路径上倒数第二个顶点的名字

Dijkstra

时间效率取决于实现优先队列的数据结构以及用来表示输入图本身的数据结构。

如果图用权重矩阵表示,优先队列用无序数据来表示,则效率为$\Theta( V ^2)$
如果图用邻接链表表示,优先队列用最小堆来实现,效率为$O(Elog V )$

哈夫曼树及编码

变长编码(variable-length encoding):与定长编码相对,把较短的代码字分配给更常用的字符,把较长的代码字分配给比较不常用的字符。

但是这样有一个问题,就是不知道文本中用了多少位来代表第一个字符。

一个解决方案是:自由前缀码,在前缀码中,所有的代码字都不是另一个字符代码字的前缀。

一个为字母表创建一套二进制前缀码的方式是,把这些字符跟二叉树的叶子联系起来。

左向边全都标记为0,右向边全都标记为1,这样可以通过记录从根到字符叶子的简单路径上

的标记来获得一个字符的代码字。

哈弗曼算法:已知字符的出现概率,构造一棵将较短位串分配给高频字符,将较长位串分配给低频字符的树。

哈弗曼算法