Change Dir

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

统计

留言簿(18)

积分与排名

“牛”们的博客

各个公司技术

我的链接

淘宝技术

阅读排行榜

评论排行榜

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

动态规划(Dynamic Programming)是用来解决最优化问题的最常用手段,但是很多初级程序员都不是很理解动态规划算法。这里开始做一个系列的问题剖析研究,通过例子来更好的深入理解动态规划方法。计划每周更新一个问题

在进入第一个问题之前,先简单介绍一下动态规划(以下简称DP)。第一次知道动态规划不是在大学的算法课上,就是在读经典的《算法导论》里,动态规划解决的问题主要是最优决策问题,就是说在一个目标问题下,需要一系列的操作决策来达到目标,那么最优化的决策是哪个,就是动态规划解决的问题。而我们一般提到最优化,无非最低成本、最高收益等可以通过定义一个函数来量化的东西。更深入的理解我们可能需要先把动态规划的过程抽象化符号化,但是我个人认为理解到这个层次就进了象牙塔,对于实际解决问题太过深奥晦涩,于是一个总结性的抽象化是:H*=(opt (h [d1,d2,…,dn]∈ Δ))  ,opt是最优函数、h是目标函数、d1-dn是一系列决策、Δ是全局决策空间,那么这个表示的含义就是在所有决策中找到一组最优决策满足目标函数h。动态规划问题的一个通用特点是具备最优子结构和重叠子问题,最优子结构可以这么理解,目标问题是可以拆分的,比如最短路问题中,你要从a到b的最短路径,这个最短路径包含了子路径从a到c的最短……。重叠子问题同样拿最短路问题举例,那就是你要求从a到b的最短路径,那么其中有多重选择,你可以选a到c再从c到b,也可以选a直接到b或者更多,而这些路径选择中,重叠情况不断出现……

具体在动态规划解决问题时的一些表示和说明,我们在描述问题的过程中边描述边解说。

下面举例来剖析求解动态规划问题。

问题1:线性搜索(Linear Search)

描述:一个数组A包含N个元素,每个元素x有权重px,有一个成本函数来计算一种排列的排列成本,线性搜索的目标是做到最小化成本来找出一个数组A的排列。

举例:A={a,b,c},pa=0.2,pb=0.5,pc=0.3;数组A共有6种排列,abc,acb,bac,bca,cab,cba。成本的计算方式是1*c1 + 2*c2 + 3*c3。即对应位置的元素优先级乘位置数,比如对于排列bca来说,成本就是1*pb+2*pc+3*pa=1.7 。

问题规范化和求解:我们首先定义状态S作为备选的元素集合,那么接下来的目标就是要做一系列决策决定哪个元素该摆在哪个位置。DPFE(动态规划方程)可以帮助我们更好的理解这个优化问题,DPFE的基本形式是f(S)=opt d∈D(S){R(S,d) o f(T(S,d))}. 其中S是状态空间的状态,d是一个从决策空间D(S)中选出的决策,R(S,d)是价值函数(reward function或者称为决策成本,也表示为C(d|S)),T(S,d)是下一个状态的状态转移函数,o是一个二元操作符。具体解释一下DPFE中的每个元素的含义,S作为状态,因为动态规划解决的问题是需要一系列决策的,S就是表示到当前决策时的问题状态;D(S)是决策空间,代表从一个状态到另一个状态转移时,可以选择的决策d的集合;f是目标函数,是关于状态S的函数,代表到达状态S所做的所有决策产生的最优利益或者最低成本;价值函数R(S,d)是个从状态S做下一个决策d所带来的收益或成本的计算函数,区别于f,它是一个单步的计算函数;T(S,d)是个转移函数,表示从S做下一个决策d所带来的结果;o作为二元操作符,多数是加法或者乘法及最大最小值等,为了将决策合并起来。因为DPFE是一个递归的形式,所以需要一个base condition作为递归的结束条件。另外DPFE可能会有高阶形式,对于某些复杂问题,形式可能是f(S)=opt d∈D(S){R(S,d) o f(T1(S,d)) o f(T2(S,d))} 这样的二阶形式或者是带有权重的f(S)=opt d∈D(S){R(S,d) o p1*f(T1(S,d)) o p2*f(T2(S,d))} 形式。

回到这个问题,本问题的DPFE 形式为 f(S) = min { C(x|S) + f(S-{x})},其中C(x|S)成本函数已经定义,C(x|S)= (N+1-|S|) * px。于是我们可以递归来描述这个过程了,这里用到一个反向搜索的方法,先从排列的最后开始向前查找。

首先base condition f(φ)=0,就是说空集的成本就是0 。

然后对于单项集合,a作为最后一个元素,f({a}) = min {C(a|{a})+f(φ)} = min {3*0.2+0} = 0.6;

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,b}) = min {C(a|{a,b})+f({b}), C(b|{a,b})+f({a})} = min {2*0.2+1.5, 2*0.5+0.6} = 1.6;

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

所以,最优答案是1.7,并且组合方式是bac。好吧,问题得解了。

换一个解法思路:状态转移图模型(State Transition Graph Model),同DPFE方法一致,只不过状态转移图更直观,状态转移图对每一个状态S当做一个节点,f(S)就是S到达φ的最短路径,之前的标准解法是从后向前的计算思路,而STGM是从前向后的计算思路,形式等价于标准,只不过方程变化一下:f’(S)=min {f’(S’) + C(x|S’)}。其中S’是一个由x决策导致状态S的前置节点,也就是说S’->S (条件是x决策)。并且f’(S)是源节点S*到S的最短路径,最终目标函数是f’(φ),起始状态是 S*={a,b,c}。

所以整个搜索过程如下:

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;

过程已经比较清晰了,更直白的理解就是,倒着数,对于这个集合,排列好后的路径长度是0,有两个已经排列好,剩下放到第一个位置的选择的最小路径,有一个已经排列好,剩下放到前两个的选择的最小路径……有0个已经排列好,剩下放到前3个的选择的最小路径,迭代计算即可。

再换一个思路:阶段决策(Stage Decision),这是个顺序决策过程,分阶段,第一阶段决定放在第一个位置的元素是什么,依次类推。方程转变为:f(k,S)=min{C(x|k,S)+f(k+1,S-{x})}。其中k是阶段标识,base condition为f(N+1 , φ)=0,目标函数是f(1,A),因为k=N+1-|S|,所以成本函数C(x|k,S)=(N+1-|S|)*px=k * px。

整个过程如下:

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;

反向代入后,得解 f(1,{a,b,c}) = 1.7 。

最后再介绍一种图论的思想:如果把S定义为从源头一直到决策d的一系列决策集(d1,d2,…,di-1),S作为一个图的节点的话,图的每个节点都表示了从初始状态φ到S的一个路径(Path-States)。那么方程变为:f(S) = min x∉S {C(x|S) + f(S ∪ {x})}。这个其实是等同于状态转移图的另一种表示。

至此,已经通过第一个简单的问题,得到了4种(其实是2种,一种直观的,一种图论的)描述动态规划问题求解策略的方法了,分别是Stage Decision 和 State Transition Graph Model。未来会有更多的动态规划问题通过这些方法来求解。

最后再附上这个问题的一个函数代码:不出意外,所有的过程都以Java代码来实现描述。

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 阅读(3125) 评论(10)  编辑  收藏 所属分类: 算法

评论

# re: 深入理解动态规划的一系列问题(1) 2014-03-10 12:34 鹏达锁业

给力支持博主分享啊。。。。欢迎回访

  回复  更多评论   

# re: 深入理解动态规划的一系列问题(1) 2014-03-10 15:00 夏日博客

你的博客流量挺大。。。  回复  更多评论   

# re: 深入理解动态规划的一系列问题(1) 2014-03-10 15:03 万利锁业

支持博主分享啊  回复  更多评论   

# re: 深入理解动态规划的一系列问题(1) 2014-03-11 10:45 万利锁业

支持博主分享啊  回复  更多评论   

# re: 深入理解动态规划的一系列问题(1) 2014-03-12 09:47 魏五锁业

期待更新啊博主  回复  更多评论   

# re: 深入理解动态规划的一系列问题(1) 2014-03-12 10:54 万利锁业

谢谢博主分享 啊  回复  更多评论   

# re: 深入理解动态规划的一系列问题(1) 2014-03-12 17:51 中文


不明觉历啊  回复  更多评论   

# re: 深入理解动态规划的一系列问题(1) 2014-03-12 17:52 中文

不明觉历啊。。。。  回复  更多评论   

# 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虽然有依赖,但是这种依赖还涉及到一个上步选择的问题,即不仅仅是上一步,而是之前的某个组合。  回复  更多评论   


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


网站导航: