深圳尚学堂:深入理解动态规划的问题
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 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++){< p="">
39:double t = f(firstIndex,d) + f(d+1,lastIndex) + sum(firstIndex,lastIndex);
40:if(t<min)< p="">
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: }
