湛江网站制作网站,免费微网站哪个好用,西安网站建设公司西安网络公司,广西建设网官方证件信息查询定义 每一步都做出当前看来最优的操作。
问题引入——活动选择问题 问题描述 活动选择问题就是对给定的包含n个活动的集合S#xff0c;在已知每个活动开始时间和结束时间的条件下#xff0c;从中选出最多可兼容活动的子集合#xff0c;称为最大兼容活动集合。 不失一般性在已知每个活动开始时间和结束时间的条件下从中选出最多可兼容活动的子集合称为最大兼容活动集合。 不失一般性设活动已经按照结束时间单调递增排序。 分析 这个问题具有最优子结构可以用动态规划但用贪心复杂度更低。 实际上任何一个可以用贪心解决的问题都可以用动态规划解决。 这里的贪心策略为每次都选择能选择的活动中结束时间最早的活动。 证明贪心正确性 感性上这样做可以为后面留出最多的时间。 严格证明只需证明如下定理 考虑任意非空子问题令是中结束时间最早的活动则必在的某个最大兼容活动子集中。 证明 设为的一个最大兼容活动子集中最早结束的活动为。 若则成立。 若则设由于中活动兼容有结束时间比中最早的还早故也是的一个兼容活动子集又故也是的一个最大兼容活动子集故在的某个最大兼容活动子集中也成立。 证毕。 实现 自顶向下 自底向上 总结——贪心算法的一般步骤 1确定问题的最优子结构 2将最优化问题转化为这样的形式每次对其作出选择后只剩下一个子问题需要求解 3证明作出贪心选择后剩余的子问题满足其最优子解与前面的贪心选择组合即可得到原问题的最优解(具有最优子结构)。
总结——证明贪心算法正确性 贪心选择性质和最优子结构性是两个关键要素。 贪心选择性质可以通过做出局部最优贪心选择来构造全局最优解的性质。 贪心选择性质使得我们进行选择时只需做出当前看起来最优的选择而不用考虑子问题的解。 例子——Huffman编码 Huffman算法 从 |C| 个叶子结点开始每次选择频率最低的两个结点合并将得到的新结点加入集合继续合并这样执行 |C|-1次 “合并” 后即可构造出一棵编码树——Huffman树。 采用以freq为关键字的最小优先队列Q提取两个最低频率的对象将之合并。 时间复杂度分析 假设Q使用最小二叉堆实现则 首先Q的初始化时间复杂度O(n)。 其次循环的总代价是O(nlgn)for循环共执行了n-1次每次从堆中找出当前频率最小的两个结点及把合并得到的新结点插入到堆中均花费O(lgn)所以循环的总代价是O(nlgn)。 总时间复杂度O(nlgn)。 正确性证明 首先可以发现一个最优字符编码方案总对应一棵满 (full) 二叉树 即每个非叶子结点都有两个孩子结点。 引理1 令C为一个字母表其中每个字符 c∈C 都有一个频率 c.freq。 令 x 和 y 是C中频率最低的两个字符。那么存在C的一个最优前缀码x和y的码字长度相同且只有最后一个二进制位不同。 证 令T是一个最优前缀码所对应的编码树a和b是T中深度最大的兄弟叶结点。 不失一般性假设 a.freq ≤ b.freq 且 x.freq ≤ y.freq。 由于x和y是叶结点中频率最低的两个结点所以应有 x.freq ≤ a.freq 且y.freq ≤ b.freq。 若 x.freq b.freq则有a.freq b.freq x.freq y.freq此时引理成立。 若 x.freq ≠ b.freq即 x≠ b。则在T中交换 x 和 a生成一棵 新树T’ 然后再在T’中交换 b和y生成另一棵新树T” 那么在T”中x和y是深度最深的两个兄弟结点。 计算代价差 同理有 因此又B(T)为最优编码故 即得证T” 也是最优解且 x 和 y 是其中深度最大的两个兄弟结点x和y的码字长度相同且只有最后一个二进制位不同。 引理2 令C为一个给定的字母表其中每个字符c∈C都有一 个频率c.freq。x和y是C中频率最低的两个字符。 令C为C去掉字符x和y并加入一个新字符z后得到的字母表 即C C - {x, y}∪{z}z.freq x.freq y.freq。 令T为字母表C的任意一个最优前缀码对应的编码树。 则有可以将T中叶子结点 z 替换为一个以x和y为孩子的内部结点得到树T而T表示字母表C的一个最优前缀码。 由引理1、2可得Huffman算法的正确性。
