2020-06-01

【04：00】 证明哈夫曼树是最优的


• 最后得到了最优的前缀码树。
• Q是优先级队列 starN的 时间复杂度
• Q是二叉堆的话， 插入和删除都是O(logn)
• 总共执行n次，总的时间复杂度O(nlogn)


• 贪心方法是有适用条件的。

【证明 08：00】


• 最优前缀码树，没有叶子结点缺失

• B（T）是编码总长

  

• proof①记住

  

  • f(a) f(x)分别表示什么？(a,b也是字符)

  • 证明贪心选择被某个最优解包含，这里要证明T`也是一颗最优前缀码树。即证明B(T) = B（T``）

  • 

  • 这一步推导是正确的，记住结论和证明思路即可。现在要证明他们是等于的，说明T`是最优的

  • 

    得证。

  最优子结构性质是怎么表现的？

  • 在贪心方法中，所谓最优子结构性质就是贪心选择加上局部最优解，最终产生原问题的最优解的一种形式。也就是说，因为贪心方法只有1个子问题，你做出了1次贪心选择之后，剩下子问题的解也是最优的

【35：00】最优子结构性质




要证T也是最优前缀码树， 贪心选择是选择了x,y这2个频度最小的，用反证法。



产生矛盾， ··· 比 一撇还要小。

注 可用归纳法证明哈夫曼算法的正确性，上面只是证明贪心产生的全局最优解;

贪心算法 比 动态规划效率高。比如最短路径 和最小生成树都用到了贪心。

djstl是高级贪心，他每步贪心选择后会对数据做调整。

【 01：02：00】贪心法的理论基础（模型）

贪心选择的证明有时候是很困难的。

如果问题是这个模型，可以直接用贪心算法。


• 独立是说 S中具有相同性质的元素组成集合

• B的成员比A少

• x属于B 不属于A

• S ，I 是集合

• S通常是输入集合

• I从S中产生

  eg:S是自然数集合，有限的， I是其中的偶数组成的集合.

  eg: S = {1,2,3,4,5,6,7,8,9} I =S中的偶数组合的集合 B= {2,4,6,8} A={2,4} ;B的所有子集都要属于I

【01：30：00】举例说明胚


• SG是E中的边集。I是所有无回路边组成的集合

• 证明它。 （交换性是比较难以证明的，通常）

  

  • 独立性的概念，独立集的概念

  


【01：52:00】最大独立子集 和定理16.6


• （定理16.6）对图来讲，生成树不唯一，但边数一样

【-02视频 开始】3.加权胚 4.最优子集

• 给S中的每个成员1个正的权值，就称为加权胚


实际问题->模型的转换

• 对于1个问题，定义有序对

• 检查有序对是否满足胚的三个条件

• 然后给S当中的每个成员一个权值

• 通过求出加权胚的最优子集 对应了求解问题的最优解

  如果是最小问题，要转化为求最大问题，实际问题中最小到最大的 转化也是比较方便的

• 连通网络是有权值的

【-02视频 14：00】 加权胚的通用贪心算法


• 胚具有最优子结构性质 和贪心选择性质，可以直接用贪心算法 求最优解
• A一开始是空集，是独立子集。
• 没有冲突才加进去
• 算法完成之后 就得到了最优子集

对于1个问题

• 首先指定贪心选择策略（核心）
• 按照策略，每次进行一个贪心选择
• 然后进行独立性检测


• f(n)表示1次独立性检测的时间