首页 >  JAVA频道 > 技术分享 > 

深入理解动态规划的问题

深入理解动态规划的问题

作者:yjl 来源:华育国际 时间:2015-02-27 访问次数:1459
Optimal Alphabetic Radix-Code Tree Problem(ARC)问题是这样一个问题,给定一系列节点,每个节点有构建成本,然后构建一棵树,树的成本计算方式是这样的,如果树的节点是叶子节点,那么它的成本就是它自己,否则如果是非叶节点,那么这棵树的成本等于

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: }