国外算法设计与分析教学课件

1、Dynamic ProgrammingCopyright Li Zimao 2007-2008-1 SCUEC第1页，共26页。Expected OutcomesStudents should be able toWrite down the four steps of dynamic programmingCompute a Fibonacci number and the binomial coefficients by dynamic programming Compute the longest common subsequence and the shortest common su

2、persequence of two given sequences by dynamic programmingSolve the invest problem by dynamic programmingCopyright Li Zimao 2007-2008-1 SCUEC第2页，共26页。Dynamic Programming Dynamic Programming is a general algorithm design technique. Invented by American mathematician Richard Bellman in the 1950s to sol

3、ve optimization problemsMain idea: solve several smaller (overlapping) subproblemsrecord solutions in a table so that each subproblem is only solved oncefinal state of the table will be (or contain) solutionDynamic programming vs. divide-and-conquerpartition a problem into overlapping subproblems an

4、d independent onesstore and not store solutions to subproblemsCopyright Li Zimao 2007-2008-1 SCUEC第3页，共26页。Frame of Dynamic ProgrammingProblem solvedSolution can be expressed in a recursive waySub-problems occur repeatedlySubsequence of optimal solution is an optimal solution to the sub-problemFrame

5、Characterize the structure of an optimal solutionRecursively define the value of an optimal solutionCompute the value of an optimal solution in a bottom-up fashionConstruct an optimal solution from computed informationCopyright Li Zimao 2007-2008-1 SCUEC第4页，共26页。Three basic componentsThe development

6、 of a dynamic programming algorithm has three basic components:A recurrence relation (for defining the value/cost of an optimal solution);A tabular computation (for computing the value of an optimal solution);A backtracing procedure (for delivering an optimal solution). Copyright Li Zimao 2007-2008-

7、1 SCUEC第5页，共26页。Example: Fibonacci numbers Recall definition of Fibonacci numbers:f(0) = 0f(1) = 1f(n) = f(n-1) + f(n-2) Computing the nth Fibonacci number recursively (top-down): f(n) f(n-1) + f(n-2)f(n-2) + f(n-3) f(n-3) + f(n-4) .Copyright Li Zimao 2007-2008-1 SCUEC第6页，共26页。Example: Fibonacci num

8、bers Computing the nth fibonacci number using bottom-up iteration: f(0) = 0 f(1) = 1 f(2) = 0+1 = 1 f(3) = 1+1 = 2 f(4) = 1+2 = 3 f(5) = 2+3 = 5 f(n-2) = f(n-1) = f(n) = f(n-1) + f(n-2)ALGORITHM Fib(n)F0 0, F1 1for i2 to n doFi Fi-1 + Fi-2return Fnextra spaceCopyright Li Zimao 2007-2008-1 SCUEC第7页，共

9、26页。Examples of Dynamic ProgrammingComputing binomial coefficientsCompute the longest common subsequenceCompute the shortest common supersquenceWarshalls algorithm for transitive closureFloyds algorithms for all-pairs shortest paths Some instances of difficult discrete optimization problems:knapsack

10、Copyright Li Zimao 2007-2008-1 SCUEC第8页，共26页。Computing Binomial CoefficientsA binomial coefficient, denoted C(n, k), is the number of combinations of k elements from an n-element set (0 k n).Recurrence relation (a problem 2 overlapping subproblems)C(n, k) = C(n-1, k-1) + C(n-1, k), for n k 0, and C(

11、n, 0) = C(n, n) = 1Dynamic programming solution:Record the values of the binomial coefficients in a table of n+1 rows and k+1 columns, numbered from 0 to n and 0 to k respectively.11 11 2 11 3 3 11 4 6 4 11 5 10 10 5 1 Copyright Li Zimao 2007-2008-1 SCUEC第9页，共26页。Dynamic Binomial Coefficient Algorit

12、hmfor i = 0 to n dofor j = 0 to minimum( i, k ) doif j = 0 or j = i thenBiCoeff i, j = 1elseBiCoeff i, j = BiCoeff i-1, j-1 + BiCoeff i-1, j end ifend for jend for iCopyright Li Zimao 2007-2008-1 SCUEC第10页，共26页。Longest Common Subsequence (LCS)A subsequence of a sequence S is obtained by deleting zer

13、o or more symbols from S. For example, the following are all subsequences of “president”: pred, sdn, predent.The longest common subsequence problem is to find a maximum length common subsequence between two sequences.Copyright Li Zimao 2007-2008-1 SCUEC第11页，共26页。LCSFor instance, Sequence 1: presiden

14、t Sequence 2: providence Its LCS is priden.presidentprovidenceCopyright Li Zimao 2007-2008-1 SCUEC第12页，共26页。LCSAnother example: Sequence 1: algorithm Sequence 2: alignmentOne of its LCS is algm.a l g o r i t h ma l i g n m e n tCopyright Li Zimao 2007-2008-1 SCUEC第13页，共26页。How to compute LCS?Let A=a

15、1a2am and B=b1b2bn .len(i, j): the length of an LCS between a1a2ai and b1b2bjWith proper initializations, len(i, j) can be computed as follows.Copyright Li Zimao 2007-2008-1 SCUEC第14页，共26页。Copyright Li Zimao 2007-2008-1 SCUEC第15页，共26页。Running time and memory: O(mn) and O(mn).Copyright Li Zimao 2007-

16、2008-1 SCUEC第16页，共26页。The backtracing algorithmCopyright Li Zimao 2007-2008-1 SCUEC第17页，共26页。Copyright Li Zimao 2007-2008-1 SCUEC第18页，共26页。Shortest common super-sequenceDefinition: Let X and Y be two sequences. A sequence Z is a super-sequence of X and Y if both X and Y are subsequence of Z.Shortest

17、 common super-sequence problem:Input: two sequences X and Y.Output: a shortest common super-sequence of X and Y.Example: X=abc and Y=abb. Both abbc and abcb are the shortest common super-sequences for X and Y.Copyright Li Zimao 2007-2008-1 SCUEC第19页，共26页。Recursive Equation:Let leni,j be the length o

18、f an SCS of X1.i and Y1.j.leni,j can be computed as follows: j if i=0, i if j=0,leni,j = leni-1,j-1+1 if i, j0 and xi=yj, minleni,j-1+1, leni-1,j+1 if i, j0 and xiyj. How to compute SCS?Copyright Li Zimao 2007-2008-1 SCUEC第20页，共26页。Solution: ABDCABDABCopyright Li Zimao 2007-2008-1 SCUEC第21页，共26页。Exe

19、rciseConsider the algorithm for LCS as an example, write down the SCS algorithm and analyze it.Copyright Li Zimao 2007-2008-1 SCUEC第22页，共26页。Suppose there are m dollars，and n products. Let fi(x) be the profit of investing x dollars to product i. How to arrange the investment such that the total profit f1(x1) + f2(x2) + + fn(xn) is maximized.Instance：5 thousand dollars，4 products xf1(x)f2(x)f3(x)f4(x)00000111022021251021313103022414153223515204024An interesting example: Investment ProblemCopyright Li Zimao 2007-2008-1 SCUEC第23页，共26页。xF1(