贪心合并模型

反复合并两个最小权对象,代价为两权之和;用二叉合并树与交换论证证明最优,是 Huffman 合并的抽象。

标签 算法 / 贪心 / 合并 / Huffman / 交换论证

模型

为避免与多重集符号冲突,状态集记作 𝒮︀:每个状态 𝑆∈𝒮︀ 是一个有限非空多重集,元素为非负实数。终止状态为

𝑇={𝑆∈𝒮︀:|𝑆|=1}.

对 𝑆∉𝑇,动作集 𝐴(𝑆) 由从 𝑆 中取两个元素组成的无序对构成;值相同的两个副本也视为不同元素。若动作 𝑎={𝑥,𝑦}∈𝐴(𝑆),则

𝛿(𝑆,𝑎)=(𝑆∖{𝑥,𝑦})∪{𝑥+𝑦}.

动作代价为 𝑐(𝑆,𝑎)=𝑥+𝑦。

令 𝐹(𝑆) 为从 𝑆 合并到单元素的最小总代价,则

𝐹(𝑆)=min𝑎∈𝐴(𝑆){𝑐(𝑆,𝑎)+𝐹(𝛿(𝑆,𝑎))}.

当 𝑆∈𝑇 时,𝐹(𝑆)=0。

贪心取

𝑔(𝑆)∈argmin𝑎={𝑥,𝑦}∈𝐴(𝑆)(𝑥+𝑦),

即当前最小的两个元素;和相同时任取一对。

正确性

按 贪心决策模型,只需证明 𝑔(𝑆) 是安全选择:存在最优动作序列以 𝑔(𝑆) 开头。

任一从 𝑆 出发的动作序列对应一棵二叉合并树。若叶子权值为 𝑤1,…,𝑤𝑛,深度为 𝑑1,…,𝑑𝑛,则总代价为

∑𝑣∈𝐼(𝑇)𝑤(𝑣)=∑𝑖=1𝑛𝑤𝑖𝑑𝑖,

其中 𝐼(𝑇) 是内部结点集合。

设 𝑥≤𝑦 是 𝑆 中最小的两个元素。取一棵最优树,选两个深度最大的兄弟叶。把 𝑥,𝑦 与这两个叶子的权值重新分配,使 𝑥,𝑦 占据这两个最深位置;因为 𝑥,𝑦 不大于原来的两个权值,且被换到的深度不超过原深度,∑𝑤𝑖𝑑𝑖 不增。因此存在一棵最优树,使 𝑥,𝑦 位于最深的兄弟位置。

把这对叶子收缩为一个权值为 𝑥+𝑦 的叶子,得到 𝑆′=(𝑆∖{𝑥,𝑦})∪{𝑥+𝑦} 的一棵合并树,且原树总代价等于

𝑥+𝑦+𝐶(𝑇′).

若 𝑇′ 不是 𝑆′ 的最优树,把 𝑆′ 的更优树与 𝑥,𝑦 合并会得到比 𝑇 更优的原树,矛盾;所以 𝑇′ 最优。

对 |𝑆| 归纳:𝑆′ 的最优总代价是 𝐹(𝑆′),于是先合并 𝑥,𝑦 再继续贪心可得到 𝑥+𝑦+𝐹(𝑆′),这正是原树的最优代价。因此

𝑔(𝑆)∈argmin𝑎∈𝐴(𝑆){𝑐(𝑆,𝑎)+𝐹(𝛿(𝑆,𝑎))},

即 𝑔(𝑆) 是安全选择。

每一步都安全,由贪心决策模型的归纳结论,反复取当前最小的两个元素得到最小总代价。

若合并代价不是两权之和,或一次合并不止两个元素,上述贪心规则不保证最优。

源码位置