算法設(shè)計(jì)與分析-王紅梅-第二版-第4章-分治法_第1頁(yè)
算法設(shè)計(jì)與分析-王紅梅-第二版-第4章-分治法_第2頁(yè)
算法設(shè)計(jì)與分析-王紅梅-第二版-第4章-分治法_第3頁(yè)
算法設(shè)計(jì)與分析-王紅梅-第二版-第4章-分治法_第4頁(yè)
算法設(shè)計(jì)與分析-王紅梅-第二版-第4章-分治法_第5頁(yè)
已閱讀5頁(yè),還剩80頁(yè)未讀 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

第4章 分治法算法設(shè)計(jì)與分析—本科生課程DesignandAnalysisofAlgorithm海南大學(xué)信息科學(xué)技術(shù)學(xué)院CollegeofInformationScienceandTechnology,HainanUniversity2024/11/30DivideandConquerMethod2本章要點(diǎn)4.1概

4.2排序問(wèn)題中的分治法4.3組合問(wèn)題中的分治法4.4幾何問(wèn)題中的分治法閱讀材料

遞歸函數(shù)的執(zhí)行過(guò)程2024/11/30DivideandConquerMethod3教學(xué)重點(diǎn)分治法的設(shè)計(jì)思想,各種經(jīng)典問(wèn)題的分治思想教學(xué)難點(diǎn)幾何問(wèn)題的分治算法教學(xué)內(nèi)容及目標(biāo)知識(shí)點(diǎn)教學(xué)要求了解理解掌握熟練掌握分治法設(shè)計(jì)思想√歸并排序和快速排序√最大子段和問(wèn)題√棋盤覆蓋問(wèn)題√最近對(duì)問(wèn)題√凸包問(wèn)題√學(xué)習(xí)目標(biāo)2024/11/30DivideandConquerMethod44.1.1分治法的設(shè)計(jì)思想

4.1.2分治法的求解過(guò)程概述2024/11/30DivideandConquerMethod5

將一個(gè)難以直接解決的大問(wèn)題,劃分成一些規(guī)模較小的子問(wèn)題,以各個(gè)擊破,分而治之。更一般地說(shuō),將要求解的原問(wèn)題劃分成k個(gè)較小規(guī)模的子問(wèn)題,對(duì)這k個(gè)子問(wèn)題分別求解。如果子問(wèn)題的規(guī)模仍然不夠小,則再將每個(gè)子問(wèn)題劃分為k個(gè)規(guī)模更小的子問(wèn)題,如此分解下去,直到問(wèn)題規(guī)模足夠小,很容易求出其解為止,再將子問(wèn)題的解合并為一個(gè)更大規(guī)模的問(wèn)題的解,自底向上逐步求出原問(wèn)題的解。分治法的設(shè)計(jì)思想:

概述-分治法思想2024/11/30DivideandConquerMethod62.獨(dú)立子問(wèn)題:各子問(wèn)題之間相互獨(dú)立,這涉及到分治法的效率,如果各子問(wèn)題不是獨(dú)立的,則分治法需要重復(fù)地解公共的子問(wèn)題。1.平衡子問(wèn)題:最好使子問(wèn)題的規(guī)模大致相同。也就是將一個(gè)問(wèn)題劃分成大小相等的k個(gè)子問(wèn)題(通常k=2、4,…),這種使子問(wèn)題規(guī)模大致相等的做法是出自一種平衡(Balancing)子問(wèn)題的思想,它幾乎總是比子問(wèn)題規(guī)模不等的做法要好。啟發(fā)式規(guī)則:概述-分治法思想2024/11/30DivideandConquerMethod7

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

子問(wèn)題1的解

子問(wèn)題2的解

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

原問(wèn)題的解

原問(wèn)題的規(guī)模是n分治法的典型情況概述-分治法思想2024/11/30DivideandConquerMethod8

一般來(lái)說(shuō),分治法的求解過(guò)程由以下三個(gè)階段組成:(1)劃分:既然是分治,當(dāng)然要把規(guī)模為n的原問(wèn)題劃分為k個(gè)規(guī)模較小的子問(wèn)題,并盡量使這

k個(gè)子問(wèn)題的規(guī)模大致相同。(2)求解子問(wèn)題:各子問(wèn)題的解法與原問(wèn)題的解法通常是相同的,可以用遞歸的方法求解各個(gè)子問(wèn)題,有時(shí)遞歸處理也可以用循環(huán)來(lái)實(shí)現(xiàn)。(3)合并:把各個(gè)子問(wèn)題的解合并起來(lái),合并的代價(jià)因情況不同有很大差異,分治算法的有效性很大程度上依賴于合并的實(shí)現(xiàn)。概述-分治法的求解過(guò)程2024/11/30DivideandConquerMethod9概述-分治法的求解過(guò)程分治法的一般過(guò)程

1DivideConquer(P)//求解規(guī)模為n的問(wèn)題P2{3if(P的規(guī)模足夠小)

直接求解P;

分解為k個(gè)子問(wèn)題P1,P2,…,Pk;4for(i=1;i<=k;i++)5yi=DivideConquer(P);//解各子問(wèn)題,通常采用遞歸

6returnMerge(y1,y2,…,yk);//將各子問(wèn)題的解合并為原問(wèn)題的解

7}C++描述

例:計(jì)算an,應(yīng)用分治技術(shù)得到如下計(jì)算方法:3432328131319313193333分解問(wèn)題求解每個(gè)子問(wèn)題合并子問(wèn)題的解

不是所有的分治法都比簡(jiǎn)單的蠻力法更有效。時(shí)間性能O(nlog2n)而蠻力法的時(shí)間性能為O(n)??éù?íì>*==1122naanaannn如果如果2024/11/30DivideandConquerMethod114.1.1分治法的設(shè)計(jì)思想4.1.2一個(gè)簡(jiǎn)單的例子——數(shù)字旋轉(zhuǎn)方陣概述2024/11/30DivideandConquerMethod12[問(wèn)題]輸出如圖4.3(a)所示N*N(1≤N≤10)的數(shù)字旋轉(zhuǎn)方陣[思路]用二維數(shù)組表示方陣,從外層向里層填數(shù),如圖(b)所示,將每一層的填數(shù)過(guò)程分為ABCD四個(gè)區(qū)域。每填一層size減2,終止條件是size≤1。數(shù)字旋轉(zhuǎn)方陣2024/11/30DivideandConquerMethod13算法4.1:數(shù)字旋轉(zhuǎn)方陣Full輸入:當(dāng)前層左上角要填的數(shù)字number,左上角的坐標(biāo)begin,方陣的階數(shù)size輸出:數(shù)字旋轉(zhuǎn)方陣如果size=0,則算法結(jié)束;如果size=1,則data[begin][begin]=number,算法結(jié)束;初始化行、列下標(biāo)i=begin,j=begin;重復(fù)下述操作size-1次,填寫區(qū)域AData[i][j]=number;number++;i++;數(shù)字旋轉(zhuǎn)方陣2024/11/30DivideandConquerMethod14重復(fù)下述操作size-1次,填寫區(qū)域BData[i][j]=number;number++;j++;重復(fù)下述操作size-1次,填寫區(qū)域CData[i][j]=number;number++;i--;重復(fù)下述操作size-1次,填寫區(qū)域DData[i][j]=number;number++;j--;遞歸調(diào)用函數(shù)Full在size-2階方陣中左上角begin+1處從數(shù)字number開始填數(shù)數(shù)字旋轉(zhuǎn)方陣2024/11/30DivideandConquerMethod15[算法分析]填寫n階方陣,四個(gè)區(qū)域由4個(gè)循環(huán)實(shí)現(xiàn),每個(gè)循環(huán)均執(zhí)行n-1,然后執(zhí)行遞歸調(diào)用,填寫n-2階方陣。遞推式:數(shù)字旋轉(zhuǎn)方陣???íì=T(n-2)+4(n-1)當(dāng)n=0時(shí)0nT1)(當(dāng)n=1時(shí)當(dāng)n>1時(shí)設(shè)n為偶數(shù),用擴(kuò)展遞歸技術(shù)解此遞推式,得T(n)=T(n-2)+4(n-1)=T(n-4)+4(n-3)+4(n-1) =T(0)+…+4(n-5)+4(n-3)+4(n-1)=O(n2)2024/11/30DivideandConquerMethod16本章要點(diǎn)4.1概

4.2排序問(wèn)題中的分治法4.3組合問(wèn)題中的分治法4.4幾何問(wèn)題中的分治法閱讀材料

遞歸函數(shù)的執(zhí)行過(guò)程2024/11/30DivideandConquerMethod17排序問(wèn)題中的分治法4.2.1歸并排序4.2.2快速排序2024/11/30DivideandConquerMethod18歸并排序

二路歸并排序的分治策略是:(1)劃分:將待排序序列r1,r2,…,rn劃分為兩個(gè)長(zhǎng)度相等的子序列r1,…,rn/2和rn/2+1,…,rn;(2)求解子問(wèn)題:分別對(duì)這兩個(gè)子序列進(jìn)行排序,得到兩個(gè)有序子序列;(3)合并:將這兩個(gè)有序子序列合并成一個(gè)有序序列。4.2.1歸并排序2024/11/30DivideandConquerMethod19

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

合并解

4.2.1歸并排序2024/11/30DivideandConquerMethod20[想法]首先將序列劃分為兩個(gè)子序列,如子序列長(zhǎng)度為1,則劃分結(jié)束,否則繼續(xù)執(zhí)行劃分,結(jié)果將具有n個(gè)待排序的記錄序列劃分為n個(gè)長(zhǎng)度為1的有序子序列;然后兩兩合并,得到n/2個(gè)長(zhǎng)度為2的有序子序列,再進(jìn)行兩兩合并…直到得到一個(gè)長(zhǎng)度為n的有序序列。4.2.1歸并排序2024/11/30DivideandConquerMethod21

算法4.3——?dú)w并排序

voidMergeSort(intr[],intr1[],ints,intt)//r[]—原序列數(shù)組,r1[]—?dú)w并后序列數(shù)組

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

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

Merge(r1,r,s,m,t);//合并兩個(gè)已排序的子序列

}}C++描述4.2.1歸并排序r[s],…,r[m]r[m+1],…,r[t]2024/11/30DivideandConquerMethod22算法4.4——合并有序子序列

voidMerge(intr[],intr1[],ints,intm,intt)

{//i,j分別指向兩個(gè)待合并的有序子序列,k指向最終有序序列的當(dāng)前記錄

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++描述4.2.1歸并排序ijr[s],…,r[m]r[m+1],…,r[t]kr1[s],…,r1[m],r1[m+1],…,r1[t]2024/11/30DivideandConquerMethod23

二路歸并排序的合并步驟的時(shí)間復(fù)雜性為O(n),所以,二路歸并排序算法存在如下遞推式:根據(jù)2.1.5節(jié)的通用分治遞推定理,二路歸并排序的時(shí)間代價(jià)是O(nlog2n)。?íì>+==2)2(221)(nnnTnnT4.2.1歸并排序2024/11/30DivideandConquerMethod24(2)求解子問(wèn)題:分別對(duì)劃分后的每一個(gè)子序列遞歸處理;(3)合并:由于對(duì)子序列r1…ri-1和ri+1…rn的排序是就地進(jìn)行的,所以合并不需要執(zhí)行任何操作。快速排序的分治策略(1)劃分:選定一個(gè)記錄作為軸值,以軸值為基準(zhǔn)將整個(gè)序列劃分為兩個(gè)子序列r1…ri-1和ri+1…rn,前一個(gè)子序列中記錄的值均小于或等于軸值,后一個(gè)子序列中記錄的值均大于或等于軸值;4.2.2快速排序[r1……

ri-1]

ri[ri+1……

rn]

均≤ri

軸值均≥ri

位于最終位置

2024/11/30DivideandConquerMethod25以第一個(gè)記錄為軸值(可隨機(jī)),對(duì)待排序序列進(jìn)行劃分的過(guò)程:(1)初始化:取第一個(gè)記錄作為基準(zhǔn),設(shè)置兩個(gè)參數(shù)i,j分別用來(lái)指示將要與基準(zhǔn)記錄進(jìn)行比較的左側(cè)記錄位置和右側(cè)記錄位置,也就是本次劃分的區(qū)間;(2)右側(cè)掃描過(guò)程:將基準(zhǔn)記錄與j指向的記錄進(jìn)行比較,如果j指向記錄的關(guān)鍵碼大,則j--,即前移一個(gè)記錄位置。重復(fù)右側(cè)掃描過(guò)程,直到右側(cè)的記錄?。捶葱颍鬷<j,則將基準(zhǔn)記錄與j指向的記錄進(jìn)行交換;(3)左側(cè)掃描過(guò)程:將基準(zhǔn)記錄與i指向的記錄進(jìn)行比較,如果i指向記錄的關(guān)鍵碼小,則i++,即后移一個(gè)記錄位置。重復(fù)左側(cè)掃描過(guò)程,直到左側(cè)的記錄大(即反序),若i<j,則將基準(zhǔn)記錄與i指向的記錄交換;4.2.2快速排序2024/11/30DivideandConquerMethod26(4)重復(fù)(2)(3)步,直到i與j指向同一位置,即基準(zhǔn)記錄最終的位置。4.2.2快速排序一次劃分示例:

(1)i=1,j=7,r[1]為基準(zhǔn)記錄;

(2)r[i]<r[j]?j--:

r[i]r[j]//右側(cè)掃描(3)r[i]>r[j]?i++:

r[i]r[j]//左側(cè)掃描(4)i=j?ifi=j,then第一次劃分基準(zhǔn)記錄位置找到2024/11/30DivideandConquerMethod2713652750384955jijj13652750384955jiii13652750384955ijjj一次劃分示例2024/11/30DivideandConquerMethod28算法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++描述4.2.2快速排序2024/11/30DivideandConquerMethod29

以軸值(如此處為軸值:38)為基準(zhǔn)將待排序序列劃分為兩個(gè)子序列后,對(duì)每一個(gè)子序列分別遞歸進(jìn)行排序。132750384955jiij13652750384955654.2.2快速排序2024/11/30DivideandConquerMethod30算法4.6——快速排序

voidQuickSort(intr[],intfirst,intend){if(first<end){

pivot=Partition(r,first,end);

//問(wèn)題分解,pivot是軸值在序列中的位置

QuickSort(r,first,pivot-1);

//遞歸地對(duì)左側(cè)子序列進(jìn)行快速排序

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

}}C++描述4.2.2快速排序2024/11/30DivideandConquerMethod31T(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)。最好情況:每次劃分對(duì)一個(gè)記錄定位后,該記錄的左側(cè)子序列與右側(cè)子序列的長(zhǎng)度相同。在具有n個(gè)記錄的序列中,一次劃分需要對(duì)整個(gè)待劃分序列掃描一遍,則所需時(shí)間為O(n)。設(shè)T(n)是對(duì)n個(gè)記錄的序列進(jìn)行排序的時(shí)間,每次劃分后,正好把待劃分區(qū)間劃分為長(zhǎng)度相等的兩個(gè)子序列,則有:4.2.2快速排序2024/11/30DivideandConquerMethod32因此,時(shí)間復(fù)雜度為O(n2)。最壞情況:待排序記錄序列正序或逆序,每次劃分只得到一個(gè)比上一次劃分少一個(gè)記錄的子序列(另一個(gè)子序列為空)。此時(shí),必須經(jīng)過(guò)n-1次遞歸調(diào)用才能把所有記錄定位,而且第i趟劃分需要經(jīng)過(guò)n-i次關(guān)鍵碼的比較才能找到第i個(gè)記錄的基準(zhǔn)位置,因此,總的比較次數(shù)為:4.2.2快速排序2024/11/30DivideandConquerMethod33在平均情況下,設(shè)基準(zhǔn)記錄的關(guān)鍵碼第k?。?≤k≤n),則有:

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

4.2.2快速排序2024/11/30DivideandConquerMethod34[空間復(fù)雜性]快速排序需要一個(gè)棧來(lái)存放每一層遞歸調(diào)用的必要信息,其最大容量應(yīng)與遞歸調(diào)用的深度一致。最好情況下進(jìn)行l(wèi)og2n次遞歸調(diào)用,棧的深度為O(log2n);最壞情況下,因?yàn)橐M(jìn)行n-1次遞歸調(diào)用,所以棧的深度為O(n);平均情況下,棧的深度為O(log2n)兩種排序的區(qū)別:歸并排序按照記錄在序列中的位置對(duì)序列進(jìn)行劃分,快速排序按照記錄的值對(duì)序列進(jìn)行劃分4.2.2快速排序2024/11/30DivideandConquerMethod35本章要點(diǎn)4.1概

4.2排序問(wèn)題中的分治法4.3組合問(wèn)題中的分治法4.4幾何問(wèn)題中的分治法閱讀材料

遞歸函數(shù)的執(zhí)行過(guò)程2024/11/30DivideandConquerMethod36組合問(wèn)題中的分治法

4.3.1最大子段和問(wèn)題

4.3.2棋盤覆蓋問(wèn)題2024/11/30DivideandConquerMethod37

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

最大子段和問(wèn)題

最大子段和問(wèn)題的分治策略是:(1)劃分:按照平衡子問(wèn)題的原則,將序列(a1,a2,…,an)劃分成長(zhǎng)度相同的兩個(gè)子序列(a1,…,a)和(a+1,

…,an),則會(huì)出現(xiàn)以下三種情況:

2024/11/30DivideandConquerMethod38①

a1,…,an的最大子段和=a1,…,a的最大子段和;②

a1,…,an的最大子段和=a+1,

…,an的最大子段和;③

a1,…,an的最大子段和=,且(2)求解子問(wèn)題:對(duì)于劃分階段的情況①和②可遞歸求解,情況③需要分別計(jì)算:

則s1+s2為情況③的最大子段和。最大子段和問(wèn)題

2024/11/30DivideandConquerMethod39a1……ai…amid

amid+1…aj……an劃分leftsum

rightsum

遞歸處理a1……ai…amid

amid+1…aj……an最大子段和橫跨兩個(gè)子序列sum不能遞歸處理max{leftsum,sum,rightsum}合并解最大子段和問(wèn)題

(3)合并:比較在劃分階段的三種情況下的最大子段和,取三者之中的較大者為原問(wèn)題的解。2024/11/30DivideandConquerMethod40算法4.7——最大子段和問(wèn)題

intMaxSum(inta[],intleft,intright){sum=0;if(left==right){ //如果序列長(zhǎng)度為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++描述最大子段和問(wèn)題

2024/11/30DivideandConquerMethod41s1=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;}最大子段和問(wèn)題

2024/11/30DivideandConquerMethod42

分析算法4.7的時(shí)間性能,對(duì)應(yīng)劃分得到的情況①和②,需要分別遞歸求解,對(duì)應(yīng)情況③,兩個(gè)并列for循環(huán)的時(shí)間復(fù)雜性是O(n),所以,存在如下遞推式:根據(jù)2.1.5節(jié)主定理,算法4.7的時(shí)間復(fù)雜性為O(nlog2n)。

最大子段和問(wèn)題

2024/11/30DivideandConquerMethod43組合問(wèn)題中的分治法

4.3.1最大子段和問(wèn)題

4.3.2棋盤覆蓋問(wèn)題2024/11/30DivideandConquerMethod44棋盤覆蓋問(wèn)題

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

(k≥0)個(gè)方格組成的棋盤中,恰有一個(gè)方格與其他方格不同,稱該方格為特殊方格。特殊方格在棋盤中出現(xiàn)的位置有4k

種情形,因而有4k種不同的棋盤,(a)圖是其中的一個(gè)。棋盤覆蓋問(wèn)題?要求用圖4.11(b)所示的4種不同形狀的L型骨牌覆蓋給定棋盤上除特殊方格以外的所有方格,且任何2個(gè)L型骨牌不得重疊覆蓋。(a)k=2時(shí)的一種棋盤(b)4種不同形狀的L型骨牌2024/11/30DivideandConquerMethod45

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

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ì)合處,從而將原問(wèn)題轉(zhuǎn)化為4個(gè)較小規(guī)模的棋盤覆蓋問(wèn)題。遞歸地使用這種劃分策略,直至將棋盤分割為1×1的子棋盤。

棋盤覆蓋問(wèn)題

2024/11/30DivideandConquerMethod462k-1×2k-12k-1×2k-12k-1×2k-12k-1×2k-1(a)棋盤分割(b)構(gòu)造相同子問(wèn)題棋盤覆蓋問(wèn)題

2024/11/30DivideandConquerMethod47下面討論棋盤覆蓋問(wèn)題中數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)。(1)棋盤:可以用一個(gè)二維數(shù)組board[size][size]表示一個(gè)棋盤,其中,size=2k。為了在遞歸處理的過(guò)程中使用同一個(gè)棋盤,將數(shù)組board設(shè)為全局變量;(2)子棋盤:整個(gè)棋盤用二維數(shù)組board[size][size]表示,其中的子棋盤由棋盤左上角的下標(biāo)tr、tc和棋盤大小s表示;(3)特殊方格:用board[dr][dc]表示特殊方格,dr和dc是該特殊方格在二維數(shù)組board中的下標(biāo);(4)L型骨牌:一個(gè)2k×2k的棋盤中有一個(gè)特殊方格,所以,用到L型骨牌的個(gè)數(shù)為(4k-1)/3,將所有L型骨牌從1

開始連續(xù)編號(hào),用一個(gè)全局變量

t表示。棋盤覆蓋問(wèn)題

2024/11/30DivideandConquerMethod48dcdrtrtcsize棋盤覆蓋問(wèn)題中的數(shù)據(jù)結(jié)構(gòu)棋盤覆蓋問(wèn)題

2024/11/30DivideandConquerMethod49算法4.8——棋盤覆蓋voidChessBoard(inttr,inttc,intdr,intdc,intsize)//tr和tc是子棋盤左上角的下標(biāo),dr和dc是特殊方格的下標(biāo),//size是棋盤的大小,t是骨牌編號(hào),已初始化為0{

if(size==1)return;//棋盤只有一個(gè)方格且是特殊方格

t++; //L型骨牌號(hào)

s=size/2; //劃分棋盤

//覆蓋左上角子棋盤

if(dr<tr+s&&dc<tc+s)//特殊方格在左上角子棋盤中

ChessBoard(tr,tc,dr,dc,s);//遞歸處理子棋盤

else{//用t號(hào)L型骨牌覆蓋右下角,再遞歸處理子棋盤

board[tr+s-1][tc+s-1]=t;ChessBoard(tr,tc,tr+s-1,tc+s-1,s);}C++描述棋盤覆蓋問(wèn)題

2024/11/30DivideandConquerMethod50

//覆蓋右上角子棋盤

if(dr<tr+s&&dc>=tc+s)//特殊方格在右上角子棋盤中

ChessBoard(tr,tc+s,dr,dc,s);//遞歸處理子棋盤

else{//用t號(hào)L型骨牌覆蓋左下角,再遞歸處理子棋盤

board[tr+s-1][tc+s]=t;ChessBoard(tr,tc+s,tr+s-1,tc+s,s);}

//覆蓋左下角子棋盤

if(dr>=tr+s&&dc<tc+s)//特殊方格在左下角子棋盤中

ChessBoard(tr+s,tc,dr,dc,s);//遞歸處理子棋盤

else{//用t號(hào)L型骨牌覆蓋右上角,再遞歸處理子棋盤

board[tr+s][tc+s-1]=t;ChessBoard(tr+s,tc,tr+s,tc+s-1,s);}棋盤覆蓋問(wèn)題

2024/11/30DivideandConquerMethod51

//覆蓋右下角子棋盤

if(dr>=tr+s&&dc>=tc+s)//特殊方格在右下角子棋盤中

ChessBoard(tr+s,tc+s,dr,dc,s);//遞歸處理子棋盤

else{//用t號(hào)L型骨牌覆蓋左上角,再遞歸處理子棋盤

board[tr+s][tc+s]=t;ChessBoard(tr+s,tc+s,tr+s,tc+s,s);}}棋盤覆蓋問(wèn)題

2024/11/30DivideandConquerMethod52

設(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)算法。

棋盤覆蓋問(wèn)題

2024/11/30DivideandConquerMethod53本章要點(diǎn)4.1概

4.2排序問(wèn)題中的分治法4.3組合問(wèn)題中的分治法4.4幾何問(wèn)題中的分治法閱讀材料

遞歸函數(shù)的執(zhí)行過(guò)程2024/11/30DivideandConquerMethod544.4幾何問(wèn)題中的分治法4.4.1最近對(duì)問(wèn)題

4.4.2凸包問(wèn)題2024/11/30DivideandConquerMethod55最近對(duì)問(wèn)題

設(shè)p1=(x1,y1),p2=(x2,y2),…,pn=(xn,yn)是平面上n個(gè)點(diǎn)構(gòu)成的集合S,最近對(duì)問(wèn)題就是找出集合S中距離最近的點(diǎn)對(duì)。嚴(yán)格地講,最接近點(diǎn)對(duì)可能多于一對(duì),簡(jiǎn)單起見,只找出其中的一對(duì)作為問(wèn)題的解。

2024/11/30DivideandConquerMethod56

用分治法解決最近對(duì)問(wèn)題,很自然的想法就是將集合S

分成兩個(gè)子集S1和S2,每個(gè)子集中有n/2個(gè)點(diǎn)。然后在每個(gè)子集中遞歸地求其最接近的點(diǎn)對(duì),在求出每個(gè)子集的最接近點(diǎn)對(duì)后,在合并步中,如果集合S中最接近的兩個(gè)點(diǎn)都在子集S1或S2中,則問(wèn)題很容易解決,如果這兩個(gè)點(diǎn)分別在S1和S2中,問(wèn)題就比較復(fù)雜了。最近對(duì)問(wèn)題

2024/11/30DivideandConquerMethod57為了使問(wèn)題易于理解,先考慮一維的情形。此時(shí),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ù)相同。遞歸地在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中的最小值。S1S2p2p1p3q3q1q2m最近對(duì)問(wèn)題

2024/11/30DivideandConquerMethod58

按這種分治策略求解最近對(duì)問(wèn)題的算法效率取決于劃分點(diǎn)m的選取,一個(gè)基本的要求是要遵循平衡子問(wèn)題的原則。如果選取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)。最近對(duì)問(wèn)題

2024/11/30DivideandConquerMethod59下面考慮二維的情形,此時(shí)S中的點(diǎn)為平面上的點(diǎn)。為了將平面上的點(diǎn)集S分割為點(diǎn)的個(gè)數(shù)大致相同的兩個(gè)子集S1和S2,選取垂直線x=m來(lái)作為分割線,其中,m為S中各點(diǎn)x坐標(biāo)的中位數(shù)。由此將S分割為S1={p∈S|xp≤m}和S2={q∈S|xq>m}。遞歸地在S1和S2上求解最近對(duì)問(wèn)題,分別得到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。

最近對(duì)問(wèn)題

2024/11/30DivideandConquerMethod60x=mddd2d1S1S2pq

最近對(duì)問(wèn)題的分治思想P1P2S1={p∈S|xp≤m}S2={q∈S|xq>m}最近對(duì)問(wèn)題

2024/11/30DivideandConquerMethod61x=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ì)超過(guò)6個(gè)(因P2中點(diǎn)之間的距離不能小于d)。故可將P1和P2中的點(diǎn)按照y軸坐標(biāo)值升序排列,順序處理P1中的點(diǎn)p,同時(shí)在P2中取出6個(gè)候選點(diǎn),計(jì)算它們與點(diǎn)p之間的距離。

2024/11/30DivideandConquerMethod62算法4.9——分治法求解最近對(duì)問(wèn)題輸入:按x坐標(biāo)升序排列的n(n≥2)個(gè)點(diǎn)的集合S={(x1,y1),…,(xn,yn)}輸出:最近點(diǎn)對(duì)的距離1.如果n=2,則返回(x1,y1)和(x2,y2)間的距離,算法結(jié)束;2.劃分:m=S中各點(diǎn)x坐標(biāo)的中位數(shù);3.d1=計(jì)算{(x1,y1),…,(xm,ym)}的最近對(duì)距離;4.d2=計(jì)算{(xm,ym),…,(xn,yn)}的最近對(duì)距離;5.d=min{d1,d2};6.依次考察集合S中的點(diǎn)p(x,y),如果(x≤xm

并且x≥xm-d),則將點(diǎn)p放入集合P1中;如果(x≥xm

并且x≤xm+d),則將點(diǎn)p放入集合P2中;7.將集合P1和P2按y坐標(biāo)升序排列;8.對(duì)集合P1中的每個(gè)點(diǎn)p(x,y),對(duì)集合P2在y坐標(biāo)區(qū)間[y-d,y+d]內(nèi)最多取出6個(gè)候選點(diǎn),計(jì)算與點(diǎn)p的最近距離d3;9.返回min{d,d3};偽代碼描述最近對(duì)問(wèn)題

2024/11/30DivideandConquerMethod63

應(yīng)用分治法求解含有n個(gè)點(diǎn)的最近對(duì)問(wèn)題,其時(shí)間復(fù)雜性可由下面的遞推式表示:根據(jù)2.1.5節(jié)的主定理,可得T(n)=O(nlog2n)。最近對(duì)問(wèn)題

2024/11/30DivideandConquerMethod644.4幾何問(wèn)題中的分治法4.4.1最近對(duì)問(wèn)題

4.4.2凸包問(wèn)題2024/11/30DivideandConquerMethod65凸包問(wèn)題

[問(wèn)題]設(shè)p1=(x1,y1),p2=(x2,y2),…,pn=(xn,yn)是平面上n個(gè)點(diǎn)構(gòu)成的集合S,凸包問(wèn)題是為集合S構(gòu)造最小凸多邊形。[想法]劃分:設(shè)S中的點(diǎn)按照x軸坐標(biāo)升序排列,幾何學(xué)中有這樣一個(gè)明顯的事實(shí):最左邊的點(diǎn)p1和最右邊的點(diǎn)pn一定是該集合的凸包頂點(diǎn)(即極點(diǎn))。設(shè)p1pn是從p1到pn的直線,這條直線把集合S分成兩個(gè)子集:S1是位于直線左側(cè)和直線上的點(diǎn)構(gòu)成的集合,S2是位于直線右側(cè)和直線上的點(diǎn)構(gòu)成的集合。S1的凸包由下列線段構(gòu)成:以p1和pn為端點(diǎn)的線段構(gòu)成的下邊界,以及由多條線段構(gòu)成的上邊界,這條上邊界稱為上包。類似地,S2中的多條線段構(gòu)成的下邊界稱為下包。整個(gè)集合S的凸包是由上包和下包構(gòu)成的。

2024/11/30DivideandConquerMethod66p1pn

點(diǎn)集合S的上包和下包S1S2凸包問(wèn)題

pmax2024/11/30DivideandConquerMethod67p1pmaxpn求解子問(wèn)題:首先找到S1中的頂點(diǎn)pmax,它是距離直線p1pn最遠(yuǎn)的頂點(diǎn),則三角形pmaxp1pn的面積最大。S1中所有在直線p1pmax左側(cè)的點(diǎn)構(gòu)成集合S1,1,S1中所有在直線pnpmax右側(cè)的點(diǎn)構(gòu)成集合S1,2,包含在三角形pmaxp1pn之中的點(diǎn)可以不考慮了。遞歸地繼續(xù)構(gòu)造集合S1,1的上包和集合S1,2的上包,然后將求解過(guò)程中得到的所有最遠(yuǎn)距離的點(diǎn)連接起來(lái),就可以得到集合S1的上包。凸包問(wèn)題

S1,1S1,22024/11/30DivideandConquerMethod68

接下來(lái)的問(wèn)題是如何判斷一個(gè)點(diǎn)是否在給定直線的左側(cè)(或右側(cè))?幾何學(xué)中有這樣一個(gè)定理:如果p1=(x1,y1),p2=(x2,y2),p3=(x3,y3)是平面上的任意三個(gè)點(diǎn),則三角形p1p2p3的面積等于下面這個(gè)行列式的絕對(duì)值的一半:

當(dāng)且僅當(dāng)點(diǎn)p3=(x3,y3)位于直線p1p2的左側(cè)時(shí),該式的符號(hào)為正。可以在一個(gè)常數(shù)時(shí)間內(nèi)檢查一個(gè)點(diǎn)是否位于兩個(gè)點(diǎn)確定的直線的左側(cè),并且可以求得這個(gè)點(diǎn)到該直線的距離。311223321321332211111yxyxyxyxyxyxyxyxyx---++=凸包問(wèn)題

2024/11/30DivideandConquerMethod69算法4.10——求直線pipj的上包輸入:按x坐標(biāo)升序排列的n(n≥2)個(gè)點(diǎn)的集合S={(xi,yi),…,(xj,yj)}輸出:凸包的極點(diǎn)1.如果n=2,則返回(xi,yi)和(xj,yj),算法結(jié)束;2.maxd=0;max=i+1;3.循環(huán)變量k從i+1~j-1,依次對(duì)集合S中點(diǎn)pk(xk,yk)執(zhí)行下列操作; 3.1如果點(diǎn)pk在直線pipj的上側(cè),則d=該點(diǎn)到直線的距離; 3.2如果(d>maxd),則maxd=d,max=k;4.遞歸求解pipmax的上包和pmaxpj的上包偽代碼描述凸包問(wèn)題

2024/11/30DivideandConquerMethod70復(fù)雜度的討論首先要對(duì)點(diǎn)集合S進(jìn)行排序,設(shè)有n個(gè)點(diǎn),則時(shí)間代價(jià)是O(nlog2n)。最好情況:每次劃分都得到規(guī)模大致相等的子集合,O(nlog2n)最壞情況:每次劃分只得到比上一次劃分少一個(gè)元素的子集合(另一個(gè)為空),O(n2)蠻力法:O(n3)凸包問(wèn)題

2024/11/30DivideandConquerMethod71補(bǔ)充閱讀材料:遞歸的概念直接或間接地調(diào)用自身的算法稱為遞歸算法(Recursion)。用函數(shù)自身給出定義的函數(shù)稱為遞歸函數(shù)。是一種描述問(wèn)題和解決問(wèn)題的基本方法。由分治法產(chǎn)生的子問(wèn)題往往是原問(wèn)題的較小模式,這就為使用遞歸技術(shù)提供了方便。在這種情況下,反復(fù)應(yīng)用分治手段,可以使子問(wèn)題與原問(wèn)題類型一致而其規(guī)模卻不斷縮小,最終使子問(wèn)題縮小到很容易直接求出其解。這自然導(dǎo)致遞歸過(guò)程的產(chǎn)生。2024/11/30DivideandConquerMethod72遞歸的概念分治與遞歸像一對(duì)孿生兄弟,經(jīng)常同時(shí)應(yīng)用在算法設(shè)計(jì)之中,并由此產(chǎn)生許多高效算法。遞歸有兩個(gè)基本要素:⑴邊界條件:確定遞歸到何時(shí)終止;⑵遞歸模式:大問(wèn)題是如何分解為小問(wèn)題的。也稱為遞歸體。遞歸的幾個(gè)實(shí)例2024/11/30DivideandConquerMethod73例1階乘(Factorial

)函數(shù)階乘函數(shù)可遞歸地定義為:邊界條件遞歸方程遞歸的概念2024/11/30DivideandConquerMethod74Factorial遞歸算法

1publicstaticintfactorial(intn)

2{3if(n==0)return1;4returnn*factorial(n-1);

5}C++描述遞歸的概念遞歸函數(shù)的經(jīng)典問(wèn)題——漢諾塔問(wèn)題在世界剛被創(chuàng)建的時(shí)候有一座鉆石寶塔(塔A),其上有64個(gè)金碟。所有碟子按從大到小的次序從塔底堆放至塔頂。緊挨著這座塔有另外兩個(gè)鉆石寶塔(塔B和塔C)。從世界創(chuàng)始之日起,婆羅門的牧師們就一直在試圖把塔A上的碟子移動(dòng)到塔C上去,其間借助于塔B的幫助。每次只能移動(dòng)一個(gè)碟子,任何時(shí)候都不能把一個(gè)碟子放在比它小的碟子上面。當(dāng)牧師們完成任務(wù)時(shí),世界末日也就到了。

遞歸的概念漢諾塔問(wèn)題可以通過(guò)以下三個(gè)步驟實(shí)現(xiàn):(1)將塔A上的n-1個(gè)碟子借助塔C先移到塔B上。(2)把塔A上剩下的一個(gè)碟子移到塔C上。(3)將n-1個(gè)碟子從塔B借助塔A移到塔C上。顯然,這是一個(gè)遞歸求解的過(guò)程遞歸的概念算法4.2——漢諾塔算法

1voidHanoi(intn,charA,charB,charC)

//第一列為語(yǔ)句行號(hào)

2{3if(n==1)Move(A,C);//Move是一個(gè)抽象操作,表示將碟子從A移到C上

4else{5Hanoi(n-1,

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

評(píng)論

0/150

提交評(píng)論