【正文】 ，則 Z是 X和 yn1的最長公共子序列。 最長公共子序列的結(jié)構(gòu) 設(shè)序列 X={x1,x2,…,x m}和 Y={y1,y2,…,y n}的最長公共子序列為Z={z1,z2,…,z k} ，則 (1)若 xm=yn，則 zk=xm=yn，且 zk1是 xm1和 yn1的最長公共子序列。 ? 給定 2個(gè)序列 X和 Y，當(dāng)另一序列 Z既是 X的子序列又是 Y的子序列時(shí)，稱 Z是序列 X和 Y的 公共子序列 。 } 最長公共子序列 ? 若給定序列 X={x1,x2,…,x m}，則另一序列 Z={z1,z2,…,z k}，是 X的子序列是指存在一個(gè)嚴(yán)格遞增下標(biāo)序列 {i1,i2,…,i k}使得對(duì)于所有 j=1,2,…,k 有： zj=xij。} } m[i][j] = u。 if (t u) { u = t。 k j。 s[i][j] = i。 if (i == j) return 0。 三、備忘錄方法 ?備忘錄方法的控制結(jié)構(gòu)與直接遞歸方法的控制結(jié)構(gòu)相同，區(qū)別在于備忘錄方法為每個(gè)解過的子問題建立了備忘錄以備需要時(shí)查看，避免了相同子問題的重復(fù)求解。 ?通常不同的子問題個(gè)數(shù)隨問題的大小呈多項(xiàng)式增長。 這種性質(zhì)稱為 子問題的重疊性質(zhì) 。最優(yōu)子結(jié)構(gòu)是問題能用動(dòng)態(tài)規(guī)劃算法求解的前提。 ?在分析問題的最優(yōu)子結(jié)構(gòu)性質(zhì)時(shí)，所用的方法具有普遍性：首先假設(shè)由問題的最優(yōu)解導(dǎo)出的子問題的解不是最優(yōu)的，然后再設(shè)法說明在這個(gè)假設(shè)下可構(gòu)造出比原問題最優(yōu)解更好的解，從而導(dǎo)致矛盾。 動(dòng)態(tài)規(guī)劃算法的基本要素 一、最優(yōu)子結(jié)構(gòu) ?矩陣連乘計(jì)算次序問題的最優(yōu)解包含著其子問題的最優(yōu)解。 ? 以自底向上的方式計(jì)算出最優(yōu)值。 n = n/2 T(n/4) T(n/4) T(n/4) T(n/4) n/2 n/2 T(n/4) T(n/4) n/2 T(n/4) T(n/4) T(n/4) T(n/4) T(n/4) T(n) 動(dòng)態(tài)規(guī)劃思想 動(dòng)態(tài)規(guī)劃基本步驟 ? 找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。在用分治法求解時(shí)，有些子問題被重復(fù)計(jì)算了許多次。 1 2 3 4 5 6 7 8 2 1 4 3 6 5 8 7 3 4 1 2 7 8 5 6 4 3 2 1 8 7 6 5 5 6 7 8 1 2 3 4 6 5 8 7 2 1 4 3 7 8 5 6 3 4 1 2 8 7 6 5 4 3 2 1 ? 但是經(jīng)分解得到的子問題往往不是互相獨(dú)立的。遞歸地用對(duì)選手進(jìn)行分割，直到只剩下 2個(gè)選手時(shí)，比賽日程表的制定就變得很簡單。 1 2 3 4 5 6 7 8 2 1 4 3 6 5 8 7 3 4 1 2 7 8 5 6 4 3 2 1 8 7 6 5 5 6 7 8 1 2 3 4 6 5 8 7 2 1 4 3 7 8 5 6 3 4 1 2 8 7 6 5 4 3 2 1 循環(huán)賽日程表 設(shè)計(jì)一個(gè)滿足以下要求的比賽日程表： (1)每個(gè)選手必須與其他 n1個(gè)選手各賽一次； (2)每個(gè)選手一天只能賽一次； (3)循環(huán)賽一共進(jìn)行 n1天。遞歸地用對(duì)選手進(jìn)行分割，直到只剩下 2個(gè)選手時(shí)，比賽日程表的制定就變得很簡單。 } 復(fù)雜度分析 T(n)=O(nlogn) ??????? 44)()2/(2)1()(nnnOnTOnT設(shè)計(jì)一個(gè)滿足以下要求的比賽日程表： (1)每個(gè)選手必須與其他 n1個(gè)選手各賽一次； (2)每個(gè)選手一天只能賽一次； (3)循環(huán)賽一共進(jìn)行 n1天。 4. 設(shè) P1是 S1中距垂直分割線 l的距離在 dm之內(nèi)的所有點(diǎn)組成的集合； P2是 S2中距分割線 l的距離在 dm之內(nèi)所有點(diǎn)組成的集合； 將 P1和 P2中點(diǎn)依其 y坐標(biāo)值排序； 并設(shè) X和 Y是相應(yīng)的已排好序的點(diǎn)列； 5. 通過掃描 X以及對(duì)于 X中每個(gè)點(diǎn)檢查 Y中與其距離在 dm之內(nèi)的所有點(diǎn) (最多 6個(gè) )可以完成合并； 當(dāng) X中的掃描指針逐次向上移動(dòng)時(shí)， Y中的掃描指針可在寬為 2dm的區(qū)間內(nèi)移動(dòng)； 設(shè) dl是按這種掃描方式找到的點(diǎn)對(duì)間的最小距離； 6. d=min(dm,dl)。 d2=cpair2(S2)。 1. m=S中各點(diǎn) x間坐標(biāo)的中位數(shù) 。 最接近點(diǎn)對(duì)問題 最接近點(diǎn)對(duì)問題 public static double cpair2(S) { n=|S|。 ?因此，若將 P1和 P2中所有 S中點(diǎn)按其 y坐標(biāo)排好序，則對(duì) P1中所有點(diǎn)，對(duì)排好序的點(diǎn)列作一次掃描，就可以找出所有最接近點(diǎn)對(duì)的候選者。由于能與p點(diǎn)一起構(gòu)成最接近點(diǎn)對(duì)候選者的 S2中點(diǎn)一定在矩形 R中，所以它們?cè)谥本€ l上的投影點(diǎn)距 p在 l上投影點(diǎn)的距離小于 d。這與 d的意義相矛盾。若矩形 R中有多于 6個(gè) S中的點(diǎn)，則由鴿舍原理易知至少有一個(gè) (d/2) (2d/3)的小矩形中有 2個(gè)以上 S中的點(diǎn)。由此可以推出 矩形 R中最多只有 6個(gè) S中的點(diǎn) 。 ?能否在線性時(shí)間內(nèi)找到 p,q？ 最接近點(diǎn)對(duì)問題 ?考慮 P1中任意一點(diǎn) p，它若與 P2中的點(diǎn) q構(gòu)成最接近點(diǎn)對(duì)的候選者，則必有 distance(p， q)＜ d。由此將 S分割為 S1和 S2。 ?選取一垂直線 l:x=m來作為分割直線。 從而我們用線性時(shí)間就可以將 S1的解和 S2的解合并成為 S的解 。由圖可以看出， 如果 (md,m]中有 S中的點(diǎn)，則此點(diǎn)就是 S1中最大點(diǎn)。 ?能否在線性時(shí)間內(nèi)找到 p3,q3？ 最接近點(diǎn)對(duì)問題 ?如果 S的最接近點(diǎn)對(duì)是 {p3,q3}，即 |p3q3|d，則 p3和 q3兩者與 m的距離不超過 d， 即 p3∈ (md,m]， q3∈ (m,m+d]。 ?假設(shè)我們用 x軸上某個(gè)點(diǎn) m將 S劃分為 2個(gè)子集 S1和 S2 ， 基于 平衡子問題 的思想，用 S中各點(diǎn)坐標(biāo)的中位數(shù)來作分割點(diǎn)。此時(shí)，S中的 n個(gè)點(diǎn)退化為 x軸上的 n個(gè)實(shí)數(shù) x1,x2,…,xn 。 ?最壞時(shí)間復(fù)雜度： O(n2) ?平均時(shí)間復(fù)雜度： O(nlogn) ?輔助空間： O(n)或 O(logn) ?穩(wěn)定性：不穩(wěn)定 最接近點(diǎn)對(duì)問題 給定平面上 n個(gè)點(diǎn)的集合 S，找其中的一對(duì)點(diǎn)，使得在 n個(gè)點(diǎn)組成的所有點(diǎn)對(duì)中，該點(diǎn)對(duì)間的距離最小。通過修改算法 partition，可以設(shè)計(jì)出采用隨機(jī)選擇策略的快速排序算法。 return partition (p, r)。 {6, 7, 5, 2, 5, 8} {5, 2, 5} 6 {7, 8} private static int randomizedPartition (int p, int r) { int i = random(p,r)。 ji{5, 2, 5, 6, 7, 8} i++。 ji{5, 7, 5, 2, 6, 8} i++。 return j。 } a[p] = a[j]。 if (i = j) break。 // 將 = x的元素交換到左邊區(qū)域 // 將 = x的元素交換到右邊區(qū)域 while (true) { while (a[++i].pareTo(x) 0)。 快速排序 private static int partition (int p, int r) { int i = p, j = r + 1。 ?在 Strassen之后又有許多算法改進(jìn)了矩陣乘法的計(jì)算時(shí)間復(fù)雜性。因此，要想進(jìn)一步改進(jìn)矩陣乘法的時(shí)間復(fù)雜性，就不能再基于計(jì)算 2 2矩陣的 7次乘法這樣的方法了。由此可將方程 C=AB重寫為： ?傳統(tǒng)方法 ： O(n3) ?分治法 : ???????????????????222112112221121122211211BBBBAAAACCCC由此可得： 2112111111 BABAC ??2212121112 BABAC ??2122112121 BABAC ??2222122122 BABAC ??復(fù)雜度分析 T(n)=O(n3) ?沒有改進(jìn) ? 22)()2/(8)1()(2 ??????? nnnOnTOnTStrassen矩陣乘法 ?傳統(tǒng)方法 ： O(n3) ?分治法 : 為了降低時(shí)間復(fù)雜度，必須減少乘法的次數(shù)。 Strassen矩陣乘法 A和 B的乘積矩陣 C中的元素 C[i,j]定義為 : ??? nkjkBkiAjiC1]][[]][[]][[若依此定義來計(jì)算 A和 B的乘積矩陣 C，則每計(jì)算 C的一個(gè)元素 C[i][j]，需要做 n次乘法和 n1次加法。該方法也可以看作是一個(gè)復(fù)雜的分治算法，對(duì)于大整數(shù)乘法，它能在 O(nlogn)時(shí)間內(nèi)解決。 大整數(shù)的乘法 請(qǐng)?jiān)O(shè)計(jì)一個(gè)有效的算法，可以進(jìn)行兩個(gè) n位大整數(shù)的乘法運(yùn)算 ?小學(xué)的方法： O(n2) ?效率太低 ?分治法 : O() ?較大的改進(jìn) ?更快的方法 ?? ?如果將大整數(shù)分成更多段，用更復(fù)雜的方式把它們組合起來，將有可能得到更優(yōu)的算法。 大整數(shù)的乘法 請(qǐng)?jiān)O(shè)計(jì)一個(gè)有效的算法，可以進(jìn)行兩個(gè) n位大整數(shù)的乘法運(yùn)算 ?小學(xué)的方法： O(n2) ?效率太低 ?分治法 : a b c d 復(fù)雜度分析 T(n)=O(n2) ?沒有改進(jìn) ? 11)()2/(4)1()(??????? nnnOnTOnTX = Y = X = a 2n/2 + b Y = c 2n/2 + d XY = ac 2n + (ad+bc) 2n/2 + bd 大整數(shù)的乘法 請(qǐng)?jiān)O(shè)計(jì)一個(gè)有效的算法，可以進(jìn)行兩個(gè) n位大整數(shù)的乘法運(yùn)算 ?小學(xué)的方法： O(n2) ?效率太低 ?分治法 : XY = ac 2n + (ad+bc) 2n/2 + bd 為了降低時(shí)間復(fù)雜度，必須減少乘法的次數(shù)。循環(huán)體內(nèi)運(yùn)算需要 O(1) 時(shí)間，因此整個(gè)算法在最壞情況下的計(jì)算時(shí)間復(fù)雜性為 O(logn) 。 // 未找到 x } 算法復(fù)雜度分析： 每執(zhí)行一次算法的while循環(huán)， 待搜索數(shù)組的大小減少一半。 else right = middle 1。 if (x == a[middle]) return middle。 int right = n 1。 二分搜索技術(shù) 給定已按升序排好序的 n個(gè)元素 a[0:n1]，現(xiàn)要在這 n個(gè)元素中找出一特定元素 x。 分析：