【文章內(nèi)容簡介】 y1, … , yn1, xm， 則 LCSXY = LCSXm1Yn1+ xm=yn. 設 zk?xm， 則可加 xm=yn到 Z， 得到一個長為 k+1的 X與 Y 的公共序列 ， 與 Z是 X和 Y的 LCS矛盾 。 于是 zk=xm=yn。 現(xiàn)在證明 Zk1是 Xm1與 Yn1的 LCS。 顯然 Zk1是 Xm1與 Yn1 的公共序列。我們需要證明 Zk1是 LCS。 設不然，則存在 Xm1與 Yn1的公共子序列 W， W的 長大 于 k1。 增加 xm=yn到 W， 我們得到一個長大于 k的 X與 Y的 公共序列，與 Z是 LCS矛盾。于是， Zk1是 Xm1與 Yn1的 LCS. HIT CSamp。E 169。DBLAB(2022) ⑵ X=x1, …, x m1, xm, Y=y1, …, y n1, yn， xm?yn， zk?xm， 則 LCSXY= LCSXm1Y 由于 zk?xm， Z是 Xm1與 Y的公共子序列。我們來 證 Z是 Xm1與 Y的 LCS。 設 Xm1與 Y有一個公共子序列 W， W的長大于 k, 則 W也是 X與 Y 的公共子序列 ， 與 Z是 LCS矛盾 。 ⑶ 同 ⑵ 可證 。 HIT CSamp。E 169。DBLAB(2022) X和 Y的 LCS的優(yōu)化解結構為 LCSXY=LCSXm1Yn1+ xm=yn if xm=yn LCSXY=LCSXm1Y if xm?yn, zk?xm LCSXY=LCSXYn1 if xm?yn, zk?yn HIT CSamp。E 169。DBLAB(2022) ?子問題重疊性 LCSXY LCSXm1Yn1 LCSXm1Y LCSXYn1 LCSXm2Yn2 LCSXm2Yn1 LCSXm1Yn2 …… LCS問題具有子問題重疊性 HIT CSamp。E 169。DBLAB(2022) 建立 LCS長度的遞歸方程 ? C[i, j] = Xi與 Yj 的 LCS的長度 ? LCS長度的遞歸方程 C[i, j] = 0 if i=0 或 j=0 C[i, j] = C[i1, j1] + 1 if i, j0 and xi = yj C[i, j] = Max(C[i, j1], C[i1, j]) if i, j0 and xi ? yj HIT CSamp。E 169。DBLAB(2022) ? 基本思想 自底向上計算 LCS的長度 C[i1, j1] C[i1,j] C[i, j1] C[i, j] HIT CSamp。E 169。DBLAB(2022) ?計算過程 C[0,0] C[0,1] C[0,3] C[0,2] C[0,4] C[1,0] C[2,0] C[3,0] C[1,1] C[2,1] C[3,1] C[1,2] C[1,3] C[1,4] C[2,2] C[2,3] C[2,4] C[3,2] C[3,3] C[3,4] HIT CSamp。E 169。DBLAB(2022) ?計算 LCS長度的算法 – 數(shù)據(jù)結構 C[0:m,0:n]: C[i,j]是 Xi與 Yj的 LCS的長度 B[1:m,1:n]: B[i,j]是指針 ， 指向計算 C[i,j] 時所選擇的子問題的優(yōu)化解 所對應的 C表的表 項 HIT CSamp。E 169。DBLAB(2022) LCSlength(X, Y) m?length(X)； n?length(Y)； For i?1 To m Do C[i,0]?0。 For j?1 To n Do C[0,j]?0。 For i?1 To m Do For j?1 To n Do If xi = yj Then C[i,j]?C[i1,j1]+1； B[i,j]?“↖ ”。 Else If C[i1,j]?C[i,j1] Then C[i,j]?C[i1,j]。 B[i,j]?“↑”。 Else C[i,j]?C[i,j1]。 B[i,j]?“←”。 Return C and B. HIT CSamp。E 169。DBLAB(2022) ?基本思想 – 從 B[m, n]開始按指針搜索 – 若 B[i, j]=“↖ ”， 則 xi=yj是 LCS的一個元素 – 如此找到的 “ LCS”是 X與 Y的 LCS的 Inverse 構造優(yōu)化解 HIT CSamp。E 169。DBLAB(2022) PrintLCS(B, X, i, j) IF i=0 or j=0 THEN Return。 IF B[i, j]=“↖ ” THEN PrintLCS(B, X, i1, j1)。 Print xi。 ELSE If B[i, j]=“↑” THEN PrintLCS(B, X, i1, j)。 ELSE PrintLCS(B, X, i, j1). PrintLCS(B, X, length(X), length(Y)) 可打印出 X與 Y的 LCS。 HIT CSamp。E 169。DBLAB(2022) ?時間復雜性 – 計算代價的時間 ? (i, j)兩 層循環(huán) ,i循環(huán) m步 , j循環(huán) n步 ? O(mn) –構造最優(yōu)解的時間 : O(m+n) –總時間復雜性為： O(mn) ?空降復雜性 – 使用數(shù)組 C和 B –需要空間 O(mn) 算法復雜性 HIT CSamp。E 169。DBLAB(2022) 凸多邊形的三角剖分 HIT CSamp。E 169。DBLAB(2022) ?多邊形 多邊形表示為頂點坐標集 P=(v0,v1,...vn)或頂點序列v0v1,...vn1vn ?簡單多邊形 除了頂點以外沒有任何邊交叉點的多邊形 ?多邊形的內(nèi)部 、 邊界與外部 – 平面上由多邊形封閉的點集合稱為多邊形 內(nèi)部 ， – 多邊形上的點集合稱為多邊形的 邊界 – 平面上除多邊形內(nèi)部和邊界以外的點集合稱為多邊形的 外部 問題的定義 HIT CSamp。E 169。DBLAB(2022) ?弦 多邊形 P上的任意兩個不相鄰結點 vi、 vi+1所對應的線段 vivi+1稱為