算法設(shè)計(jì)與分析教案

《算法設(shè)計(jì)與分析》教案

張靜

第1章緒論

算法理論的兩大論題：

1.算法設(shè)計(jì)

2.算法分析

1.1算法的基本概念

1.1.1為什么要學(xué)習(xí)算法

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

＞問(wèn)題的求解過(guò)程：

分析問(wèn)題一設(shè)計(jì)算法一編寫程序一整理結(jié)果

＞程序設(shè)計(jì)研究的四個(gè)層次：

算法一方法學(xué)一語(yǔ)言~工具

理由2：提高分析問(wèn)題的能力

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

1.1.2算法及其重要特性

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

序列。

算法的五大特性：

⑴輸入：一個(gè)算法有零個(gè)或多個(gè)輸入。

⑵輸出：一個(gè)算法有一個(gè)或多個(gè)輸出。

⑶有窮性：一個(gè)算法必須總是在執(zhí)行有窮步之后結(jié)束，且每一步都

在有窮時(shí)間內(nèi)完成。

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

入只能得到相同的輸出。

⑸可行性：算法描述的操作可以通過(guò)已經(jīng)實(shí)現(xiàn)的基本操作執(zhí)行有限

次來(lái)實(shí)現(xiàn)。

1.1.3算法的描述方法

⑴自然語(yǔ)言

優(yōu)點(diǎn)：容易理解

缺點(diǎn)：冗長(zhǎng)、二義性

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

注意事項(xiàng)：避免寫成自然段

歐兒里德算法

開(kāi)始

⑶程序設(shè)計(jì)語(yǔ)言

優(yōu)點(diǎn)：能由計(jì)算機(jī)執(zhí)行

缺點(diǎn)：抽象性差，對(duì)語(yǔ)言要求高

使用方法：算法需要驗(yàn)證

注意事項(xiàng)：將算法寫成子函數(shù)

歐幾里德算法

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)偽代碼一一算法語(yǔ)言

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

它采用某一程序設(shè)計(jì)語(yǔ)言的基本語(yǔ)法，操作指令可以結(jié)合自然語(yǔ)言來(lái)設(shè)

計(jì)。

優(yōu)點(diǎn)：表達(dá)能力強(qiáng)，抽象性強(qiáng)，容易理解

使用方法：7±2

歐幾里德算法

1.r=m%n;

2.循環(huán)直到r等于0

2.1m=n;

2.2n=r;

2.3rm%n;

3.輸出n;

1.1.4算法設(shè)計(jì)的一般過(guò)程

1.理解問(wèn)題

2.預(yù)測(cè)所有可能的輸入

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

4.確定適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)

5.算法設(shè)計(jì)技術(shù)

6.描述算法

7.跟蹤算法

8.分析算法的效率

9.根據(jù)算法編寫代碼

1.2算法分析

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

——時(shí)間和空間進(jìn)行估算

>時(shí)間復(fù)雜性(TimeComplexity)

>空間復(fù)雜性(SpaceComplexity)

算法分析的目的：

>設(shè)計(jì)算法一一設(shè)計(jì)出復(fù)雜性盡可能低的算法

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

時(shí)間復(fù)雜性分析的關(guān)鍵:

>問(wèn)題規(guī)模：輸入量的多少;

>基本語(yǔ)句：執(zhí)行次數(shù)與整個(gè)算法的執(zhí)行時(shí)間

成正比的語(yǔ)句

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

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

x++;

問(wèn)題規(guī)模：n

基本語(yǔ)句：x++

1.2.1漸進(jìn)符號(hào)

1.大。符號(hào)

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

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

2.大Q符號(hào)

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

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

3.?符號(hào)

定義1.3若存在三個(gè)正的常數(shù)cl、c2和〃0,對(duì)于任意都有cl

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

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

當(dāng)〃21時(shí)，5〃2+8〃+1W5/72+8〃+A

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

當(dāng)時(shí)，5〃2+8〃+125成=Q（成）

當(dāng)〃21時(shí)，14〃225成+8/?+125成

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

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

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

1.2.2最好、最壞和平均情況

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

該數(shù)組中有且僅有一個(gè)元素值為k)

intFind(intA[],intn)

(

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

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

returni;

}

結(jié)論：如果問(wèn)題規(guī)模相同，時(shí)間代價(jià)與輸入數(shù)據(jù)有關(guān)，則需要分析最

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

/最好情況：出現(xiàn)概率較大時(shí)分析

,最差情況：實(shí)時(shí)系統(tǒng)

/平均情況：已知輸入數(shù)據(jù)是如何分布的，

通常假設(shè)等概率分布

1.2.3非遞歸算法的分析

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

例：求數(shù)組最小值算法

intArrayMin(inta[],intn)

min=a[O];

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

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

returnmin;

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

1.決定用哪個(gè)(或哪些)參數(shù)作為算法問(wèn)題規(guī)模的度量

2.找出算法中的基本語(yǔ)句

3.檢查基本語(yǔ)句的執(zhí)行次數(shù)是否只依賴于問(wèn)題規(guī)模

4.建立基本語(yǔ)句執(zhí)行次數(shù)的求和表達(dá)式

5.用漸進(jìn)符號(hào)表示這個(gè)求和表達(dá)式

?關(guān)鍵：建立一個(gè)代表算法運(yùn)行時(shí)間的求和表達(dá)式，然后用

漸進(jìn)符號(hào)表示這個(gè)求和表達(dá)式。

1.2.4遞歸算法的分析

關(guān)鍵：根據(jù)遞歸過(guò)程建立遞推關(guān)系式，然后求解這個(gè)遞推關(guān)系式。

1.猜測(cè)技術(shù):對(duì)遞推關(guān)系式估計(jì)一個(gè)上限，然后(用數(shù)學(xué)歸納法)證

明它正確。

2.擴(kuò)展遞歸技術(shù)

3.通用分治遞推式

大小為〃的原問(wèn)題分成若干個(gè)大小為的子問(wèn)題，其中a個(gè)子問(wèn)題

需要求解，而。成是合并各個(gè)子問(wèn)題的解需要的工作量。

1.2.5算法的后驗(yàn)分析

算法的后驗(yàn)分析(Posteriori)也稱算法的實(shí)驗(yàn)分析，它是一種事后

計(jì)算的方法，通常需要將算法轉(zhuǎn)換為對(duì)應(yīng)的程序并上機(jī)運(yùn)行。

一般步驟：

1.明確實(shí)驗(yàn)?zāi)康?/p>

2.決定度量算法效率的方法，為實(shí)驗(yàn)準(zhǔn)備算法的程序?qū)崿F(xiàn)

3.決定輸入樣本，生成實(shí)驗(yàn)數(shù)據(jù)

4.對(duì)輸入樣本運(yùn)行算法對(duì)應(yīng)的程序，記錄得到的實(shí)驗(yàn)數(shù)據(jù)

5.分析得到的實(shí)驗(yàn)數(shù)據(jù)

表格法記錄實(shí)驗(yàn)數(shù)據(jù)

散點(diǎn)圖記錄實(shí)驗(yàn)數(shù)據(jù)

問(wèn)題規(guī)模〃

第4章分治法

4.1概述

4.1.1分治法的設(shè)計(jì)思想

將一個(gè)難以直接解決的大問(wèn)題，劃分成一些規(guī)模較小的子問(wèn)題，以便

各個(gè)擊破，分而治之。更一般地說(shuō)，將要求解的原問(wèn)題劃分成衣個(gè)較小規(guī)

模的子問(wèn)題，對(duì)這攵個(gè)子問(wèn)題分別求解。如果子問(wèn)題的規(guī)模仍然不夠小，

則再將每個(gè)子問(wèn)題劃分為4個(gè)規(guī)模更小的子問(wèn)題，如此分解下去，直到問(wèn)

題規(guī)模足夠小，很容易求出其解為止，再將子問(wèn)題的解合并為一個(gè)更大規(guī)

模的問(wèn)題的解，自底向上逐步求出原問(wèn)題的解。

啟發(fā)式規(guī)則：

1.平衡子問(wèn)題：最好使子問(wèn)題的規(guī)模大致相同。也就是將一個(gè)問(wèn)題

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

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

題規(guī)模不等的做法要好。

2.獨(dú)立子問(wèn)題：各子問(wèn)題之間相互獨(dú)立，這涉及到分治法的效率，

如果各子問(wèn)題不是獨(dú)立的，則分治法需要重復(fù)地解公共的子問(wèn)題。

分治法的典型情況

4.1.2分治法的求解過(guò)程

一般來(lái)說(shuō)，分治法的求解過(guò)程由以下三個(gè)階段組成：

（1）劃分：既然是分治，當(dāng)然需要把規(guī)模為n的原問(wèn)題劃分為4個(gè)

規(guī)模較小的子問(wèn)題，并盡量使這在個(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ò)程

DivideConquer（P）

（

if（P的規(guī)模足夠小）直接求解P;

分解為k個(gè)子問(wèn)題Pl,P2,…Pk;

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

yi=DivideConquer(Pi);

returnMerge(yl,?,,,yk);

例：計(jì)算am應(yīng)用分治技術(shù)得到如下計(jì)算方法:

4.2遞歸

4.2.1遞歸的定義

遞歸就是子程序（或函數(shù)）直接調(diào)用自己或通過(guò)一系列調(diào)用語(yǔ)句間接

調(diào)用自己，是一種描述問(wèn)題和解決問(wèn)題的基本方法。

遞歸有兩個(gè)基本要素：

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

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

4.2.2遞歸函數(shù)的運(yùn)行軌跡

在遞歸函數(shù)中，調(diào)用函數(shù)和被調(diào)用函數(shù)是同一個(gè)函數(shù)，需要注意的是

遞歸函數(shù)的調(diào)用層次，如果把調(diào)用遞歸函數(shù)的主函數(shù)稱為第0層，進(jìn)入函

數(shù)后，首次遞歸調(diào)用自身稱為第1層調(diào)用；從第，層遞歸調(diào)用自身稱為第

，+1層。反之，退出第，+1層調(diào)用應(yīng)該返回第，層。采用圖示方法描述遞

歸函數(shù)的運(yùn)行軌跡，從中可較直觀地了解到各調(diào)用層次及其執(zhí)行情況。

4.2.3遞歸函數(shù)的內(nèi)部執(zhí)行過(guò)程

一個(gè)遞歸函數(shù)的調(diào)用過(guò)程類似于多個(gè)函數(shù)的嵌套調(diào)用，只不過(guò)調(diào)用函

數(shù)和被調(diào)用函數(shù)是同一個(gè)函數(shù)。為了保證遞歸函數(shù)的正確執(zhí)行，系統(tǒng)需設(shè)

立一個(gè)工作棧。具體地說(shuō)，遞歸調(diào)用的內(nèi)部執(zhí)行過(guò)程如下：

(1)運(yùn)行開(kāi)始時(shí)，首先為遞歸調(diào)用建立一個(gè)工作棧，其結(jié)構(gòu)包括值

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

(2)每次執(zhí)行遞歸調(diào)用之前，把遞歸函數(shù)的值參和局部變量的當(dāng)前

值以及調(diào)用后的返回地址壓棧;

（3）每次遞歸調(diào)用結(jié)束后，將棧頂元素出棧，使相應(yīng)的值參和局部

變量恢復(fù)為調(diào)用前的值，然后轉(zhuǎn)向返回地址指定的位置繼續(xù)執(zhí)行。

漢諾塔算法在執(zhí)行過(guò)程中，工作棧的變化下圖所示，其中棧元素的結(jié)

構(gòu)為（返回地址，n值，A值，B值，C值），返回地址對(duì)應(yīng)算法中語(yǔ)句的

行號(hào)。

遞歸算法結(jié)構(gòu)清晰，可讀性強(qiáng)，而且容易用數(shù)學(xué)歸納法來(lái)證明算法的

正確性，因此，它為設(shè)計(jì)算法和調(diào)試程序帶來(lái)很大方便，是算法設(shè)計(jì)中的

一種強(qiáng)有力的工具。但是，因?yàn)檫f歸算法是一種自身調(diào)用自身的算法，隨

著遞歸深度的增加，工作棧所需要的空間增大，遞歸調(diào)用時(shí)的輔助操作增

多，因此，遞歸算法的運(yùn)行效率較低。

4.3排序問(wèn)題中的分治法

4.3.1歸并排序

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

（1）劃分：將待排序序列力，12,…，277劃分為兩個(gè)長(zhǎng)度相等的子

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

（2）求解子問(wèn)題：分別對(duì)這兩個(gè)子序列進(jìn)行排序，得到兩個(gè)有序子

序列；

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

算法4.3---歸并排序

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

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

else{

m=(s+t)/2;

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

列

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

列

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

序列

}

}

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

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

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

elsewhile(j<=t)

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

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

)

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

法存在如下遞推式：

、1n1

7(〃)/

27(〃/2)nn1

根據(jù)1.2.4節(jié)的主定理，二路歸并排序的時(shí)間代價(jià)是0(〃log2〃)。

二路歸并排序在合并過(guò)程中需要與原始記錄序列同樣數(shù)量的存儲(chǔ)空

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

4.3.2快速排序

快速排序的分治策略是：

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

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

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

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

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

進(jìn)行的，所以合并不需要執(zhí)行任何操作。

?歸并排序按照記錄在序列中的位置對(duì)序列進(jìn)行劃分,

。快速排序按照記錄的值對(duì)序列進(jìn)行劃分。

以第一個(gè)記錄作為軸值，對(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è)的記錄小(即反序)，若i<j,則將基準(zhǔn)記錄與j指向的記錄進(jìn)行交

換；

(3)左側(cè)掃描過(guò)程：將基準(zhǔn)記錄與i指向的記錄進(jìn)行比較，如果i

指向記錄的關(guān)鍵碼小，則i后移一個(gè)記錄位置。重復(fù)左側(cè)掃描過(guò)程，直到

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

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

的位置。

一次劃分示例

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

到前面

i++;

)

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

if(i<j){

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

到后面

}

)

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

}

以軸值為基準(zhǔn)將待排序序列劃分為兩個(gè)子序列后，對(duì)每一個(gè)子序列分

別遞歸進(jìn)行排序。

算法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)行快速排序

}

}

在最好情況下，每次劃分對(duì)一個(gè)記錄定位后，該記錄的左側(cè)子序列與

右側(cè)子序列的長(zhǎng)度相同。在具有〃個(gè)記錄的序列中，一次劃分需要對(duì)整個(gè)

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

進(jìn)行排序的時(shí)間，每次劃分后，正好把待劃分區(qū)間劃分為長(zhǎng)度相等的兩個(gè)

子序列，則有：

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

因此，時(shí)間復(fù)雜度為0(〃log2〃)。

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

上一次劃分少一個(gè)記錄的子序列(另一個(gè)子序列為空)。此時(shí)，必須經(jīng)過(guò)

51次遞歸調(diào)用才能把所有記錄定位，而且第，趟劃分需要經(jīng)過(guò)小，.次關(guān)

鍵碼的比較才能找到第，個(gè)記錄的基準(zhǔn)位置，因此，總的比較次數(shù)為：

因此，時(shí)間復(fù)雜度為0(為)。

在平均情況下，設(shè)基準(zhǔn)記錄的關(guān)鍵碼第4小(1W4。)，則有：

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

0(nlog2n)a

4.4組合問(wèn)題中的分治法

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

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

該序列形如的最大值(lWiW/W”)，當(dāng)序列中所有整數(shù)均為負(fù)整數(shù)時(shí),

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

為：

最大子段和問(wèn)題的分治策略是：

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

成長(zhǎng)度相同的兩個(gè)子序列（al,…，a）和（2+1,…，an）,

則會(huì)出現(xiàn)以下三種情況：

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

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

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

（2）求解子問(wèn)題：對(duì)于劃分階段的情況①和②可遞歸求解，情況③

需要分別計(jì)算

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

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

中的較大者為原問(wèn)題的解。

算法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)情況②，遞

歸求解

sl=O;lefts=O;〃以下對(duì)應(yīng)情況③，先求

解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;〃計(jì)算情況③的最大子段和

if(sum<leftsum)sum=leftsum;

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

較大者

if(sum<rightsum)sum=rightsum;

)

returnsum;

)

分析算法4.7的時(shí)間性能，對(duì)應(yīng)劃分得到的情況①和②，需要分別遞

歸求解，對(duì)應(yīng)情況③，兩個(gè)并列for循環(huán)的時(shí)間復(fù)雜性是。(〃)，所以，存

在如下遞推式：

根據(jù)1.2.4節(jié)主定理，算法4.7的時(shí)間復(fù)雜性為0(〃log2〃)。

4.4.2棋盤覆蓋問(wèn)題

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

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

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

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

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

大小相同，并且每個(gè)子棋盤均包含一個(gè)特殊方格，從而將原問(wèn)題分解為規(guī)

模較小的棋盤覆蓋問(wèn)題。

冷0時(shí)，可將2在X2A的棋盤劃分為4個(gè)24-lX2hl的子棋盤，這樣

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

子棋盤包含該特殊方格，其余3個(gè)子棋盤中沒(méi)有特殊方格。為了將這3個(gè)

沒(méi)有特殊方格的子棋盤轉(zhuǎn)化為特殊棋盤，以便采用遞歸方法求解，可以用

一個(gè)L型骨牌覆蓋這3個(gè)較小棋盤的會(huì)合處，從而將原問(wèn)題轉(zhuǎn)化為4個(gè)較

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

XI的子棋盤。

下面討論棋盤覆蓋問(wèn)題中數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)。

（1）棋盤：可以用一個(gè)二維數(shù)組board[size][size]表示一個(gè)棋盤，

其中，size=2Ao為了在遞歸處理的過(guò)程中使用同一個(gè)棋盤，將數(shù)組board

設(shè)為全局變量；

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

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

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

特殊方格在二維數(shù)組board中的下標(biāo)；

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

到L型骨牌的個(gè)數(shù)為（4代1）/3,將所有L型骨牌從1開(kāi)始連續(xù)編號(hào)，用一

個(gè)全局變量t表示。

算法4.8---棋盤覆蓋

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

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

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

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

格

t++;〃1型骨牌號(hào)

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

//覆蓋左上角子棋盤

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

子棋盤中

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

子棋盤

else{〃用t號(hào)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號(hào)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號(hào)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號(hào)L型骨牌覆蓋左上角，再遞歸處理

子棋盤

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

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

!

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

7々)滿足如下遞推式：

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

個(gè)數(shù)為(4kl)/3,所以，算法4.8是一個(gè)在漸進(jìn)意義下的最優(yōu)算法。

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

設(shè)有爐2A個(gè)選手要進(jìn)行網(wǎng)球循環(huán)賽，要求設(shè)計(jì)一個(gè)滿足以下要求的

比賽日程表：

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

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

按此要求,可將比賽日程表設(shè)計(jì)成一個(gè)n行小1列的二維表,

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

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

比賽日程表就可以通過(guò)為n/2=2k-\個(gè)選手設(shè)計(jì)的比賽日程表來(lái)決定。遞

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

簡(jiǎn)單：只要讓這2個(gè)選手進(jìn)行比賽就可以了。

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

手比賽

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

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

上角部分的所有數(shù)字按其對(duì)應(yīng)位置抄到右下角，將左下角的所有數(shù)字按其

對(duì)應(yīng)位置抄到右上角，這樣，就分別安排好了選手1至選手4以及選手5

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

依此類推。

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

24個(gè)選手的比賽日程問(wèn)題，換言之，2★個(gè)選手的比賽日程是在2hl個(gè)選

手的比賽日程的基礎(chǔ)上通過(guò)迭代的方法求得的。在每次迭代中，將問(wèn)題劃

分為4部分：

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

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

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

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

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

的比賽日程；

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

比賽日程；

算法設(shè)計(jì)的關(guān)鍵在于尋找這4部分元素之間的對(duì)應(yīng)關(guān)系。

算法4.9——循環(huán)賽日程表

voidGameTable(intk,inta[][])

(

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

〃二維數(shù)組a表示日程安排，數(shù)組下標(biāo)從1開(kāi)始

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

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

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

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

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

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

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;

〃左下角元素和左上角元素的對(duì)應(yīng)關(guān)系

〃填右上角元素

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的時(shí)間性能，迭代處理的循環(huán)體內(nèi)部有3個(gè)循環(huán)語(yǔ)句，

每個(gè)循環(huán)語(yǔ)句都是一個(gè)嵌套的for循環(huán)，且他們的執(zhí)行次數(shù)相同，基本語(yǔ)

句是最內(nèi)層循環(huán)體的賦值語(yǔ)句，即填寫比賽日程表中的元素?；菊Z(yǔ)句的

執(zhí)行次數(shù)是:

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

4.5幾何問(wèn)題中的分治法

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

設(shè)。1=(x1,yl),p2=(A2,總)，…，pn={xn,y”)是平面上〃個(gè)點(diǎn)構(gòu)

成的集合S,最近對(duì)問(wèn)題就是找出集合S中距離最近的點(diǎn)對(duì)。

嚴(yán)格地講，最接近點(diǎn)對(duì)可能多于一對(duì)，簡(jiǎn)單起見(jiàn)，只找出其

中的一對(duì)作為問(wèn)題的解。

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

51和S2,每個(gè)子集中有〃/2個(gè)點(diǎn)。然后在每個(gè)子集中遞歸地求其最接近

的點(diǎn)對(duì)，在求出每個(gè)子集的最接近點(diǎn)對(duì)后，在合并步中，如果集合S中

最接近的兩個(gè)點(diǎn)都在子集S1或52中，則問(wèn)題很容易解決，如果這兩個(gè)

點(diǎn)分別在51和52中，問(wèn)題就比較復(fù)雜了。

為了使問(wèn)題易于理解，先考慮一維的情形。

此時(shí)，S中的點(diǎn)退化為x軸上的〃個(gè)點(diǎn)xl,嵬，…，xn。用x軸上的

某個(gè)點(diǎn)勿將S劃分為兩個(gè)集合51和52,并且51和52含有點(diǎn)的個(gè)數(shù)相同。

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

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

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

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

按這種分治策略求解最近對(duì)問(wèn)題的算法效率取決于劃分點(diǎn)力的選取，

一個(gè)基本的要求是要遵循平衡子問(wèn)題的原則。如果選取

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

51和52的不平衡，如果用S中各點(diǎn)坐標(biāo)的中位數(shù)(即S的中值)作為分

割點(diǎn)，則會(huì)得到一個(gè)平衡的分割點(diǎn)勿，使得子集51和52中有個(gè)數(shù)大致相

同的點(diǎn)。

下面考慮二維的情形，此時(shí)S中的點(diǎn)為平面上的點(diǎn)。

為了將平面上的點(diǎn)集S分割為點(diǎn)的個(gè)數(shù)大致相同的兩個(gè)子集51和

52,選取垂直線下力來(lái)作為分割線，其中，加為S中各點(diǎn)x坐標(biāo)的中位數(shù)。

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

和S2上求解最近對(duì)問(wèn)題，分別得到51中的最近距離M和52中的最近距

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

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

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

網(wǎng)和K中，垂直帶之外的任何點(diǎn)對(duì)之間的距離都一定大于d。

對(duì)于點(diǎn),《外，需要考察風(fēng)中的各個(gè)點(diǎn)和點(diǎn)P之間的距離是否小于d,

顯然，K中這樣點(diǎn)的y軸坐標(biāo)一定位于區(qū)間［廠“尹M之間，而且，這樣

的點(diǎn)不會(huì)超過(guò)6個(gè)。

應(yīng)用分治法求解含有〃個(gè)點(diǎn)的最近對(duì)問(wèn)題，其時(shí)間復(fù)雜性可由下面的

遞推式表示：

合并子問(wèn)題的解的時(shí)間A〃)=0(1),根據(jù)1.2.4節(jié)的主定理，可得

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

4.5.2凸包問(wèn)題

設(shè)。1=（x1,yl）,p2=（A2,總），…，pn={xn,y”）是平面上〃個(gè)點(diǎn)構(gòu)

成的集合S,并且這些點(diǎn)按照x軸坐標(biāo)升序排列。幾何學(xué)中有這樣一個(gè)明

顯的事實(shí)：最左邊的點(diǎn)夕1和最右邊的點(diǎn)功一定是該集合的凸包頂點(diǎn)（即

極點(diǎn)）。設(shè)夕1W是從夕1到功的直線，這條直線把集合S分成兩個(gè)子集：

51是位于直線左側(cè)和直線上的點(diǎn)構(gòu)成的集合，S2是位于直線右側(cè)和直線

上的點(diǎn)構(gòu)成的集合。51的凸包由下列線段構(gòu)成：以01和功為端點(diǎn)的線段

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

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

包和下包構(gòu)成的。

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

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

點(diǎn)構(gòu)成集合51,1,S1中所有在直線加祝w右側(cè)的點(diǎn)構(gòu)成集合51,2,包含

在三角形"的中1勿之中的點(diǎn)可以不考慮了。遞歸地繼續(xù)構(gòu)造集合51,1的

上包和集合51,2的上包，然后將求解過(guò)程中得到的所有最遠(yuǎn)距離的點(diǎn)連

接起來(lái)，就可以得到集合51的上包。

接下來(lái)的問(wèn)題是如何判斷一個(gè)點(diǎn)是否在給定直線的左側(cè)（或右側(cè)）？

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

是平面上的任意三個(gè)點(diǎn)，則三角形0102P3的面積等于下面這個(gè)行列式的

絕對(duì)值的一半：

當(dāng)且僅當(dāng)點(diǎn)03=（x3,為）位于直線0102的左側(cè)時(shí)，該式的符號(hào)為正。

可以在一個(gè)常數(shù)時(shí)間內(nèi)檢查一個(gè)點(diǎn)是否位于兩個(gè)點(diǎn)確定的直線的左側(cè)，并

且可以求得這個(gè)點(diǎn)到該直線的距離。

第6章動(dòng)態(tài)規(guī)劃法

6.1.1最優(yōu)化問(wèn)題

最優(yōu)化問(wèn)題：有〃個(gè)輸入，它的解由這〃個(gè)輸入的一個(gè)子集組成，這

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

條件的解稱為問(wèn)題的可行解。滿足約束條件的可行解可能不只一個(gè)，為了

衡量這些可行解的優(yōu)劣，事先給出一定的標(biāo)準(zhǔn)，這些標(biāo)準(zhǔn)通常以函數(shù)的形

式給出，這些標(biāo)準(zhǔn)函數(shù)稱為目標(biāo)函數(shù)，使目標(biāo)函數(shù)取得極值（極大或極?。?/p>

的可行解稱為最優(yōu)解，這類問(wèn)題就稱為最優(yōu)化問(wèn)題。

例：付款問(wèn)題：

超市的自動(dòng)柜員機(jī)（POS機(jī)）要找給顧客數(shù)量最少的現(xiàn)金。

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

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

從夕中選取一個(gè)最小子集S,使得

（式6.1）

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

x=?PQ（式6.2）

,[0Pi史S

那么，P0S機(jī)支付的現(xiàn)金必須滿足

（式6.3）

并且

（式6.4）

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

式6.2是解的表現(xiàn)形式，因?yàn)橄蛄縄中有〃個(gè)元素，每個(gè)元素的取值為0

或1,所以，可以有2〃個(gè)不同的向量，所有這些向量的全體構(gòu)成該問(wèn)題的

解空間，式6.3是該問(wèn)題的約束條件，式6.4是該問(wèn)題的目標(biāo)函數(shù)，使式

6.4取得極小值的解稱為該問(wèn)題的最優(yōu)解。

6.1.2最優(yōu)性原理

對(duì)于一個(gè)具有〃個(gè)輸入的最優(yōu)化問(wèn)題，其求解過(guò)程往往可以劃分為若

干個(gè)階段，每一階段的決策僅依賴于前一階段的狀態(tài)，由決策所采取的動(dòng)

作使?fàn)顟B(tài)發(fā)生轉(zhuǎn)移，成為下一階段決策的依據(jù)。從而，一個(gè)決策序列在不

斷變化的狀態(tài)中產(chǎn)生。這個(gè)決策序列產(chǎn)生的過(guò)程稱為多階段決策過(guò)程。

在每一階段的決策中有一個(gè)賴以決策的策略或目標(biāo)，這種策略或目標(biāo)

是由問(wèn)題的性質(zhì)和特點(diǎn)所確定，通常以函數(shù)的形式表示并具有遞推關(guān)系，

稱為動(dòng)態(tài)規(guī)劃函數(shù)。

多階段決策過(guò)程滿足最優(yōu)性原理(OptimalPrinciple)：無(wú)論決策過(guò)

程的初始狀態(tài)和初始決策是什么，其余的決策都必須相對(duì)于初始決策所產(chǎn)

生的當(dāng)前狀態(tài)，構(gòu)成一個(gè)最優(yōu)決策序列。

如果一個(gè)問(wèn)題滿足最優(yōu)性原理通常稱此問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。

6.1.3動(dòng)態(tài)規(guī)劃法的設(shè)計(jì)思想

動(dòng)態(tài)規(guī)劃法將待求解問(wèn)題分解成若干個(gè)相互重疊的子問(wèn)題，每個(gè)子問(wèn)

題對(duì)應(yīng)決策過(guò)程的一個(gè)階段，一般來(lái)說(shuō)，子問(wèn)題的重疊關(guān)系表現(xiàn)在對(duì)給定

問(wèn)題求解的遞推關(guān)系（也就是動(dòng)態(tài)規(guī)劃函數(shù)）中，將子問(wèn)題的解求解一次

并填入表中，當(dāng)需要再次求解此子問(wèn)題時(shí)，可以通過(guò)查表獲得該子問(wèn)題的

解而不用再次求解，從而避免了大量重復(fù)計(jì)算。

動(dòng)態(tài)規(guī)劃法的求解過(guò)程

例：計(jì)算斐波那契數(shù)：

爐5時(shí)分治法計(jì)算斐波那契數(shù)的過(guò)程。

注意到，計(jì)算網(wǎng)〃）是以計(jì)算它的兩個(gè)重疊子問(wèn)題以中1）和夕（h2）的

形式來(lái)表達(dá)的，所以，可以設(shè)計(jì)一張表填入戶1個(gè)網(wǎng)力的值。

動(dòng)態(tài)規(guī)劃法求解斐波那契數(shù)網(wǎng)9）的填表過(guò)程：

用動(dòng)態(tài)規(guī)劃法求解的問(wèn)題具有特征：

,能夠分解為相互重疊的若干子問(wèn)題；

/滿足最優(yōu)性原理（也稱最優(yōu)子結(jié)構(gòu)性質(zhì)）：該問(wèn)題的最優(yōu)

解中也包含著其子問(wèn)題的最優(yōu)解。

（用反證法）分析問(wèn)題是否滿足最優(yōu)性原理：

1.先假設(shè)由問(wèn)題的最優(yōu)解導(dǎo)出的子問(wèn)題的解不是最優(yōu)的；

2.然后再證明在這個(gè)假設(shè)下可構(gòu)造出比原問(wèn)題最優(yōu)解更好的解，

從而導(dǎo)致矛盾。

動(dòng)態(tài)規(guī)劃法設(shè)計(jì)算法一般分成三個(gè)階段：

（1）分段：將原問(wèn)題分解為若干個(gè)相互重疊的子問(wèn)題；

（2）分析：分析問(wèn)題是否滿足最優(yōu)性原理，找出動(dòng)態(tài)規(guī)劃函數(shù)的遞

推式;

（3）求解：利用遞推式自底向上計(jì)算，實(shí)現(xiàn)動(dòng)態(tài)規(guī)劃過(guò)程。

動(dòng)態(tài)規(guī)劃法利用問(wèn)題的最優(yōu)性原理，以自底向上的方式從子問(wèn)

題的最優(yōu)解逐步構(gòu)造出整個(gè)問(wèn)題的最優(yōu)解。

6.2圖問(wèn)題中的動(dòng)態(tài)規(guī)劃法

6.2.1TSP問(wèn)題

TSP問(wèn)題是指旅行家要旅行〃個(gè)城市，要求各個(gè)城市經(jīng)歷且僅經(jīng)歷一

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

各個(gè)城市間的距離可以用代價(jià)矩陣來(lái)表示。

證明TSP問(wèn)題滿足最優(yōu)性原理

設(shè)s,si,s2,…，sp,s是從s出發(fā)的一條路徑長(zhǎng)度最短的簡(jiǎn)單回

路，假設(shè)從s到下一個(gè)城市si已經(jīng)求出，則問(wèn)題轉(zhuǎn)化為求從si到s的最

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

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

路徑且經(jīng)過(guò)hl個(gè)不同城市，則s,si,rl,z2,…，rq,s將是一條從s

出發(fā)的路徑長(zhǎng)度最短的簡(jiǎn)單回路且比s,si,s2,…，sp,s要短，從而

導(dǎo)致矛盾。所以，TSP問(wèn)題滿足最優(yōu)性原理。

假設(shè)從頂點(diǎn)i出發(fā)，令Mi,r)表示從頂點(diǎn)，出發(fā)經(jīng)過(guò)片中各個(gè)頂

點(diǎn)一次且僅一次，最后回到出發(fā)點(diǎn)i的最短路徑長(zhǎng)度，開(kāi)始時(shí)，v'=v-

{i}，于是，TSP問(wèn)題的動(dòng)態(tài)規(guī)劃函數(shù)為：

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

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

從城市0出發(fā)經(jīng)城市1、2、3然后回到城市0的最短路徑長(zhǎng)度是:

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

{1,2}))

這是最后一個(gè)階段的決策，而:

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

這一階段的決策又依賴于下面的計(jì)算結(jié)果:

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

而下式可以直接獲得(括號(hào)中是該決策引起的狀態(tài)轉(zhuǎn)移):

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)

所以，從頂點(diǎn)0出發(fā)的TSP問(wèn)題的最短路徑長(zhǎng)度為10,路徑是0-1

f2-3-0。

動(dòng)態(tài)規(guī)劃法求解TSP問(wèn)題的填表過(guò)程

假設(shè)n個(gè)頂點(diǎn)用0?nT的數(shù)字編號(hào)，首先生成1?nT個(gè)元素的子集

存放在數(shù)組V[2nT]中,設(shè)數(shù)組d[n][2n-1]存放迭代結(jié)果,其中

表示從頂點(diǎn)i經(jīng)過(guò)子集V[j]中的頂點(diǎn)一次且僅一次，最后回到出發(fā)點(diǎn)0的

最短路徑長(zhǎng)度。

設(shè)頂點(diǎn)之間的代價(jià)存放在數(shù)組c[n][n]中，動(dòng)態(tài)規(guī)劃法求解TSP問(wèn)題

的算法如下：

算法6.1——TSP問(wèn)題

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

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

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

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

對(duì)V[j]中的每個(gè)元素k,計(jì)算

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

3.對(duì)V[2n-1-1]中的每一個(gè)元素k,計(jì)算

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

4.輸出最短路徑長(zhǎng)度d[0][2n-bl];

顯然，算法6.1的時(shí)間復(fù)雜性為。(2〃)。和蠻力法相比，動(dòng)態(tài)規(guī)劃法

求解TSP問(wèn)題，把原來(lái)的時(shí)間復(fù)雜性是。5!)的排列問(wèn)題，轉(zhuǎn)化為組合問(wèn)

題，從而降低了算法的時(shí)間復(fù)雜性，但它仍需要指數(shù)時(shí)間。

6.2.2多段圖的最短路徑問(wèn)題

設(shè)圖俏(匕0是一個(gè)帶權(quán)有向連通圖，如果把頂點(diǎn)集合/劃分成4個(gè)

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

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

仁Pl為源點(diǎn)，方金次為終點(diǎn)。多段圖的最短路徑問(wèn)題是求從源點(diǎn)到終點(diǎn)的

最小代價(jià)路徑。

由于多段圖將頂點(diǎn)劃分為4個(gè)互不相交的子集，所以，多段圖劃分為

左段，每一段包含頂點(diǎn)的一個(gè)子集。不失一般性，將多段圖的頂點(diǎn)按照段

的順序進(jìn)行編號(hào)，同一段內(nèi)頂點(diǎn)的相互順序無(wú)關(guān)緊要。假設(shè)圖中的頂點(diǎn)個(gè)

數(shù)為〃，則源點(diǎn)s的編號(hào)為0,終點(diǎn)匕的編號(hào)為廳1,并且，對(duì)圖中的任何

一條邊(“，0,頂點(diǎn)”的編號(hào)小于頂點(diǎn)/的編號(hào)。

證明多段圖問(wèn)題滿足最優(yōu)性原理

設(shè)s,si,跳，…，sp,才是從s到t的一條最短路徑，從源點(diǎn)s開(kāi)

始，設(shè)從s到下一段的頂點(diǎn)si已經(jīng)求出，則問(wèn)題轉(zhuǎn)化為求從si到1的最

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

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

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

sp,t的路徑長(zhǎng)度要短，從而導(dǎo)致矛盾。所以，多段圖的最短路徑問(wèn)題滿

足最優(yōu)性原理。

對(duì)多段圖的邊(“，力，用cuv表示邊上的權(quán)值，將從源點(diǎn)s到終點(diǎn)t

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

式確定：

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

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

計(jì)算結(jié)果，而

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)的計(jì)

算結(jié)果：

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,