贪心算法概述贪心算法（又称贪婪算法），基本原理是，遵循某种既定原则，不断地选取当前条件下最优的选择来构造每一个子步骤，直到获得问题最终的求解。即在求解时，总是作出当前看来最好的选择。也就是说，不从整体最优上加以考虑，仅是求解局部最优解，以期望能找到全局最优解。 贪心算法与动态规划类似，都是将原来的较大规模的问题拆分为规模较小的问题，依据大问题与小问题之间的递推关系，通过解决较小规模的问题，最终获得原始问题的求解。但是动态规划要通盘考虑各个阶段各子问题的求解情况，从全局的角度进行衡量，最终找到解决原始问题的最佳解决方案。贪心算法与动态规划的不同之处在于，贪心算法利用问题的贪心性质，简化了分解原始问题的过程，每次只关注在当前状态下可以获得的局部最优解，通过拼接各阶段的局部最优解获得最终问题的解。因为贪心选择可以依赖于以往所做的选择，但绝不依赖于未来所做的选择，也不依赖于子问题的解。故而贪心算法往往求解时与动态规划相反，采用自顶向下的方式，迭代作出贪心选择，不断化简问题规模。 利用贪心算法解题，需要解决两个问题： - 是否适合用贪心法求解，即所求解问题是否具有贪心选择性质。所谓贪心选择性质是指应用同一规则，将原问题变为一个相似的但规模更小的子问题，而后的每一步都是当前看似最佳的选择。这种选择依赖于已做出的选择，但不依赖于未做出的选择。从全局来看，运用贪心策略解决的问题在程序的运行过程中无回溯过程。贪心选择性质的证明一般采用数学归纳法，证明每一步做出的贪心选择确实能导致问题的整体（全局）最优解，也有基于算法的输出，或使用一种“拟阵”结构等形式的证明。
- 是否具有局部最优解，从而通过选择一个贪心标准，可以得到问题的最优解。贪心算法和动态规划都依赖于问题具有最优子结构性质，但并不是具有最优子结构性质的问题就可以用贪心算法求解。贪心算法不是总能对动态规划求解最优化问题进行优化的。
贪心算法解题思路- 建立对问题精确描述的数学模型，包括定义最优解的模型；
- 将问题分成一系列的子问题，同时定义子问题的最优解结构；
- 应用贪心算法原则可以确定每个子问题的局部最优解，并根据最优解模型，用子问题的局部最优解堆叠出全局最优解。
代码示例- 硬币找零问题是给定找零金额，计算如何搭配使得使用的硬币数量最少
# 硬币找零问题是给定找零金额，计算如何搭配使得使用的硬币数量最少def get_change(coins, amount): coins.sort() # 从面值最大的硬币开始遍历 i = len(coins) - 1 di = {} while i >= 0: if amount >= coins[i]: n = int(amount // coins[i]) change = n * coins[i] amount -= change di[coins[i]] = n i -= 1 return di
现在有一个包含 5 个字符的字符表 {A,B,C,D,E}，各字符出现的频率A:0.35, B:0.1, C:0.2, D:0.2, E:0.15； 构造一种有效率的编码类型，使用该编码表达以上字符表内容时可以产生平均长度最短的位串。在对由 n 个字符组成的文本进行编码过程中，有两种编码方式，即定长编码和变长编码。对于定长编码而言，会为每个字符赋予一个长度固定为 m(m≥log2n) 的位串，我们常用的标准 ASCII 码就是采用定长编码策略对字符集进行编码的。长度各异的编码，其中出现频率较高的字符，采用长度较短的编码表示，出现频率较低的字符，采用长度较长的编码表示。 为了对某字母表构造一套二进制的前缀码，可以借助二叉树。将树中所有的左向边都标记为0，所有的右向边都标记为 1。通过记录从根节点到字符所在的叶子节点的简单路径上的所有 0-1 标记来获得表示该字符的编码。 # 参考文档: https://www.92python.com/view/354.html# 树节点定义class Node: def __init__(self, pro): self.left = None self.right = None self.parent = None self.pro = pro def is_left(self): # 判断左子树 return self.parent.left == self# create nodes创建叶子节点def create_nodes(pros): return [Node(pro) for pro in pros]# create Huffman-Tree创建Huffman树def create_huffman_tree(nodes): '''从下向上创建二叉树''' queue = nodes[:] while len(queue) > 1: queue.sort(key=lambda item: item.pro) node_left = queue.pop(0) node_right = queue.pop(0) node_parent = Node(node_left.pro + node_right.pro) # 二节点值合并 node_parent.left = node_left # 父亲认儿子， node_parent.right = node_right node_left.parent = node_parent # 儿子认父亲 node_right.parent = node_parent queue.append(node_parent) queue[0].parent = None return queue[0]# Huffman编码def huffman_encoding(nodes, root): '''根据当前节点为左右子树进行判断赋值''' codes = [''] * len(nodes) for i in range(len(nodes)): node_temp = nodes[i] while node_temp != root: if node_temp.is_left(): codes[i] = '0' + codes[i] else: codes[i] = '1' + codes[i] node_temp = node_temp.parent # 当前节点替换为父子节点 return codesif __name__ == '__main__': letters_pros = [('B', 10), ('E', 15), ('C', 20), ('D', 20), ('A', 35)] nodes = create_nodes([item[1] for item in letters_pros]) # 生成树节点 root = create_huffman_tree(nodes) codes = huffman_encoding(nodes, root) for item in zip(letters_pros, codes): print('Label:%s pro:%-2d Huffman Code:%s' % (item[0][0], item[0][1], item[1]))
哈夫曼树： 总结- 贪心算法需要具备贪心选择性质和最优子结构性质
- 动态规划和贪心算法的计算顺序是相反的，动态规划由下而上，贪心从顶而下；
|
