贪心算法是一种短视的算法,所做的每个选择都是独立的,并且是在当时环境下所能采取的最佳决策。

贪心算法由一系列选择组成,贪心体现在每一个基于当时信息所做的选择中,在不考虑整体或者将来的情况,做出最好的选择。但是必须确保每个选择的安全。主要在于如何确保这种安全性。贪心算法的问题解决方案都是逐步形成的,可以先分别取得一组方案片段,然后将其合并成最终的解决方案。

总体来讲,过程如下:首先形成局部解决方案,然后检查分段式解决方案是否有效或者可行。

舞伴的配对,将各个配对集看成片段,将每一个配对集看做一个局部解决方案。只有当同一个人只会存在在至多一个配对集中,其对应的局部解决方案才是有效的。

分数背包问题

贪心算法,始终优先选择最好的东西,将这些东西按照价值排一个序,然后按这个顺序一个个装包。

整数背包问题

给特有的价值。每个类别增加一个总数值,每个类别的对象都有固定质量,以及一个特有价值。整数背包问题分为无边界和有边界。有边界情况下,每个类别中的对象数量是固定的。无边界情况下,对象的数量是无限的。贪心策略无法求解。但是动态规划可以设计出伪多项式级时间的解决方案。

哈夫曼算法

使用可变长度的编码来表示文本,这样达到压缩。文本中每个字符都有出现频率,根据这样频率信息为其分配不同长度的字符编码,从而实现文本长度的最小化。用最少的一个比特位来表示字符。都可以用二叉树的结构的叶节点路径来表示。

最明显的贪心策略就是从出现概率最大的字符开始,一个个添加字符(叶节点),或者先形成分段式解决方案,以形成若干个树结构分段,然后把这些分段反复合并起来。两个树合并的时候,添加一个新的共享根节点,赋予所有子节点之和相等的加权值。

在下面这种哈夫曼算法实现方式中,维护着一个局部解决方案,形成了一个森林结构。只要森林中还存在着两个彼此独立的树结构,就从中选取两个分量最轻的树,然后合并后放回原处,赋予根节点新的加权值(加权和)。使用了堆这种数据结构来维护分量最少的节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
from heapq import heapify, heappush, heappop
from itertools import count
def huffman(seq, frq):
num = count()
trees = list(zip(frq, num, seq))
heapify(trees)
while len(trees) > 1:
# 取出两个最小的
fa, _, a = heappop(trees)
fb, _, b = heappop(trees)
n = next(num)
heappush(trees, (fa+fb, n, [a, b]))
return trees[0][-1]

考虑这些节点从单个节点到整个树的过程。最后的结果就是,在权值和深度最小的情况下,遍历完每个叶节点。使用堆结构将反复选取,合并两个最小无序列表项的平方操作,化简成了线性对数级操作。如果森林结构中的两棵树概率相同时,堆结构需要找出较小的那棵树,所以使用到了计数器。

要进行压缩的话,需要预处理和后期加工,首先对字符出现的概率进行计数,然后构建哈夫曼树,然后找到所有字符的编码

提取哈夫曼编码:

1
2
3
4
5
6
7
def codes(tree, prefix=""):
if len(tree) == 1:
yield (tree, prefix)
return
for bit, child in zip("01", tree):
for pair in codes(child, prefix+bit):
yield pair

每次拿出最小的两个,使用最小堆实现,然后将其合并,节点值也是概率值的和,创建出了新的值,然后再添到树中。这样下去,就可以创建出一个树。那么为什么这种贪心策略就可以将该结构到达任何一个叶节点的预期深度实现为最小。

贪心选择性,每次都通过贪心选择得到了一个最优解决方案的一部分。最优子结构,作出选择之后剩下的子问题和原有的问题有着同样的解决方案。如果可以找到子问题的最佳解决方案,就可以用贪心选择将其合并成整个问题的解决方案。一个问题的最佳解决方案由其子问题的最佳解决方案构建而成。

最小生成树

一个连通无向图G的生成树T,她的节点集和G相同,边集是G的子集。最小生成树问题中,找出一种权重最小,但是能够覆盖整个G的生成树。最小生成树可以用递增步骤构建,使用贪心策略。通过一次增加一条边线的方式来逐步构建树结构。每一步中,都会选择当前构建过程中能允许加入的值最低的边。最优选择,不可撤销。主要任务就是当下部分的最优选择是全局的最优解决方案。

最小生成树一定会包含最短边。

Kruskal算法

先对图中的边进行排序,然后进行选取,因为寻找短边,所有按照权重递增顺序排序。检查导致解决方案无效的边,也就是回路,对于每一个要加入的边,检测目前所在的树结构上是否存在从u到v的路径,如果存在,就丢弃这个边。

通过标记解决方案中的每个节点来了解它们的所属树结构。可以在算法产生的每个独立部分来选择一个节点当作代表节点,让该部分的所有节点指向它。这样就是各部分的合并操作,直到所有节点要变成指向同一个代表,这就完成了各个部分的归并,这样的合并过程就是一个线性级操作。

另外一种方法就是让每一个节点都指向某个别的节点,然后顺着其方向一路链接下去,直到到达我们之前设定的代表节点,它会指向其本身。刚开始的时候,每个节点都是其所在部分的代表,然后会按照从小到达的顺序反复地用新的边把各个部分连接起来。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def naive_kruskal(G):
# 找出所有的 边的权重,节点
E = [(G[u][v], u, v) for u in G for v in G[u]]
T = set()
# 初始化 各个节点指向的字典,都指向自己
C = {u:u for u in G}
for _, u, v in sorted(E):
# 最终的节点指向如果不是一个的话
# 说明没在一个树里面,将两个节点的这条边加入结果集中
# 并且将一个节点指向另外一个节点
if naive_find(C, u) != naive_find(C, v):
T.add((u, v))
naive_union(C, u, v)
return T

找到某个节点最终指向的元素,最终的元素会指向自己,因为是按权重从小到大排序的,所以首先会找到最小边然后加入的

1
2
3
4
5
6
7
8
9
def naive_find(C, u):
while C[u] != u:
u = C[u]
return u
def naive_union(C, u, v):
# 将一个元素的代表节点指向另外一个元素的代表节点
u = naive_find(C, u)
v = naive_find(C, v)
C[u] = v

另外一种优化的思路就是在将元素指向另外一个元素的时候,让较小的指向较大的那个,这样来获得平衡。所以可以给节点赋予高度,这样从等级低的代表节点指向等级高的节点的代表,时间为O(mlgn)

路径压缩,确保探索路径的所有节点可以直接指向代表节点。这样指向的查询就可以更快一点。之前的查找就是一个接一个的去查找。这里就直接把最后一个代表节点赋值给C[u]了,所以在寻找的时候,直接经历一个函数递归就可以找到代表节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def find(C, u):
if C[u] != u:
C[u] = find(C, C[u])
return C[u]
def union(C, R, u, v):
u, v = find(C, u), find(C, v)
# 小节点指向大的,这块减少了查询次数
# 这里经过仔细研究,发现最后一个部分的节点都指向了同一个代表节点
# 代表节点的深度都是最大的
if R[u] > R[v]:
C[v] = u
else:
C[u] = v
# u指向v,因此v的高度增加1
if R[u] == R[v]:
R[v] += 1
def kruskal(G):
E = [(G[u][v], u, v) for u in G for v in G[u]]
T = set()
C, R = {u:u for u in G}, {u:0 for u in G}
for _, u, v in sorted(E):
if find(C, u) != find(C, v):
T.add((u, v))
union(C, R, u, v)
return T

Prim算法

Prim算法从某个起始节点开始对目标图结构进行遍历,并且始终将最短的连接边加入到树结构中。Prim算法是遍历型算法,遍历型算法之间主要区别在于待定列表中的顺序。Prim中将使用堆结构实现优先级队列。

1
2
3
4
5
6
7
8
9
10
11
12
from heapq import heappop, heappush
def prim(G, s):
P, Q = {}, [(0, None, s)]
while Q:
_, p, u = heappop(Q)
# 如果已经在遍历树中,跳过
if u in P: continue
P[u] = p
# 将u节点连接的所有边加入队列
for v, w in G[u].items():
heappush(Q, (w, u, v))
return P

多次添加节点的时候,每次移除的时候肯定是权值最低的那一个。并且在遍历树中不会重复添加节点。

贪心算法在逐步构建某解决方案的过程中,坚持每一步都选择添加当下最合适的元素,而不去管之前或者之后会发生什么情况。