动态规划正确入门的规则-武汉北大青鸟课程讲座

动态规划正确入门的规则-武汉北大青鸟课程讲座

　　动态规划是什么?在运筹学中它属于一个分支，是求解决策过程(decision process)优化的数学方法。是信息学竞赛中选手必须熟练掌握的一种算法,他以其多元性广受出题者的喜爱。

　　问题具体化：有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: }