无规则采集器列表算法(贪心算法(又称贪婪算法)是指，在对问题求解时)

　　无规则采集器列表算法(贪心算法(又称贪婪算法)是指，在对问题求解时)

　　贪心算法（也称为贪心算法）是指在解决问题时，始终在当前视图中做出最佳选择。也就是说，不考虑整体最优性，他所做的只是某种意义上的局部最优解。

　　贪心算法并没有得到所有问题的整体最优解。关键是贪心策略的选择。选择的贪心策略一定没有后遗症，即某个状态的前一个过程不会影响后一个状态，只影响当前状态。

　　在开始之前，我们介绍一个非常简单的问题，这个问题需要使用尽可能少的*敏*感*词*和纸币来添加指定的总量。

　　首先，我们会尽量从币值最大的地方开始，依次进行，并附上代码：

　　# 100美元购买物品，找钱的程序

denom = [10000, 5000, 2000, 1000, 500, 200, 100, 50, 25, 10, 5, 1]

owed = 9876

payed = []

for d in denom:

while owed >= d:

owed -= d

payed.append(d)

print(sum(payed))

print(payed)

　　编译后会输出如下结果：

　　9876

[5000, 2000, 2000, 500, 200, 100, 50, 25, 1]

　　但是这个解决方案非常脆弱，货币表的内容稍有改变就可能被破坏。

　　我们来谈谈整数背包问题。

　　您可以将整数背包视为更改问题的广义版本。

　　背包问题是组合优化的NP完全问题。问题可以描述为：给定一组物品，每件物品都有自己的重量和价格，在有限的总重量内，我们如何选择使物品的总价格最高。

　　背包问题一般分为两类：

　　分数背包问题和整数背包问题。

　　得分背包问题：

　　分数背包问题其实可以看作是最简单的一种背包问题，因为这里的对象是可以分割的，只能选择其中的一部分。

　　比如去野餐，背包里放什么，沙子、威士忌和水都可以放。

　　我们先放沙子，打完沙子后放威士忌，因为威士忌的价值介于两者之间，最后放水。

　　其实，得分背包问题的重点是找到重量比。

　　将它们按重量比排序，然后从高到低的顺序一一包装。

　　整数背包问题：

　　整数背包问题可以分为无界和有界两种情况。

　　在有边界的情况下，假设每个类别中的对象都是固定的，在没有边界的情况下，我们使用任意数量的对象。

　　贪心策略在这两种情况下都不可行，而且它们都是未解决的问题。多项式级别内没有复杂度的算法来解决它们。

　　其实还有更好的解决方案，比如动态规划，可以设计出伪多项式级别的时间复杂度程序。

　　现在我们开始介绍霍夫曼算法：

　　我们在构建平衡二叉树时，会意识到平衡二叉树的结构是在发生概率均匀分布的前提下构建的。

　　事实上，平衡二叉树构造问题在压缩领域也有应用。例如，压缩字段致力于用可变长度代码来表达文本，使其在形式上更加紧凑。在表示形式中，文本的每个字符都会有自己的出现概率，我们会根据概率信息为其分配不同长度的字符代码。从而尽量减少文本的长度。

　　具体算法实现如下：

　　# 哈弗曼算法

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]

seq = "abcdefghi"

frq = [4, 5, 6, 9, 11, 12, 15, 16, 20]

print(huffman(seq, frq))

　　上面的输出：

　　[['i', [['a', 'b'], 'e']], [['f', 'g'], [['c', 'd'], 'h']]]

　　该算法使用了堆结构（引入了 heapq 模块）。

　　在上面的算法中，是重复选择，合并两个最小的无序列表项是平方级操作（线性级的选择，乘以线性级迭代），我们用堆结构将其简化为线性对数运算（用于在多个级别选择和重新添加操作）。

　　增加了原有的祖先“概率，树”，可以在不同的概率下进行操作。但是当有两棵树的概率相同时。堆结构必须找到较小的一个。这时，我们遇到了一个不确定的比较操作。

　　但是无法比较 Python 中不兼容的对象。所以我们添加了一个字段来区分其他对象。

　　这时候如果应用于文本的压缩和解压，我们就需要进行一些处理和处理。例如，统计字符出现的概率。

　　下面附上实现，其中counting可以调用采集

s研磨中的Counter类：

　　# 从哈弗曼树中提取出哈弗曼编码

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

　　这时候就需要验证贪心算法的正确性。这时候我们就可以用归纳法来证明了。证明一般分为贪婪选择性和最优子结构两部分。

　　贪心选择是指每次我们通过贪心选择得到最有效解决方案的一部分。

　　最优子结构意味着我们做出选择后的剩余问题与原创

问题具有相同的解决方案。

　　至于霍夫曼算法的证明，详细过程这里就不写了。

　　然后看下一个问题，我们介绍最小生成树问题。

　　最小生成树是指具有n个节点的连通图的生成树是原图的一个最小连通子图，收录

原图中所有n个节点，且保持图连通的边最少。

　　这里将介绍两个新的算法 Kruskal 和 Prim 算法。

　　我们先来看最短边问题。

　　

　　这是欧几里得图的最小生成树（粗体）。

　　因为(e, i)是最短边，而且(e, i)节点必须收录

在生成树中，所以必须收录

两点之间的路径。如果我们将 (e, i) 添加到循环中，则会出现一个循环。所以，为了让生成树恢复正常，我们还得花一天的时间。因为 (e, i) 是最短边，通过去除任何其他边生成的生成树将小于我们的原创

数据结构。

　　最小生成树必须收录

最短边，这实际上是 Kruskal 算法背后的基本思想。

　　我们继续看b一定是连通的，但是b只能连通点d和a。看来短边会好一些。然后我们假设(b, a)是一个更好的选择，然后把它加入到结构中形成一个循环，但是我们去掉这条边，我们会发现得到的生成树会因为选择而更多。短边变得更小。这时候，我们的假设是错误的。因此，不收录

(b, d) 的生成树不能是最小生成树。这实际上是 Prim 算法背后的思想。

　　那么我们先来看看Kruskal算法：

　　该算法首先对图中的边进行排序，然后进行选择。由于我们这次寻找的是短边，所以我们按照长度增加的顺序对它们进行排序。

　　这里最重要的问题是检查将使解决方案无效的边。

　　这时候我们通过标记解中的每个节点来了解每个节点所属的部分，然后选择每个部分的一个节点作为代表。然后让该部分中的所有节点都指向它。

　　下面是代码实现：

　　# Kruskal算法实现的朴素版

def native_find(C, u):

while C[u] !=u:

u = C[u]

return u

def native_union(C, u, v):

u = native_find(C, u)

v = native_find(C, v)

C[u] = v

def native_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 native_find(C, u) != native_find(C, v):

T.add((u, v))

na

　　事实上，这个算法还有改进的空间。在最坏的情况下，我们用来跟踪参考链的 naive_find() 可能是一个线性级别的函数。在这两个部分之间，我们让 native_union() 总是把较小的那个指向较大的那个，来寻找平衡。

　　我们也可以直接把它们看成一组平衡树，然后给每个节点分配一定的高度。

　　这样，调用 native_find() 和 native_union() 的整体操作时间应该是 O(mlgn)。

　　优化后的代码：

　　# Kruskal算法

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

if R[u] == R[v]:

R[v] += 1

　　然后继续看Prim算法：

　　Prim 算法的主要思想是从某个起始节点开始遍历目标图结构，并始终将最短链接添加到相应的树结构中。

　　然后看具体的实现代码：

　　# Prim算法

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

for v, w in G[u].items():

heappush(Q, (w, u, v))

return P

　　至此，贪心算法的一些问题和一些算法的实现几乎是一样的。

　　这里有一点额外的。虽然一般情况下，贪心算法的正确性是通过归纳证明的，但这也可以使用一些额外的方法来完成。

　　第一个选择是保持领先。

　　主要思想是证明，当我们一步一步构建自己的解时，贪心算法总是会越来越接近某个家乡的最优解。当它到达终点时，自然证明它是最优算法。

　　第二种选择是努力做到完美。

　　该方案在前面展示了霍夫曼算法的贪婪选择特性时使用。主要是考虑如何在没有伤害和效率的情况下将假设的最佳解决方案转换为贪婪算法。,

　　第三种选择是采取安全措施。

　　主要思想是保证贪心算法的正确性是我们一切工作的出发点，必须保证每一步采用的贪心策略都是安全的。

　　在这里说这么多。

　　谢谢大家的关注。

　　天冷了，大家注意身体。