《算法設計與分析》教案

張靜

第1章緒論

算法理論的兩大論題：

1.算法設計

2.算法分析

1.1算法的基本概念

1.1.1為什么要學習算法

理由1：算法----程序的靈魂

＞問題的求解過程：

分析問題一設計算法一編寫程序一整理結果

＞程序設計研究的四個層次：

算法一方法學一語言~工具

理由2：提高分析問題的能力

算法的形式化一思維的邏輯性、條理性

1.1.2算法及其重要特性

算法(Algorithm)：對特定問題求解步驟的一種描述，是指令的有限

序列。

算法的五大特性：

⑴輸入：一個算法有零個或多個輸入。

⑵輸出：一個算法有一個或多個輸出。

⑶有窮性：一個算法必須總是在執行有窮步之后結束，且每一步都

在有窮時間內完成。

（4）確定性：算法中的每一條指令必須有確切的含義，對于相同的輸

入只能得到相同的輸出。

⑸可行性：算法描述的操作可以通過已經實現的基本操作執行有限

次來實現。

1.1.3算法的描述方法

⑴自然語言

優點：容易理解

缺點：冗長、二義性

使用方法：粗線條描述算法思想

注意事項：避免寫成自然段

歐兒里德算法

開始

⑶程序設計語言

優點：能由計算機執行

缺點：抽象性差，對語言要求高

使用方法：算法需要驗證

注意事項：將算法寫成子函數

歐幾里德算法

ttinclude<iostream.h>

intCommonFactor(intm,intn)

{

intr=m%n;

while(r!=0)

m二n;

n=r;

r初%n;

}

returnn;

)

voidmain()

(

cout<<CommonFactor(63,54)<<endl;

)

(4)偽代碼一一算法語言

偽代碼(Pseudocode)：介于自然語言和程序設計語言之間的方法，

它采用某一程序設計語言的基本語法，操作指令可以結合自然語言來設

計。

優點：表達能力強，抽象性強，容易理解

使用方法：7±2

歐幾里德算法

1.r=m%n;

2.循環直到r等于0

2.1m=n;

2.2n=r;

2.3rm%n;

3.輸出n;

1.1.4算法設計的一般過程

1.理解問題

2.預測所有可能的輸入

3.在精確解和近似解間做選擇

4.確定適當的數據結構

5.算法設計技術

6.描述算法

7.跟蹤算法

8.分析算法的效率

9.根據算法編寫代碼

1.2算法分析

算法分析(AlgorithmAnalysis)：對算法所需要的兩種計算機資源

——時間和空間進行估算

>時間復雜性(TimeComplexity)

>空間復雜性(SpaceComplexity)

算法分析的目的：

>設計算法一一設計出復雜性盡可能低的算法

>選擇算法一一在多種算法中選擇其中復雜性最低者

時間復雜性分析的關鍵:

>問題規模：輸入量的多少;

>基本語句：執行次數與整個算法的執行時間

成正比的語句

for(i=l;i<=n;i++)

for(j=l;j<=n;j++)

x++;

問題規模：n

基本語句：x++

1.2.1漸進符號

1.大。符號

定義1.1若存在兩個正的常數。和M,對于任意都有7(〃)

WCXF(A),則稱7(A)=0(F(A))

2.大Q符號

定義1.2若存在兩個正的常數c和M,對于任意都有T(〃)

2cXg(〃),則稱T(n)=Q(g?)

3.?符號

定義1.3若存在三個正的常數cl、c2和〃0,對于任意都有cl

Xf?X7(A)Xc2Xf\n),則稱7?=?(f(力)

例：Az?）=5T?2+8/7+1

當〃21時，5〃2+8〃+1W5/72+8〃+A

=5〃2+9/7^5/72+9/72W14成=0（成）

當時，5〃2+8〃+125成=Q（成）

當〃21時，14〃225成+8/?+125成

則：5A2+8A+1=?（〃2）

定理1.1若T{ii)-amnm+amTnm-l+…(ani>Q),則有

7(〃)=。(〃血且7(〃)=。(〃勿)，因此，有7(〃)=。(〃%)。

1.2.2最好、最壞和平均情況

例：在一維整型數組A[n]中順序查找與給定值k相等的元素(假設

該數組中有且僅有一個元素值為k)

intFind(intA[],intn)

(

for(i=0;i<n;i++)

if(A[i]==k)break;

returni;

}

結論：如果問題規模相同，時間代價與輸入數據有關，則需要分析最

好情況、最壞情況、平均情況。

/最好情況：出現概率較大時分析

,最差情況：實時系統

/平均情況：已知輸入數據是如何分布的，

通常假設等概率分布

1.2.3非遞歸算法的分析

算法一一非遞歸算法、遞歸算法

例：求數組最小值算法

intArrayMin(inta[],intn)

min=a[O];

for(i=l;i<n;i++)

if(a[i]<min)min=a[i];

returnmin;

非遞歸算法分析的一般步驟：

1.決定用哪個(或哪些)參數作為算法問題規模的度量

2.找出算法中的基本語句

3.檢查基本語句的執行次數是否只依賴于問題規模

4.建立基本語句執行次數的求和表達式

5.用漸進符號表示這個求和表達式

?關鍵：建立一個代表算法運行時間的求和表達式，然后用

漸進符號表示這個求和表達式。

1.2.4遞歸算法的分析

關鍵：根據遞歸過程建立遞推關系式，然后求解這個遞推關系式。

1.猜測技術:對遞推關系式估計一個上限，然后(用數學歸納法)證

明它正確。

2.擴展遞歸技術

3.通用分治遞推式

大小為〃的原問題分成若干個大小為的子問題，其中a個子問題

需要求解，而。成是合并各個子問題的解需要的工作量。

1.2.5算法的后驗分析

算法的后驗分析(Posteriori)也稱算法的實驗分析，它是一種事后

計算的方法，通常需要將算法轉換為對應的程序并上機運行。

一般步驟：

1.明確實驗目的

2.決定度量算法效率的方法，為實驗準備算法的程序實現

3.決定輸入樣本，生成實驗數據

4.對輸入樣本運行算法對應的程序，記錄得到的實驗數據

5.分析得到的實驗數據

表格法記錄實驗數據

散點圖記錄實驗數據

問題規?！?/p>

第4章分治法

4.1概述

4.1.1分治法的設計思想

將一個難以直接解決的大問題，劃分成一些規模較小的子問題，以便

各個擊破，分而治之。更一般地說，將要求解的原問題劃分成衣個較小規

模的子問題，對這攵個子問題分別求解。如果子問題的規模仍然不夠小，

則再將每個子問題劃分為4個規模更小的子問題，如此分解下去，直到問

題規模足夠小，很容易求出其解為止，再將子問題的解合并為一個更大規

模的問題的解，自底向上逐步求出原問題的解。

啟發式規則：

1.平衡子問題：最好使子問題的規模大致相同。也就是將一個問題

劃分成大小相等的4個子問題(通常左=2),這種使子問題規模大致相等

的做法是出自一種平衡(Balancing)子問題的思想，它幾乎總是比子問

題規模不等的做法要好。

2.獨立子問題：各子問題之間相互獨立，這涉及到分治法的效率，

如果各子問題不是獨立的，則分治法需要重復地解公共的子問題。

分治法的典型情況

4.1.2分治法的求解過程

一般來說，分治法的求解過程由以下三個階段組成：

（1）劃分：既然是分治，當然需要把規模為n的原問題劃分為4個

規模較小的子問題，并盡量使這在個子問題的規模大致相同。

（2）求解子問題：各子問題的解法與原問題的解法通常是相同的，

可以用遞歸的方法求解各個子問題，有時遞歸處理也可以用循環來實現。

（3）合并：把各個子問題的解合并起來，合并的代價因情況不同有

很大差異，分治算法的有效性很大程度上依賴于合并的實現。

分治法的一般過程

DivideConquer（P）

（

if（P的規模足夠?。┲苯忧蠼釶;

分解為k個子問題Pl,P2,…Pk;

for(i=l;i<=k;i++)

yi=DivideConquer(Pi);

returnMerge(yl,?,,,yk);

例：計算am應用分治技術得到如下計算方法:

4.2遞歸

4.2.1遞歸的定義

遞歸就是子程序（或函數）直接調用自己或通過一系列調用語句間接

調用自己，是一種描述問題和解決問題的基本方法。

遞歸有兩個基本要素：

⑴邊界條件：確定遞歸到何時終止；

⑵遞歸模式：大問題是如何分解為小問題的，確定遞歸體。

4.2.2遞歸函數的運行軌跡

在遞歸函數中，調用函數和被調用函數是同一個函數，需要注意的是

遞歸函數的調用層次，如果把調用遞歸函數的主函數稱為第0層，進入函

數后，首次遞歸調用自身稱為第1層調用；從第，層遞歸調用自身稱為第

，+1層。反之，退出第，+1層調用應該返回第，層。采用圖示方法描述遞

歸函數的運行軌跡，從中可較直觀地了解到各調用層次及其執行情況。

4.2.3遞歸函數的內部執行過程

一個遞歸函數的調用過程類似于多個函數的嵌套調用，只不過調用函

數和被調用函數是同一個函數。為了保證遞歸函數的正確執行，系統需設

立一個工作棧。具體地說，遞歸調用的內部執行過程如下：

(1)運行開始時，首先為遞歸調用建立一個工作棧，其結構包括值

參、局部變量和返回地址；

(2)每次執行遞歸調用之前，把遞歸函數的值參和局部變量的當前

值以及調用后的返回地址壓棧;

（3）每次遞歸調用結束后，將棧頂元素出棧，使相應的值參和局部

變量恢復為調用前的值，然后轉向返回地址指定的位置繼續執行。

漢諾塔算法在執行過程中，工作棧的變化下圖所示，其中棧元素的結

構為（返回地址，n值，A值，B值，C值），返回地址對應算法中語句的

行號。

遞歸算法結構清晰，可讀性強，而且容易用數學歸納法來證明算法的

正確性，因此，它為設計算法和調試程序帶來很大方便，是算法設計中的

一種強有力的工具。但是，因為遞歸算法是一種自身調用自身的算法，隨

著遞歸深度的增加，工作棧所需要的空間增大，遞歸調用時的輔助操作增

多，因此，遞歸算法的運行效率較低。

4.3排序問題中的分治法

4.3.1歸并排序

二路歸并排序的分治策略是：

（1）劃分：將待排序序列力，12,…，277劃分為兩個長度相等的子

序列rl,rn/2Drn/2+1,,,,,rn；

（2）求解子問題：分別對這兩個子序列進行排序，得到兩個有序子

序列；

（3）合并：將這兩個有序子序列合并成一個有序序列。

算法4.3---歸并排序

voidMergeSort(intr[],intrl[],ints,intt)

if(s==t)rl[s]=r[s];

else{

m=(s+t)/2;

Mergesort(r,rl,s,m);〃歸并排序前半個子序

列

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

列

Merge(rl,r,s,m,t);〃合并兩個已排序的子

序列

}

}

算法4.4——合并有序子序列

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

(

i=s;j=m+l;k=s;

while(i<=m&&j<=t)

(

if(r[i]<=r[j])rl[k++]=r[i++];〃取r[i]和r[j]

中較小者放入rl[k]

elserl[k++]=r[j++];

if(i<=m)while(i<=m)

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

rl[k++]=r[i++];

elsewhile(j<=t)

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

rl[k++]=r[j++];

)

二路歸并排序的合并步的時間復雜性為。(〃)，所以，二路歸并排序算

法存在如下遞推式：

、1n1

7(〃)/

27(〃/2)nn1

根據1.2.4節的主定理，二路歸并排序的時間代價是0(〃log2〃)。

二路歸并排序在合并過程中需要與原始記錄序列同樣數量的存儲空

間，因此其空間復雜性為。(力。

4.3.2快速排序

快速排序的分治策略是：

(1)劃分：選定一個記錄作為軸值，以軸值為基準將整個序列劃分

為兩個子序列力…ri~\和ri+1rn,前一個子序列中記錄的值均小

于或等于軸值，后一個子序列中記錄的值均大于或等于軸值；

(2)求解子問題：分別對劃分后的每一個子序列遞歸處理；

(3)合并：由于對子序列H???ri-l和ri+1-??rn的排序是就地

進行的，所以合并不需要執行任何操作。

?歸并排序按照記錄在序列中的位置對序列進行劃分,

?？焖倥判虬凑沼涗浀闹祵π蛄羞M行劃分。

以第一個記錄作為軸值，對待排序序列進行劃分的過程為：

(1)初始化：取第一個記錄作為基準，設置兩個參數i,j分別用來

指示將要與基準記錄進行比較的左側記錄位置和右側記錄位置，也就是本

次劃分的區間；

(2)右側掃描過程：將基準記錄與j指向的記錄進行比較，如果j

指向記錄的關鍵碼大，則j前移一個記錄位置。重復右側掃描過程，直到

右側的記錄小(即反序)，若i<j,則將基準記錄與j指向的記錄進行交

換；

(3)左側掃描過程：將基準記錄與i指向的記錄進行比較，如果i

指向記錄的關鍵碼小，則i后移一個記錄位置。重復左側掃描過程，直到

左側的記錄大(即反序)，若則將基準記錄與i指向的記錄交換；

(4)重復(2)(3)步，直到i與j指向同一位置，即基準記錄最終

的位置。

一次劃分示例

算法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]——rlj];〃將較小記錄交換

到前面

i++;

)

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

if(i<j){

rr[i];〃將較大記錄交換

到后面

}

)

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

}

以軸值為基準將待排序序列劃分為兩個子序列后，對每一個子序列分

別遞歸進行排序。

算法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);

〃遞歸地對右側子序列進行快速排序

}

}

在最好情況下，每次劃分對一個記錄定位后，該記錄的左側子序列與

右側子序列的長度相同。在具有〃個記錄的序列中，一次劃分需要對整個

待劃分序列掃描一遍，則所需時間為。(〃)。設7(〃)是對〃個記錄的序列

進行排序的時間，每次劃分后，正好把待劃分區間劃分為長度相等的兩個

子序列，則有：

7(A)W27W2)+A

W2(27(〃/4)+A/2)+A=47(A/4)+2〃

W4(27(A/8)+Z?/4)+2T?=87(〃/8)+3Z?

W〃7(l)+〃log2z?=〃(〃log2z?)

因此，時間復雜度為0(〃log2〃)。

在最壞情況下，待排序記錄序列正序或逆序，每次劃分只得到一個比

上一次劃分少一個記錄的子序列(另一個子序列為空)。此時，必須經過

51次遞歸調用才能把所有記錄定位，而且第，趟劃分需要經過小，.次關

鍵碼的比較才能找到第，個記錄的基準位置，因此，總的比較次數為：

因此，時間復雜度為0(為)。

在平均情況下，設基準記錄的關鍵碼第4小(1W4。)，則有：

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

0(nlog2n)a

4.4組合問題中的分治法

4.4.1最大子段和問題

給定由〃個整數組成的序列(al,a2,…，aii),最大子段和問題要求

該序列形如的最大值(lWiW/W”)，當序列中所有整數均為負整數時,

其最大子段和為0。例如,序列大20,11,-4,13,-5,-2）的最大子段和

為：

最大子段和問題的分治策略是：

（1）劃分：按照平衡子問題的原則，將序列（al,a2,…，a〃）劃分

成長度相同的兩個子序列（al,…，a）和（2+1,…，an）,

則會出現以下三種情況：

①al,…，的最大子段和=al,???,a的最大子段和；

②al,…，an的最大子段和=a+1,…，a〃的最大子段和；

③al,???,的最大子段和=,且

（2）求解子問題：對于劃分階段的情況①和②可遞歸求解，情況③

需要分別計算

則sl+s2為情況③的最大子段和。

（3）合并：比較在劃分階段的三種情況下的最大子段和，取三者之

中的較大者為原問題的解。

算法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);

〃對應情況②，遞

歸求解

sl=O;lefts=O;〃以下對應情況③，先求

解si

for(i=center;i>=left;i一)

{

lefts+=a[i];

if(lefts>sl)sl=lefts;

)

s2=0;rights=0;〃再求解s2

for(j=center+l;j<=right;j++)

{

rights+=a[j];

if(rights>s2)s2=rights;

sum=sl+s2;〃計算情況③的最大子段和

if(sum<leftsum)sum=leftsum;

〃合并，在sum>leftsum和rightsum中取

較大者

if(sum<rightsum)sum=rightsum;

)

returnsum;

)

分析算法4.7的時間性能，對應劃分得到的情況①和②，需要分別遞

歸求解，對應情況③，兩個并列for循環的時間復雜性是。(〃)，所以，存

在如下遞推式：

根據1.2.4節主定理，算法4.7的時間復雜性為0(〃log2〃)。

4.4.2棋盤覆蓋問題

在一個2kx2k(A'O)個方格組成的棋盤中，恰有一個方格與其他

方格不同，稱該方格為特殊方格。棋盤覆蓋問題要求用圖4.11(b)所示

的4種不同形狀的L型骨牌覆蓋給定棋盤上除特殊方格以外的所有方格，

且任何2個L型骨牌不得重疊覆蓋。

分治法求解棋盤覆蓋問題的技巧在于劃分棋盤，使劃分后的子棋盤的

大小相同，并且每個子棋盤均包含一個特殊方格，從而將原問題分解為規

模較小的棋盤覆蓋問題。

冷0時，可將2在X2A的棋盤劃分為4個24-lX2hl的子棋盤，這樣

劃分后，由于原棋盤只有一個特殊方格，所以，這4個子棋盤中只有一個

子棋盤包含該特殊方格，其余3個子棋盤中沒有特殊方格。為了將這3個

沒有特殊方格的子棋盤轉化為特殊棋盤，以便采用遞歸方法求解，可以用

一個L型骨牌覆蓋這3個較小棋盤的會合處，從而將原問題轉化為4個較

小規模的棋盤覆蓋問題。遞歸地使用這種劃分策略，直至將棋盤分割為1

XI的子棋盤。

下面討論棋盤覆蓋問題中數據結構的設計。

（1）棋盤：可以用一個二維數組board[size][size]表示一個棋盤，

其中，size=2Ao為了在遞歸處理的過程中使用同一個棋盤，將數組board

設為全局變量；

（2）子棋盤：整個棋盤用二維數組board[size][size]表示，其中的

子棋盤由棋盤左上角的下標tr、tc和棋盤大小s表示；

（3）特殊方格：用board[dr][de]表示特殊方格，dr和de是該

特殊方格在二維數組board中的下標；

（4）L型骨牌：一個2*X24的棋盤中有一個特殊方格，所以，用

到L型骨牌的個數為（4代1）/3,將所有L型骨牌從1開始連續編號，用一

個全局變量t表示。

算法4.8---棋盤覆蓋

voidChessBoard（inttr,inttc,intdr,intde,intsize）

//tr和tc是棋盤左上角的下標，dr和de是特殊方格的下標，

//size是棋盤的大小，t已初始化為0

if（size==1）return;〃棋盤只有一個方格且是特殊方

格

t++;〃1型骨牌號

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

//覆蓋左上角子棋盤

if(dr<tr+s&&de<tc+s)//特殊方格在左上角

子棋盤中

ChessBoard(tr,tc,dr,de,s);〃遞歸處理

子棋盤

else{〃用t號L型骨牌覆蓋右下角，再遞歸處理子

棋盤

board[tr+s-1][tc+s-1]=t;

ChessBoard(tr,tc,tr+s-1,tc+s-1,s);

)

//覆蓋右上角子棋盤

if(dr<tr+s&&de>=tc+s)//特殊方格在右上

角子棋盤中

ChessBoard(tr,tc+s,dr,de,s);〃遞歸處

理子棋盤

else{〃用t號L型骨牌覆蓋左下角，再遞歸處理

子棋盤

board[tr+s-1][tc+s]=t;

ChessBoard(tr,tc+s,tr+s-1,tc+s,s);}

//覆蓋左下角子棋盤

if(dr>=tr+s&&de<tc+s)//特殊方格在左下角

子棋盤中

ChessBoard(tr+s,tc,dr,de,s);〃遞歸處理

子棋盤

else{〃用t號L型骨牌覆蓋右上角，再遞歸處理

子棋盤

board[tr+s][tc+s-1]=t;

ChessBoard(tr+s,tc,tr+s,tc+s-1,s);}

//覆蓋右下角子棋盤

if(dr>=tr+s&&de>=tc+s)//特殊方格在右下角

子棋盤中

ChessBoard(tr+s,tc+s,dr,de,s);〃遞歸處理

子棋盤

else{〃用t號L型骨牌覆蓋左上角，再遞歸處理

子棋盤

board[tr+s][tc+s]=t;

ChessBoard(tr+s,tc+s,tr+s,tc+s,s);}

!

設7(而是覆蓋一個2*X24棋盤所需時間，從算法的劃分策略可知，

7々)滿足如下遞推式：

解此遞推式可得m)=m)o由于覆蓋一個2Ax2A棋盤所需的骨牌

個數為(4kl)/3,所以，算法4.8是一個在漸進意義下的最優算法。

4.4.3循環賽日程安排問題

設有爐2A個選手要進行網球循環賽，要求設計一個滿足以下要求的

比賽日程表：

(1)每個選手必須與其他k1個選手各賽一次；

(2)每個選手一天只能賽一次。

按此要求,可將比賽日程表設計成一個n行小1列的二維表,

其中，第，行第j列表示和第i個選手在第j天比賽的選手。

按照分治的策略，可將所有參賽的選手分為兩部分，〃=2在個選手的

比賽日程表就可以通過為n/2=2k-\個選手設計的比賽日程表來決定。遞

歸地執行這種分割，直到只剩下2個選手時，比賽日程表的制定就變得很

簡單：只要讓這2個選手進行比賽就可以了。

(b)2"(A=2)個選手比賽(c)2*0=3)個選

手比賽

顯然，這個求解過程是自底向上的迭代過程，其中左上角和左下角分

別為選手1至選手4以及選手5至選手8前3天的比賽日程，據此，將左

上角部分的所有數字按其對應位置抄到右下角，將左下角的所有數字按其

對應位置抄到右上角，這樣，就分別安排好了選手1至選手4以及選手5

至選手8在后4天的比賽日程，如圖(c)所示。具有多個選手的情況可以

依此類推。

這種解法是把求解2A個選手比賽日程問題劃分成依次求解21、22、…、

24個選手的比賽日程問題，換言之，2★個選手的比賽日程是在2hl個選

手的比賽日程的基礎上通過迭代的方法求得的。在每次迭代中，將問題劃

分為4部分：

(1)左上角：左上角為24-L個選手在前半程的比賽日程；

(2)左下角：左下角為另2hl個選手在前半程的比賽日程，由左上

角加2hl得到，例如22個選手比賽，左下角由左上角直接加2得到，23

個選手比賽，左下角由左上角直接加4得到；

(3)右上角：將左下角直接抄到右上角得到另2hl個選手在后半程

的比賽日程；

(4)右下角：將左上角直接抄到右下角得到2bl個選手在后半程的

比賽日程；

算法設計的關鍵在于尋找這4部分元素之間的對應關系。

算法4.9——循環賽日程表

voidGameTable(intk,inta[][])

(

//爐24(*21)個選手參加比賽，

〃二維數組a表示日程安排，數組下標從1開始

n=2;//k=0,2個選手比賽日程可直接求得

〃求解2個選手比賽日程，得到左上角元素

a[l][l]=l;a⑴⑵=2;

a⑵⑴=2;a⑵⑵=1;

for(t=l;t<k;t++)

〃迭代處理，依次處理22,…，2攵個選手比賽日程

temp=n;n=n*2;

〃填左下角元素

for(i=temp+l;i<=n;i++)

for(j=l;j<=temp;j++)

a[i][j]=a[i-temp][j]+temp;

〃左下角元素和左上角元素的對應關系

〃填右上角元素

for(i=l;i<=temp;i++)

for(j=temp+l;j<=n;j++)

a[i][j]=a[i+temp][(j+temp)%n];

〃填右下角元素

for(i=temp+l;i<=n;i++)

for(j=temp+l;j<=n;j++)

a[i][j]=a[i-temp][j-temp];

}

)

分析算法4.9的時間性能，迭代處理的循環體內部有3個循環語句，

每個循環語句都是一個嵌套的for循環，且他們的執行次數相同，基本語

句是最內層循環體的賦值語句，即填寫比賽日程表中的元素?；菊Z句的

執行次數是:

所以，算法4.9的其時間復雜性為。(44)。

4.5幾何問題中的分治法

4.5.1最近對問題

設。1=(x1,yl),p2=(A2,總)，…，pn={xn,y”)是平面上〃個點構

成的集合S,最近對問題就是找出集合S中距離最近的點對。

嚴格地講，最接近點對可能多于一對，簡單起見，只找出其

中的一對作為問題的解。

用分治法解決最近對問題，很自然的想法就是將集合S分成兩個子集

51和S2,每個子集中有〃/2個點。然后在每個子集中遞歸地求其最接近

的點對，在求出每個子集的最接近點對后，在合并步中，如果集合S中

最接近的兩個點都在子集S1或52中，則問題很容易解決，如果這兩個

點分別在51和52中，問題就比較復雜了。

為了使問題易于理解，先考慮一維的情形。

此時，S中的點退化為x軸上的〃個點xl,嵬，…，xn。用x軸上的

某個點勿將S劃分為兩個集合51和52,并且51和52含有點的個數相同。

遞歸地在51和52上求出最接近點對(夕1,曲和(相，壯)，如果集合S

中的最接近點對都在子集51或52中，則曲min{(01,02),(gl,Q2)}即

為所求，如果集合S中的最接近點對分別在51和52中，則一定是(03,公),

其中，虎是子集51中的最大值，公是子集52中的最小值。

按這種分治策略求解最近對問題的算法效率取決于劃分點力的選取，

一個基本的要求是要遵循平衡子問題的原則。如果選取

爐(max{S}+min{S})/2,則有可能因集合S中點分布的不均勻而造成子集

51和52的不平衡，如果用S中各點坐標的中位數(即S的中值)作為分

割點，則會得到一個平衡的分割點勿，使得子集51和52中有個數大致相

同的點。

下面考慮二維的情形，此時S中的點為平面上的點。

為了將平面上的點集S分割為點的個數大致相同的兩個子集51和

52,選取垂直線下力來作為分割線，其中，加為S中各點x坐標的中位數。

由此將S分割為51={pWS|孫W血和52={geS|xq＞而。遞歸地在S1

和S2上求解最近對問題，分別得到51中的最近距離M和52中的最近距

離龍，令加min(班，血)，若S的最近對(p,g)之間的距離小于4則夕

和g必分屬于51和S2,不妨設S2,則0和q距直線尸加的距

離均小于a所以，可以將求解限制在以產加為中心、寬度為2d的垂直帶

網和K中，垂直帶之外的任何點對之間的距離都一定大于d。

對于點,《外，需要考察風中的各個點和點P之間的距離是否小于d,

顯然，K中這樣點的y軸坐標一定位于區間［廠“尹M之間，而且，這樣

的點不會超過6個。

應用分治法求解含有〃個點的最近對問題，其時間復雜性可由下面的

遞推式表示：

合并子問題的解的時間A〃)=0(1),根據1.2.4節的主定理，可得

r(〃)=〃(〃iog2〃)。

4.5.2凸包問題

設。1=（x1,yl）,p2=（A2,總），…，pn={xn,y”）是平面上〃個點構

成的集合S,并且這些點按照x軸坐標升序排列。幾何學中有這樣一個明

顯的事實：最左邊的點夕1和最右邊的點功一定是該集合的凸包頂點（即

極點）。設夕1W是從夕1到功的直線，這條直線把集合S分成兩個子集：

51是位于直線左側和直線上的點構成的集合，S2是位于直線右側和直線

上的點構成的集合。51的凸包由下列線段構成：以01和功為端點的線段

構成的下邊界，以及由多條線段構成的上邊界，這條上邊界稱為上包。類

似地，52中的多條線段構成的下邊界稱為下包。整個集合S的凸包是由上

包和下包構成的。

快包的思想是：首先找到S1中的頂點外它是距離直線加加最遠

的頂點，則三角形夕勿a如的面積最大。51中所有在直線0以。中1左側的

點構成集合51,1,S1中所有在直線加祝w右側的點構成集合51,2,包含

在三角形"的中1勿之中的點可以不考慮了。遞歸地繼續構造集合51,1的

上包和集合51,2的上包，然后將求解過程中得到的所有最遠距離的點連

接起來，就可以得到集合51的上包。

接下來的問題是如何判斷一個點是否在給定直線的左側（或右側）？

幾何學中有這樣一個定理：如果yl）,02=（嵬，y2）,p3=（x3,y3）

是平面上的任意三個點，則三角形0102P3的面積等于下面這個行列式的

絕對值的一半：

當且僅當點03=（x3,為）位于直線0102的左側時，該式的符號為正。

可以在一個常數時間內檢查一個點是否位于兩個點確定的直線的左側，并

且可以求得這個點到該直線的距離。

第6章動態規劃法

6.1.1最優化問題

最優化問題：有〃個輸入，它的解由這〃個輸入的一個子集組成，這

個子集必須滿足某些事先給定的條件，這些條件稱為約束條件，滿足約束

條件的解稱為問題的可行解。滿足約束條件的可行解可能不只一個，為了

衡量這些可行解的優劣，事先給出一定的標準，這些標準通常以函數的形

式給出，這些標準函數稱為目標函數，使目標函數取得極值（極大或極小）

的可行解稱為最優解，這類問題就稱為最優化問題。

例：付款問題：

超市的自動柜員機（POS機）要找給顧客數量最少的現金。

假定POS機中有n張面值為oPWnW"）的貨幣，用集合

尸仿1,電…,pn｝表示,如果P0S機需支付的現金為4那么，它必須

從夕中選取一個最小子集S,使得

（式6.1）

如果用向量游（H,嵬，…，M）表示S中所選取的貨幣，則

x=?PQ（式6.2）

,[0Pi史S

那么，P0S機支付的現金必須滿足

（式6.3）

并且

（式6.4）

在付款問題中，集合夕是該問題的輸入，滿足式6.1的解稱為可行解,

式6.2是解的表現形式，因為向量I中有〃個元素，每個元素的取值為0

或1,所以，可以有2〃個不同的向量，所有這些向量的全體構成該問題的

解空間，式6.3是該問題的約束條件，式6.4是該問題的目標函數，使式

6.4取得極小值的解稱為該問題的最優解。

6.1.2最優性原理

對于一個具有〃個輸入的最優化問題，其求解過程往往可以劃分為若

干個階段，每一階段的決策僅依賴于前一階段的狀態，由決策所采取的動

作使狀態發生轉移，成為下一階段決策的依據。從而，一個決策序列在不

斷變化的狀態中產生。這個決策序列產生的過程稱為多階段決策過程。

在每一階段的決策中有一個賴以決策的策略或目標，這種策略或目標

是由問題的性質和特點所確定，通常以函數的形式表示并具有遞推關系，

稱為動態規劃函數。

多階段決策過程滿足最優性原理(OptimalPrinciple)：無論決策過

程的初始狀態和初始決策是什么，其余的決策都必須相對于初始決策所產

生的當前狀態，構成一個最優決策序列。

如果一個問題滿足最優性原理通常稱此問題具有最優子結構性質。

6.1.3動態規劃法的設計思想

動態規劃法將待求解問題分解成若干個相互重疊的子問題，每個子問

題對應決策過程的一個階段，一般來說，子問題的重疊關系表現在對給定

問題求解的遞推關系（也就是動態規劃函數）中，將子問題的解求解一次

并填入表中，當需要再次求解此子問題時，可以通過查表獲得該子問題的

解而不用再次求解，從而避免了大量重復計算。

動態規劃法的求解過程

例：計算斐波那契數：

爐5時分治法計算斐波那契數的過程。

注意到，計算網〃）是以計算它的兩個重疊子問題以中1）和夕（h2）的

形式來表達的，所以，可以設計一張表填入戶1個網力的值。

動態規劃法求解斐波那契數網9）的填表過程：

用動態規劃法求解的問題具有特征：

,能夠分解為相互重疊的若干子問題；

/滿足最優性原理（也稱最優子結構性質）：該問題的最優

解中也包含著其子問題的最優解。

（用反證法）分析問題是否滿足最優性原理：

1.先假設由問題的最優解導出的子問題的解不是最優的；

2.然后再證明在這個假設下可構造出比原問題最優解更好的解，

從而導致矛盾。

動態規劃法設計算法一般分成三個階段：

（1）分段：將原問題分解為若干個相互重疊的子問題；

（2）分析：分析問題是否滿足最優性原理，找出動態規劃函數的遞

推式;

（3）求解：利用遞推式自底向上計算，實現動態規劃過程。

動態規劃法利用問題的最優性原理，以自底向上的方式從子問

題的最優解逐步構造出整個問題的最優解。

6.2圖問題中的動態規劃法

6.2.1TSP問題

TSP問題是指旅行家要旅行〃個城市，要求各個城市經歷且僅經歷一

次然后回到出發城市，并要求所走的路程最短。

各個城市間的距離可以用代價矩陣來表示。

證明TSP問題滿足最優性原理

設s,si,s2,…，sp,s是從s出發的一條路徑長度最短的簡單回

路，假設從s到下一個城市si已經求出，則問題轉化為求從si到s的最

短路徑，顯然si,s2,…，sp,s一定構成一條從si到s的最短路徑。

如若不然，設si,r\,i2,rq,s是一條從si到s的最短

路徑且經過hl個不同城市，則s,si,rl,z2,…，rq,s將是一條從s

出發的路徑長度最短的簡單回路且比s,si,s2,…，sp,s要短，從而

導致矛盾。所以，TSP問題滿足最優性原理。

假設從頂點i出發，令Mi,r)表示從頂點，出發經過片中各個頂

點一次且僅一次，最后回到出發點i的最短路徑長度，開始時，v'=v-

{i}，于是，TSP問題的動態規劃函數為：

d(i,/)=min{c?%+d(A,—{*})}(*￡/')(式6.5)

d(k,O)=cki(k次i)(式6.6)

從城市0出發經城市1、2、3然后回到城市0的最短路徑長度是:

<7(0,{1,2,3})=min{c01+d(l,{2,3}),c02+d(2,{1,3}),c03+d(3,

{1,2}))

這是最后一個階段的決策，而:

<7(1,{2,3})=min{cl2+d(2,⑶),cl3+d(3,{2})}

d(2,{1,3})=min{c21+d(l,⑶),c23+d(3,{1})}

d(3,{1,2})=min{c31+d(l,⑵),c32+d(2,{1})}

這一階段的決策又依賴于下面的計算結果:

d(l,⑵)=cl2+d(2,{})d(2,⑶)=c23+d(3,{})

d(3,⑵)=c32+d(2,{})d(l,{3})=cl3+d(3,{})

d(2,{l})=c21+t/(l,{})d(3,{l})=c31+d(l,{})

而下式可以直接獲得(括號中是該決策引起的狀態轉移):

d(l,{})=cl0=5(l-*0)d(2,{})=c20=6(2-0)d(3,{})=c30=3(3

-*o)

再向前倒推，有:

d(l,{2})=cl2+d(2,{})=2+6=8(1-*2)d(l,{3})=cl3+d(3,

{})=3+3=6(1-3)

d(2,{3})=c23+d(3,{})=2+3=5(2-3)d(2,{1})=c21+d(l,

{})=4+5=9(2-1)

d(3,{1})=c31+d(l,{})=7+5=12(31)d(3,⑵)=c32+d(2,

{})=5+6=11(3-2)

再向前倒退，有:

d(l,{2,3})=min{cl2+d(2,{3}),cl3+d(3,{2})}=min{2+5,

3+11}=7(1-*2)

d(2,{1,3})=min{c21+t/(l,{3}),c23+"(3,{l})}=min{4+6,

2+12)=10(2-1)

<7(3,{1,2})=min{c31+d(l,{2}),c32+<7(2,{l})}=min{7+8,

5+9}=14(3-*2)

最后有：

40,{1,2,3})=min{c01+d(l,{2,3}),c02+d(2,{1,3}),c03+

”(3,{1,2})}

=min{3+7,6+10,7+14}=10(0-*l)

所以，從頂點0出發的TSP問題的最短路徑長度為10,路徑是0-1

f2-3-0。

動態規劃法求解TSP問題的填表過程

假設n個頂點用0?nT的數字編號，首先生成1?nT個元素的子集

存放在數組V[2nT]中,設數組d[n][2n-1]存放迭代結果,其中

表示從頂點i經過子集V[j]中的頂點一次且僅一次，最后回到出發點0的

最短路徑長度。

設頂點之間的代價存放在數組c[n][n]中，動態規劃法求解TSP問題

的算法如下：

算法6.1——TSP問題

1.for(i=l;i<n;i++)〃初始化第0列

2.for(j=l;j<2n-l-l;j++)

for(i=l;i<n;i++)〃依次進行第i次迭代

if(子集V[j]中不包含i)

對V[j]中的每個元素k,計算

d[i][j]=min(c[i][k]+d[k][j-1]);

3.對V[2n-1-1]中的每一個元素k,計算

d[0][2n-l-l]=min(c[0][k]+d[k][2n-l-2]);

4.輸出最短路徑長度d[0][2n-bl];

顯然，算法6.1的時間復雜性為。(2〃)。和蠻力法相比，動態規劃法

求解TSP問題，把原來的時間復雜性是。5!)的排列問題，轉化為組合問

題，從而降低了算法的時間復雜性，但它仍需要指數時間。

6.2.2多段圖的最短路徑問題

設圖俏(匕0是一個帶權有向連通圖，如果把頂點集合/劃分成4個

互不相交的子集乙(2WAW/?,使得片中的任何一條邊(〃，v),

必有“金勿，reVi+mIVi+mWk),則稱圖G為多段圖，稱s

仁Pl為源點，方金次為終點。多段圖的最短路徑問題是求從源點到終點的

最小代價路徑。

由于多段圖將頂點劃分為4個互不相交的子集，所以，多段圖劃分為

左段，每一段包含頂點的一個子集。不失一般性，將多段圖的頂點按照段

的順序進行編號，同一段內頂點的相互順序無關緊要。假設圖中的頂點個

數為〃，則源點s的編號為0,終點匕的編號為廳1,并且，對圖中的任何

一條邊(“，0,頂點”的編號小于頂點/的編號。

證明多段圖問題滿足最優性原理

設s,si,跳，…，sp,才是從s到t的一條最短路徑，從源點s開

始，設從s到下一段的頂點si已經求出，則問題轉化為求從si到1的最

短路徑，顯然si,s2,???,sp,力一定構成一條從si?到t的最短路徑，

如若不然，設si,H,r2,…，rq,方是一條從si到1的最短路徑，則

s,si,ri,r2,…，rq,力將是一條從s到方的路徑且比s,si,s2,…，

sp,t的路徑長度要短，從而導致矛盾。所以，多段圖的最短路徑問題滿

足最優性原理。

對多段圖的邊(“，力，用cuv表示邊上的權值，將從源點s到終點t

的最短路徑記為d(s,t),則從源點0到終點9的最短路徑"(0,9)由下

式確定：

d(0,9)=min{c01+t7(l,9),c02+d(2,9),c03+d(3,9)}

這是最后一個階段的決策，它依賴于力1,9)、力2,9)和d(3,9)的

計算結果，而

d(l,9)=min{cl4+d(4,9),cl5+d(5,9))

d(2,9)=min{c24+"(4,9),c25+d(5,9),c26+d(6,9)}

"(3,9)=min{c35+d(5,9),c36+d(6,9))

這一階段的決策又依賴于d(4,9)、d(5,9)和d(6,9)的計

算結果：

d(4,9)=min{c47+d(7,9),c48+d(8,9))

d(5,9)=min{c57+d(7,9),c58+d(8,9))

d(6,9)=min{c67+d(7,