算法-分治法課件

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

述

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

分治法是最著名的算法設(shè)計(jì)技術(shù)。1/562023/8/1分治法第4章分治法4.1概述2023/10/2分治法4.1概

述

4.1.1分治法的設(shè)計(jì)思想4.1.2數(shù)字旋轉(zhuǎn)方陣2/562023/8/1分治法4.1概述4.1.1分治2023/10/2分治法

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

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

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

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

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

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

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

子問題1的解

子問題2的解

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

原問題的解

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

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

N(1

N

10)數(shù)字旋轉(zhuǎn)方陣。2019181716213231301522333629142334352813242526271278910116

6的旋轉(zhuǎn)方陣8/562023/8/1分治法4.1.2數(shù)字旋轉(zhuǎn)方陣問題：輸出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劃分為兩個(gè)長度相等的子序列r1,…,rn/2和rn/2＋1,…,rn；（2）求解子問題：分別對(duì)這兩個(gè)子序列進(jìn)行排序，得到兩個(gè)有序子序列；（3）合并：將這兩個(gè)有序子序列合并成一個(gè)有序序列。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——?dú)w并排序

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

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

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

}}C++描述12/562023/8/1分治法算法4.3——?dú)w并排序C++2023/10/2分治法

二路歸并排序的合并步的時(shí)間復(fù)雜性為O(n)，所以，二路歸并排序算法存在如下遞推式：可得二路歸并排序的時(shí)間代價(jià)是O(nlog2n)。二路歸并排序在合并過程中需要與原始記錄序列同樣數(shù)量的存儲(chǔ)空間，因此其空間復(fù)雜性為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)

//若第一個(gè)子序列沒處理完，則進(jìn)行收尾處理

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

//若第二個(gè)子序列沒處理完，則進(jìn)行收尾處理

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

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

ri-1]

ri[ri+1……

rn]

均≤ri

軸值均≥ri

位于最終位置

歸并排序按照記錄在序列中的位置對(duì)序列進(jìn)行劃分，快速排序按照記錄的值對(duì)序列進(jìn)行劃分。16/562023/8/1分治法[r1……ri-1]2023/10/2分治法以第一個(gè)記錄作為軸值，對(duì)待排序序列進(jìn)行劃分的過程為：（1）初始化：取第一個(gè)記錄作為基準(zhǔn)，設(shè)置兩個(gè)參數(shù)i，j；（2）右側(cè)掃描過程：（3）左側(cè)掃描過程：（4）重復(fù)（2）（3）步，直到i與j指向同一位置，即基準(zhǔn)記錄最終的位置。172023/8/1分治法以第一個(gè)記錄作為軸值，對(duì)待排序序列進(jìn)行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--；//右側(cè)掃描

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

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

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

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

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

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

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

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

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

}}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)

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

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

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

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

4.3.1最大子段和問題

4.3.2棋盤覆蓋問題補(bǔ)充：

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

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

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

4.3.1最大子段和問題

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

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

…,an)，則：

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

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

…,an的最大子段和；③

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

，則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最大子段和橫跨兩個(gè)子序列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);//對(duì)應(yīng)情況①，遞歸求解

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

//以下對(duì)應(yīng)情況③，先求解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;//計(jì)算情況③的最大子段和

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

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

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

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

在一個(gè)2k×2k

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

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

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

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

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

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

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

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

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

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

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

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

4.4.2

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

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

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

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

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

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

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

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

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

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

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

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

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

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