贪心合并模型
反复合并两个最小权对象,代价为两权之和;用二叉合并树与交换论证证明最优,是 Huffman 合并的抽象。标签 算法 / 贪心 / 合并 / Huffman / 交换论证
模型
为避免与多重集符号冲突,状态集记作 :每个状态 是一个有限非空多重集,元素为非负实数。终止状态为
对 ,动作集 由从 中取两个元素组成的无序对构成;值相同的两个副本也视为不同元素。若动作 ,则
动作代价为 。
令 为从 合并到单元素的最小总代价,则
当 时,。
贪心取
即当前最小的两个元素;和相同时任取一对。
正确性
按 贪心决策模型,只需证明 是安全选择:存在最优动作序列以 开头。
任一从 出发的动作序列对应一棵二叉合并树。若叶子权值为 ,深度为 ,则总代价为
其中 是内部结点集合。
设 是 中最小的两个元素。取一棵最优树,选两个深度最大的兄弟叶。把 与这两个叶子的权值重新分配,使 占据这两个最深位置;因为 不大于原来的两个权值,且被换到的深度不超过原深度, 不增。因此存在一棵最优树,使 位于最深的兄弟位置。
把这对叶子收缩为一个权值为 的叶子,得到 的一棵合并树,且原树总代价等于
若 不是 的最优树,把 的更优树与 合并会得到比 更优的原树,矛盾;所以 最优。
对 归纳: 的最优总代价是 ,于是先合并 再继续贪心可得到 ,这正是原树的最优代价。因此
即 是安全选择。
每一步都安全,由贪心决策模型的归纳结论,反复取当前最小的两个元素得到最小总代价。
若合并代价不是两权之和,或一次合并不止两个元素,上述贪心规则不保证最优。