遞歸、分治、動態(tài)規(guī)劃、回溯ppt課件

1、遞歸、分治、動態(tài)規(guī)劃與回溯 回溯 遞歸 遞推普通實現(xiàn)方式正反方向有時可相互轉(zhuǎn)化較簡約,要求數(shù)學規(guī)律性較強DFS窮舉的優(yōu)化版啟發(fā)式搜索途徑尋覓圖論/網(wǎng)絡(luò)流數(shù)學問題：組合數(shù)學樹、圖、排序等問題分治、以大化小動態(tài)規(guī)劃的實現(xiàn)DP=遞歸貪婪回溯、遞歸、遞推是計算機算法中根底內(nèi)容，范圍極其廣泛。遞歸與分治根本原理n對這k個子問題分別求解。假設(shè)子問題的規(guī)模依然不夠小，那么再劃分為k個子問題，如此遞歸的進展下去，直到問題規(guī)模足夠小，很容易求出其解為止。T(n/2)nT(n/2)T(n/2)T(n/2)T(n)=T(n/2)nT(n/2)T(n/2)T(n/2)T(n)=n對這k個子問題分別求解。假設(shè)子問題的規(guī)

2、模依然不夠小，那么再劃分為k個子問題，如此遞歸的進展下去，直到問題規(guī)模足夠小，很容易求出其解為止。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4) n將求出的小規(guī)模的問題的解合并為一個更大規(guī)模的問題的解，自底向上逐漸求出原來問題的解。遞歸與分治根本原理n/2T(n/4)T(n/4)T(n/4)T(n/4)n將求出的小規(guī)模的問題的解合并為一個更大規(guī)模的問題的解，自底向上逐漸求出原來問題的解。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4

3、)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)遞歸與分治根本原理n直接或間接地調(diào)用本身的算法稱為遞歸算法。用函數(shù)本身給出定義的函數(shù)稱為遞歸函數(shù)。n由分治法產(chǎn)生的子問題往往是原問題的較小方式，這就為運用遞歸技術(shù)提供了方便。在這種情況下，反復運用分治手段，可以使子問題與原問題類型一致而其規(guī)模卻不斷減少，最終使子問題減少到很容易直接求出其解。這自然導致遞歸過程的產(chǎn)生。n分治與遞歸像一對孿生兄弟，經(jīng)常同時運用在算法設(shè)計之中，并由此產(chǎn)生許多高效算法。遞推與遞歸 n遞歸與遞推外表看來是相逆的過程，其實也是類

4、似的，最終的計算都是從小算到大。n遞推的運用環(huán)境要求高導致了遞推的高效性，遞推沒有反復計算什么數(shù)據(jù)，堅持了高效。n遞歸大多數(shù)會反復計算子問題，導致時間浪費，所以普通不要運用過深的遞歸，甚至會空間溢出。但是也不能說遞推好，遞歸差，由于遞歸卻能處理很多遞推做不到的事情，在某些特定的環(huán)境下也能實現(xiàn)高效，并且遞歸容易運用。我們要就事論事！斐波那契數(shù)列Fibonacci，對于f30，假設(shè)運用遞歸那么需求運轉(zhuǎn)1664079次，而遞推只需30次就可以了，速度懸殊。遞歸：long f (long n) if i3 then return 1; else f(i-1)+f(i-2);遞推：long f (lon

5、g n)a 1:=1;a 2:=1;for i:=1 to n-2 dof i+2:=f i+f i+1;遞推與遞歸 1.經(jīng)典遞歸例如Hanoi塔問題：經(jīng)典的遞歸，原問題包含子問題。有些問題或者數(shù)據(jù)構(gòu)造本來就是遞歸描畫的，用遞歸做很自然。2.遞歸與遞推，數(shù)學式關(guān)系利用遞歸的思想建立遞推關(guān)系，如由兔子生崽而來的fibonacci數(shù)列。但遞推由于沒有前往段，因此更為簡單，有時可以直接用循環(huán)實現(xiàn)。3.分治等以大化小算法不少分治方法是源于遞歸思想，或是遞歸分解+合并處置。遞歸的運用范圍遞歸的運用范圍n4.回溯n 規(guī)模較小的問題用回溯處理比較自然。留意遞歸前后要保證現(xiàn)場的保管和恢復，即正確的轉(zhuǎn)化問題。n

6、5.動態(tài)規(guī)劃n 動態(tài)規(guī)劃的子問題重疊性質(zhì)與遞歸有某種類似之處。遞歸+動態(tài)修正查表是一種不錯的建立動態(tài)規(guī)劃模型的方法。n 樹、圖、排序等符合遞歸子問題思想的構(gòu)造n 樹、圖等數(shù)據(jù)構(gòu)造本身就是遞歸構(gòu)造，因此當然是運用遞歸來處置。n7.其他n 例如陳列組合等，很雜的。例例1 1 階乘函數(shù)階乘函數(shù)階乘函數(shù)可遞歸地定義為：階乘函數(shù)可遞歸地定義為：00)!1(1!nnnnn邊境條件邊境條件遞歸方程遞歸方程邊境條件與遞歸方程是遞歸函數(shù)的二個要素，遞歸函數(shù)只需具備了這兩個要素，才干在有限次計算后得出結(jié)果。例例2 Fibonacci2 Fibonacci數(shù)列數(shù)列無窮數(shù)列無窮數(shù)列1 1，1 1，2 2，3 3，5

7、5，8 8，1313，2121，3434，5555，被，被稱為稱為FibonacciFibonacci數(shù)列。它可以遞歸地定義為：數(shù)列。它可以遞歸地定義為：邊境條件邊境條件遞歸方程遞歸方程110)2() 1(11)(nnnnFnFnF第n個Fibonacci數(shù)可遞歸地計算如下：public static int fibonacci(int n) if (n 1時，perm(R)由(r1)perm(R1)，(r2)perm(R2)，(rn)perm(Rn)構(gòu)成。 例例5 5 整數(shù)劃分問題整數(shù)劃分問題將正整數(shù)將正整數(shù)n n表示成一系列正整數(shù)之和：表示成一系列正整數(shù)之和：n=n1+n2+nkn=n1+

8、n2+nk，其中其中n1n2nk1n1n2nk1，k1k1。正整數(shù)正整數(shù)n n的這種表示稱為正整數(shù)的這種表示稱為正整數(shù)n n的劃分。求正整數(shù)的劃分。求正整數(shù)n n的不的不同劃分個數(shù)。同劃分個數(shù)。 例如正整數(shù)例如正整數(shù)6 6有如下有如下1111種不同的劃分：種不同的劃分： 6 6； 5+1 5+1； 4+2 4+2，4+1+14+1+1； 3+3 3+3，3+2+13+2+1，3+1+1+13+1+1+1； 2+2+2 2+2+2，2+2+1+12+2+1+1，2+1+1+1+12+1+1+1+1； 1+1+1+1+1+1 1+1+1+1+1+1。(2) q(n,m)=q(n,n),mn;最大加

9、數(shù)n1實踐上不能大于n。因此，q(1,m)=1。(1) q(n,1)=1,n1;當最大加數(shù)n1不大于1時，任何正整數(shù)n只需一種劃分方式，即nn111 (4) q(n,m)=q(n,m-1)+q(n-m,m),nm1;正整數(shù)n的最大加數(shù)n1不大于m的劃分由n1=m的劃分和n1n-1 的劃分組成。(3) q(n,n)=1+q(n,n-1);正整數(shù)n的劃分由n1=n的劃分和n1n-1的劃分組成。例例5 5 整數(shù)劃分問題整數(shù)劃分問題前面的幾個例子中，問題本身都具有比較明顯的遞歸關(guān)系，因前面的幾個例子中，問題本身都具有比較明顯的遞歸關(guān)系，因此容易用遞歸函數(shù)直接求解。此容易用遞歸函數(shù)直接求解。在本例中，假

10、設(shè)設(shè)在本例中，假設(shè)設(shè)p(n)p(n)為正整數(shù)為正整數(shù)n n的劃分數(shù)，那么難以找到遞歸的劃分數(shù)，那么難以找到遞歸關(guān)系，因此思索添加一個自變量：將最大加數(shù)關(guān)系，因此思索添加一個自變量：將最大加數(shù)n1n1不大于不大于m m的劃分的劃分個數(shù)記作個數(shù)記作q(n,m)q(n,m)。可以建立。可以建立q(n,m)q(n,m)的如下遞歸關(guān)系。的如下遞歸關(guān)系。11, 1),() 1,() 1,(1),(1),(mnmnmnmnmmnqmnqnnqnnqmnq例例5 5 整數(shù)劃分問題整數(shù)劃分問題前面的幾個例子中，問題本身都具有比較明顯的遞歸關(guān)系，因前面的幾個例子中，問題本身都具有比較明顯的遞歸關(guān)系，因此容易用遞歸

11、函數(shù)直接求解。此容易用遞歸函數(shù)直接求解。在本例中，假設(shè)設(shè)在本例中，假設(shè)設(shè)p(n)p(n)為正整數(shù)為正整數(shù)n n的劃分數(shù)，那么難以找到遞歸的劃分數(shù)，那么難以找到遞歸關(guān)系，因此思索添加一個自變量：將最大加數(shù)關(guān)系，因此思索添加一個自變量：將最大加數(shù)n1n1不大于不大于m m的劃分的劃分個數(shù)記作個數(shù)記作q(n,m)q(n,m)?？梢越ⅰ？梢越(n,m)q(n,m)的如下遞歸關(guān)系。的如下遞歸關(guān)系。正整數(shù)n的劃分數(shù)p(n)=q(n,n)。 例例6 Hanoi6 Hanoi塔問題塔問題設(shè)設(shè)a,b,ca,b,c是是3 3個塔座。開場時，在塔座個塔座。開場時，在塔座a a上有一疊共上有一疊共n n個圓個圓

12、盤，這些圓盤自下而上，由大到小地疊在一同。各圓盤，這些圓盤自下而上，由大到小地疊在一同。各圓盤從小到大編號為盤從小到大編號為1,2,n,1,2,n,現(xiàn)要求將塔座現(xiàn)要求將塔座a a上的這一上的這一疊圓盤移到塔座疊圓盤移到塔座b b上，并仍按同樣順序疊置。在挪動圓上，并仍按同樣順序疊置。在挪動圓盤時應(yīng)遵守以下挪動規(guī)那么：盤時應(yīng)遵守以下挪動規(guī)那么：規(guī)那么規(guī)那么1 1：每次只能挪動：每次只能挪動1 1個圓盤；個圓盤；規(guī)那么規(guī)那么2 2：任何時辰都不允許將較大的圓盤壓在較小的圓：任何時辰都不允許將較大的圓盤壓在較小的圓盤之上；盤之上；規(guī)那么規(guī)那么3 3：在滿足挪動規(guī)那么：在滿足挪動規(guī)那么1 1和和2 2

13、的前提下，可將圓盤移的前提下，可將圓盤移至至a,b,ca,b,c中任一塔座上。中任一塔座上。在問題規(guī)模較大時，較難找到普通的方法，因此我們嘗試用遞歸技術(shù)來處理這個問題。當n=1時，問題比較簡單。此時，只需將編號為1的圓盤從塔座a直接移至塔座b上即可。當n1時，需求利用塔座c作為輔助塔座。此時假設(shè)能設(shè)法將n-1個較小的圓盤按照挪動規(guī)那么從塔座a移至塔座c，然后，將剩下的最大圓盤從塔座a移至塔座b，最后，再設(shè)法將n-1個較小的圓盤按照挪動規(guī)那么從塔座c移至塔座b。由此可見，n個圓盤的挪動問題可分為2次n-1個圓盤的挪動問題，這又可以遞歸地用上述方法來做。由此可以設(shè)計出解Hanoi塔問題的遞歸算法如

14、下。例例6 Hanoi6 Hanoi塔問題塔問題 public static void hanoi(int n, int a, int b, int c) if (n 0) hanoi(n-1, a, c, b); move(a,b); hanoi(n-1, c, b, a); 優(yōu)點：構(gòu)造明晰，可讀性強，而且容易用數(shù)學歸納優(yōu)點：構(gòu)造明晰，可讀性強，而且容易用數(shù)學歸納法來證明算法的正確性，因此它為設(shè)計算法、調(diào)法來證明算法的正確性，因此它為設(shè)計算法、調(diào)試程序帶來很大方便。試程序帶來很大方便。缺陷：遞歸算法的運轉(zhuǎn)效率較低，無論是耗費的計缺陷：遞歸算法的運轉(zhuǎn)效率較低，無論是耗費的計算時間還是占用的存儲

15、空間都比非遞歸算法要多。算時間還是占用的存儲空間都比非遞歸算法要多。divide-and-conquer(P) if ( | P | = n0) adhoc(P); /處理小規(guī)模的問題處理小規(guī)模的問題 divide P into smaller subinstances P1,P2,.,Pk；/分解問分解問題題 for (i=1,i=k,i+) yi=divide-and-conquer(Pi); /遞歸的解各子問題遞歸的解各子問題 return merge(y1,.,yk); /將各子問題的解合并為原問題的解將各子問題的解合并為原問題的解 人們從大量實際中發(fā)現(xiàn)，在用分治法設(shè)計算法時，最好使子

16、人們從大量實際中發(fā)現(xiàn)，在用分治法設(shè)計算法時，最好使子問題的規(guī)模大致一樣。即將一個問題分成大小相等的問題的規(guī)模大致一樣。即將一個問題分成大小相等的k個子問個子問題的處置方法是行之有效的。這種使子問題規(guī)模大致相等的做題的處置方法是行之有效的。這種使子問題規(guī)模大致相等的做法是出自一種平衡法是出自一種平衡(balancing)子問題的思想，它幾乎總是比子子問題的思想，它幾乎總是比子問題規(guī)模不等的做法要好。問題規(guī)模不等的做法要好。一個分治法將規(guī)模為n的問題分成k個規(guī)模為nm的子問題去解。設(shè)分解閥值n0=1，且adhoc解規(guī)模為1的問題耗費1個單位時間。再設(shè)將原問題分解為k個子問題以及用merge將k個子

17、問題的解合并為原問題的解需用f(n)個單位時間。用T(n)表示該分治法解規(guī)模為|P|=n的問題所需的計算時間，那么有：11)()/() 1 ()(nnnfmnkTOnT經(jīng)過迭代法求得方程的解：1log0log)/()(nmjjjkmmnfknnT留意：遞歸方程及其解只給出留意：遞歸方程及其解只給出n等于等于m的方冪時的方冪時T(n)的值，但的值，但是假設(shè)以為是假設(shè)以為T(n)足夠平滑，那么由足夠平滑，那么由n等于等于m的方冪時的方冪時T(n)的值的值可以估計可以估計T(n)的增長速度。通常假定的增長速度。通常假定T(n)是單調(diào)上升的，從是單調(diào)上升的，從而當而當minmi+1時，時，T(mi)T

18、(n)T(mi+1)。 分析：假設(shè)n=1即只需一個元素，那么只需比較這個元素和x就可以確定x能否在表中。因此這個問題滿足分治法的第一個適用條件分析：比較x和a的中間元素amid，假設(shè)x=amid，那么x在L中的位置就是mid；假設(shè)xai，同理我們只需在amid的后面查找x即可。無論是在前面還是后面查找x，其方法都和在a中查找x一樣，只不過是查找的規(guī)模減少了。這就闡明了此問題滿足分治法的第二個和第三個適用條件。 分析：很顯然此問題分解出的子問題相互獨立，即在ai的前面或后面查找x是獨立的子問題，因此滿足分治法的第四個適用條件。給定已按升序排好序的給定已按升序排好序的n個元素個元素a0:n-1，現(xiàn)

19、要在這，現(xiàn)要在這n個元素中找個元素中找出一特定元素出一特定元素x。分析：分析：給定已按升序排好序的給定已按升序排好序的n個元素個元素a0:n-1，現(xiàn)要在這，現(xiàn)要在這n個元素中找個元素中找出一特定元素出一特定元素x。據(jù)此容易設(shè)計出二分搜索算法：public static int binarySearch(int a, int x, int n) / 在 a0 = a1 = . = an-1 中搜索 x / 找到x時前往其在數(shù)組中的位置，否那么前往-1 int left = 0; int right = n - 1; while (left amiddle) left = middle + 1;

20、else right = middle - 1; return -1; / 未找到x 算法復雜度分析：算法復雜度分析：每執(zhí)行一次算法的每執(zhí)行一次算法的while循環(huán)，循環(huán)， 待搜索數(shù)待搜索數(shù)組的大小減少一半。因組的大小減少一半。因此，在最壞情況下，此，在最壞情況下，while循環(huán)被執(zhí)行了循環(huán)被執(zhí)行了O(logn) 次。循環(huán)體內(nèi)次。循環(huán)體內(nèi)運算需求運算需求O(1) 時間，時間，因此整個算法在最壞情因此整個算法在最壞情況下的計算時間復雜性況下的計算時間復雜性為為O(logn) 。 請設(shè)計一個有效的算法，可以進展兩個請設(shè)計一個有效的算法，可以進展兩個n n位大整數(shù)的乘法運算位大整數(shù)的乘法運算u小學的

21、方法：O(n2) 效率太低u分治法: abcd復雜度分析復雜度分析T(n)=O(n2) 沒有改良沒有改良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è)計一個有效的算法，可以進展兩個請設(shè)計一個有效的算法，可以進展兩個n n位大整數(shù)的乘法運算位大整數(shù)的乘法運算u小學的方法：O(n2) 效率太低u分治法: XY = ac 2n + (ad+bc) 2n/2 + bd 為了降低時間復雜度，必需減少乘法的次數(shù)。XY = ac 2n + (a-c)(b-d)+a

22、c+bd) 2n/2 + bdXY = ac 2n + (a+c)(b+d)-ac-bd) 2n/2 + bd復雜度分析復雜度分析T(n)=O(nlog3) =O(n1.59) 較大的改良較大的改良11)()2/(3) 1 ()(nnnOnTOnT細節(jié)問題：兩個細節(jié)問題：兩個XYXY的復雜度都是的復雜度都是O(nlog3)O(nlog3)，但思索到，但思索到a+c,b+da+c,b+d能夠得到能夠得到m+1m+1位的結(jié)果，使問題的規(guī)模變大，故不選擇第位的結(jié)果，使問題的規(guī)模變大，故不選擇第2 2種方種方案。案。 請設(shè)計一個有效的算法，可以進展兩個請設(shè)計一個有效的算法，可以進展兩個n n位大整數(shù)的

23、乘法運算位大整數(shù)的乘法運算u小學的方法：O(n2) 效率太低u分治法: O(n1.59) 較大的改良u更快的方法?假設(shè)將大整數(shù)分成更多段，用更復雜的方式把它們組合起來，將有能夠得到更優(yōu)的算法。最終的，這個思想導致了快速傅利葉變換(Fast Fourier Transform)的產(chǎn)生。該方法也可以看作是一個復雜的分治算法，對于大整數(shù)乘法，它能在O(nlogn)時間內(nèi)處理。能否能找到線性時間的算法？目前為止還沒有結(jié)果。A和B的乘積矩陣C中的元素Ci,j定義為: nkjkBkiAjiC1假設(shè)依此定義來計算A和B的乘積矩陣C，那么每計算C的一個元素Cij，需求做n次乘法和n-1次加法。因此，算出矩陣C

24、的 個元素所需的計算時間為O(n3)u傳統(tǒng)方法：O(n3)運用與上例類似的技術(shù)，將矩陣A，B和C中每一矩陣都分塊成4個大小相等的子矩陣。由此可將方程C=AB重寫為：u傳統(tǒng)方法：O(n3)u分治法:222112112221121122211211BBBBAAAACCCC由此可得：2112111111BABAC2212121112BABAC2122112121BABAC2222122122BABAC復雜度分析復雜度分析T(n)=O(n3) 沒有改良沒有改良22)()2/(8) 1 ()(2nnnOnTOnTu傳統(tǒng)方法：O(n3)u分治法:為了降低時間復雜度，必需減少乘法的次數(shù)。2221121122

25、21121122211211BBBBAAAACCCC)(2212111BBAM2212112)(BAAM1122213)(BAAM)(1121224BBAM)(221122115BBAAM)(222122126BBAAM)(121121117BBAAM624511MMMMC2112MMC4321MMC731522MMMMC復雜度分析復雜度分析T(n)=O(nlog7) =O(n2.81) 較大的改良較大的改良22)()2/(7) 1 ()(2nnnOnTOnTu傳統(tǒng)方法：O(n3)u分治法: O(n2.81)u更快的方法?Hopcroft和Kerr曾經(jīng)證明(1971)，計算2個矩陣的乘積，7次

26、乘法是必要的。因此，要想進一步改良矩陣乘法的時間復雜性，就不能再基于計算22矩陣的7次乘法這樣的方法了?；蛟S該當研討或矩陣的更好算法。在Strassen之后又有許多算法改良了矩陣乘法的計算時間復雜性。目前最好的計算時間上界是 O(n2.376)能否能找到O(n2)的算法？目前為止還沒有結(jié)果。private static int partition (int p, int r) int i = p, j = r + 1; Comparable x = ap; / 將= x的元素交換到左邊區(qū)域 / 將= x的元素交換到右邊區(qū)域 while (true) while (a+ipareTo(x) 0)

27、; if (i = j) break; MyMath.swap(a, i, j); ap = aj; aj = x; return j; 初始序列6, 7, 5, 2, 5, 8j-;ji5, 7, 5, 2, 6, 8i+;ji5, 6, 5, 2, 7, 8j-;ji5, 2, 5, 6, 7, 8i+;ji完成快速排序具有不穩(wěn)定性。6, 7, 5, 2, 5, 85, 2, 5 6 7, 8private static int randomizedPartition (int p, int r) int i = random(p,r); MyMath.swap(a, i, p); ret

28、urn partition (p, r); 快速排序算法的性能取決于劃分的對稱性。經(jīng)過修正算法partition，可以設(shè)計出采用隨機選擇戰(zhàn)略的快速排序算法。在快速排序算法的每一步中，當數(shù)組還沒有被劃分時，可以在ap:r中隨機選出一個元素作為劃分基準，這樣可以使劃分基準的選擇是隨機的，從而可以期望劃分是較對稱的。&最壞時間復雜度：最壞時間復雜度：O(n2)&平均時間復雜度：平均時間復雜度：O(nlogn)&輔助空間：輔助空間：O(n)或或O(logn)&穩(wěn)定性：不穩(wěn)定穩(wěn)定性：不穩(wěn)定給定平面上n個點的集合S，找其中的一對點，使得在n個點組成的一切點對中，該點對間的間隔最小。 u為了使問題易于了解和

29、分析，先來思索一維的情形。此時，S中的n個點退化為x軸上的n個實數(shù) x1,x2,xn。最接近點對即為這n個實數(shù)中相差最小的2個實數(shù)。假設(shè)我們用x軸上某個點m將S劃分為2個子集S1和S2 ，基于平衡子問題的思想，用S中各點坐標的中位數(shù)來作分割點。遞歸地在S1和S2上找出其最接近點對p1,p2和q1,q2，并設(shè)d=min|p1-p2|,|q1-q2|，S中的最接近點對或者是p1,p2，或者是q1,q2，或者是某個p3,q3，其中p3S1且q3S2。能否在線性時間內(nèi)找到p3,q3？u假設(shè)S的最接近點對是p3,q3，即|p3-q3|d，那么p3和q3兩者與m的間隔不超越d，即p3(m-d,m，q3(m

30、,m+d。u由于在S1中，每個長度為d的半閉區(qū)間至多包含一個點否那么必有兩點間隔小于d，并且m是S1和S2的分割點，因此(m-d,m中至多包含S中的一個點。由圖可以看出，假設(shè)(m-d,m中有S中的點，那么此點就是S1中最大點。u因此，我們用線性時間就能找到區(qū)間(m-d,m和(m,m+d中一切點，即p3和q3。從而我們用線性時間就可以將S1的解和S2的解合并成為S的解。能否在線性時間內(nèi)找到能否在線性時間內(nèi)找到p3,q3？u下面來思索二維的情形。選取一垂直線l:x=m來作為分割直線。其中m為S中各點x坐標的中位數(shù)。由此將S分割為S1和S2。遞歸地在S1和S2上找出其最小間隔d1和d2，并設(shè)d=mi

31、nd1,d2，S中的最接近點對或者是d，或者是某個p,q，其中pP1且qP2。能否在線性時間內(nèi)找到p,q？u思索P1中恣意一點p，它假設(shè)與P2中的點q構(gòu)成最接近點對的候選者，那么必有distance(p，q)d。滿足這個條件的P2中的點一定落在一個d2d的矩形R中u由d的意義可知，P2中任何2個S中的點的間隔都不小于d。由此可以推出矩形R中最多只需6個S中的點。u因此，在分治法的合并步驟中最多只需求檢查6n/2=3n個候選者能否在線性時間內(nèi)找到能否在線性時間內(nèi)找到p3,q3？證明證明:將矩形將矩形R的長為的長為2d的邊的邊3等分，將它的長為等分，將它的長為d的邊的邊2等分，由此導出等分，由此導

32、出6個個(d/2)(2d/3)的矩形。的矩形。假設(shè)矩形假設(shè)矩形R中有多于中有多于6個個S中的點，那么由鴿舍中的點，那么由鴿舍原理易知至少有一個原理易知至少有一個(d/2)(2d/3)的小矩形中有的小矩形中有2個以上個以上S中的點。設(shè)中的點。設(shè)u，v是位于同一小矩形中是位于同一小矩形中的的2個點，那么個點，那么distance(u,v)d。這與。這與d的意義相矛盾。的意義相矛盾。222223625)3/2()2/()()()()(dddvyuyvxux為了確切地知道要檢查哪6個點，可以將p和P2中一切S2的點投影到垂直線l上。由于能與p點一同構(gòu)成最接近點對候選者的S2中點一定在矩形R中，所以它們

33、在直線l上的投影點距p在l上投影點的間隔小于d。由上面的分析可知，這種投影點最多只需6個。因此，假設(shè)將P1和P2中一切S中點按其y坐標排好序，那么對P1中一切點，對排好序的點列作一次掃描，就可以找出一切最接近點對的候選者。對P1中每一點最多只需檢查P2中排好序的相繼6個點。public static double cpair2(S) n=|S|; if (n 2) return ;1. m=S中各點x間坐標的中位數(shù); 構(gòu)造S1和S2； /S1=pS|x(p)m2. d1=cpair2(S1); d2=cpair2(S2);3. dm=min(d1,d2);4. 設(shè)P1是S1中距垂直分割線l的間

34、隔在dm之內(nèi)的一切點組成的集合； P2是S2中距分割線l的間隔在dm之內(nèi)一切點組成的集合； 將P1和P2中點依其y坐標值排序； 并設(shè)X和Y是相應(yīng)的已排好序的點列；5. 經(jīng)過掃描X以及對于X中每個點檢查Y中與其間隔在dm之內(nèi)的一切點(最多6個)可以完成合并； 當X中的掃描指針逐次向上挪動時，Y中的掃描指針可在寬為2dm的區(qū)間內(nèi)挪動； 設(shè)dl是按這種掃描方式找到的點對間的最小間隔；6. d=min(dm,dl); return d;復雜度分析復雜度分析T(n)=O(nlogn)44)()2/(2) 1 ()(nnnOnTOnT設(shè)計一個滿足以下要求的競賽日程表：(1)每個選手必需與其他n-1個選手各

35、賽一次；(2)每個選手一天只能賽一次；(3)循環(huán)賽一共進展n-1天。按分治戰(zhàn)略，將一切的選手分為兩半，n個選手的競賽日程表就可以經(jīng)過為n/2個選手設(shè)計的競賽日程表來決議。遞歸地用對選手進展分割，直到只剩下2個選手時，競賽日程表的制定就變得很簡單。這時只需讓這2個選手進展競賽就可以了。1234567821436587341278564321876556781234658721437856341287654321設(shè)計一個滿足以下要求的競賽日程表：(1)每個選手必需與其他n-1個選手各賽一次；(2)每個選手一天只能賽一次；(3)循環(huán)賽一共進展n-1天。按分治戰(zhàn)略，將一切的選手分為兩半，n個選手的競賽

36、日程表就可以經(jīng)過為n/2個選手設(shè)計的競賽日程表來決議。遞歸地用對選手進展分割，直到只剩下2個選手時，競賽日程表的制定就變得很簡單。這時只需讓這2個選手進展競賽就可以了。1234567821436587341278564321876556781234658721437856341287654321n但是經(jīng)分解得到的子問題往往不是相互獨立的。不同子問題的數(shù)目經(jīng)常只需多項式量級。在用分治法求解時，有些子問題被反復計算了許多次。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n

37、/2T(n/4)T(n/4)T(n/4)T(n/4)n假設(shè)可以保管已處理的子問題的答案，而在需求時再找出已求得的答案，就可以防止大量反復計算，從而得到多項式時間算法。n=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2n/2T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4) T(n/4)T(n)n找出最優(yōu)解的性質(zhì)，并刻劃其構(gòu)造特征。n遞歸地定義最優(yōu)值。n以自底向上的方式計算出最優(yōu)值。n根據(jù)計算最優(yōu)值時得到的信息，構(gòu)造最優(yōu)解。矩陣連乘計算次序問題的最優(yōu)解包含著其子問題的最優(yōu)解。這種性質(zhì)稱為最優(yōu)子構(gòu)造性質(zhì)。在分析問題的最優(yōu)子構(gòu)造性質(zhì)時，所用的方法具有普遍性：

38、首先假設(shè)由問題的最優(yōu)解導出的子問題的解不是最優(yōu)的，然后再設(shè)法闡明在這個假設(shè)下可構(gòu)造出比原問題最優(yōu)解更好的解，從而導致矛盾。 利用問題的最優(yōu)子構(gòu)造性質(zhì)，以自底向上的方式遞歸地從子問題的最優(yōu)解逐漸構(gòu)造出整個問題的最優(yōu)解。最優(yōu)子構(gòu)造是問題能用動態(tài)規(guī)劃算法求解的前提。留意：同一個問題可以有多種方式刻劃它的最優(yōu)子構(gòu)造，有些表示方法的求解速度更快空間占用小，問題的維度低遞歸算法求解問題時，每次產(chǎn)生的子問題并不總是新問題，有些子問題被反復計算多次。這種性質(zhì)稱為子問題的重疊性質(zhì)。動態(tài)規(guī)劃算法，對每一個子問題只解一次，而后將其解保管在一個表格中，當再次需求解此子問題時，只是簡單地用常數(shù)時間查看一下結(jié)果。 通常不

39、同的子問題個數(shù)隨問題的大小呈多項式增長。因此用動態(tài)規(guī)劃算法只需求多項式時間，從而獲得較高的解題效率。 備忘錄方法的控制構(gòu)造與直接遞歸方法的控制構(gòu)造一樣，區(qū)別在于備忘錄方法為每個解過的子問題建立了備忘錄以備需求時查看，防止了一樣子問題的反復求解。m0private static int lookupChain(int i, int j) if (mij 0) return mij; if (i = j) return 0; int u = lookupChain(i+1,j) + pi-1*pi*pj; sij = i; for (int k = i+1; k j; k+) int t = lo

40、okupChain(i,k) + lookupChain(k+1,j) + pi-1*pk*pj; if (t u) u = t; sij = k; mij = u; return u; 假設(shè)給定序列X=x1,x2,xm，那么另一序列Z=z1,z2,zk，是X的子序列是指存在一個嚴厲遞增下標序列i1,i2,ik使得對于一切j=1,2,k有：zj=xij。例如，序列Z=B，C，D，B是序列X=A，B，C，B，D，A，B的子序列，相應(yīng)的遞增下標序列為2，3，5，7。給定2個序列X和Y，當另一序列Z既是X的子序列又是Y的子序列時，稱Z是序列X和Y的公共子序列。給定2個序列X=x1,x2,xm和Y=y

41、1,y2,yn，找出X和Y的最長公共子序列。 設(shè)序列X=x1,x2,xm和Y=y1,y2,yn的最長公共子序列為Z=z1,z2,zk ，那么(1)假設(shè)xm=yn，那么zk=xm=yn，且zk-1是xm-1和yn-1的最長公共子序列。(2)假設(shè)xmyn且zkxm，那么Z是xm-1和Y的最長公共子序列。(3)假設(shè)xmyn且zkyn，那么Z是X和yn-1的最長公共子序列。由此可見，2個序列的最長公共子序列包含了這2個序列的前綴的最長公共子序列。因此，最長公共子序列問題具有最優(yōu)子構(gòu)造性質(zhì)。 由最長公共子序列問題的最優(yōu)子構(gòu)造性質(zhì)建立子問題最優(yōu)值的遞歸關(guān)系。用cij記錄序列和的最長公共子序列的長度。其中，

42、 Xi=x1,x2,xi；Yj=y1,y2,yj。當i=0或j=0時，空序列是Xi和Yj的最長公共子序列。故此時Cij=0。其他情況下，由最優(yōu)子構(gòu)造性質(zhì)可建立遞歸關(guān)系如下：jijiyxjiyxjijijicjicjicjic; 0,; 0,0, 01,1max1 110由于在所思索的子問題空間中，總共有(mn)個不同的子問題，因此，用動態(tài)規(guī)劃算法自底向上地計算最優(yōu)值能提高算法的效率。 Algorithm lcsLength(x,y,b)1: mx.length-1;2: ny.length-1;3: ci0=0; c0i=0;4: for (int i = 1; i = m; i+)5: fo

43、r (int j = 1; j =cij-1) 10: cij=ci-1j;11: bij=2;12: else 13: cij=cij-1;14: bij=3;構(gòu)造最長公共子序列構(gòu)造最長公共子序列Algorithm lcs(int i,int j,char x,int b) if (i =0 | j=0) return; if (bij= 1) lcs(i-1,j-1,x,b); System.out.print(xi); else if (bij= 2) lcs(i-1,j,x,b); else lcs(i,j-1,x,b); 在算法lcsLength和lcs中，可進一步將數(shù)組b省去。現(xiàn)實

44、上，數(shù)組元素cij的值僅由ci-1j-1，ci-1j和cij-1這3個數(shù)組元素的值所確定。對于給定的數(shù)組元素cij，可以不借助于數(shù)組b而僅借助于c本身在時間內(nèi)確定cij的值是由ci-1j-1，ci-1j和cij-1中哪一個值所確定的。假設(shè)只需求計算最長公共子序列的長度，那么算法的空間需求可大大減少。現(xiàn)實上，在計算cij時，只用到數(shù)組c的第i行和第i-1行。因此，用2行的數(shù)組空間就可以計算出最長公共子序列的長度。進一步的分析還可將空間需求減至O(min(m,n)。用多邊形頂點的逆時針序列表示凸多邊形，即P=v0,v1,vn-1表示具有n條邊的凸多邊形。假設(shè)vi與vj是多邊形上不相鄰的2個頂點，那

45、么線段vivj稱為多邊形的一條弦。弦將多邊形分割成2個多邊形vi,vi+1,vj和vj,vj+1,vi。多邊形的三角剖分是將多邊形分割成互不相交的三角形的弦的集合T。給定凸多邊形P，以及定義在由多邊形的邊和弦組成的三角形上的權(quán)函數(shù)w。要求確定該凸多邊形的三角剖分，使得即該三角剖分中諸三角形上權(quán)之和為最小。 一個表達式的完全加括號方式相應(yīng)于一棵完全二叉樹，稱為表達式的語法樹。例如，完全加括號的矩陣連乘積(A1(A2A3)(A4(A5A6)所相應(yīng)的語法樹如圖 (a)所示。凸多邊形v0,v1,vn-1的三角剖分也可以用語法樹表示。例如，圖 (b)中凸多邊形的三角剖分可用圖 (a)所示的語法樹表示。

46、矩陣連乘積中的每個矩陣Ai對應(yīng)于凸(n+1)邊形中的一條邊vi-1vi。三角剖分中的一條弦vivj，ij，對應(yīng)于矩陣連乘積Ai+1:j。凸多邊形的最優(yōu)三角剖分問題有最優(yōu)子構(gòu)造性質(zhì)?，F(xiàn)實上，假設(shè)凸(n+1)邊形P=v0,v1,vn-1的最優(yōu)三角剖分T包含三角形v0vkvn，1kn-1，那么T的權(quán)為3個部分權(quán)的和：三角形v0vkvn的權(quán)，子多邊形v0,v1,vk和vk,vk+1,vn的權(quán)之和?？梢詳嘌裕蒚所確定的這2個子多邊形的三角剖分也是最優(yōu)的。由于假設(shè)有v0,v1,vk或vk,vk+1,vn的更小權(quán)的三角剖分將導致T不是最優(yōu)三角剖分的矛盾。 定義tij，1ijn為凸子多邊形vi-1,vi,v

47、j的最優(yōu)三角剖分所對應(yīng)的權(quán)函數(shù)值，即其最優(yōu)值。為方便起見，設(shè)退化的多邊形vi-1,vi具有權(quán)值0。據(jù)此定義，要計算的凸(n+1)邊形P的最優(yōu)權(quán)值為t1n。tij的值可以利用最優(yōu)子構(gòu)造性質(zhì)遞歸地計算。當j-i1時，凸子多邊形至少有3個頂點。由最優(yōu)子構(gòu)造性質(zhì)，tij的值應(yīng)為tik的值加上tk+1j的值，再加上三角形vi-1vkvj的權(quán)值，其中ikj-1。由于在計算時還不知道k確實切位置，而k的一切能夠位置只需j-i個，因此可以在這j-i個位置中選出使tij值到達最小的位置。由此，tij可遞歸地定義為：jijivvvwjktkitjitjkijki)(1min01多邊形游戲是一個單人玩的游戲，開場時

48、有一個由n個頂點構(gòu)成的多邊形。每個頂點被賦予一個整數(shù)值，每條邊被賦予一個運算符“+或“*。一切邊依次用整數(shù)從1到n編號。游戲第1步，將一條邊刪除。隨后n-1步按以下方式操作：(1)選擇一條邊E以及由E銜接著的2個頂點V1和V2；(2)用一個新的頂點取代邊E以及由E銜接著的2個頂點V1和V2。將由頂點V1和V2的整數(shù)值經(jīng)過邊E上的運算得到的結(jié)果賦予新頂點。最后，一切邊都被刪除，游戲終了。游戲的得分就是所剩頂點上的整數(shù)值。問題:對于給定的多邊形，計算最高得分。在所給多邊形中，從頂點i(1in)開場，長度為j(鏈中有j個頂點)的順時針鏈p(i，j) 可表示為vi，opi+1，vi+j-1。假設(shè)這條鏈

49、的最后一次合并運算在opi+s處發(fā)生(1sj-1)，那么可在opi+s處將鏈分割為2個子鏈p(i，s)和p(i+s，j-s)。設(shè)m1是對子鏈p(i，s)的恣意一種合并方式得到的值，而a和b分別是在一切能夠的合并中得到的最小值和最大值。m2是p(i+s，j-s)的恣意一種合并方式得到的值，而c和d分別是在一切能夠的合并中得到的最小值和最大值。依此定義有am1b，cm2d(1)當opi+s=+時，顯然有a+cmb+d(2)當opi+s=*時，有minac，ad，bc，bdmmaxac，ad，bc，bd 換句話說，主鏈的最大值和最小值可由子鏈的最大值和最小值得到。 圖像的變位緊縮存儲格式將所給的象素

50、點序列p1,p2,pn,0pi255分割成m個延續(xù)段S1,S2,Sm。第i個象素段Si中(1im)，有l(wèi)i個象素,且該段中每個象素都只用bi位表示。設(shè) 那么第i個象素段Si為設(shè) ，那么hibi8。因此需求用3位表示bi,假設(shè)限制1li255，那么需求用8位表示li。因此，第i個象素段所需的存儲空間為li*bi+11位。按此格式存儲象素序列p1,p2,pn，需求 位的存儲空間。 圖像緊縮問題要求確定象素序列p1,p2,pn的最優(yōu)分段，使得依此分段所需的存儲空間最少。每個分段的長度不超越256位。11ikklit1maxlog1kilitkitiphmibilmi11*1設(shè)li，bi，是p1,p2

51、,pn的最優(yōu)分段。顯而易見，l1，b1是p1,pl1的最優(yōu)分段，且li，bi，是pl1+1,pn的最優(yōu)分段。即圖像緊縮問題滿足最優(yōu)子構(gòu)造性質(zhì)。設(shè)si，1in，是象素序列p1,pn的最優(yōu)分段所需的存儲位數(shù)。由最優(yōu)子構(gòu)造性質(zhì)易知：其中11), 1max(b*min256,min1ikikkisisik1maxlog),bmax(kjkipji算法復雜度分析：算法復雜度分析：由于算法由于算法compress中對中對k的循環(huán)次數(shù)不超這的循環(huán)次數(shù)不超這256，故對每一個確定的故對每一個確定的i，可在時間，可在時間O(1)內(nèi)完成的計算。因內(nèi)完成的計算。因此整個算法所需的計算時間為此整個算法所需的計算時間為O(n)。 在一塊電路板的上、下2端分別有n個接線柱。根據(jù)電路設(shè)計，要求用導線(i,(i)將上端接線柱與下端接線柱相連，如下圖。其中(i)是1,2,n的一個陳列。導線(i,(i)稱為該電路板上的第i條連線。對于任何1i(j)。電路布線問題要確定將哪些連線安排在第一層上，使得該層上有盡能夠多的連線。換句話說，該問題要求確定導線集Nets=(i,(i),1in的最大不相交子集。 記 。N(i,j)的最大不相交子集為MNS(i,j)。Size(i,j)=|MNS(i,j)|。(1)當i=1時，