算法学习之贪婪技术（贪心算法）

贪婪技术（贪心算法）

定义

贪婪法建议通过一系列步骤来构造问题的解，每一步对目前构造的部分解做一个扩展，直到获得问题的完整解为止。这个技术的核心是，所做的每一步选择都必须满足：

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

理解

这种方法模式一般将求解过程分成若干个步骤，在每个步骤都应用贪心原则，选取当前状态下最好的或最优的选择(局部最有利的选择)，并以此希望最后对跌出的结果也是最好的或最优的解。

贪心算法。动态规划法、分治法都是对问题进行分解，定义最优解的子结构.
贪心算法与其他方法最大的不同在于，贪心算法每一步做完之后，局部最优解就确定了，不再进行回溯处理，也就是说，每个步骤的局部最优解确定以后，就不再修改，直到算法结束。因为不会进行回溯，贪婪法只在很少的情况下可以得到真正的最优解，比如最短路径问题、图的最小生成树问题。
大多数情况下，贪婪法会错过真正的最优解，但是贪婪法简单高效，省去了为找最优解可能需要的穷举操作，可以得到与最优解比较接近的近似最优解，通常作为其他算法的辅助算法使用.

Prim算法（最小生成树）

Prim算法通过一系列不断扩张的子树来构造一棵最小生成树。我们从图的顶点集合V中任意选择的一个单顶点，作为序列中的初始子树。每一次迭代时，以一种贪婪的方式来扩张当前的生成树，即简单地把不在树中的最近顶点添加到树中。（我们所说的最近顶点，是指一个不在树中的顶点，它以一条权重最小的边和树中的顶点相连。而树的形状是无所谓的。）当图的所有顶点都包含在所构造的树中以后，该算法就停止了。
因为在每次迭代的时候，该算法只对树扩展一个顶点，这种迭代的总次数是n-1，其中n是图中的顶点个数。对树进行扩展时用到的边的集合用来表示该算法的生成树。

算法 Prim（G）
//构造最小生成树的Prim算法
//输入：加权连通图G=<V,E>
//输出：ET组成G的最小生成树的边的集合
VT←{v0}     // 可以用任意顶点来初始化树的顶点集合
ET←Ф
For i←1 to |V|-1 do
       在所有的边(v, u)中，求权重最小的边e*=(v*，u*)，
       使得v在VT中，而u在V-VT中
        VT←VT∪{u*}
        ET ← ET ∪{e*}
Return ET

Prim算法要求出：对于每一个不在当前树T=<VT,ET>中的顶点，它连接树中顶点的最短边的信息——对一个顶点附加两个标记(最近顶点,相应边权重)，可以提供这种信息。

确定了一个加入树中的顶点u*以后，需要做两步操作：

• 把u从集合V-VT移动到树的顶点集合VT中。
• 对于集合V-VT中每一个剩下的顶点u，如果它用一条比u的当前距离标记更短的边和u相连，分别把它的标记更新为u以及u*与u之间的权重

Kruskal算法

• Kruskal算法把一个加权连通图G=<V,E>的最小生成树看作是一个具有|V|-1条边的无环子图，并且边的权重和最小的（不难证明这样的子图一定是一棵树）。因此，该算法通过对子图的一系列扩展来构造一棵最小生成树，这些子图总是无环的，但在算法的中间阶段，并不一定是连通的。
• 该算法开始的时候，会按照权重的非递减顺序对图中的边进行排序。然后，从一个空子图开始，它会扫描这个有序列表，并试图把列表中的下一条边加到当前的子图中；当然，这种添加不应导致一个回路，如果产生了回路，就简单地把这条边跳过。

算法 Kruskal（G）
//构造最小生成树的Kruskal算法
//输入：加权连通图G=<V,E>
//输出：ET，组成G的最小生成树的边的集合
按照边的权重w（ei1 ≤ … ≤ ei|E|）的非递减顺序对集合E排序
ET ←Ф；ecounter←0  //初始化树中边的顶点集合以及集合的规模
k ← 0      // 初始化已处理的边的数量
while ecounter<|V|-1
     k ← k +1
if ET ∪{eik}无回路
ET ← ET ∪{eik}; ecounter ←ecounter+1
Return ET

在每一次迭代的时候，Kruskal算法必须要检查把下一条边加入到已经选中的边中是否会形成一条回路。不难发现，当且仅当新的边所连接的两个顶点之间已经有一种路径时才会形成一条新的回路，也就是说当且仅当这两个顶点属于相同的连通分量时，这种情况才会出现。

可以对Kruskal算法做出一种略微不同的解释。可以把该算法的操作看成是对包含给定图的所有顶点和某些边的一系列森林所做的连续动作。初始森林是由|V|棵普通的树构成的，每棵树包含图的一个单独顶点。而最终的森林是由一棵单独的树构成的，它就是该图的最小生成树。在每次迭代的时候，该算法从图的边有序列表中取出下一条边（u，v），并找到包含顶点u和v的树，如果它们不是同一棵树，通过加入边（u，v）把这两棵树连成一棵更大的树。

相交子集和并查算法

• 有许多应用要求把一个n元素集合S动态划分为一系列不相交的子集S1，S2，……，Sk，Kruskal算法就是其中的一种。在把它们初始化为n个单元素子集以后，每一个子集都包含了S中一个不同的元素，然后可以对这些子集做一系列求并集和查找的混合操作。

** 定义一种抽象数据类型，这种数据类型是由某个有限集的一系列不相交子集以及下面这些操作所构成的：**

• Makeset(x)生成一个单元素集合{x}。假设这个操作对集合S的每一个元素只能应用一次。
• Find(x)返回一个包含x的子集。
• Union(x, y)构造分别包含x和y的不相交子集Sx和Sy的并集，并把它添加到子集的集合中，以代替被删除后的Sx和Sy.
  这种抽象数据类型的大多数实现都会使用每一个不相交子集中的一个元素作为子集的代表。

例：
S={1，2，3，4，5，6}。因为make(i)可以生成集合{i}，把这个操作应用6次以后，就初始化好了一个由6个单元素集合组成的结构：
{1}，{2}，{3}，{4}，{5}，{6}
执行union(1，4)和union(5，2)产生出
{1，4}，{5，2}，{3}，{6}
如果再执行union(4，5)和union(3，6)，则最后就得到了这两个不相交的子集：
{1，4，5，2}，{3，6}

实现这种数据结构有两种主要的做法。第一种称为快速查找，其查找操作的时间效率是最优的；第二种称为快速求并，其求并集操作是最优的。

快速查找要使用一个数组，并以集合S中的元素来索引数组；数组中的值指出了包含这些元素的子集代表。每一个子集都是由链表实现的，表头包含了指向表头和表尾元素的指针以及表中的元素个数。

效率分析：

对每个需要长久保存其对象实例的类，要增加一个属性（类属性）“类名”，指出自己是属于哪个类的。 makeset(x)的实现要求把代表数组中相应元素的值赋为x，并把相应的链表初始化为值为x的单节点链表。这种操作的时间效率显然属于Θ(1)，因此初始n个单元素子集属于Θ(n)。

• find(x)的效率也是属于Θ(1)：我们所需要做的就是从代表数组中取出x的代表。

• union(x，y)的执行时间就要长一些。一种直接的做法就是简单地把y的列表添加到x列表的后面，对于y列表中的所有元素更新它们的代表信息，然后再删除y的列表。然而，很容易验证，如果以这种算法进行一系列的求并集操作
  union(2，1)，union(3，2)，…union(i+1，i)，…union(n，n-1)
  它的运行时间属于Θ(n2) 。

• 有一种简单的方法可以改进一系列union操作的总效率，即总是将两个链表中较短的表添加到较长的表之后，而顺序则是无所谓的。当然，前提是每个链表的大小是已知的，比如可以在表头中存储元素的数量。这种改进称为按大小求并。虽然这不会改善一次union操作的最差效率（它还是属于Θ(n)），但对于一系列按大小求并的操作，可以证明任何合理的操作序列的最差效率是属于O(nlogn)的。

• 证明:设要对集合S中的子集进行处理，ai是S中的一个元素，在一系列按大小求并胡操作中，ai的代表被更新的次数为Ai。如果集合S有n个元素，Ai最多能达到多大？每次更新ai的代表时，ai总是属于求并集的两个字集中较小的子集，而并集的规模至少是包含ai的子集的两倍大。因此，当ai的代表第一次被更新的时候，结果集至少包含两个元素；当第二次被更新的时候，结果集至少包含4个元素；推而广之，当它被第Ai更新的时候，结果集将至少包含2Ai个元素。因为整个集合S只有n个元素，所以2Ai ≤n，因此Ai ≤ log2n。所以，对于S中的所有n个元素来说，代表可能被 更新的总次数不会超过nlog2n。

• 因此，对于按大小求并，不超过n-1次求并和m次查找的操作序列的时间效率属于O(nlogn+m)。

• 快速求并用一棵有根树来表示每一个子集。树中的节点包含子集中的元素（每个节点一个元素），而根中的元素就被当作该子集的代表；树中的边从子女指向它们的父母。

• makeset(x)需要创建一棵单节点的树， 这是一个Θ(1)的操作；因此初始化n棵单节点树是Θ(n)的操作
• union(x,y)的实现方法是把y树的根附加到x树的根上(并把指向y树的根的指针轩为空，来把y树删除)。这种操作的时间效率显然属于Θ(1)。
• find(x)实现方法是沿着一条指针链，从包含x的节点开始找到树的根（根中元素作为子集代表就是该函数的返回值）。相应的，单次find操作的时间效率属于O(n)，因为一棵表示子集的树可以退化为一个n节点的链表
• 对于快速求并来说，不超过n-1次求并和m次查找的操作序列的时间效率属于O(n+mlog n)。

Dijkstra算法

考虑单起点最短路径问题：对于加权连通图的一个称为起点的给定顶点，求出它到所有其他顶点之间的一系列最短路径。
Dijkstra算法按照从给定起点到图中顶点的距离，顺序求出最短的路径。首先，它求出从起点到最接近起点的顶点之间的最短路径，然后求出第二近的，以此类推。

• 在第i次迭代开始以前，该算法已经确定了i-1条连接起点和离起点最近顶点之间的最短路径。这些顶点、起点和从起点到顶点的路径上的边，构成了给定图的一棵子树Ti。因为所有边的权重都是非负数，可以从与Ti的顶点相邻的顶点中找到下一个和起点最接近的顶点。和Ti的顶点相邻的顶点集合称为“边缘顶点”；以它们为候选对象，Dijkstra算法可以从中选出下一个最接近起点的顶点。为了确定第i个最接近的顶点，对于每一个边缘顶点u，该算法求出它到最近的树中顶点v的距离（根据边(v,u)的权重）以及从起点到v（刚才由算法所确定的）的最短路径长度dv的和，再从中选出具有最小和的顶点。

哈夫曼树

• 假设我们为文本中的每一个字符赋予一串称为代码字的比特位，对来自于某张字母表的n个不同字符组成的文本进行编码。

• 定长编码：对每个字符赋予一个长度同为m（m>=log2n）的比特串。

• 变长编码：要求对不同的字符赋予长度不同的代码字。

• *前缀码（或者简称前缀码）。在前缀码中，所有的代码字都不是另一个字符代码字的前缀。因此，经过这样的编码，可以简单地扫描一个比特串，直到得到一组等于某个字符代码字的比特位，用该字符替换这些比特位，然后重复上述操作，直到达到比特串的末尾。

• 如果对某个字母表创建一套二进制前缀码，很自然地可以把字母表中的字符和一棵二叉树的叶了联系起来，树中所有的左向边都标记为0，而所有的右向边都标记为1（反之亦然）。可以通过记录从根到字符叶子的简单路径上的标记来获得一个字符的代码字。因为从一个叶子到另一个叶子的简单路径不存在，所以一个代码字不可能是另一个代码字的前缀；也就是说，任何这样的树都会生成一套前缀码。

• 如果已知字符的出现概率，可以按照这种方式构造许多棵代表给定字母表的树，但如何构造一棵将较短比特串分配给高频字符、将较长比特串分配给低频字符的树呢？

根据贪婪算法来构造哈夫曼树的哈夫曼编码算法：

1. 初始化n个单节点的树，并为它们标上字母表中的字符。把每个字符的概率记在树的根中，用来指出树的权重（更一般地来说，树的权重等于树中所有叶子的概率之和）。
2. 重复下面的步骤，直到只剩一棵单独的树。找到两棵权重最小的树，把它们作为新树中的左右子树，并把其权重之和作为新的权重记录在新树的根中。