算法設計與分析動態(tài)規(guī)劃

主要內(nèi)容動態(tài)規(guī)劃的基本性質(zhì)和步驟最大子數(shù)組問題0-1背包問題旅行商問題最長公共子序列狀態(tài)壓縮動態(tài)規(guī)劃1引例：斐波那契數(shù)遞歸形式的算法：procedurefib(n)ifn=1orn=2thenreturn1elsereturnfib(n-1)+fib(n-2)1引例：斐波那契數(shù)存在大量重復計算當n=100時，用遞歸求解的時間T(100)≈3.53×1020,若每秒計算108次，需111,935年1解決方法從第1個元素開始計算，從而消除重復計算f1←1f2←1fori←3tonresult←f1+f2f1←f2f2←resultendforreturnresult1基本性質(zhì)和分治類似動態(tài)規(guī)劃也是將原問題分解為子問題求解和分治不同不是通過遞歸的方式，而是自低向上的求解問題1基本性質(zhì)動態(tài)規(guī)劃和分治的比較需要列出遞歸式1機器人行走1機器人行走分治1機器人行走分治需要計算多少次？55次

1機器人行走動態(tài)規(guī)劃自底向上的計算：12次1基本性質(zhì)動態(tài)規(guī)劃適用的場景子問題并不獨立，即子問題是可能重復的主要用于優(yōu)化問題（求最優(yōu)解），且問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)1最優(yōu)子結(jié)構(gòu)性質(zhì)最短路徑問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)（替換法證明）1最優(yōu)子結(jié)構(gòu)性質(zhì)最長路徑問題不具有最優(yōu)子結(jié)構(gòu)性質(zhì)1基本步驟定義子問題，并分析最優(yōu)解的結(jié)構(gòu)特征分治通常是將原問題對半分，而動態(tài)規(guī)劃是將n規(guī)模的問題分解成n?1規(guī)模的問題找出最優(yōu)解對應的最優(yōu)值，并遞歸地定義最優(yōu)值以自底向上的方式計算出最優(yōu)值根據(jù)計算最優(yōu)值時得到的信息，構(gòu)造最優(yōu)解2最大子數(shù)組問題子問題的定義：基于分治的方法2最大子數(shù)組問題遞歸定義最優(yōu)值是否存在重復計算？2最大子數(shù)組問題動態(tài)規(guī)劃：n-1為原問題n的子問題求解改為：包含數(shù)組最后一個元素的最大子數(shù)組2最大子數(shù)組問題動態(tài)規(guī)劃：最大子數(shù)組問題最優(yōu)解的結(jié)構(gòu)特征找出最優(yōu)解對應的最優(yōu)值，并遞歸地定義最優(yōu)值2最大子數(shù)組問題動態(tài)規(guī)劃：自底向上的求解最優(yōu)值2最大子數(shù)組問題動態(tài)規(guī)劃：根據(jù)b值矩陣得出最優(yōu)解3

0-1背包問題3

0-1背包問題分析0-1背包問題最優(yōu)解的結(jié)構(gòu)特征一種情況是第n個物品不包括在最優(yōu)解里第二種情況是第n個物品包括在最優(yōu)解里3

0-1背包問題找出0-1背包問題最優(yōu)解對應的最優(yōu)值，并遞歸地定義最優(yōu)值3

0-1背包問題自底向上的求解最優(yōu)值3

0-1背包問題自底向上的求解最優(yōu)值3

0-1背包問題根據(jù)m值矩陣得出最優(yōu)解算法復雜度分析：從m(i，j)的遞歸式容易看出，算法需要O(nc)計算時間。當背包容量c很大時，算法需要的計算時間較多。例如，當c>2n時，算法需要Ω(n2n)計算時間。4旅行商問題4旅行商問題旅行商問題最優(yōu)解的結(jié)構(gòu)特征最優(yōu)子結(jié)構(gòu)性質(zhì)旅行商問題的子問題是顯然重疊的假設路徑c1...cn?1cn

是城市{c1,c2,...,cn?1,cn}的最短路徑，取這個路徑子路徑c1...cn-1

必然是城市{c1,c2,...,cn-1}中從c1

到cn-1

經(jīng)過其他城市一次且僅一次的最短路徑。如下兩個路徑c1c2c3c4...cn

和c1c3c2c4...cn

都具有相同的子路徑c4...cn?1cn。4旅行商問題旅行商問題最優(yōu)解對應的最優(yōu)值，并遞歸地定義最優(yōu)值4旅行商問題旅行商問題最優(yōu)解對應的最優(yōu)值，并遞歸地定義最優(yōu)值4旅行商問題自底向上求解最優(yōu)值4旅行商問題4旅行商問題4旅行商問題自底向上求解最優(yōu)值在此算法中，因TSP(c1,C,ci)中的c1

可忽略，我們用一個二維數(shù)組TP[C][ci]存儲TSP(c1,C,ci)的值4旅行商問題構(gòu)造最優(yōu)解While循環(huán)(語句4-18)依次往最短路徑添加城市，每次添加實際上就是找出下一層哪一個TSP和當前城市c?形成了最短回路5最長公共子序列若給定序列X={x1,x2,…,xm}，則另一序列Z={z1,z2,…,zk}，是X的子序列是指存在一個嚴格遞增下標序列{i1,i2,…,ik}使得對于所有j=1,2,…,k有：zj=xij。例如，序列Z={B，C，D，B}是序列X={A，B，C，B，D，A，B}的子序列，相應的遞增下標序列為{2，3，5，7}。給定2個序列X和Y，當另一序列Z既是X的子序列又是Y的子序列時，稱Z是序列X和Y的公共子序列。給定2個序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最長公共子序列。

窮舉法(Brute-Force)：找出X字符串所有可能的子序列(2n)；對于X的每一個子序列，判斷其是否是Y的一個子序列,需要的時間為Θ(m);求max;總的時間為Θ(m2n).5最長公共子序列5最長公共子序列的結(jié)構(gòu)設序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}的最長公共子序列為Z={z1,z2,…,zk}，則5子問題的遞歸結(jié)構(gòu)415自底向上計算c[i][j]

兩個序列分別為X=<A,B,C,B,D,A,B>和Y=<B,D,C,A,B,A>j0123456iyiBDCABA0xi1A2B3C4B5D6A7B00000000000000443221433221332221332211222211221111111000425計算最優(yōu)值由于在所考慮的子問題空間中，總共有θ(mn)個不同的子問題，因此，用動態(tài)規(guī)劃算法自底向上地計算最優(yōu)值能提高算法的效率。435構(gòu)造最長子序列6狀態(tài)壓縮動態(tài)規(guī)劃集合狀態(tài)壓縮用二進制表示集合，之后用整型表示二進制，如旅行商問題中的TP數(shù)組空間狀態(tài)壓縮自底向上的方法求解最優(yōu)值的過程中，壓縮最優(yōu)值的存儲空間6集合狀態(tài)壓縮整數(shù)的一些基本的位操作6集合狀態(tài)壓縮旅行商問題的狀態(tài)壓縮TP[C][ci]數(shù)組通過狀態(tài)壓縮可以用二維數(shù)組TP[m][n?1]表示，其中m=2n?1

?1那么如何依次計算這個TP表?按行依次計算6集合狀態(tài)壓縮旅行商問題的狀態(tài)壓縮TP[C][ci]數(shù)組通過狀態(tài)壓縮可以用二維數(shù)組TP[m][n?1]表示，其中m=2n?1

?1那么如何依次計算這個TP表?按行依次計算6集合狀態(tài)壓縮旅行商問題的狀態(tài)壓縮需要判斷一下:

j所代表的城市集合C是否包含了i所代表的城市，如果不包含，就無需做任何處理，如包含，則依次比較j集合所有下一層的TP值6空間狀態(tài)壓縮采用一種維度更低的數(shù)據(jù)結(jié)構(gòu)來存儲高維度的數(shù)據(jù)結(jié)構(gòu)如在機器人行走的例子中