算法-分治法課件

2023/10/2分治法第4章分治法4.1概

述

4.2排序問題中的分治法4.3組合問題中的分治法4.4幾何問題中的分治法

分治法是最著名的算法設計技術。1/562023/8/1分治法第4章分治法4.1概述2023/10/2分治法4.1概

述

4.1.1分治法的設計思想4.1.2數字旋轉方陣2/562023/8/1分治法4.1概述4.1.1分治2023/10/2分治法

將一個難以直接解決的大問題，劃分成一些規(guī)模較小的子問題，分別求解各個子問題，再合并子問題的解得到原問題的解。4.1.1分治法的設計思想

如果子問題的規(guī)模仍然不夠小，可繼續(xù)分解下去。

3/562023/8/1分治法將一個難以直接解決的大2023/10/2分治法分治法的求解過程：分-治-合

（1）劃分：把規(guī)模為n的原問題劃分為k個規(guī)模較小的子問題，并盡量使這k個子問題的規(guī)模大致相同。

（2）求解子問題：各子問題的解法與原問題的解法通常是相同的，可以用遞歸的方法求解各個子問題。

（3）合并：把各個子問題的解合并起來，分治算法的有效性很大程度上依賴于合并的實現。4/562023/8/1分治法分治法的求解過程：分-治-合2023/10/2分治法2.獨立子問題：各子問題之間相互獨立。1.平衡子問題：最好使子問題的規(guī)模大致相同。啟發(fā)式規(guī)則：5/562023/8/1分治法2.獨立子問題：各子問題之間相互獨立2023/10/2分治法

子問題1的規(guī)模是n/2

子問題1的解

子問題2的解

子問題2的規(guī)模是n/2

原問題的解

原問題的規(guī)模是n分治法的典型情況6/562023/8/1分治法子問題1子問題1的解子問2023/10/2分治法例：計算an，應用分治技術得到如下計算方法：3432328131319313193333分解問題求解每個子問題合并子問題的解

不是所有的分治法都比簡單的蠻力法更有效。分析時間性能??éù?íì>′==1122naanaannn如果如果7/562023/8/1分治法例：計算an，應用分治技術得到如下計算2023/10/2分治法4.1.2數字旋轉方陣問題：輸出N

N(1

N

10)數字旋轉方陣。2019181716213231301522333629142334352813242526271278910116

6的旋轉方陣8/562023/8/1分治法4.1.2數字旋轉方陣問題：輸出N2023/10/2分治法4.2排序問題中的分治法4.2.1歸并排序4.2.2快速排序92023/8/1分治法4.2排序問題中的分治法4.2.12023/10/2分治法4.3.1歸并排序

二路歸并排序的分治策略是：（1）劃分：將待排序序列r1,r2,…,rn劃分為兩個長度相等的子序列r1,…,rn/2和rn/2＋1,…,rn；（2）求解子問題：分別對這兩個子序列進行排序，得到兩個有序子序列；（3）合并：將這兩個有序子序列合并成一個有序序列。10/562023/8/1分治法4.3.1歸并排序2023/10/2分治法

r1……rn/2

rn/2＋1……rn

劃分r‘1<……<r’n/2r’n/2＋1<……<r’n

遞歸處理r''1<……<r''n/2<r''n/2＋1<……<r''n

合并解

舉例：8326715411/562023/8/1分治法r1……rn/22023/10/2分治法

算法4.3——歸并排序

voidMergeSort(intr[],ints,intt){intm,r1[1000];if(s==t)return;else{m=(s+t)/2;Mergesort(r,s,m);//歸并排序前半個子序列

Mergesort(r,m+1,t);//歸并排序后半個子序列

Merge(r,r1,s,m,t);//合并兩個已排序的子序列for(inti=s;i<=t;i++)//將有序序列傳回數組r中r[i]=r1[i];

}}C++描述12/562023/8/1分治法算法4.3——歸并排序C++2023/10/2分治法

二路歸并排序的合并步的時間復雜性為O(n)，所以，二路歸并排序算法存在如下遞推式：可得二路歸并排序的時間代價是O(nlog2n)。二路歸并排序在合并過程中需要與原始記錄序列同樣數量的存儲空間，因此其空間復雜性為O(n)。

?íì>+==1)2(211)(nnnTnnT13/562023/8/1分治法二路歸并排序的合并步2023/10/2分治法算法4.4——合并有序子序列

voidMerge(intr[],intr1[],ints,intm,intt){i=s;j=m+1;k=s;while(i<=m&&j<=t){if(r[i]<=r[j])r1[k++]=r[i++];//取r[i]和r[j]中較小者放入r1[k]elser1[k++]=r[j++];}if(i<=m)while(i<=m)

//若第一個子序列沒處理完，則進行收尾處理

r1[k++]=r[i++];elsewhile(j<=t)

//若第二個子序列沒處理完，則進行收尾處理

r1[k++]=r[j++];}C++描述14/562023/8/1分治法算法4.4——合并有序子序列C++描述2023/10/2分治法4.3.2快速排序

（2）求解子問題：分別對劃分后的每一個子序列遞歸處理；（3）合并：由于對子序列r1…ri-1和ri+1…rn的排序是就地進行的，所以合并不需要執(zhí)行任何操作?？焖倥判虻姆种尾呗允牵海?）劃分：選定一個記錄作為軸值，以軸值為基準將整個序列劃分為兩個子序列；15/562023/8/1分治法4.3.2快速排序（2）求解子問2023/10/2分治法[r1……

ri-1]

ri[ri+1……

rn]

均≤ri

軸值均≥ri

位于最終位置

歸并排序按照記錄在序列中的位置對序列進行劃分，快速排序按照記錄的值對序列進行劃分。16/562023/8/1分治法[r1……ri-1]2023/10/2分治法以第一個記錄作為軸值，對待排序序列進行劃分的過程為：（1）初始化：取第一個記錄作為基準，設置兩個參數i，j；（2）右側掃描過程：（3）左側掃描過程：（4）重復（2）（3）步，直到i與j指向同一位置，即基準記錄最終的位置。172023/8/1分治法以第一個記錄作為軸值，對待排序序列進行2023/10/2分治法13652750384955jijj13652750384955jiii13652750384955ijjj一次劃分示例182023/8/1分治法13652750384955jijj12023/10/2分治法算法4.5——一次劃分

intPartition(intr[],intfirst,intend){i=first;j=end;//初始化

while(i<j){

while(i<j&&r[i]<=r[j])j--；//右側掃描

if(i<j){r[i]←→r[j];//將較小記錄交換到前面

i++;}while(i<j&&r[i]<=r[j])i++；//左側掃描

if(i<j){r[j]←→r[i];//將較大記錄交換到后面

j--;}}retutni;//i為軸值記錄的最終位置

}C++描述192023/8/1分治法算法4.5——一次劃分C++描述192023/10/2分治法

以軸值為基準將待排序序列劃分為兩個子序列后，對每一個子序列分別遞歸進行排序。132750384955jiij1365275038495565202023/8/1分治法以軸值為基準將待排序序2023/10/2分治法算法4.6——快速排序

voidQuickSort(intr[],intfirst,intend){if(first<end){pivot=Partition(r,first,end);//問題分解，pivot是軸值在序列中的位置

QuickSort(r,first,pivot-1);//遞歸地對左側子序列進行快速排序

QuickSort(r,pivot+1,end);//遞歸地對右側子序列進行快速排序

}}C++描述212023/8/1分治法算法4.6——快速排序C++描述212023/10/2分治法T(n)=2T(n/2)＋n=2(2T(n/4)＋n/2)＋n＝4T(n/4)＋2n=4(2T(n/8)＋n/4)＋2n＝8T(n/8)＋3n………

=nT(1)＋nlog2n＝O(nlog2n)

因此，時間復雜度為O(nlog2n)。最好情況:每次劃分后把待劃分區(qū)間劃分為長度相等的兩個子序列。在具有n個記錄的序列中，一次劃分需要對整個待劃分序列掃描一遍，則所需時間為O(n)。設T(n)是對n個記錄的序列進行排序的時間，則有：222023/8/1分治法T(n)=2T(n/2)＋n最好情況2023/10/2分治法因此，時間復雜度為O(n2)。

最壞情況：待排序記錄序列正序或逆序。此時，必須經過n-1次遞歸調用，而且第i趟劃分需要經過n-i次關鍵碼的比較，因此，總的比較次數為：232023/8/1分治法因此，時間復雜度為O(n2)。2023/10/2分治法平均情況：設基準記錄的關鍵碼第k小(1≤k≤n)，則有：

這是快速排序的平均時間性能，可以用歸納法證明，其數量級也為O(nlog2n)。

快速排序的空間復雜性如何?24/562023/8/1分治法平均情況：設基準記錄的關鍵碼第k小(12023/10/2分治法4.3組合問題中的分治法

4.3.1最大子段和問題

4.3.2棋盤覆蓋問題補充：

循環(huán)賽日程安排問題

25/562023/8/1分治法4.3組合問題中的分治法4.3.2023/10/2分治法

給定由n個整數組成的序列(a1,a2,…,an)，最大子段和問題要求該序列形如的最大值(1≤i≤j≤n)。當序列中所有整數均為負整數時，其最大子段和為0。如，序列(-20,11,-4,13,-5,-2)的最大子段和為：

4.3.1最大子段和問題

26/562023/8/1分治法給定由n個整數組成的序列(a2023/10/2分治法

最大子段和問題的分治策略是：（1）劃分：按照平衡子問題的原則，將序列(a1,a2,…,an)劃分成長度相同的兩個子序列(a1,…,a)和(a＋1,

…,an)，則：

先考慮最大子段和問題的簡單算法27/562023/8/1分治法最大子段和問題的分治策略2023/10/2分治法①a1,…,an的最大子段和＝a1,…,a的最大子段和；②

a1,…,an的最大子段和＝a＋1,

…,an的最大子段和；③

a1,…,an的最大子段和＝，且（2）求解子問題：對于劃分階段的情況①和②可遞歸求解，情況③需要分別計算，

，則s1+s2為情況③的最大子段和。（3）合并：比較在劃分階段的三種情況下的最大子段和，取三者之中的較大者為原問題的解。282023/8/1分治法①a1,…,an的最大子段和＝a2023/10/2分治法a1……ai…amid

amid+1…aj……an劃分leftsum

rightsum遞歸處理a1……ai…amid

amid+1…aj……an最大子段和橫跨兩個子序列sum不能遞歸處理max{leftsum,sum,rightsum}合并解292023/8/1分治法a1……ai…amid2023/10/2分治法算法4.7——最大子段和問題

intMaxSum(inta[],intleft,intright){sum=0;if(left==right){//如果序列長度為1，直接求解

if(a[left]>0)sum=a[left];elsesum=0;}else{center=(left+right)/2;//劃分

leftsum=MaxSum(a,left,center);//對應情況①，遞歸求解

rightsum=MaxSum(a,center+1,right);//對應情況②，遞歸求解C++描述302023/8/1分治法算法4.7——最大子段和問題C++描述2023/10/2分治法s1=0;lefts=0;

//以下對應情況③，先求解s1for(i=center;i>=left;i--){lefts+=a[i];if(lefts>s1)s1=lefts;}s2=0;rights=0;//再求解s2for(j=center+1;j<=right;j++){rights+=a[j];if(rights>s2)s2=rights;}sum=s1+s2;//計算情況③的最大子段和

if(sum<leftsum)sum=leftsum;//合并，在sum、leftsum和rightsum中取較大者

if(sum<rightsum)sum=rightsum;}returnsum;}31/562023/8/1分治法s1=0;lefts2023/10/2分治法

算法的時間性能：對應劃分得到的情況①和②，需要分別遞歸求解，對應情況③，兩個并列for循環(huán)的時間復雜性是O(n)，所以，存在如下遞推式：

從而可得算法4.7的時間復雜性為O(nlog2n)。322023/8/1分治法算法的時間性能：對應劃2023/10/2分治法4.3.2棋盤覆蓋問題

在一個2k×2k

（k≥0）個方格組成的棋盤中，恰有一個方格與其他方格不同，稱該方格為特殊方格。棋盤覆蓋問題要求用圖（b）所示的4種不同形狀的L型骨牌覆蓋給定棋盤上除特殊方格以外的所有方格，且任何2個L型骨牌不得重疊覆蓋。(a)k=2時的一種棋盤(b)4種不同形狀的L型骨牌332023/8/1分治法4.3.2棋盤覆蓋問題2023/10/2分治法

分治法求解棋盤覆蓋問題的技巧在于劃分棋盤，使劃分后的子棋盤的大小相同，并且每個子棋盤均包含一個特殊方格，從而將原問題分解為規(guī)模較小的棋盤覆蓋問題。

k>0時，可將2k×2k的棋盤劃分為4個2k-1×2k-1的子棋盤，這樣劃分后，由于原棋盤只有一個特殊方格，所以，這4個子棋盤中只有一個子棋盤包含該特殊方格，其余3個子棋盤中沒有特殊方格。

為了將這3個沒有特殊方格的子棋盤轉化為特殊棋盤，以便采用遞歸方法求解，可以用一個L型骨牌覆蓋這3個較小棋盤的會合處，從而將原問題轉化為4個較小規(guī)模的棋盤覆蓋問題。遞歸地使用這種劃分策略，直至將棋盤分割為1×1的子棋盤。342023/8/1分治法分治法求解棋盤覆蓋問題的技巧在2023/10/2分治法2k-1×2k-12k-1×2k-12k-1×2k-12k-1×2k-1(a)棋盤分割(b)構造相同子問題35/562023/8/1分治法2k-1×2k-12k-1×2k-122023/10/2分治法

設T(k)是覆蓋一個2k×2k棋盤所需時間，從算法的劃分策略可知，T(k)滿足如下遞推式：

解此遞推式可得T(k)=O(4k)。由于覆蓋一個2k×2k棋盤所需的骨牌個數為(4k-1)/3，所以，算法4.8是一個在漸進意義下的最優(yōu)算法。

362023/8/1分治法設T(k)是覆蓋一個2k×2k2023/10/2分治法補充：

循環(huán)賽日程安排問題

設有n=2k個選手要進行網球循環(huán)賽，要求設計一個滿足以下要求的比賽日程表：（1）每個選手必須與其他n-1個選手各賽一次；（2）每個選手一天只能賽一次。

按此要求，可將比賽日程表設計成一個n行n-1列的二維表，其中，第i行第j列表示和第i個選手在第j天比賽的選手。37/562023/8/1分治法補充：循環(huán)賽日程安排問題2023/10/2分治法按照分治的策略，可將所有參賽的選手分為兩部分，n＝2k個選手的比賽日程表就可以通過為n/2＝2k-1個選手設計的比賽日程表來決定。遞歸地執(zhí)行這種分割，直到只剩下2個選手時，比賽日程表的制定就變得很簡單：只要讓這2個選手進行比賽就可以了。38/562023/8/1分治法按照分治的策略，可將所有參賽的選手分為2023/10/2分治法

顯然，這個求解過程是自底向上的迭代過程。具有多個選手的情況可以依此類推。

(b)2k(k=2)個選手比賽(c)2k(k=3)個選手比賽加4加2(a)2k(k=1)個選手比賽122112213443344312211234214334124321567865877856876556786587785687651234214334124321392023/8/1分治法顯然，這個求解過程是自底向上的2023/10/2分治法4.4幾何問題中的分治法4.4.1最近對問題

4.4.2

凸包問題（略）402023/8/1分治法4.4幾何問題中的分治法4.4.12023/10/2分治法4.4.1最近對問題

設p1=(x1,y1),p2=(x2,y2),…,pn=(xn,yn)是平面上n個點構成的集合S，最近對問題就是找出集合S中距離最近的點對。

蠻力法求解時間性能為O(n2)。一維情況下排序后求解，效率可提高到O(nlogn)。二維情況？

最接近點對可能多于一對。為簡單起見，只找出其中的一對作為問題的解。41/562023/8/1分治法4.4.1最近對問題2023/10/2分治法劃分：將集合S分成兩個子集S1和S2，每個子集中有n/2個點。

在每個子集中遞歸地求其最接近的點對，在求出每個子集的最接近點對后，在合并步分兩種情況，1集合S中最接近的兩個點都在子集S1或S2中，則問題很容易解決，2這兩個點分別在S1和S2中，問題比較復雜。42/562023/8/1分治法劃分：將集合S分成兩個子集S1和2023/10/2分治法求解子問題：先考慮一維的情形。S中的點退化為x軸上的n個點x1,x2,…,xn。用x軸上的某個點m將S劃分為兩個集合S1和S2，并且S1和S2含有點的個數相同。432023/8/1分治法求解子問題：先考慮一維的情形。2023/10/2分治法S1S2p2p1p3q3q1q2m

遞歸地在S1和S2上求出最接近點對(p1,p2)和(q1,q2)，如果集合S中的最接近點對都在子集S1或S2中，則d=min{(p1,p2),(q1,q2)}即為所求如果集合S中的最接近點對分別在S1和S2中，則一定是(p3,q3)，其中，p3是子集S1中的最大值，q3是子集S2中的最小值。442023/8/1分治法S1S2p2p1p3q3q1q2m2023/10/2分治法

按這種分治策略求解最近對問題的算法效率取決于劃分點m的選取，一個基本的要求是要遵循平衡子問題的原則。

如果選取m=(max{S}+min{S})/2，則有可能因集合S中點分布的不均勻而造成子集S1和S2的不平衡，如果用S中各點坐標的中位數（即S的中值）作為分割點，則會得到一個平衡的分割點m，使得子集S1和S2中有個數大致相同的點。45/562023/8/1分治法按這種分治策略求解最近2023/10/2分治法下面考慮二維的情形，此時S中的點為平面上的點。

選取垂直線x=m來作為分割線，其中，m為S中各點x坐標的中位數。由此將S分割為兩個子集S1={p∈S|xp≤m}和S2={q∈S|xq＞m}。此時，S1和S2包含點的個數大致相同。462023/8/1分治法下面考慮二維的情形，此時S中的點為平面2023/10/2分治法

遞歸地在S1和S2上求解最近對問題，分別得到S1中的最近距離d1和S2中的最近距離d2，令d=min(d1,d2)，若S的最近對(p,q)之間的距離小于d，則p和q必分屬于S1和S2。

不妨設p∈S1，q∈S2，則p和q距直線x=m的距離均小于d，所以，可以將求解限制在以x=m為中心、寬度為2d的垂直帶P1和P2中，垂直帶之外的任何點對之間的距離都一定大于d。

472023/8/1分治法遞歸地在S1和S2上求解最近對2023/10/2分治法x=mddd2d1S1S2pq

最近對問題的分治思想P1P2S1={p∈S|xp≤m}S2={q∈S|xq＞m}482023/8/1分治法x=mddd2d1S1S2pq2023/10/2分治法x=mddp(a)包含點q的d×2d的矩形區(qū)域(b)最壞情況下需要檢查的6個點P1P22dx=mddpP1P22d

對于點p∈P1，需要考察P2中的各個點和點p之間的距離是否小于d，顯然，P2中這樣點的y軸坐標一定位于區(qū)間[y-d,y+d]之間，而且，這樣的點不會超過6個