Algorithms第五章
第五章讲的是贪心算法，主要通过最小生成树的Kruskal算法来讲解，另外还讲到了prim算法和huffman算法和horn formulas以及set cover。下面就顺着书上的顺序大致记录下。
首先讲了MST(minimum spanning trees)问题，从而引出kruskal。对于一个图来说我们知道如下性质是成立的
1. 从一个环里面移除一条边并不会导致这个图变得不联通
对于MST问题，我们要求的就是求出最少的边，使得图依旧联通，而且weight(G’)即所有被选中的边的和是所有可能的选择方案中最小的。这就是MST需要解决的问题。kruskal算法的基本思想如下
不停的添加权值最小的边到当前的G中，当然加入的边有一个条件：不能形成环。
这是一个贪心算法，因为每一步都是考虑当前情况下最好的选择，下图是一个kruskal算法的列子，来自《Algorithms》
对于树还有几条性质如下：
2. 一棵有n个节点的树有n-1条边。这个是显然的，因为我们首先可以把n个节点都看成是独立的，然后每次选择两个没有联通的点直接加上一条边，这样的话每一次都会减少一个独立的点/或块[连起来之后算成一块]，最后变成了一整块，那么我们需要连n-1次，也就是有n-1条边[因为树是无环的，所以上面加边的时候我们就有一定的保证和限制]，当然反过来也是成立的
3. 任何联通的无向图G=(V,E)如果，|E|=|V|-1的话，那么就是一棵树。这里我们只需要证明G无环就行了，首先我们假设有环，那么我们可以通过删掉环中的一条边破坏这个环，这样G的联通性还是没有被破坏的，假设删掉所有的环之后的边数为E’’,那么我们有|E’’| = |V|-1[因为删掉环之后是树了，由性质2可得]。那么我们知道|E’’| == |E|也就是说图G是一棵树。所以我们也可以通过判断一个联通无向图的边数来判断是否是一棵树
4.一个无向图是一棵树的话当且仅当每两个节点之间的路径唯一。首先我们知道如果一个图是一棵树的话，那么每两个点之间的路径肯定唯一[因为无环]；另外，如果一个图每两个节点间的路径唯一的话，每两个节点之间是联通的，又因为路径唯一，所以表示无环，这样的话这个图就是一棵树了。
在引出kruskal之前，讲了一个叫做cut property的东西。表述如下：
cut property: 如果边的集合X是图G=(V,E)的MST的一部分，任选图G的一个子图S，只要X不跨越S和V-S，也就是X在S内或者在V-S内；假设边e是连接S和V-S两部分的权值最小的边，那么X∪{e}也一定是G的MST的一部分。
Kruskal算法的基本框架如下：
Input: A connected undirecte graph G=(V,E) with edge weights w[e]
Output: A minimum spanning tree defined by the edges Xfor all u in V:
makeset(u)X = {}
Sort the edges E by weight
for all edges {u,v} in E, in increasing order of weight:
if find(u) = find(v):
add edge {u,v} to X
union(u,v)
其中makeset(x): 创建一个单独的集合只包含自己；find(x)：查找x属于哪一个集合；union(x,y): 把包含x和y的两个集合合并。
上叙算法一共用了|V|的makeset时间，2|E|的find时间和|V|-1的union时间。讲完这个算法框架之后，我们需要知道其中的makeset, find, union是怎么实现的。或者什么数据结构。这里就引出了并查集。首先给出makeset, find, union三个方法的框架，如下
par[x] = x
rank[x] = 0procedure find(x)
while x =/= par[x]:
x = par[x]
return xprocedure union(x, y)
rx = find(x)
ry = find(y)
if rx == ry:
return
if rx > ry:
par[ry] = rx
else:
par[rx] = ry
if rx == ry:
rank[ry] = rank[ry]+1
其中par[]用来表示每个节点属于哪个组，rank[]是一个辅助数组，它的作用后面会说到。对于rank数组有如下几个性质
1. 对所有的点x，rank[x] < rank[par[x]]。对于这一点我们只需要看union的实现就行了，每次合并的时候，把rank值小的往大的那边合并，如果一样的话那么就随便，但是父节点的rank会加1.这样还是父节点的rank会大。
2. 任何rank为k的根节点，这棵树至少有2^k个节点。这个可以用归纳法证明，首先每个节点是只有自己，rank为0，有1=2^0个节点。对于union的时候，如果是rank不相等的话，那么肯定是符合这个情况的，如果rank相等的话，那么两个rank为t的合并之后根节点的rank为t+1.总节点>=2^t+2^t=2^(t+1)也符合情况
3.如果一棵树有n个节点，那么rank为k的节点最多有n/2^k个，这个可以有性质2推出来。然后这样的话对于含有n个节点的树，rank的最大值为log[n]。这样的话find和union的上届就是log[n]了。
到这里为之，我们的kruskal算法的整个时间为排序的时间O(|E|log|V|)(这里我们当log[E] = log[V])再加上另外一个O(Elog[V])这是find和union所花费的时间。排序的时间基本不能改善了，那么我们是否还可以改善后面的时间呢？事实上是可以的。最简单的方法就是在find的过程中进行路径压缩，那么find就变成了如下
if x =/= par[x]:
par[x] = find(par[x])
return par[x]
这样的话，只要对x进行一次查找之后，那么x就直接指向了这个集合的根节点，而且x和根节点之间的所有点也直接指向了根节点，下一次如果需要查找这些点的时候，查找的时间就会大大减少。基本可以看成是O(1)的了，而不是O(log[n])[log[n]是树的深度]。当然还可以优化到更好，不过实现起来就更麻烦，如果想具体了解，请参看Algorithms第147页。
接下来的Prim算法就简单了。基本思想和Dijkstra算法类似，不过每次的最短长度是更新的到已知树的，而不是到源点的。而且cut property保证了这个算法的正确性。算法如下
Input: A connected undirected graph G = (E,V) with edge weights w[e]
Output: A minimum spanning tree defined by the array prevfor all v in V
cost[u] = inf
pre[u] = nil
pick any initial node u0
cost[u0] = 0H = makequeue(V) (priority queue, using cost-values as keys)
while H is not empty:
v = deletemin(H)
for each {v,z} in E:
if cost[z] > w[v,z]
cost[z] = w[v,z]
pre[z] = v
decreasekey(H, z)
接下来是Huffman encoding算法。Huffman算法由如下事例引出。假设我们需要对一个包含ABCD四个字母的一长串字符串进行01编码，那么怎样的编码使得编码后的长度最短呢，最直接的想法当然是用logn个bit来进行编码，这样的话我们可以表示最少n个字母[因为前面的log需要向上取整]，这样的编码简单，但是并不是最好的，比如说其中某些字母非常的多，但是其他的字母非常的少。这样的话我们就没有很好的利用这些已知的信息，也就是我们默认的把所有字母出现的次数看成是一样的。这当然是不好的。那么编码只需要需要满足几个条件每个编码能唯一的表示一个字母，任何编码不是其他编码的前缀。这样我们可以生成一棵这样的树，树是一棵二叉树，每个节点的左字节点值为0，右字节点值为1，所有的字母在叶子节点，从根节点到叶子节点所路过的所有值组成这个字母的编码。下图是一个列子
这个图的左边是各个字母的编码，右边是编码树，其中非叶子节点是我们构造出来的。右图中的括号内数字是改字母出现的次数，对于构造出来的节点处的括号内数字，表示这个节点会被访问的次数。我们可以算出，整棵树的cost是Σfi*(depth of ith symbol in tree).其中fi表示每个字母出现的次数。我们知道这个结果和所有的括号内数字的和是相等的。对于上图我们知道等于70+60+23+37+3+20.这样的话，所有叶子节点的值的和是不变，那么我们只需要使得我们构造出来的所有节点的权值和最小就行了。那么算法就变成了下面这样
Input: An array f[1...n] of frequencies
Output: An encoding tree with n leaveslet H be a priority queue of integers, ordered by f
for i = 0 to n:
insert(H, i)for k=n+1 to 2n-1:
i = deletemin(H), j = deletemin(H)
create a node numbered k with children i,j
f[k] = f[i]+f[j]
insert(H, k)
接下来讲的是Horn formulas。也就是给出很多Implications和negative clauses。其中Implilcations是像这样的：(z^W)=>u.negative clauses则是这样的：((not u) or (not v) or (not y))问你有没有可能存在一种可能使得所有的式子都为真。具体的贪心算法如下：
Input: a Horn formula
Output: a satisfying assignment, if one existsset all variables to false
while there is an implication that is not satisfied:
set the right-hand variable of the implication to trueif all pure negative clauses are satisfied:
return the assignment
else:
return “formula is not satisfiable.”
这个算法的准确性是可以证明的，在while循环结束的时候保证了所有的Implicatons都为真，如果还有negative clauses为假的话[所有变量初值设为false，在这里就有作用了，取反之后就变成了true]。那么就不能可能有符合的情况。当然这个算法还可以进一步进行优化，即类似于把Implications链成一条链，这个可以自行google。
下面是set cover。不过书上给的是一个近似的贪心算法，不保证能得到最优值，不过证明了和最优值的差距。问题是这样的：给你n个点，需要选去最少的基站个数，使得每个点到最近的基站距离不超过一个定值[如果基站在该店，那么距离为0]。先给出贪心算法：
Input: A set of elements B; sets S1, … Sm in B
Output: A selection of the Si whose union is B
Cost: Number of the picked.Repeat unitl all elements of B are covered:
Pick the set Si with the largest number of uncovered elements.
也就是最直观的想法，每次选择邻接点最多的点，直到所有节点都包含为止。但是这个算法不能保证最优，下图就是一个例子
上图中[右图的边表示两个节点的距离不超过某个定值]我们的算法会得到的是a,c,j,f/g但是实际上我们可以只用3个节点就行了：b,e,i。但是这个贪心算法可以保证比最优的不是坏很多。也就是说：
Claim: 假设B有n个节点的话而且最少可以用k个集合达到要求的话，那么我们的贪心算法最多只会用k*lnn个集合[其中ln表示自然对数]。证明如下：
我们假设n[t]表示在贪心算法中迭代t次之后还没有被覆盖的顶点数目（n[0]=n），因为剩下的顶点一定能被k个集合覆盖，所以某一个集合一定含有至少n[t]/k个顶点，也就是说n[t+1]<=n[t]-n[t]/k = nt这里我们得到n[t] <= n[0](1-1/k)^t.又因为1-x<=e^(-x)对所有x成立，x=0时取等号。那么n[t]<=n[0](1-1/k)^t < n0)^t = ne^(-t/k)当t=klnn的时候，n[t]已经等于1了，也就是说所有顶点都被包含了。这样就得到证明了。
贪心这一章比前两章写起来难多了，贪心最难的还是在证明，一般贪心算法简单，但是证明很难。但是这个怎么搞可能也只有多练习了。
