算法設(shè)計(jì)與分析chap8(dynamic programming2014)

2023/9/23zhengjin,CentralSouthUniversity1DynamicProgramming2023/9/23zhengjin,CentralSouthUniversity22023/9/232DynamicProgramming

動(dòng)態(tài)規(guī)劃(dynamicprogramming)是運(yùn)籌學(xué)的一個(gè)分支，是求解決策過(guò)程(decisionprocess)最優(yōu)化的數(shù)學(xué)方法。20世紀(jì)50年代初美國(guó)數(shù)學(xué)家R.E.Bellman等人提出了著名的最優(yōu)化原理(principleofoptimality)，把多階段過(guò)程轉(zhuǎn)化為一系列單階段問(wèn)題，利用各階段之間的關(guān)系，逐個(gè)求解，創(chuàng)立了解決這類過(guò)程優(yōu)化問(wèn)題的新方法——?jiǎng)討B(tài)規(guī)劃。動(dòng)態(tài)規(guī)劃問(wèn)世以來(lái)，在經(jīng)濟(jì)管理、生產(chǎn)調(diào)度、工程技術(shù)和最優(yōu)控制等方面得到了廣泛的應(yīng)用。例如最短路線、庫(kù)存管理、資源分配、設(shè)備更新、排序、裝載等問(wèn)題。

動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃比分治法進(jìn)出的更早，那時(shí)還沒(méi)有計(jì)算機(jī)，比計(jì)算機(jī)科學(xué)更早，主要用于運(yùn)籌學(xué)。從子問(wèn)題開始做(小問(wèn)題),小問(wèn)題解決了,則大問(wèn)題就能解決(利用小問(wèn)題和大問(wèn)題之間的遞推關(guān)系)分治法也是把大問(wèn)題劃分成子問(wèn)題，分治法邏輯清晰，但需要子問(wèn)題不重疊(或重疊少)。動(dòng)態(tài)規(guī)劃是屬于枚舉方法(把所有的子問(wèn)題都解決),唯一亮點(diǎn)就是把子問(wèn)題的解記下來(lái)(存儲(chǔ)),需要時(shí)讀取(調(diào)用).因此需占用空間。因此要特別考慮空間的占用。分治法與動(dòng)態(tài)規(guī)劃如果子問(wèn)題獨(dú)立，則用分治法比較好。例如，歸并排序如果子問(wèn)題重疊多，則用動(dòng)態(tài)規(guī)劃比較好。例如:多段圖問(wèn)題如果子問(wèn)題獨(dú)立，則用分治法比較好。例如，歸并排序如果子問(wèn)題獨(dú)立，則用分治法比較好。例如，歸并排序如果子問(wèn)題獨(dú)立，則用分治法比較好。例如，歸并排序如果子問(wèn)題重疊多，則用動(dòng)態(tài)規(guī)劃比較好。例如:多段圖問(wèn)題2023/9/23zhengjin,CentralSouthUniversity5Example:Fibonaccinumbers

RecalldefinitionofFibonaccinumbers:f(0)=0f(1)=1f(n)=f(n-1)+f(n-2)ComputingthenthFibonaccinumberrecursively(Top-Down):

f(n)

f(n-1)+f(n-2)f(n-2)+f(n-3)f(n-3)+f(n-4)...2023/9/23zhengjin,CentralSouthUniversity6Top-Down(分治形式:大量重疊現(xiàn)象)F(n){if(n<=1)return1;elsereturnF(n-1)+F(n-2);

}F6F4F5F2F1F0F3F1F2F0F1F3F1F2F0F1F4F3F1F2F0F1F2F1F02023/9/23zhengjin,CentralSouthUniversity7Example:Fibonaccinumbers（自底向上)

Computingthenthfibonaccinumberusingbottom-upiteration:

f(0)=0f(1)=1f(2)=0+1=1f(3)=1+1=2f(4)=1+2=3f(5)=2+3=5…

f(n-2)=f(n-1)=f(n)=f(n-1)+f(n-2)ALGORITHMFib(n)f[0]0,f[1]1fori2tondo

f[i]f[i-1]+f[i-2]returnf[n]extraspace空間換取時(shí)間（時(shí)空權(quán)衡）遞歸算法效率低的主要原因是因?yàn)檫M(jìn)行了大量的重復(fù)計(jì)算。而動(dòng)態(tài)規(guī)劃的基本動(dòng)機(jī)就是充分利用重疊子問(wèn)題(Overlappingsubproblems)。因?yàn)閯?dòng)態(tài)規(guī)劃將以前（子問(wèn)題）計(jì)算過(guò)的結(jié)果都記錄下來(lái)，遇到使用子問(wèn)題結(jié)果的時(shí)候只需查表。動(dòng)態(tài)規(guī)劃是一種用空間換取時(shí)間的方法。動(dòng)態(tài)規(guī)劃常常因?yàn)榭臻g消耗太大而難以實(shí)現(xiàn)。2023/9/23zhengjin,CentralSouthUniversity9Fibonacci(n){if(n<=1)return1last=1nextlast=1fori=2tondoanswer=last+nextlast

nextlast=last

last=answerreturnanswer}此問(wèn)題中，由于該算法只用到最近的兩個(gè)子問(wèn)題的解，因此，只用兩個(gè)變量存儲(chǔ)子問(wèn)題的解2023/9/23zhengjin,CentralSouthUniversity10ExamplesofDynamicProgrammingAlgorithms1.MultistageGraphproblem（多段圖問(wèn)題）2.Floyd’salgorithmsforall-pairsshortestpaths3.Investmentprofitproblem4.LongestpathinDAG（最長(zhǎng)路徑問(wèn)題)5.Editdistance6.Knapsack（背包問(wèn)題)7.Constructinganoptimalbinarysearchtree(最優(yōu)二分檢索樹)

2023/9/23zhengjin,CentralSouthUniversity111.MultistageGraphproblem（多段圖問(wèn)題)

/k/433/practice/5.htm2023/9/23zhengjin,CentralSouthUniversity12COST(4,9)=4,COST(4,10)=2,COST(4,11)=5COST(3，6)＝min{6+COST(4，9)，5+COST(4，10)}＝7COST(3，7)＝min{4+COST(4，9)，3+COST(4，10)}＝5COST(3，8)＝7COST(2，2)=min{4十COST(3，6)，2+COST(3，7)，1+COST(3，8)}=7COST(2，3)＝9COST(2，4)=18COST(2，5)＝15COST(1，1)＝min{9+COST(2，2)，7+COST(2，3)，3+COST(2，4)，2+COST(2，5)}＝162023/9/23zhengjin,CentralSouthUniversity13最優(yōu)子結(jié)構(gòu)性質(zhì)最優(yōu)子結(jié)構(gòu)性質(zhì)：?jiǎn)栴}的最優(yōu)解包含子問(wèn)題的最優(yōu)解2023/9/23zhengjin,CentralSouthUniversity14123456最優(yōu)子結(jié)構(gòu)性質(zhì):214134431246214原問(wèn)題的最優(yōu)解12342141包含子問(wèn)題的最優(yōu)解2023/9/23zhengjin,CentralSouthUniversity15AssemblyLineOptimalScheduling(裝配線最優(yōu)調(diào)度）2023/9/23zhengjin,CentralSouthUniversity16

f*=min(f1[n]+x1,f2[n]+x2);2023/9/23zhengjin,CentralSouthUniversity172.Floyd’sAlgorithm:Allpairsshortestpaths（所有點(diǎn)對(duì)之間的最短路徑）

Allpairsshortestpathsproblem:

Inaweightedgraph,findshortestpathsbetweeneverypairofvertices.Applicableto:undirectedanddirectedweightedgraphs;nonegativeweight.Example:34214161530410630

51004104306510weightmatrixdistancematrixdij(k)

=lengthoftheshortestpathfromitojwitheachvertexnumberednohigherthank.2023/9/23zhengjin,CentralSouthUniversity18距離矩陣Dij0410630

51034214161530410530

510041053065100410430651004105306510節(jié)點(diǎn)間的路徑不包含內(nèi)部節(jié)點(diǎn)允許含節(jié)點(diǎn)1的最短路徑值允許含節(jié)點(diǎn)1，2的最短路徑值允許含節(jié)點(diǎn)1,2,3的最短路徑值允許含節(jié)點(diǎn)1,2,3,4的最短路徑值2023/9/23zhengjin,CentralSouthUniversity19Floyd’sAlgorithmD(k):allow1,2,…,ktobeintermediatevertices.Inthekth

stage：

determinewhethertheintroductionofkasanewintermediatevertexwillbringaboutashorterpathfromitoj.

dij(k)=min{dij(k-1),dik(k-1)+dkj(k-1)}fork

1,dij(0)=wijijkkthstagedij(k-1)dik(k-1)dkj(k-1)2023/9/23zhengjin,CentralSouthUniversity20Floyd’sAlgorithm

DW//isnotnecessaryifWcanbeoverwritten

fork1tondo for

i1ton

do

for

j1tondo

D[i,j]min{D[i,j],D[i,k]+D[k,j]}

return

D

Timeefficiency:O(n3)

2023/9/23zhengjin,CentralSouthUniversity21GeneralComments

Thecrucialstepindesigningadynamicprogrammingalgorithm:Derivingarecurrencerelatingasolutiontotheproblem’scurrentinstancewithsolutionsofitssmaller(andoverlapping)instances.2023/9/23zhengjin,CentralSouthUniversity222023/9/23223.LongestpathinDAG

(有向加權(quán)圖中的最長(zhǎng)路徑)Problem:GivenaweighteddirectedacyclicgraphG=(V,E),anvertexv,whereeachedgeisassignedanintegerweight,findalongestpathingraphG.2023/9/23zhengjin,CentralSouthUniversity232023/9/2323LongestpathinDAGdilg(V):thelongestpathendingwithV.dilg(D),dilg(B),dilg(C)dilg(D)=max{dilg(B)+1,dilg(C)+3}Foranyvertexv,dilg(v)=max(u,v)∈E{dilg(u)+w(u,v)}2023/9/23zhengjin,CentralSouthUniversity242023/9/2324LongestpathinDAGDplongestpath(G)Initializealldilg(.)valuesto0;LetSbethesetofverticeswithindegree=0;（從入度為0的節(jié)點(diǎn)開始算)3.Foreachv∈V-SinTopologicalSortingorderdo(拓?fù)渑判虻捻樞驅(qū)λ泄?jié)點(diǎn)進(jìn)行計(jì)算與處理)

dilg(v)=max(u,v)∈E{dilg(u)+w(u,v)}4.Returnthedilg(.)withmaximumvalue.2023/9/23zhengjin,CentralSouthUniversity2525LongestpathinDAGThealgorithmonlygetthevalueofthelongestpath.Problem:Howtofindsuchpath?Dplongestpath(G)Initializealldilg(.)valuesto0;LetSbethesetofverticeswithindegree=0;Foreachv∈V-SinTopologicalSortingorderdo

dilg(v)=max(u,v)∈E{dilg(u)+w(u,v)4.Returnthedilg(.)withmaximumvalue.2023/9/23zhengjin,CentralSouthUniversity2626LongestpathinDAGDplongestpath(G)Initializealldilg(.)valuesto0;LetSbethesetofverticeswithindegree=0;Foreachv∈V-SinTopologicalSortingorderdo

dilg(v)=max(u,v)∈E{dilg(u)+w(u,v)}let(u,v)betheedgetogetthemaximumvalue;

dad(v)=u;//使dilg(v)達(dá)到最大的那個(gè)節(jié)點(diǎn)u，即為v的父節(jié)點(diǎn)

5.Returnthedilg(.)withmaximumvalue.2023/9/23zhengjin,CentralSouthUniversity272023/9/23274.EditDistance（比對(duì)）

/developerworks/cn/java/j-seqalign/Thedistancebetweenstrings:alignment（比對(duì)）Alignment:awayofwritingthestringsoneabovetheother.

The“－”indicatesa“gap”;（-表示空格）anynumberofthesegapcanbeplacedineitherstring(串中任何地方都可以插入空格).為什么比對(duì)中可以插入空格?比對(duì)主要用于評(píng)價(jià)兩個(gè)串的差別有多大，在生物計(jì)算中，看DNA串有多象，如親子簽定），生物物種不一樣，DNA差別很大，同種的則比較象）ACTACTGGTTCACTA

CTGGTT

這兩個(gè)串,如果一一比對(duì),匹配的很少.但很可能上面少測(cè)了一位,或下面多測(cè)了一位!而實(shí)際上，二者很象，就錯(cuò)了一位。(如果在上面左測(cè)插入一個(gè)空格,則二者相似性很高),所以,允許插入空格.(直觀也是這二者很象!）。-ACTACTGGTTCACTA

CTGGTT基因組數(shù)據(jù)庫(kù)保存了海量的原始數(shù)據(jù)。人類基因本身就有接近30億個(gè)DNA堿基對(duì)。為了查遍所有數(shù)據(jù)并找到其中有意義的關(guān)系，分子生物學(xué)家們?cè)絹?lái)越依賴于高效的計(jì)算機(jī)科學(xué)字符串算法?；蛸Y料—DNA和RNA—鏈?zhǔn)欠Q為核苷酸的小單元組成的序列。為了回答某些重要的研究問(wèn)題，研究人員把基因串看作計(jì)算機(jī)科學(xué)的字符串—也就是說(shuō)，可以忽略基因串的物理和化學(xué)性質(zhì)，而將其想像成字符的序列。注：更多內(nèi)容，請(qǐng)自已上網(wǎng)查詢2023/9/23zhengjin,CentralSouthUniversity302023/9/2330EditDistance（mismatch的位數(shù))Thecostofanalignmentisthenumberofcolumnsinwhichthelettersdiffer.Cost:3Cost:5The

editdistancebetweentwostringsisthecostoftheirbestpossiblealignment（最好的比對(duì)中mismatch位數(shù)最小的）2023/9/23zhengjin,CentralSouthUniversity312023/9/2331EditDistanceProblem:Giventwostrings,howtogettheeditdistance?Strategy1:getallpossiblealignmentsbetweentwostrings;searchthroughallofthemforthebestone.Strategy2:

Dynamicprogramming2023/9/23zhengjin,CentralSouthUniversity322023/9/2332EditDistanceDynamicProgrammingforEditDistanceGiventwostringsx[1..m],y[1..n],findtheEditDistancebetweenxandy：E(m,n).Whatarethesubproblems?Howabouttheeditdistancebetweensomeprefixofstrings（字符串前綴）:EXPONENTIALPOLYNOMIALx[1..i],y[1..j]

subproblemE(i,j)2023/9/23zhengjin,CentralSouthUniversity332023/9/2333EditDistanceSubproblemE(7,5)

subproblemE(i,j):expressE(i,j)intermsofsmallersubproblems2023/9/23zhengjin,CentralSouthUniversity342023/9/2334EditDistance

subproblemE(i,j):expressE(i,j)intermsofsmallersubproblemsWhatdoweknowaboutthebestalignmentbetweenx[1..i],y[1..j]?rightmostcolumn（最右邊那列有4種比對(duì)可能）2023/9/23zhengjin,CentralSouthUniversity352023/9/2335EditDistancerightmostcolumnE(i,j)E(i-1,j)E(i,j)=1+E(i-1,j)RelationshipE(i,j)E(i,j-1)E(i,j)=1+E(i,j-1)RelationshipE(i,j)E(i-1,j-1)E(i,j)=1/0+E(i-1,j-1)Relationship2023/9/23zhengjin,CentralSouthUniversity362023/9/2336EditDistance（遞推關(guān)系式）Ifx[i]=x[j]thendiff(i,j)=0,otherwisediff(i,j)=1.E(0,j)=j.E(i,0)=i.2023/9/23zhengjin,CentralSouthUniversity372023/9/2337EditDistanceTheanswerstoallthesubproblemsE(i,j)formatwo-dimensionaltable（用二維表格記錄所有子問(wèn)題的最優(yōu)解）.2023/9/23zhengjin,CentralSouthUniversity382023/9/2338EditDistanceEditdistanceofEXPONENTIALandPOLYNOMIAL2023/9/23zhengjin,CentralSouthUniversity392023/9/2339EditDistanceDPEditDis(x[1..m],y[1..n])Fori=0tomdo

E(i,0)=i;2.Forj=1tondoE(0,j)=j;//初始化3.Fori=1tomdo//以行序計(jì)算forj=1tondo

E(i,j)=min{E(i-1,j)+1,E(i,j-1)+1,E(i-1,j-1)+diff(i,j)}4.ReturnE(m,n).Runningtime:O(mn)2023/9/23zhengjin,CentralSouthUniversity402023/9/2340EditDistanceEditdistanceofEXPONENTIALandPOLYNOMIAL2023/9/23zhengjin,CentralSouthUniversity412023/9/2341EditDistanceUnderlyingDAGforEXPONENTIALandPOLYNOMIAL2023/9/23zhengjin,CentralSouthUniversity422023/9/2342ThefindingofsubproblemsisanimportantstepinDynamicprogramming.Subproblemschoosing（子問(wèn)題的選取方法）Commonlyusedmethods:Theinputisx1,x2,…,xn.asubproblemisx1,x2,…,xi.Howmanysubproblemsforthiscase?O(n)2023/9/23zhengjin,CentralSouthUniversity432023/9/2343Subproblemschoosing（子問(wèn)題的選取方法）2.Theinputisx1,x2,…,xn,andy1,y2,…,ym.asubproblemisx1,x2,…,xiandy1,…,yj.Howmanysubproblemsforthiscase?O(mn)2023/9/23zhengjin,CentralSouthUniversity442023/9/2344Subproblemschoosing（子問(wèn)題的選取方法）3.Theinputisx1,x2,…,xn.asubproblemisxi,xi+1,…,xj.Howmanysubproblemsforthiscase?O(n2)2023/9/23zhengjin,CentralSouthUniversity455.Knapsack（背包問(wèn)題）Duringarobbery,aburglarfindsmuchmorelootthanhehadexpectedandhastodecidewhattotake.2023/9/23zhengjin,CentralSouthUniversity462023/9/2346KnapsackHisbag(or.knapsack.)willholdatotalweightofatmostWpounds.Therearenitemstopickfrom,ofweightw1,…,wnandvaluev1,…,vn.What'sthemostvaluablecombinationofitemshecanfitintohisbag?2023/9/23zhengjin,CentralSouthUniversity472023/9/2347KnapsackTwoversionsoftheproblemeachitem:unlimitedquantityeachitem:onlyoneKnapsackwithrepetitionKnapsackwithoutrepetitionW=102023/9/23zhengjin,CentralSouthUniversity482023/9/2348Knapsackwithoutrepetition（沒(méi)有重復(fù)的背包問(wèn)題：每種物品都只有一件）Whatarethesubproblems?smallerknapsackcapacitiesw≤Wfeweritems(forinstance,items1,2,…,j,forj≤n).K(j,w)=maximumvalueachievableusingaknapsackofcapacitywanditems1,…,j.2023/9/23zhengjin,CentralSouthUniversity492023/9/2349Knapsackwithoutrepetition

Whatarethesubproblems?

K(i,w)=maximumvalueachievableusingaknapsackofcapacitywanditems1,…,i.

K(n,W)istheanswer.Howtogetsubproblem

K(i,w)intermsofsmallersubproblems?K(i,w)=max{K(i-1,w-wi)+vi,K(i-1,w)}w≥wiK(i,0)=0,K(0,w)=0.w<wiK(i,w)=K(i-1,w)

這個(gè)方程非常重要，基本上所有跟背包相關(guān)的問(wèn)題的方程都是由它衍生出來(lái)的。“將前i件物品放入重量為w的背包中”這個(gè)子問(wèn)題的含義:若只考慮第i件物品的策略（放或不放），那么就可以轉(zhuǎn)化為一個(gè)只牽扯前i-1件物品的問(wèn)題。如果不放第i件物品，那么問(wèn)題就轉(zhuǎn)化為“前i-1件物品放入容量為w的背包中”，價(jià)值