計算機算法設計與分析第三章

分治法學習目標掌握分治法的基本思想掌握分治法的特點和基本框架掌握分治法解決實際問題3.1分治法基本思想孫子兵法兵勢篇曰：凡治眾如治寡，分數是也。其大致意思就是管理大規模部隊和管理小股部隊是一樣的，分開治理就是了。這就是分治法在軍事上的運用。分治法的基本思想就是將一個較難以解決的規模大的問題，分割成多個相似的規模較小的子問題，先求出小規模子問題的解，然后將各小規模子問題的解組合起來就是規模大的問題的解。其中的一個關鍵點是分割的子問題一定要相似，這樣就可以采取同樣的方法來求解，從而將問題簡化。例3.1

二分查找問題。在一個升序的含n個元素的數組a[]中查找x，輸出x在數組a中的下標位置，若沒查到返回-1。分析：可以考慮使用分治思想來解決，具體做法是設計三個變量left，mid和right將整個數組分成3個部分a[left,mid-1],a[mid],a[mid+1,right]。如果a[mid]>x，則使用相同的辦法在較小范圍[left,mid-1]中查找；如果a[mid]=x，則已查找到，返回mid即可；如果a[mid]<x，則使用相同的辦法在較小范圍[mid+1,right]中查找。以上過程都沒查找到的話，則數組中不存在x，返回-1。3.1分治法基本思想例3.2

二分歸并排序。將含有n個元素的數組a[]按關鍵字大小升序排列。以數組a[8]={8,4,5,7,1,3,6,2}為例來分析。3.1分治法基本思想3.2分治法的特點和基本框架當采用分治法時，一般原問題都需要具備以下幾個特征：（1）難度遞降：即原問題的解決難度，隨著數據的規模的縮小而降低，當降低到一定程度時，問題很容易解決。（2）問題可分：原問題可以分解為若干個規模較小的同類型問題，即該問題具有最優子結構性質。這是應用分治法的前提。（3）解可合并：利用所有子問題的解，可合并出原問題的解。這個特征很關鍵，能否利用分治法完全取決于這個特征。（4）相互獨立：各個子問題之間相互獨立，某個子問題的求解不會影響到另一個子問題。如果子問題之間不獨立，則分治法需要重復地解決公共的子問題，造成效率低下的結果。設P是要求解的問題，|P|為問題P的輸入規模，現將分治法求解問題的基本框架描述如下：Divide-and-Conquer(P)：if|P|≤cthenS(P)

//當問題規模較小時，很容易求出解endifdividePintoP1,P2,...,Pk//將原問題分割為規模小的子問題fori=1tokdoxi=Divide-and-Conquer(Pi)//遞歸求解每個子問題endforreturnMerge(x1,x2,...,xk)//將子問題的解合并成原問題的解3.2分治法的特點和基本框架3.3分治法的時間復雜度分析分治法的實現一般都是采用遞歸算法。分析分治法的時間復雜度需要使用其遞推公式來推導。分治法中通常的遞推方程有以下兩種類型：第一類是歸約后子問題規模比原問題規模呈常數級減少。遞推方程為如Hanoi塔問題使用分治法，將n個圓盤的問移動題歸約為兩個n-1圓盤移動子問題，也就是歸約后的子問題規模只比原問題規模少1。遞推方程為解得：第二類是歸約后子問題規模比原問題規模呈倍數減少。該算法的時間復雜度可以通過以下遞推公式求出：根據1.4.4節介紹的MasterTheorem主定理結論可知：3.3分治法的時間復雜度分析3.4.1分治法的典型實例——快速排序快速排序是數據結構中經典且高效的一種排序算法，它在實踐中應用非常廣泛。設待排的數組為A，快速排序的基本思想為：用數組的首元素作為標準將A劃分為前、后兩部分，前部分元素都比首元素小，后部分元素都比首元素大，這兩部分就構成兩個新的子問題。算法接著分別對這兩部分遞歸地進行排序，各子問題排序完成后自然整個數組也就排序完成。算法的關鍵在于怎樣劃分數組A而將其歸約成兩個相同結構的子問題。3.4.1分治法的典型實例——快速排序快速排序算法Quicksort(A,p,r) //p和r分別為數組A的首元素和尾元素的下標輸入：數組A[p..r],1≤p≤r≤n輸出：從A[p]到A[r]按照升序排好序的數組Aifp<rthenq←Partition(A,p,r) //劃分數組，找到首元素A[p]在排好序后的位置qA[p]?A[q] //交換A[p]，A[q]中元素的值Quicksort(A,p,q-1) //對前部分繼續遞歸地用快速排序算法Quicksort(A,q+1,r) //對后部分繼續遞歸地用快速排序算法endif其算法中的Partition函數是劃分的過程函數，它實現的就是以A[p..r]的首元素A[p]作為標準，輸出q表示A[p]應該處在的正確位置，即排好序后A[p]應該放在數組下標為q的位置。過程如下：（1）先從后向前掃描數組A，找到第一個不大于A[p]的元素A[j]（2）從前向后掃描A找到第一個大于A[p]的元素A[i]（3）當i＜j時，交換A[i]與A[j]。這時A[j]后面的元素都大于A[p]，A[i]前面的元素都小于或等于A[p]。（4）接著對數組A從i到j之間的部分繼續上面的掃描過程，直到i和j相遇，當i>j時，j就代表了A在排好序的數組中的正確位置q。此刻在q位置之前的元素都不大于A[p]，在q位置后面的元素都大于A[p]。3.4.1分治法的典型實例——快速排序3.4.1分治法的典型實例——快速排序劃分算法Partition(A,p,r)輸入：數組A[p..r],1≤p≤r≤n輸出：數組首元素A[p]在排好序的數組中的位置x←A[p]i←pj←r+1whiletruedorepeatj←j-1untilA[j]≤x//從后往前找到不大于x的元素repeati←i+1untilA[i]>x//從前往后找到大于x的元素ifi<jthenA[i]?A[j]//交換A[i]，A[j]中元素的值elsereturnj //i，j相遇，返回相遇的位置即為數組首元素A[p]的正確位置endifendwhile舉例說明一趟劃分的過程數組A[6]={64，57，86，42，12，53}，第一趟劃分以64為標準，p=1i=2j=5交換A[2]和A[5]的值，繼續循環。j=4i=5i<j不成立，一趟劃分結束，返回值為4。在Quicksort中q=4,交換A[p]，A[q]中元素的值，就得到一次劃分后的結果。在一趟快速排序結束后，繼續對兩個子數組{12,57,53,42}和{86}實施相同的操作。3.4.1分治法的典型實例——快速排序第1次循環645786421253第2次循環645753421286劃分后1257534264863.4.2分治法的典型實例——大整數乘法1.問題描述采用分治法設計一個有效的算法，計算兩個n位大整數的乘法。（n=2k,k=1,2,3....）。2.問題分析根據分治法的思想，可以將兩個大的整數乘法分而治之。將大整數按位數的一半分成兩個小整數，轉換成稍簡單的小整數乘法，再進行合并。上述的過程可以重復進行，直到得到最簡單的兩個1位數的乘法，從而解決上述問題。

3.4.2分治法的典型實例——大整數乘法3.4.2分治法的典型實例——大整數乘法3.算法設計BigIntMul(X,Y,n)輸入：大整數X，Y和位數n輸出：X與Y的乘積結果sx←sign(X),sy←sign(Y) //取X，Y的符號s←sx*sy //求出X×Y的符號ifs=0thenreturn0endifX←|X|,Y←|Y|ifn=1thenreturns*X*YendifA←X的左邊n/2位, B←X的右邊n/2位C←Y的左邊n/2位, D←Y的右邊n/2位m1←BigIntMul(A,C，n/2), m2←BigIntMul((A-B),(D-C)，n/2)m3←BigIntMul(B,D，n/2)S←m1*10^n+(m1+m2+m3)*10^(n/2)+m3returnS舉例:以計算3141×5247為例來說明。將3141分拆成31和41，5247分拆成52和47。然后計算31×52，-10×-5，41×47。當出現兩個數位數不等時，可以將位數小的高位補0再進行計算。如：-10×-5=10×05=(1×10+0)×(0×10+5)=1×0×100+(1×5+1×0+0×5)×10+0×5=0+50+0=50其他兩個個同理算出：31×52=1612，41×47=1927。帶入原來的算式得：3141×5247=16120000+(50+1612+1927)×100+1927=16480827。3.4.2分治法的典型實例——大整數乘法4.算法效率分析根據上述的計算過程得到遞推方程。改進前：根據主定理理論可得：改進后：根據主定理可得：

，有較大的改進。3.4.3分治法的典型實例——平面內最近點問題

3.4.3分治法的典型實例——平面內最近點問題

2.問題分析如果采用蠻力法，就需要遍歷平面上任意兩個點之間的距離，然后比較得出最小的值。很顯然其時間復雜度是O(n2)。那有沒有更快的方法呢？考慮分治法，如圖3.2所示，用一條垂直的直線l將整個平面中的點分為左半平面PL和右半平面PR兩部分，使得兩部分的點數近似相等。

3.4.3分治法的典型實例——平面內最近點問題將平面的點集一分為二PLPRP直線l

3.4.3分治法的典型實例——平面內最近點問題

3.4.4分治法的典型實例——選擇第k小問題

大小S3S4S1S2中位數組M

3.4.3分治法的典型實例——平面內最近點問題平面上最臨近點對算法MinDistance(P,X,Y)輸入：n()個點集合P，X,Y分別表示n個點的x,y坐標的值輸出：最近的兩個點以及距離ifn≤

3then直接計算n個點之間的最短距離endifSort(n,X,Y) //把所有的點按照橫坐標X排序

l←mid(X) //用一條豎直的線L將所有的點分成兩等份MinDistance(PL,XL,YL)d1←PL中最短距離MinDistance(PR,XR,YR)d2←PR中最短距離d←min(d1,d2)while(PL中的點andXL≥l-d)dowhile(PR中的點andXR≤l+d)doifdistance(XL,YL,XR,YR)<dthen存儲點對(XL,YL),(XR,YR)d←distance(XL,YL,XR,YR)endifendwhileendwhile該算法是遞歸算法，且里面有排序，為了提高效率，可以把排序操作放到遞歸算法的外面。另外在直線l兩邊距離不超過d的區域內檢查與所取點的距離是否小于d的點不超過7個即可。

3.4.3分治法的典型實例——平面內最近點問題

3.4.4分治法的典型實例——選擇第k小問題1.問題描述設A是含有n個元素的數組，從A中選出第k小的元素，其中1≤k≤n。所以選最小就是k=1；選最大就是k=n；選次大就是k=n-1；選中位數就是k=n/2。

3.4.4分治法的典型實例——選擇第k小問題

3.4.4分治法的典型實例——選擇第k小問題

計算機算法設計與分析第四章

動態規劃學習目標了解動態規劃法的基本概念。掌握動態規劃法的基本思想。掌握動態規劃法解決實際問題。4.1動態規劃的提出在現實生活中，有一類活動的過程，由于它的特殊性，可將過程分成若干個互相聯系的階段，在它的每一階段都需要作出決策，從而使整個過程達到最好的活動效果。當然，各個階段決策的選取不是任意確定的，它依賴于當前面臨的狀態，又影響以后的發展，當各個階段決策確定后，就組成一個決策序列，因而也就確定了整個過程的一條活動路線，如下圖所示。這種把一個問題看作是一個前后關聯具有鏈狀結構的多階段過程就稱為多階段決策過程，這種問題就稱為多階段決策問題。1狀態決策2狀態狀態決策n狀態狀態...決策4.1動態規劃的提出在多階段決策問題中，各個階段采取的決策，一般來說是與時間有關的，決策取決于當前的狀態，然后又會引起狀態的轉移，一個決策序列就是在不斷變化的狀態中依次產生出來的，故有動態的含義。因此，把處理它的方法稱為動態規劃方法。但是，一些與時間沒有關系的靜態規劃，如線性規劃、非線性規劃等問題，只要人為地引進時間因素，也可把它視為多階段決策問題，用動態規劃方法去處理。4.2動態規劃基本概念1.階段動態規劃方法求解的問題都屬于多階段決策問題。因此需要將所求問題劃分為若干個階段。把描述階段的變量稱為階段變量，用k來表示。在劃分階段時，要求劃分后的階段按照時間或空間特征是有序的，否則問題就無法求解。在下圖中，階段可以劃分為5個，即k=1,2,3,4,5。2.狀態每個階段所處的客觀條件稱為狀態，它描述了研究問題過程的中間狀況。狀態就是某階段的出發位置，既是該階段某支路的起點，又是前一階段某支路的終點。通常一個階段有若干狀態。在下圖中，第一階段只有狀態{A}，第二階段有狀態{B1，B2}，第三階段有狀態{C1，C2，C3，C4}。描述狀態的變量稱為狀態變量。通常用Sk表示第k階段的狀態變量。在圖中，S3={C1，C2，C3，C4}，該集合就稱為第三階段的可達狀態集。4.2動態規劃基本概念2.狀態這里的狀態必須滿足無后效性（馬爾可夫性），即某階段狀態一旦確定，就不受這個狀態以后決策的影響。也就是說，某狀態以后的過程不會影響以前的狀態，而只與當前狀態有關。4.2動態規劃基本概念

4.2動態規劃基本概念4.狀態轉移方程狀態轉移方程是確定從一個狀態轉移到另一個狀態的過程。給定第k階段的某個狀態變量sk，在選定好決策uk后，第k+1階段的狀態變量sk+1也就完全確定下來。這種由sk和uk確定sk+1的對應關系Tk就稱為狀態轉移方程，即sk+1=Tk(sk,uk)。4.2動態規劃基本概念5.指標函數和最優值函數指標函數是用來衡量所選定策略優劣的一種數量指標。它是定義在全過程和所有后部子過程上確定的數量函數。常用Vk,n表示。即Vk,n=Vk,n(sk,uk,sk+1,...,sn+1)，k=1,2,...,n。常見的指標函數的形式如下：（1）過程和它的任一子過程的指標是它所包含的各階段的指標的和。（2）過程和它的任一子過程的指標是它所包含的各階段的指標的乘積。4.2動態規劃基本概念5.指標函數和最優值函數指標函數的最優值，稱為最優值函數，記為fk(sk)。它表示從第k階段的狀態sk開始到第n階段的終止狀態的過程，采取最優策略所得到的指標函數值。在不同的問題中，指標函數的含義是不同的，它可能是距離、利潤、成本、產品的產量或資源消耗等。4.2動態規劃基本概念4.3動態規劃基本思想與優化原則動態規劃的基本思想可以總結為：（1）將多階段決策過程劃分階段，恰當的選取狀態變量、決策變量及定義最優指標函數，從而把問題化為一組同類型的子問題，然后逐個求解。（2）求解時從邊界條件開始，逆（或順）過程行進方向，逐段遞推尋優。在每個子問題求解時，都要使用前面已求出的子問題的最優結果，最后一個子問題的最優解，就是整個問題的最優解。（3）動態規劃的基本方程是遞推逐段求解的依據，一般的動態規劃的基本方程

4.3動態規劃基本思想與優化原則下面以例子來說明（3）k=2，狀態變量可以取2個狀態B1、B2，它們到達終點E需要通過C1、C2、C3或C4，同樣需要選擇一條最短的路徑。計算如下：（4）k=1，同理可以計算出從而從起點A到終點E的最短路徑為A-B2-C4-D3-E，最短距離為13。4.3動態規劃基本思想與優化原則優化原則（最優子結構性質）：一個最優決策序列的任何子序列本身一定是相對于子序列的初始和結束狀態的最優決策序列。一般來說，能用動態規劃求解的問題具有以下三個性質：（1）滿足最優子結構；（2）滿足無后效性；（3）有重疊的子問題。4.3動態規劃基本思想與優化原則動態規劃和分治法的區別：

分治法拆分的子問題只是求解過程類似，但問題本身是相互獨立的；而動態規劃法的子問題之間并不獨立，尤其是相鄰階段的子問題最優值函數是有依賴關系的，這就是所謂的有重疊的子問題。有重疊的子問題并非動態規劃法必須滿足的性質，但如果沒有這個性質，那么動態規劃法相比其他的算法不具備優越性。因此，在使用動態規劃法時，從邊界條件開始將某子問題的最優解求出并保存起來，然后利用它來求解依賴它的其他子問題，直到求出整個問題的解。4.3動態規劃基本思想與優化原則4.4.1動態規劃的典型實例——背包問題1.問題描述給定n種物品和一個背包。物品i的重量是wi，其價值為vi，背包的承重量為C。應如何選擇裝入背包的物品，使得裝入背包中的物品重量在不超過C的前提下，總價值最大？在第2章中，假定每件物品至多只能裝一個，所以所裝的第i件物品xi=0或1，是一個0-1背包問題。現在問題是每件物品可以裝多個，但仍然不能分割只裝一部分，此時就是一個整數規劃問題。2.問題分析（1）不難驗證該背包問題滿足優化原則和無后效性，可以使用動態規劃法求解。（2）按照所裝物品種類來劃分階段，規定第i階段可以選擇新裝進第i件物品，比如第1階段只能選擇裝第1種物品，第2階段可以選擇裝前兩種物品，……，第k階段可以選擇裝前k種物品，以此下去，最后一階段可以選擇裝入全部的物品，此時的最優解就是背包問題的解。4.4.1動態規劃的典型實例——背包問題

4.4.1動態規劃的典型實例——背包問題3.實例計算：設v1=1，v2=3，v3=5，v4=9；w1=2，w2=3，w3=4，w4=7;C=10。構建遞推計算的備忘錄，根據優化函數計算過程如下：現在還有一個問題是如何得到這個最大價值12，也就是如何裝物品。4.4.1動態規劃的典型實例——背包問題ky1234567891010112233445201334667993013556810101140135569101012

4.4.1動態規劃的典型實例——背包問題

4.4.1動態規劃的典型實例——背包問題ky1234567891010111111111201222222223012333333340123334344

4.4.2動態規劃的典型實例——最長公共子序列問題

4.4.2動態規劃的典型實例——最長公共子序列問題

4.4.2動態規劃的典型實例——最長公共子序列問題

4.4.2動態規劃的典型實例——最長公共子序列問題3.算法設計算法LCS(X,Y,m,n) else//最后一個字符不同時 ifC[i-1,j]>C[i,j-1]then //滿足情況（2） C[i,j]←C[i-1,j] B[i,j]←‘↑’ endif else //滿足情況（3） C[i,j]←C[i,j-1] B[i,j]←‘←’ end end endforendfor

4.4.2動態規劃的典型實例——最長公共子序列問題

4.4.2動態規劃的典型實例——最長公共子序列問題

4.4.2動態規劃的典型實例——最長公共子序列問題4.實例計算：設X=<1,3,5,4,2,6,7,8>，Y=<1,4,8,6,7,5>，其中m=8，n=6。構建遞推計算的備忘錄，根據優化函數計算過程如下：4.4.2動態規劃的典型實例——最長公共子序列問題ij0123456000000001011111120111111301111124012222250122222601223337012234480123344

4.4.2動態規劃的典型實例——最長公共子序列問題根據以上遞推得下表：下面給出求解的追蹤過程：B[8,6]→B[8,5]→B[7,5]→B[6,4]→B[5,3]→B[5,2]→B[4,2]→B[3,1]→B[2,1]→B[1,1]，其中B[7,5]，B[6,4]，B[4,2]，B[1,1]的值為↖，也就是第①種情況，此時應該將對應的字符加入最長公共子序列中，即為<1,4,6,7>。4.4.2動態規劃的典型實例——最長公共子序列問題ij1234561↖←←←←←2↑←←←←←3↑←←←←↖4↑↖←←←←5↑↑←←←←6↑↑←↖←←7↑↑←↑↖←8↑↑↖←↑←6.算法效率分析在算法LCS中，兩重for循環時間復雜度為，在算法TrackSolution中，最多標記m+n次，時間復雜度為。因此，綜合起來整個算法的時間復雜度為，它從蠻力法的降至，可見在求解這個問題中動態規劃法的優越性。

4.4.2動態規劃的典型實例——最長公共子序列問題

4.4.3動態規劃的典型實例——最大字段和問題

4.4.3動態規劃的典型實例——最大字段和問題

4.4.3動態規劃的典型實例——最大字段和問題

4.4.3動態規劃的典型實例——最大字段和問題3.算法設計算法MaxConSubSeqSum_DP(A[],n)輸入：序列A[1..n]輸出：最大子段和maxSum，對應的開始和結束位置begin和endmaxSum←-INFb←

0//b是前一個最大子段和fori←