Change Dir

先知cd——热爱生活是一切艺术的开始

统计

留言簿(18)

积分与排名

“牛”们的博客

各个公司技术

我的链接

淘宝技术

阅读排行榜

评论排行榜

深入理解动态规划的一系列问题(6)

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: public class ARC {
  21:  
  22:     private static double[] weight = { 2, 3, 1, 4 };
  23:  
  24:     private static int N = weight.length - 1;
  25:  
  26:     private static double 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:     public static double 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:     public static void main(String[] args) {
  50:         Arrays.sort(weight);
  51:         System.out.println(f(0,N));
  52:     }
  53:  
  54: }


posted on 2014-04-16 15:06 changedi 阅读(1183) 评论(0)  编辑  收藏 所属分类: 算法


只有注册用户登录后才能发表评论。


网站导航: