资源描述：
《算法分析与设计2003秋.课件.第03讲》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、Lecture3.Dynamicprogramming（continue）•Longestcommonsubsequence•Printingneatly•Editdistance•Optimalbinarysearchtree•技巧：Memoization[备忘录法]1动态规划方法回顾•与分治方法有没有共同点？【不同点】•子问题空间？决定复杂性因子之一•子问题的治与合？复杂性因子之二•最优值•最优解21LongestCommonsubsequence•Background:–Inbioinformatics,itneedsoftentocomparetheDNA
2、oftwoormoredifferentorganisms.–AstrandofDNAconsistsofastringofmoleculescalledbase,wherethepossiblebasesare:•Adenine:腺嘌呤•Guanine:鸟嘌呤•Cytosine:胞核嘧啶,氧氨嘧啶•Thymine:胸腺嘧啶–ADNAcanberepresentedbyastringoverthefiniteset[A,C,G,T]3LongestCommonsubsequence•TwopossibleDNAstring;–S1=ACCGGTCGAGTGCGCG
3、GAAGCCGGCCGAA–S2=GTCGTTCGGAATCGGCTTGCCGTTG•Ourgoal:Comparethetwostringtodeterminehow“similar”thetwostrandsare.•Issue:Thesimilaritycanbedefinedinmanyways,hereweusethe“longestcommonsubsequence”todescribethesimilarity42Concepts•Subsequenceandsubstring–Asubstringofastringisacontinuouspart
4、ofthestring–Asubsequenceofastringxisastringywithitselementsinyinthesameorder.5一般的问题提法•有限字符集Σ、有限数量字符串A属于A*•求最大公共子序列•具体参考所附资料《lcs991029.pdf》63LongestCommonsubsequenceproblem•Giventwosequences–X=–Y=•Findthelongestcommonsubsequence,whereacommonsubsequenceoftw
5、ostringsisanotherstringysuchthatitisasubsequenceofbothofthetwogivenstrings.7Step1:Characteringthealongestcommonsubsequence•Abrute-forcemethod:–Howmanysubsequencesforstringx?–Checkeachoneisalsoasubsequenceofstringy.–Complexity?84Theorem15.1OptimalsubstructureofanLCS•LetX=beY=<
6、y,y,…,y>two12m12nsequencesandletZ=beanyLCSof12kXandY.–Ifxm=yn,thenzk=xm=ynandZk-1isanLCSofXm-1andYn-1–Ifxm!=yn,thenzk!=xmimpliesthatZkisanLCSofXm-1andYn–Ifxm!=yn,thenzk!=ynandZkisanLCSofXmandYn-19ProofofTheorem15.1•Proofof“Ifx=y,thenz=x=yandZisanmnkmnk-1LCSofXandY”m-1n-1–Ifzk
7、!=xmÆwecouldappendxmtoZtoobtainalongercommonstringofXandY,whichisacontradiction,hencewehavezk=xm=ynand–Zk-1isacommonstringofXm-1andYn-1,whichwewillshowitisanLCSofXm-1andYn-1.Ifnot,thereareanothercommonstringwhichislongerthenZk-1andthenweappendyntoit,whichisacontradiction.105Continuing
8、proof
