《Python Algorithm》7.贪婪是好的？证明它！

《Python Algorithm》7.贪婪是好的？证明它！哈夫曼算法是给定N个权值作为N个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。

《Python Algorithm》7.贪婪是好的？证明它！

• 保持安全，一步一步
  • 贪心算法
    • 只关注当前最优解
    • 确保安全
  • 七巧板
    • 给每块添加值
    • 从左上开始逐行填充
      • 按值倒序排列
      • 逐个考虑
        • 不合适，舍弃
        • 合适，使用
      • 不考虑未来的拼图片
    • 需要
      • 一个候选元素集合，或有值附加的拼图片
      • 一个检查解决方法是否合理的/可行的方法
  • 换零钱
    • 按面额排序，并从最大面额开始
    • 代码实现
  • 最大权匹配问题
    • 算法
      • 列出潜在的配对，按兼容性降序排列
      • 从列表中取出第一个未使用的配对
      • 配对中是否有人已经被占领了？有则放弃，否则使用
      • 重复执行，直至结束
    • 类似Kruskal的最小生成树算法（那个算法不考虑边的权重）
  • sidebar
    • 热切的追求者和稳定的婚姻
      • 问题
        • 一个小组每个人都有他/她想结婚的人
        • 期望所有人结婚并且稳定（没有男人在婚姻外喜欢一个也喜欢他的女人）
        • 不考虑同性婚姻和多配偶
      • 算法
        • 每个男人向还没拒绝过他的女性中排在心里第一位的求婚
        • 每名女性从追求者中选出最中意的一个，并拒绝其他人
        • 重新以上步骤，直至没有未订婚的男性
• 背包问题
  • 问题
    • 有一组我们想带的物品，每个都有重量和价值，背包有最大容量，我们希望获得最大价值
  • 应用
    • 选择一组有价值的对象时
      • 内存块
      • 文本片段
      • 项目
      • 人
    • 特例
      • 子集和问题（Ch11）
      • 零钱问题
    • 应用广泛造成解决困难
      • 解决特例
  • 部分背包问题
    • 不被要求包含或排除全部物品（即物品的任意多部分放入背包）
    • 重要的事
      • 找到价值-重量比
    • 解决
      • 按比率排序，先放单位重量最有价值的
  • 整数背包问题
    • 每类对象（价值、重量相同）有多个，必须包含整数个
    • 两种情景
      • 有界
        • 每类有固定数目
      • 无界
        • 每类都有无限多个
      • 都无法以多项式算法解决
      • 可以使用动态规划以伪多项式时间解决
        • Ch8
      • 贪心法可能得到一个不算太好也不算太坏的方法
        • Ch11
• 哈夫曼算法
  • 例子
    • 急救中心回答问题
    • 压缩
  • 算法
    • 算法
      • n个节点作为树生成森林
      • 从中挑选两个最小的树合并，根为两根树的权重和
      • 重复执行第二步
    • 代码实现
      • 哈夫曼算法
        • 使用heapq把时间从平方降为log
      • 编码
  • 第一个贪心选择
    • 证明
      • 贪心选择性质
        • 贪心选择给我们新的解决方案部分是一个最优解
      • 最优子结构
        • 选择后剩下的问题可以按原始的解决
  • 走完剩下的路
    • 把结合的两点当作一个新元素
  • 最优合并
    • 最优前缀编码
    • 决策树
    • 合并有序文件
  • tip
    • Python压缩模块
      • zlib
      • gzip
      • bz2
      • zipfile
      • tar
• 最小生成树
  • 最短的边
    • 最小生成树必须包括最短的边
    • cut
    • 选最短的边是安全的
  • 剩下的呢？
  • Kruskal算法
    • 算法
      • 把边按大小排序
      • 每次选择最小边
      • 如果不生成回路则添加
    • 重点：判断回路
      • 遍历
        • 每次要加边(u,v)时从u遍历树看是否有路径到v
          • 有则舍弃
      • 并查集
        • 朴素
          • 如果某两个节点属于同一棵树，则合并后会形成回路
          • 链表
          • 代码实现
        • 路径压缩
          • 添加一个集合时把所有节点都指向根节点
          • 代码实现
    • 从边出发，适合稀疏情况
  • Prim算法
    • 比Kruskal简单
    • 算法
      • 从一个节点开始，总是添加相连的最小边
    • 节点已在队列问题
      • 每次你找一个到某节点的边，添加包含适当权重的节点到堆/优先队列，不用管是否已经在
      • 原因
        • 使用优先队列，如果被添加多次，当删除其中一个时，会是权重低的那个
        • 确保遍历树时不添加相同节点，依赖一个常数时间的成员检查
        • 多个重复点不影响运行时间
    • 代码实现
    • 从节点出发，适合稠密情况
    • sidebar
      • 一个稍微不同的角度
        • 算法
          • 添加一个最短的边连接两个不同的碎片
          • 添加一个最短的边链接包含根的碎片和另一个碎片
          • 对于每个碎片，添加最短的边连接另一个碎片
• 贪婪奏效了，但是什么时候呢？
  • 保持最优
    • 保持领先
      • 步骤
        • 每次一步建立解决方案
        • 贪心法使之为到目前为止假设的最优算法
        • 一旦到达终点线，证明是最优的
      • 例
        • 资源调度
      • 问题
        • 选择一个兼容间隔的集合
      • 算法
        • 在解决方案中包含含有最少完成时间的间隔
        • 移除所有 和第一步重复的剩下的间隔
        • 还有剩下的间隔？回到第一步
  • 近乎完美
    • 交换参数
      • 持续时间和截止时间
      • 最小化这些持续时间的最大值
    • 证明
      • 如果最优方案包含一个倒置，有两个连续的任务，其中第一个的截止时间晚于第二个
      • 交换两个，移除倒置
      • 移除不会增加最大持续时间
  • 保持安全
    • 两步
      • 贪婪选择性质
      • 最优子结构
    • 把安全当作不变
    • 双贪婪
    • 证明
• 扩展阅读
  • 没涉及到
    • 拟阵
    • 广义拟阵
    • 拟阵嵌入
  • 零钱问题
    • Ch11
  • 建立最小化定向生成树
    • 不要用Prim算法
    • the book by Kleinberg and Tardos