动态22.3最优字母基码树问题ARC.pdfVIP

2.3 最优字母基码树问题(ARC) 最优字母基码树问题[23]是 编码树问题的一个变种。 编码树可以通过“贪心” 得到：每次把权值最小的两个节点a 和b 合并到一棵 ，并将节点a 和b 用一个权值为 a,b 权值之和的节点c 替换。而变更成字母，则每次只能合并相邻的节点，并用新节点替换 原来位置上的节点。有了这个约束条件，贪心就不再严格最优，但是 可以利用DP 解决 这个问题。由于这棵树可以通过添加括号来表示，所以此问题等价 最佳括号添加方案， 而且可以用和BST 、MCM 类似的方法解决该问题。如何得到每个决策的花费是解决本题的 关键。 注意到 树是自底向上构造的，即第一次决策是选择两个应作为最初组合的 叶子节点。而另一方面，字母基码树是自顶向下构造的，这里的第一个决策是选择整棵树的 根节点，并据其将叶子节点划分到左右子集。那么最主要 就是如果定义每个划分的费 用。 基码树有一个十分有用的性质，它给 提供了解决这个最优问题的契机。即这棵树的总花 费是其每个节点的花费之和，且每个节点的花费是以之为根节点的 中叶子节点的花费之 和。这些节点，当然，就对应了决策。因此， 可以令字母基码树中每个节点的花费为以 之为根的 中叶子节点的花费之和。这个费用与叶子节点如何划分没有关系。于是 可 以用类似MCM 的状态转移方程自顶向下地解决这个有约束 。给定叶子节点的权值表 S=(w0,w1,…,wn-1)(这是一个有序序列) ， 用数对(i,j) 来定义状态，它代表权值表 (wi,wi+1,...,j) 。那么： 这里c(i,j,d) (wi+wi+1+…+wj) 。 的目标是以f(i,i)=0 为边界条件寻找f(0,n-1)。 例如，如果初始费用是 S=(1,2,3,4)，那么最优树是((1,2),3),4)且 f(S)=3+6+10=19 。初始状态 (0,3)表示权表(1,2,3,4) ，最初决策是 d=2 ，它导出了两个新状态，状态(0,2)表示权表(1,2,3) 而状态(3,3)表示权表(4);决策的费用和是1+2+3+4=10。另一个例子，如果最初S=(2,3,3,4)， 那么最优树是((2,3),(3,4))而且费用f(S)=5+7+12=24 。