動態規劃（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: }