算法设计与分析chap8(dynamic programming2014)

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

动态规划(dynamicprogramming)是运筹学的一个分支，是求解决策过程(decisionprocess)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人提出了著名的最优化原理(principleofoptimality)，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题。

动态规划动态规划比分治法进出的更早，那时还没有计算机，比计算机科学更早，主要用于运筹学。从子问题开始做(小问题),小问题解决了,则大问题就能解决(利用小问题和大问题之间的递推关系)分治法也是把大问题划分成子问题，分治法逻辑清晰，但需要子问题不重叠(或重叠少)。动态规划是属于枚举方法(把所有的子问题都解决),唯一亮点就是把子问题的解记下来(存储),需要时读取(调用).因此需占用空间。因此要特别考虑空间的占用。分治法与动态规划如果子问题独立，则用分治法比较好。例如，归并排序如果子问题重叠多，则用动态规划比较好。例如:多段图问题如果子问题独立，则用分治法比较好。例如，归并排序如果子问题独立，则用分治法比较好。例如，归并排序如果子问题独立，则用分治法比较好。例如，归并排序如果子问题重叠多，则用动态规划比较好。例如:多段图问题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(分治形式:大量重叠现象)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空间换取时间（时空权衡）递归算法效率低的主要原因是因为进行了大量的重复计算。而动态规划的基本动机就是充分利用重叠子问题(Overlappingsubproblems)。因为动态规划将以前（子问题）计算过的结果都记录下来，遇到使用子问题结果的时候只需查表。动态规划是一种用空间换取时间的方法。动态规划常常因为空间消耗太大而难以实现。2023/9/23zhengjin,CentralSouthUniversity9Fibonacci(n){if(n<=1)return1last=1nextlast=1fori=2tondoanswer=last+nextlast

nextlast=last

last=answerreturnanswer}此问题中，由于该算法只用到最近的两个子问题的解，因此，只用两个变量存储子问题的解2023/9/23zhengjin,CentralSouthUniversity10ExamplesofDynamicProgrammingAlgorithms1.MultistageGraphproblem（多段图问题）2.Floyd’salgorithmsforall-pairsshortestpaths3.Investmentprofitproblem4.LongestpathinDAG（最长路径问题)5.Editdistance6.Knapsack（背包问题)7.Constructinganoptimalbinarysearchtree(最优二分检索树)

2023/9/23zhengjin,CentralSouthUniversity111.MultistageGraphproblem（多段图问题)

/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最优子结构性质最优子结构性质：问题的最优解包含子问题的最优解2023/9/23zhengjin,CentralSouthUniversity14123456最优子结构性质:214134431246214原问题的最优解12342141包含子问题的最优解2023/9/23zhengjin,CentralSouthUniversity15AssemblyLineOptimalScheduling(装配线最优调度）2023/9/23zhengjin,CentralSouthUniversity16

f*=min(f1[n]+x1,f2[n]+x2);2023/9/23zhengjin,CentralSouthUniversity172.Floyd’sAlgorithm:Allpairsshortestpaths（所有点对之间的最短路径）

Allpairsshortestpathsproblem:

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

51004104306510weightmatrixdistancematrixdij(k)

=lengthoftheshortestpathfromitojwitheachvertexnumberednohigherthank.2023/9/23zhengjin,CentralSouthUniversity18距离矩阵Dij0410630

51034214161530410530

510041053065100410430651004105306510节点间的路径不包含内部节点允许含节点1的最短路径值允许含节点1，2的最短路径值允许含节点1,2,3的最短路径值允许含节点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

(有向加权图中的最长路径)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的节点开始算)3.Foreachv∈V-SinTopologicalSortingorderdo(拓扑排序的顺序对所有节点进行计算与处理)

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)达到最大的那个节点u，即为v的父节点

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

/developerworks/cn/java/j-seqalign/Thedistancebetweenstrings:alignment（比对）Alignment:awayofwritingthestringsoneabovetheother.

The“－”indicatesa“gap”;（-表示空格）anynumberofthesegapcanbeplacedineitherstring(串中任何地方都可以插入空格).为什么比对中可以插入空格?比对主要用于评价两个串的差别有多大，在生物计算中，看DNA串有多象，如亲子签定），生物物种不一样，DNA差别很大，同种的则比较象）ACTACTGGTTCACTA

CTGGTT

这两个串,如果一一比对,匹配的很少.但很可能上面少测了一位,或下面多测了一位!而实际上，二者很象，就错了一位。(如果在上面左测插入一个空格,则二者相似性很高),所以,允许插入空格.(直观也是这二者很象!）。-ACTACTGGTTCACTA

CTGGTT基因组数据库保存了海量的原始数据。人类基因本身就有接近30亿个DNA碱基对。为了查遍所有数据并找到其中有意义的关系，分子生物学家们越来越依赖于高效的计算机科学字符串算法。基因资料—DNA和RNA—链是称为核苷酸的小单元组成的序列。为了回答某些重要的研究问题，研究人员把基因串看作计算机科学的字符串—也就是说，可以忽略基因串的物理和化学性质，而将其想像成字符的序列。注：更多内容，请自已上网查询2023/9/23zhengjin,CentralSouthUniversity302023/9/2330EditDistance（mismatch的位数)Thecostofanalignmentisthenumberofcolumnsinwhichthelettersdiffer.Cost:3Cost:5The

editdistancebetweentwostringsisthecostoftheirbestpossiblealignment（最好的比对中mismatch位数最小的）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种比对可能）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（递推关系式）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（用二维表格记录所有子问题的最优解）.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//以行序计算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（子问题的选取方法）Commonlyusedmethods:Theinputisx1,x2,…,xn.asubproblemisx1,x2,…,xi.Howmanysubproblemsforthiscase?O(n)2023/9/23zhengjin,CentralSouthUniversity432023/9/2343Subproblemschoosing（子问题的选取方法）2.Theinputisx1,x2,…,xn,andy1,y2,…,ym.asubproblemisx1,x2,…,xiandy1,…,yj.Howmanysubproblemsforthiscase?O(mn)2023/9/23zhengjin,CentralSouthUniversity442023/9/2344Subproblemschoosing（子问题的选取方法）3.Theinputisx1,x2,…,xn.asubproblemisxi,xi+1,…,xj.Howmanysubproblemsforthiscase?O(n2)2023/9/23zhengjin,CentralSouthUniversity455.Knapsack（背包问题）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（没有重复的背包问题：每种物品都只有一件）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)

这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的。“将前i件物品放入重量为w的背包中”这个子问题的含义:若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为w的背包中”，价值