算法分析与设计2004春.课件.第03讲

《算法分析与设计2004春.课件.第03讲》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Lecture3.Dynamicprogramming（continue）•Longestcommonsubsequence•Printingneatly•Editdistance•Optimalbinarysearchtree•技巧：Memoization[备忘录法]清华大学宋斌恒1动态规划方法回顾•与分治方法有没有共同点？【不同点】•子问题空间？决定复杂性因子之一•子问题的治与合？复杂性因子之二•最优值•最优解清华大学宋斌恒21LongestCommonsubsequence•Background:–Inbioinformatics,itneedsoftentocom

2、paretheDNAoftwoormoredifferentorganisms.–AstrandofDNAconsistsofastringofmoleculescalledbase,wherethepossiblebasesare:•Adenine:腺嘌呤•Guanine:鸟嘌呤•Cytosine:胞核嘧啶,氧氨嘧啶•Thymine:胸腺嘧啶–ADNAcanberepresentedbyastringoverthefiniteset[A,C,G,T]清华大学宋斌恒3LongestCommonsubsequence•TwopossibleDNAstring;–S1=ACC

3、GGTCGAGTGCGCGGAAGCCGGCCGAA–S2=GTCGTTCGGAATCGGCTTGCCGTTG•Ourgoal:Comparethetwostringtodeterminehow“similar”thetwostrandsare.•Issue:Thesimilaritycanbedefinedinmanyways,hereweusethe“longestcommonsubsequence”todescribethesimilarity清华大学宋斌恒42Concepts•Subsequenceandsubstring–Asubstringofastringi

4、sacontinuouspartofthestring–Asubsequenceofastringxisastringywithitselementsinyinthesameorder.清华大学宋斌恒5一般的问题提法•有限字符集Σ、有限数量字符串A属于Σ*•求最大公共子序列•具体参考所附资料《lcs991029.pdf》清华大学宋斌恒63LongestCommonsubsequenceproblem•Giventwosequences–X=–Y=•Findthelongestcommonsubsequence,w

5、hereacommonsubsequenceoftwostringsisanotherstringysuchthatitisasubsequenceofbothofthetwogivenstrings.清华大学宋斌恒7Step1:Analyzingtheproblem•Abrute-forcemethod:–Howmanysubsequencesforstringx?–Checkeachoneisalsoasubsequenceofstringy.–Complexity?清华大学宋斌恒84Theorem15.1OptimalsubstructureofanLCS•LetX

6、=,Y=betwo12m12nsequencesandletZ=beaLCSofX12kandY.–Ifxm=yn,thenzk=xm=ynandZk-1isanLCSofXm-1andYn-1–Ifxm!=yn,thenzk!=xmimpliesthatZkisanLCSofXm-1andYn–Ifxm!=yn,thenzk!=ynandZkisanLCSofXmandYn-1清华大学宋斌恒9ProofofTheorem15.1•Proofof“Ifx=y,thenz=x=yandZisanmnkmnk-1LCSof

7、XandY”m-1n-1–Ifzk!=xmÆwecouldappendxmtoZtoobtainalongercommonstringofXandY,whichisacontradiction,hencewehavezk=xm=ynand–Zk-1isacommonstringofXm-1andYn-1,whichwewillshowitisanLCSofXm-1andYn-1.Ifnot,thereareanothercommonstringwhichislongerthenZk-1andthenweappendyntoit