2016-02-16供稿中心: 北大青鸟武汉中南软件学院
Optimal Alphabetic Radix-Code Tree Problem(ARC)问题是这样一个问题,给定一系列节点,每个节点有构建成本,然后构建一棵树,树的成本计算方式是这样的,如果树的节点是叶子节点,那么它的成本就是它自己,否则如果是非叶节点,那么这棵树的成本等于所有子树的和,而ARC问题就是要求个优树,使得这棵树的成本小化。很显然看出这个树的求和是递归的。
这个问题的描述很容易让我们想起huffman tree,霍夫曼树是优二叉树,满足的条件就是节点权值*路径长度,求和后小。ARC树与霍夫曼树类似,也是二叉树,条件是对所有节点的权值求和后小,只不过霍夫曼树因为不递归不重叠,所以直接贪心解即可。而ARC树一个明显的特点就是递归包含。所以我们使用动态规划来求解。而前提同huffman一样,需要先对节点权值进行排序。
问题具体化:有4个节点,分别具有权重(2,3,1,4),现求这四个节点构成的ARC树。解决这个问题的思路就在于,如果是动态规划解,那么构建这个树的方法是如何开始呢?我们知道huffman树是一个经典的自底向上方法,而ARC动态规划要转换为自顶向下。一但思路确定,定义DPFE就很明显了,我们抽象表示定义S=(w0,w1,…wn),这里的w已经有序,接下来定义状态(i,j)为{wi,…,wj}的子树求和,那么动态规划方程为:f(i,j)=min i≤d<j {c(i,j,d)+f(i,d)+f(d+1,j)} 当i<j。基本条件是f(i,j)=0当i=j时,成本计算函数c(i,j,d)=Σwk k=i,…,j。目标函数是求f(0,n)。我们以中缀括号表示一棵ARC树,那么对于具体化问题的节点集(2,3,1,4),后的结果就是(((2,1),3),4)。这棵树的权值为f(S)=(2+1)+((2+1)+3)+(2+1+3+4)=19。
代码如下:
1:/*
2: * Copyright (C) 2013 changedi
3: *
4: * Licensed under the Apache License, Version 2.0 (the "License");
5: * you may not use this file except in compliance with the License.
6: * You may obtain a copy of the License at
7: *
8: * http://www.apache.org/licenses/LICENSE-2.0
9: *
10: * Unless required by applicable law or agreed to in writing, software
11: * distributed under the License is distributed on an "AS IS" BASIS,
12: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13: * See the License for the specific language governing permissions and
14: * limitations under the License.
15: */
16:package com.jybat.dp;
17:
18:import java.util.Arrays;
19:
20:publicclass ARC {
21:
22:privatestaticdouble[] weight = { 2, 3, 1, 4 };
23:
24:privatestaticint N = weight.length - 1;
25:
26:privatestaticdouble sum(int p, int q) {
27:double result = 0.0;
28:for (int k = p; k <= q; k++) {
29: result += weight[k];
30: }
31:return result;
32: }
33:
34:publicstaticdouble f(int firstIndex, int lastIndex){
35:if(firstIndex == lastIndex)
36:return 0.0;
37:double min = Double.MAX_VALUE;
38:for(int d=firstIndex;d<lastIndex;d++){
39:double t = f(firstIndex,d) + f(d+1,lastIndex) + sum(firstIndex,lastIndex);
40:if(t<min)
41: min = t;
42: }
43:return min;
44: }
45:
46:/**
47: * @param args
48: */
49:publicstaticvoid main(String[] args) {
50: Arrays.sort(weight);
51: System.out.println(f(0,N));
52: }
53:
54: }