# Change Dir

• 随笔 - 222
• 文章 - 0
• 评论 - 182
• 引用 - 0

• 积分 - 416729
• 排名 - 133

## 深入理解动态规划的一系列问题（1）

b作为最后一个元素，f({b}) = min {C(b|{b})+f(φ)} = min {3*0.5+0} = 1.5；

c作为最后一个元素，f({c}) = min {C(b|{b})+f(φ)} = min {3*0.3+0} = 0.9；

f({a,c}) = min {C(a|{a,c})+f({c}), C(c|{a,c})+f({a})} = min {2*0.2+0.9, 2*0.3+0.6} = 1.2；

f({b,c}) = min {C(b|{b,c})+f({c}), C(c|{b,c})+f({b})} = min {2*0.5+0.9, 2*0.3+1.5} = 1.9；

f({a,b,c}) = min {C(a|{a,b,c})+f({b,c}), C(b|{a,b,c})+f({a,c}), C(c|{a,b,c})+f({a,b})} = min {1*0.2+1.9, 1*0.5+1.2, 1*0.3+1.6} = 1.7

f’({a,b,c})=0；

f’({b,c}) = min {f’({a,b,c})+C(a|{a,b,c}) } = min{0+0.2} = 0.2；

f’({a,c}) = min {f’({a,b,c})+C(b|{a,b,c}) } = min{0+0.5} = 0.5；

f’({a,b}) = min {f’({a,b,c})+C(c|{a,b,c}) } = min{0+0.3} = 0.3；

f’({c}) = min {f’({b,c})+C(b|{b,c}), f’({a,c})+C(a|{a,c}) } = min{0.2+2*0.5,0.5+2*0.2} = 0.9；

f’({b}) = min {f’({a,b})+C(a|{a,b}), f’({b,c})+C(c|{b,c}) } = min{0.3+2*0.2,0.2+2*0.3} = 0.7；

f’({a}) = min {f’({a,b})+C(b|{a,b}), f’({a,c})+C(c|{a,c}) } = min{0.3+2*0.5,0.5+2*0.3} = 1.1；

f’(φ) = min {f’({a})+C(a|{a}), f’({b})+C(b|{b}), f’({c})+C(c|{c}) } = min{1.1+3*0.2, 0.7+3*0.5, 0.9+3*0.3} = 1.7；

f(1,{a,b,c}) = min {C(a|1,{a,b,c})+f(2,{b,c}), C(b|1,{a,b,c})+f(2,{a,c}), C(c|1,{a,b,c})+f(2,{a,b})}

= min {3*0.2+1.1, 3*0.5+0.7, 3*0.3+0.9} = 1.7；

f(2,{b,c}) = min {C(b|2,{b,c})+f(3,{c}), C(c|2,{b,c})+f(3,{b})} = min{2*0.5+0.3,2*0.3+0.5}=1.1；

f(2,{a,c}) = min {C(a|2,{a,c})+f(3,{c}), C(c|2,{a,c})+f(3,{a})} = min{2*0.2+0.3,2*0.3+0.2}=0.7；

f(2,{a,b}) = min {C(a|2,{a,b})+f(3,{b}), C(b|2,{a,b})+f(3,{a})} = min{2*0.2+0.5,2*0.5+0.2}=0.9；

f(3,{a}) = min {C(a|3,{a})+f(4,φ)} = min{0.2+0} = 0.2；

f(3,{b}) = min {C(b|3,{b})+f(4,φ)} = min{0.5+0} = 0.5；

f(3,{c}) = min {C(c|3,{c})+f(4,φ)} = min{0.3+0} = 0.3；

f(4,φ) = 0；

source code:

   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.HashMap;
  19: import java.util.HashSet;
  20: import java.util.Map;
  21: import java.util.Set;
  22:
  23: public class LinearSearch {
  24:
  25:     int N = 3;
  26:     Map<String,Double> map = new HashMap<String,Double>();
  27:
  28:     public LinearSearch(){
  29:         map.put("a", 0.2);
  30:         map.put("b", 0.5);
  31:         map.put("c", 0.3);
  32:     }
  33:     public void dp() {
  34:         Set<String> A = new HashSet<String>();
  35:         for (String k : map.keySet()) {
  36:             A.add(k);
  37:         }
  38:         System.out.println(f(A));
  39:     }
  40:
  41:     private double cost(String x, Set<String> A) {
  42:         return map.get(x) * (N + 1 - A.size());
  43:     }
  44:
  45:     private double f(Set<String> A) {
  46:         double fx = Double.MAX_VALUE;
  47:         if(A.isEmpty()){
  48:             fx = 0;
  49:         }
  50:         else{
  51:             for(String key : A){
  52:                 Set<String> A1 = new HashSet<String>();
  53:                 for(String ik : A){
  54:                     A1.add(ik);
  55:                 }
  56:                 A1.remove(key);
  57:                 double tmp = cost(key,A) + f(A1);
  58:                 if(tmp<fx)
  59:                     fx = tmp;
  60:             }
  61:         }
  62:         return fx;
  63:     }
  64:
  65:     public static void main(String[] args) {
  66:         LinearSearch ls = new LinearSearch();
  67:         ls.dp();
  68:     }
  69:
  70: }

posted on 2014-03-10 11:23 changedi 阅读(3133) 评论(10)  编辑  收藏 所属分类: 算法

### 评论

回复  更多评论

#### #re: 深入理解动态规划的一系列问题（1）[未登录] 2014-04-05 10:51 Calvin

CD，你好。很感谢你发表这样一系列的文章。我对动态规划很感兴趣。对你的第一篇帖子，我有以下问题，希望得到你的回答。谢谢。

1. 文中的例程是用递归来做的。如果不用递归，而用递推，则应该把集合当前的元素和对应的目标最值的一个映射存下来。例如({a,b,c}, 0), ({b,c}, 0.2), ({a,c}, 0.5)...不知这在实现时有什么有效的办法做到吗？如果用每个元素的hashcode来运算，是不是会产生重复的值？

2. 这类型的问题是不是都可以用贪心算法来解决？  回复  更多评论

#### #re: 深入理解动态规划的一系列问题（1） 2014-04-08 10:21 changedi

@Calvin
1，这个具体实现，像算导里有介绍备忘录的方法来实现，其实DP的问题就是因为不是一个顺序下来就能完成的求解，所以需要某种方式来记录当前状态之前的所有状态，这个根据复杂程度不同有不同的方式，一般的做法就是一个多维数组来记录即可。hashcode重复与否那是hash算法的事了，就是另一回事了。
2，以我的理解，我认为不都是，可能在计算理论层面它们最终是能彼此规约的，我暂时没法证明，但是就一般思路来讲，DP和贪心面对的最优化问题不同，贪心的思路是一条路走到底，下一步依赖上一步，而DP虽然有依赖，但是这种依赖还涉及到一个上步选择的问题，即不仅仅是上一步，而是之前的某个组合。  回复  更多评论

 只有注册用户登录后才能发表评论。 网站导航: 相关文章: