江苏龙网

  1. 主页 > 生活百科 > >

python算法基础之贪心算法

贪心算法

贪心算法概述贪心算法（又称贪婪算法），基本原理是，遵循某种既定原则，不断地选取当前条件下最优的选择来构造每一个子步骤，直到获得问题最终的求解 。即在求解时，总是作出当前看来最好的选择 。也就是说，不从整体最优上加以考虑，仅是求解局部最优解，以期望能找到全局最优解 。
贪心算法与动态规划类似，都是将原来的较大规模的问题拆分为规模较小的问题，依据大问题与小问题之间的递推关系，通过解决较小规模的问题，最终获得原始问题的求解 。但是动态规划要通盘考虑各个阶段各子问题的求解情况，从全局的角度进行衡量，最终找到解决原始问题的最佳解决方案 。贪心算法与动态规划的不同之处在于，贪心算法利用问题的贪心性质，简化了分解原始问题的过程，每次只关注在当前状态下可以获得的局部最优解，通过拼接各阶段的局部最优解获得最终问题的解 。因为贪心选择可以依赖于以往所做的选择，但绝不依赖于未来所做的选择，也不依赖于子问题的解 。故而贪心算法往往求解时与动态规划相反，采用自顶向下的方式，迭代作出贪心选择，不断化简问题规模 。
【python算法基础之贪心算法】利用贪心算法解题，需要解决两个问题：

  • 是否适合用贪心法求解，即所求解问题是否具有贪心选择性质 。所谓贪心选择性质是指应用同一规则，将原问题变为一个相似的但规模更小的子问题，而后的每一步都是当前看似最佳的选择 。这种选择依赖于已做出的选择，但不依赖于未做出的选择 。从全局来看，运用贪心策略解决的问题在程序的运行过程中无回溯过程 。贪心选择性质的证明一般采用数学归纳法，证明每一步做出的贪心选择确实能导致问题的整体（全局）最优解，也有基于算法的输出，或使用一种“拟阵”结构等形式的证明 。
  • 是否具有局部最优解，从而通过选择一个贪心标准，可以得到问题的最优解 。贪心算法和动态规划都依赖于问题具有最优子结构性质，但并不是具有最优子结构性质的问题就可以用贪心算法求解 。贪心算法不是总能对动态规划求解最优化问题进行优化的 。
贪心算法解题思路
  1. 建立对问题精确描述的数学模型，包括定义最优解的模型；
  2. 将问题分成一系列的子问题，同时定义子问题的最优解结构；
  3. 应用贪心算法原则可以确定每个子问题的局部最优解，并根据最优解模型，用子问题的局部最优解堆叠出全局最优解 。
代码示例
  • 硬币找零问题是给定找零金额，计算如何搭配使得使用的硬币数量最少
# 硬币找零问题是给定找零金额，计算如何搭配使得使用的硬币数量最少def get_change(coins, amount):coins.sort()# 从面值最大的硬币开始遍历i = len(coins) - 1di = {}while i >= 0:if amount >= coins[i]:n = int(amount // coins[i])change = n * coins[i]amount -= changedi[coins[i]] = ni -= 1return 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 = Noneself.right = Noneself.parent = Noneself.pro = prodef 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_rightnode_left.parent = node_parent# 儿子认父亲node_right.parent = node_parentqueue.Append(node_parent)queue[0].parent = Nonereturn 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]))


推荐阅读


上一篇：集客营销长期精准获取引流

下一篇：视频如何合并？三种方法