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

1、算法設(shè)計(jì)與分析教案張靜第 1章緒論算法理論的兩大論題：1. 算法設(shè)計(jì)2. 算法分析1.1 算法的基本概念1.1.1 為什么要學(xué)習(xí)算法理由1 ： 算法程序的靈魂問題的求解過程：分析問題“設(shè)計(jì)算法”編寫程序“整理結(jié)果程序設(shè)計(jì)研究的四個(gè)層次：算法“方法學(xué)”語言”工具理由2： 提高分析問題的能力算法的形式化”思維的邏輯性、條理性1.1.2 算法及其重要特性算法( Algorithm ) ：對(duì)特定問題求解步驟的一種描述，是指令的有限序列。算法的五大特性： 輸入：一個(gè)算法有零個(gè)或多個(gè)輸入。 輸出：一個(gè)算法有一個(gè)或多個(gè)輸出。 有窮性：一個(gè)算法必須總是在執(zhí)行有窮步之后結(jié)束，且每一步都在有窮時(shí)間內(nèi)完成。 確定性

2、：算法中的每一條指令必須有確切的含義，對(duì)于相同的輸入只能得到相同的輸出。 可行性：算法描述的操作可以通過已經(jīng)實(shí)現(xiàn)的基本操作執(zhí)行有限次來實(shí)現(xiàn)。1.1.3 算法的描述方法 自然語言優(yōu)點(diǎn)：容易理解缺點(diǎn)：冗長、二義性使用方法：粗線條描述算法思想注意事項(xiàng)：避免寫成自然段歐幾里德算法優(yōu)點(diǎn)：能由計(jì)算機(jī)執(zhí)行缺點(diǎn)：抽象性差，對(duì)語言要求高使用方法：算法需要驗(yàn)證注意事項(xiàng)：將算法寫成子函數(shù)歐幾里德算法#include <iostream.h>int CommonFactor(int m, int n)int r=m % n;while (r!=0)m=n;n=r;r=m % n;return n;void

3、 main( )cout<<CommonFactor(63, 54)<<endl; 偽代碼算法語言偽代碼(Pseudocode) ：介于自然語言和程序設(shè)計(jì)語言之間的方法，它采用某一程序設(shè)計(jì)語言的基本語法，操作指令可以結(jié)合自然語言來設(shè)計(jì)。優(yōu)點(diǎn)：表達(dá)能力強(qiáng)，抽象性強(qiáng)，容易理解使用方法：7 ± 2歐幾里德算法1. r = m % n;2. 循環(huán)直到r 等于 02.1 m = n;2.2 n = r;2.3 r = m % n;3. 輸出 n ;1.1.4 算法設(shè)計(jì)的一般過程1 理解問題2預(yù)測所有可能的輸入3. 在精確解和近似解間做選擇4. 確定適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)5算法設(shè)

4、計(jì)技術(shù)6描述算法7跟蹤算法8分析算法的效率9根據(jù)算法編寫代碼1.2 算法分析算法分析(Algorithm Analysis ) ：對(duì)算法所需要的兩種計(jì)算機(jī)資源時(shí)間和空間進(jìn)行估算時(shí)間復(fù)雜性(Time Complexity )空間復(fù)雜性(Space Complexity )算法分析的目的：設(shè)計(jì)算法設(shè)計(jì)出復(fù)雜性盡可能低的算法選擇算法在多種算法中選擇其中復(fù)雜性最低者時(shí)間復(fù)雜性分析的關(guān)鍵：問題規(guī)模：輸入量的多少;基本語句：執(zhí)行次數(shù)與整個(gè)算法的執(zhí)行時(shí)間成正比的語句for (i=1; i<=n; i+)for (j=1; j<=n; j+)x+;問題規(guī)模：n基本語句：x+1.2.1漸進(jìn)符號(hào)1 .

5、大。符號(hào)定義1.1若存在兩個(gè)正的常數(shù)c和n0,對(duì)于任意n>n0,都有T(n)問題規(guī)模n2 .大Q符號(hào)定義1.2 若存在兩個(gè)正的常數(shù) c和n0,對(duì)于任意n>n0,都有T； n)cxg(n),則稱 T(n)=Q(g(n)T(n)cx g( n)n。之前的情況無關(guān)緊要n。問題規(guī)模n3 .。符號(hào)定義1.3若存在三個(gè)正的常數(shù)cl、c2和n0,對(duì)于任意n>n0都有clxf(n) >T(n) >c2xf (n),則稱 T( n尸 X (f (n)例：T( n) = 5n2 + 8n + 1當(dāng) n>1 時(shí)，5n2+8n+1 0 5n2+8n+n= 5n2+ 9n< 5

6、n2+ 9n2< 14n2= 0( n2)當(dāng) n>1 時(shí)，5n2+8n+1)5n2= Q(n2)，當(dāng) n)1 時(shí)，14n2>5n2+8n+1>5n2貝U: 5n2+8n+ 1=O(n2)定理 1.1 若 T(n)=amnn+ am-1nm-1 + + a1n+a0 (am>0),貝U有T( n)=qnn)且 T( n尸 Q (n m),因此，有 T(n)= O ( n m)。1.2.2 最好、最壞和平均情況例：在一維整型數(shù)組An 中順序查找與給定值k 相等的元素(假設(shè)該數(shù)組中有且僅有一個(gè)元素值為k)int Find(int A , int n)for (i=0;

7、i<n; i+) if (Ai= =k) break;return i;結(jié)論：如果問題規(guī)模相同，時(shí)間代價(jià)與輸入數(shù)據(jù)有關(guān)，則需要分析最好情況、最壞情況、平均情況。最好情況：出現(xiàn)概率較大時(shí)分析 最差情況：實(shí)時(shí)系統(tǒng) 平均情況：已知輸入數(shù)據(jù)是如何分布的，通常假設(shè)等概率分布1.2.3 非遞歸算法的分析算法非遞歸算法、遞歸算法 例：求數(shù)組最小值算法int ArrayMin(int a , int n)min=a0;for (i=1; i<n; i+)if (ai<min) min=ai;return min;非遞歸算法分析的一般步驟：1. 決定用哪個(gè)(或哪些)參數(shù)作為算法問題規(guī)模的度量2

8、. 找出算法中的基本語句3. 檢查基本語句的執(zhí)行次數(shù)是否只依賴于問題規(guī)模4. 建立基本語句執(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ān)系式，然后求解這個(gè)遞推關(guān)系式。1. 猜測技術(shù): 對(duì)遞推關(guān)系式估計(jì)一個(gè)上限，然后(用數(shù)學(xué)歸納法)證明它正確。2. 擴(kuò)展遞歸技術(shù)3. 通用分治遞推式大小為 n 的原問題分成若干個(gè)大小為n/ b 的子問題，其中a 個(gè)子問題需要求解，而cnk是合并各個(gè)子問題的解需要的工作量1.2.5 算法的后驗(yàn)分析算法的后驗(yàn)分析(Posterio

9、ri )也稱算法的實(shí)驗(yàn)分析，它是一種事后 計(jì)算的方法，通常需要將算法轉(zhuǎn)換為對(duì)應(yīng)的程序并上機(jī)運(yùn)行。一般步驟：1 .明確實(shí)驗(yàn)?zāi)康? .決定度量算法效率的方法，為實(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ù)問題規(guī)模n第 4 章 分治法4.1 概 述4.1.1 分治法的設(shè)計(jì)思想將一個(gè)難以直接解決的大問題，劃分成一些規(guī)模較小的子問題，以便各個(gè)擊破，分而治之。更一般地說，將要求解的原問題劃分成k 個(gè)較小規(guī)模的子問題，對(duì)這k 個(gè)子問題分別求解。如果子問題的規(guī)模仍然不夠小，則再將每個(gè)子問

10、題劃分為k 個(gè)規(guī)模更小的子問題，如此分解下去，直到問題規(guī)模足夠小，很容易求出其解為止，再將子問題的解合并為一個(gè)更大規(guī)模的問題的解，自底向上逐步求出原問題的解。啟發(fā)式規(guī)則：1. 平衡子問題：最好使子問題的規(guī)模大致相同。也就是將一個(gè)問題劃分成大小相等的k個(gè)子問題(通常k=2),這種使子問題規(guī)模大致相等的做法是出自一種平衡(Balancing )子問題的思想，它幾乎總是比子問題規(guī)模不等的做法要好。2. 獨(dú)立子問題：各子問題之間相互獨(dú)立，這涉及到分治法的效率，如果各子問題不是獨(dú)立的，則分治法需要重復(fù)地解公共的子問題。分治法的典型情況4.1.2 分治法的求解過程一般來說，分治法的求解過程由以下三個(gè)階段組

11、成：(1)劃分：既然是分治，當(dāng)然需要把規(guī)模為n的原問題劃分為規(guī)模較小的子問題，并盡量使這k個(gè)子問題的規(guī)模大致相同。(2)求解子問題：各子問題的解法與原問題的解法通常是相同的， 可以用遞歸的方法求解各個(gè)子問題，有時(shí)遞歸處理也可以用循環(huán)來實(shí)現(xiàn)。(3)合并：把各個(gè)子問題的解合并起來，合并的代價(jià)因情況不同有 很大差異，分治算法的有效性很大程度上依賴于合并的實(shí)現(xiàn)。分治法的一般過程DivideConquer(P)if(P的規(guī)模足夠小)直接求解 P;分解為k個(gè)子問題P1,P2,Pk;for(i=1;i<=k;i+)yi= DivideConquer(Pi);return Merge(y1, ,yk);

12、例：計(jì)算an,應(yīng)用分治技術(shù)得到如下計(jì)算方法:分解問題求解每個(gè)子問題合并子問題的解4.2 遞歸4.2.1 遞歸的定義遞歸就是子程序（或函數(shù)）直接調(diào)用自己或通過一系列調(diào)用語句間接 調(diào)用自己，是一種描述問題和解決問題的基本方法。遞歸有兩個(gè)基本要素：邊界條件：確定遞歸到何時(shí)終止；遞歸模式：大問題是如何分解為小問題的，確定遞歸體。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)用；從第i層遞歸調(diào)用自身稱為第 i +1層。反之，退出第i +1層調(diào)用應(yīng)該返回第i層。采

13、用圖示方法描述遞 歸函數(shù)的運(yùn)行軌跡，從中可較直觀地了解到各調(diào)用層次及其執(zhí)行情況。4.2.3 遞歸函數(shù)的內(nèi)部執(zhí)行過程一個(gè)遞歸函數(shù)的調(diào)用過程類似于多個(gè)函數(shù)的嵌套調(diào)用，只不過調(diào)用函 數(shù)和被調(diào)用函數(shù)是同一個(gè)函數(shù)。為了保證遞歸函數(shù)的正確執(zhí)行，系統(tǒng)需設(shè) 立一個(gè)工作棧。具體地說，遞歸調(diào)用的內(nèi)部執(zhí)行過程如下：(1)運(yùn)行開始時(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í)行

14、過程中，工作棧的變化下圖所示，其中棧元素的結(jié)構(gòu)為（返回地址，n 值， A 值， B 值， C 值） ，返回地址對(duì)應(yīng)算法中語句的行號(hào)。遞歸算法結(jié)構(gòu)清晰，可讀性強(qiáng)，而且容易用數(shù)學(xué)歸納法來證明算法的正確性，因此，它為設(shè)計(jì)算法和調(diào)試程序帶來很大方便，是算法設(shè)計(jì)中的一種強(qiáng)有力的工具。但是，因?yàn)檫f歸算法是一種自身調(diào)用自身的算法，隨著遞歸深度的增加，工作棧所需要的空間增大，遞歸調(diào)用時(shí)的輔助操作增多，因此，遞歸算法的運(yùn)行效率較低。4.3 排序問題中的分治法4.3.1 歸并排序二路歸并排序的分治策略是：（1）劃分：將待排序序列r1, r2,，rn劃分為兩個(gè)長度相等的子序列 r1,，rn/2 和 m/2+1,，r

15、n；（ 2）求解子問題：分別對(duì)這兩個(gè)子序列進(jìn)行排序，得到兩個(gè)有序子序列；（ 3）合并：將這兩個(gè)有序子序列合并成一個(gè)有序序列。算法 4.3 歸并排序void MergeSort（int r , int r1 , int s, int t）if (s= =t) r1s=rs;else m=(s+t)/2;Mergesort(r, r1, s, m); /列Mergesort(r, r1, m+1, t); /列Merge(r1, r, s, m, t);/序列算法 4.4 合并有序子序列void Merge(int r , int r1 , int s, int m, int t)i=s; j=m

16、+1; k=s;while (i<=m && j<=t)if (ri<=rj) r1k+=ri+; /中較小者放入r1kelse r1k+=rj+;歸并排序前半個(gè)子序歸并排序后半個(gè)子序合并兩個(gè)已排序的子取 ri 和 rjif (i<=m) while (i<=m)/若第一個(gè)子序列沒處理完，則進(jìn)行收尾處理r1k+=ri+;else while (j<=t)/若第二個(gè)子序列沒處理完，則進(jìn)行收尾處理r1k+=rj+;二路歸并排序的合并步的時(shí)間復(fù)雜性為qn),所以，二路歸并排序算法存在如下遞推式：T(n)：2T(n/2) : n根據(jù)1.2.4節(jié)的主定

17、理，二路歸并排序的時(shí)間代價(jià)是Qnlog2n)二路歸并排序在合并過程中需要與原始記錄序列同樣數(shù)量的存儲(chǔ)空 間，因此其空間復(fù)雜性為 Qn)4.3.2 快速排序快速排序的分治策略是：(1)劃分：選定一個(gè)記錄作為軸值，以軸值為基準(zhǔn)將整個(gè)序列劃分 為兩個(gè)子序列r1ri -1和ri +1rn,前一個(gè)子序列中記錄的值均小 于或等于軸值，后一個(gè)子序列中記錄的值均大于或等于軸值；(2)求解子問題：分別對(duì)劃分后的每一個(gè)子序列遞歸處理；(3)合并：由于對(duì)子序列 r1ri -1和ri +1rn的排序是就地 進(jìn)行的，所以合并不需要執(zhí)行任何操作。歸并排序按照記錄在序列中的位置對(duì)序列進(jìn)行劃分，快速排序按照記錄的值對(duì)序列進(jìn)行

18、劃分。以第一個(gè)記錄作為軸值，對(duì)待排序序列進(jìn)行劃分的過程為：(1)初始化：取第一個(gè)記錄作為基準(zhǔn)，設(shè)置兩個(gè)參數(shù) i , j分別用來 指示將要與基準(zhǔn)記錄進(jìn)行比較的左側(cè)記錄位置和右側(cè)記錄位置，也就是本 次劃分的區(qū)間；(2)右側(cè)掃描過程：將基準(zhǔn)記錄與 j指向的記錄進(jìn)行比較，如果 j 指向記錄的關(guān)鍵碼大，則j前移一個(gè)記錄位置。重復(fù)右側(cè)掃描過程，直到 右側(cè)的記錄小(即反序)，若i vj ,則將基準(zhǔn)記錄與j指向的記錄進(jìn)行交 換；(3)左側(cè)掃描過程：將基準(zhǔn)記錄與i指向的記錄進(jìn)行比較，如果 i指向記錄的關(guān)鍵碼小，則i后移一個(gè)記錄位置。重復(fù)左側(cè)掃描過程，直到 左側(cè)的記錄大(即反序)，若i vj ,則將基準(zhǔn)記錄與i指

19、向的記錄交換；(4)重復(fù)(2) (3)步，直到i與j指向同一位置，即基準(zhǔn)記錄最終 的位置。一次劃分示例算法4.5 次劃分int Partition(int r , int first, int end)i=first; j=end; /while (i<j)while (i<j && ri<= rj) j-if (i<j) ri<> rj；到前面i+；while (i<j && ri<= rj) i+if (i<j) 初始化/右側(cè)掃描/將較小記錄交換/左側(cè)掃描rjr ri；/將較大記錄交換到后面j-;retu

20、tn i; / i為軸值記錄的最終位置以軸值為基準(zhǔn)將待排序序列劃分為兩個(gè)子序列后，對(duì)每一個(gè)子序列分別遞歸進(jìn)行排序。算法 4.6 快速排序void QuickSort(int r , int first, int end)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)行快速排序在最好情況下，每次劃分對(duì)一個(gè)記錄定位后，該記錄的左側(cè)子序列與

21、右側(cè)子序列的長度相同。在具有n 個(gè)記錄的序列中，一次劃分需要對(duì)整個(gè) 待劃分序列掃描一遍，則所需時(shí)間為 Qn)。設(shè)T(n)是對(duì)n個(gè)記錄的序列 進(jìn)行排序的時(shí)間，每次劃分后，正好把待劃分區(qū)間劃分為長度相等的兩個(gè)子序列，則有：T( n) < 2 T(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)+ nlog2 n= 0( nlog2 n)因此，時(shí)間復(fù)雜度為O( nlog2 n) 。在最壞情況下，待排序記錄序列正序或逆序，每次劃分只得到一個(gè)比上一次劃分少一個(gè)記

22、錄的子序列(另一個(gè)子序列為空)。此時(shí)，必須經(jīng)過n-1 次遞歸調(diào)用才能把所有記錄定位，而且第i 趟劃分需要經(jīng)過n- i 次關(guān)鍵碼的比較才能找到第i 個(gè)記錄的基準(zhǔn)位置，因此，總的比較次數(shù)為：因此，時(shí)間復(fù)雜度為O(n2) 。在平均情況下，設(shè)基準(zhǔn)記錄的關(guān)鍵碼第k小(iwkwn),則有：這是快速排序的平均時(shí)間性能，可以用歸納法證明，其數(shù)量級(jí)也為O( nlog2 n) 。4.4 組合問題中的分治法4.4.1 最大子段和問題給定由n個(gè)整數(shù)組成的序列(a1, a2,，an),最大子段和問題要求 該序列形如的最大值(1<i <j &n),當(dāng)序列中所有整數(shù)均為負(fù)整數(shù)時(shí)，的最大子段和其最大子段和

23、為0。例如，序列(-20, 11, -4, 13, -5, -2)為：最大子段和問題的分治策略是：(1)劃分：按照平衡子問題的原則，將序列(al, a2,，an)劃分成長度相同的兩個(gè)子序列(a1,，a )和(2十1，an),則會(huì)出現(xiàn)以下三種情況：a1,，an的最大子段和=a1,，a的最大子段和；a1,，an的最大子段和=a +1,，an的最大子段和；a1,，an的最大子段和=,且(2)求解子問題：對(duì)于劃分階段的情況和可遞歸求解，情況需要分別計(jì)算則 s1+s2 為情況的最大子段和。( 3)合并：比較在劃分階段的三種情況下的最大子段和，取三者之 中的較大者為原問題的解。算法 4.7 最大子段和問題

24、int MaxSum(int a , int left, int right)sum=0;if (left= =right) /如果序列長度為1，直接求解if (aleft>0) sum=aleft;else sum=0;歸求解歸求解解 s1else center=(left+right)/2; /leftsum=MaxSum(a, left, center);/rightsum=MaxSum(a, center+1, right);/s1=0; lefts=0; ?/for (i=center; i>=left; i-)lefts+=ai;if (lefts>s1) s1=

25、lefts;s2=0; rights=0; /for (j=center+1; j<=right; j+)rights+=aj;if (rights>s2) s2=rights;劃分對(duì)應(yīng)情況，遞對(duì)應(yīng)情況，遞以下對(duì)應(yīng)情況，先求再求解 s2sum=s1+s2;/計(jì)算情況的最大子段和if (sum<leftsum) sum=leftsum;/合并，在sum、 leftsum 和 rightsum 中取較大者if (sum<rightsum) sum=rightsum; return sum;分析算法4.7的時(shí)間性能，對(duì)應(yīng)劃分得到的情況和，需要分別遞 歸求解，對(duì)應(yīng)情況，兩個(gè)并列

26、 for循環(huán)的時(shí)間復(fù)雜性是 Qn),所以，存 在如下遞推式：根據(jù) 1.2.4 節(jié)主定理，算法4.7 的時(shí)間復(fù)雜性為O( nlog2 n)。4.4.2 棋盤覆蓋問題在一個(gè)2kx 2k (k>0)個(gè)方格組成的棋盤中，恰有一個(gè)方格與其他 方格不同，稱該方格為特殊方格。棋盤覆蓋問題要求用圖4.11 (b)所示的 4 種不同形狀的L 型骨牌覆蓋給定棋盤上除特殊方格以外的所有方格，且任何 2 個(gè) L 型骨牌不得重疊覆蓋。分治法求解棋盤覆蓋問題的技巧在于劃分棋盤，使劃分后的子棋盤的大小相同，并且每個(gè)子棋盤均包含一個(gè)特殊方格，從而將原問題分解為規(guī) 模較小的棋盤覆蓋問題。k>0時(shí)，可將2kx 2k的

27、棋盤劃分為4個(gè)2k-1x2k-1的子棋盤，這樣劃分后，由于原棋盤只有一個(gè)特殊方格，所以，這4 個(gè)子棋盤中只有一個(gè)子棋盤包含該特殊方格，其余3 個(gè)子棋盤中沒有特殊方格。為了將這3 個(gè)沒有特殊方格的子棋盤轉(zhuǎn)化為特殊棋盤，以便采用遞歸方法求解，可以用一個(gè) L 型骨牌覆蓋這3 個(gè)較小棋盤的會(huì)合處，從而將原問題轉(zhuǎn)化為4 個(gè)較小規(guī)模的棋盤覆蓋問題。遞歸地使用這種劃分策略，直至將棋盤分割為1X 1的子棋盤。下面討論棋盤覆蓋問題中數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)。( 1)棋盤：可以用一個(gè)二維數(shù)組boardsizesize 表示一個(gè)棋盤，其中，size=2 k。為了在遞歸處理的過程中使用同一個(gè)棋盤，將數(shù)組 board設(shè)為全局變量

28、；( 2)子棋盤：整個(gè)棋盤用二維數(shù)組boardsizesize 表示，其中的子棋盤由棋盤左上角的下標(biāo)tr 、 tc 和棋盤大小s 表示；( 3)特殊方格：用boarddrdc 表示特殊方格，dr 和 dc 是該特殊方格在二維數(shù)組board 中的下標(biāo);4 4) L型骨牌：一個(gè)2kx 2k的棋盤中有一個(gè)特殊方格，所以，用到 L 型骨牌的個(gè)數(shù)為(4 k-1)/3 ，將所有L 型骨牌從1 開始連續(xù)編號(hào)，用一個(gè)全局變量t 表示。算法 4.8 棋盤覆蓋void ChessBoard(int tr, int tc, int dr, int dc, int size)/ tr 和 tc 是棋盤左上角的下標(biāo)，d

29、r 和 dc 是特殊方格的下標(biāo)，/ size 是棋盤的大小，t 已初始化為0棋盤只有一個(gè)方格且是特殊方if (size = = 1) return; /t+; / L型骨牌號(hào)5 = size/2; /劃分棋盤/ 覆蓋左上角子棋盤if (dr < tr + s && dc < tc + s) /特殊方格在左上角子棋盤中ChessBoard(tr, tc, dr, dc, s);/遞歸處理子棋盤else /用 t 號(hào) L 型骨牌覆蓋右下角，再遞歸處理子棋盤boardtr + s - 1tc + s - 1 = t;ChessBoard(tr, tc, tr+s-1, t

30、c+s-1, s);/ 覆蓋右上角子棋盤if (dr < tr + s && dc >= tc + s) /特殊方格在右上角子棋盤中ChessBoard(tr, tc+s, dr, dc, s);/遞歸處理子棋盤else /用 t 號(hào) L 型骨牌覆蓋左下角，再遞歸處理子棋盤boardtr + s - 1tc + s = t;ChessBoard(tr, tc+s, tr+s-1, tc+s, s); 覆蓋左下角子棋盤/if (dr >= tr + s && dc < tc + s) /特殊方格在左下角子棋盤中ChessBoard(tr+s

31、, tc, dr, dc, s);/遞歸處理子棋盤else /用 t 號(hào) L 型骨牌覆蓋右上角，再遞歸處理子棋盤boardtr + stc + s - 1 = t;ChessBoard(tr+s, tc, tr+s, tc+s-1, s); / 覆蓋右下角子棋盤if (dr >= tr + s && dc >= tc + s) /特殊方格在右下角子棋盤中ChessBoard(tr+s, tc+s, dr, dc, s);/遞歸處理子棋盤else /用 t 號(hào) L 型骨牌覆蓋左上角，再遞歸處理子棋盤boardtr + stc + s = t;ChessBoard(tr

32、+s, tc+s, tr+s, tc+s, s); 設(shè)T( k)是覆蓋一個(gè)2kx 2k棋盤所需時(shí)間,從算法的劃分策略可知,T( k) 滿足如下遞推式：解此遞推式可得T(k)=Q4k)。由于覆蓋一個(gè)2kx 2k棋盤所需的骨牌個(gè)數(shù)為 (4k-1)/3 ，所以，算法4.8 是一個(gè)在漸進(jìn)意義下的最優(yōu)算法。4.4.3 循環(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

33、天比賽的選手。按照分治的策略，可將所有參賽的選手分為兩部分，n = 2k個(gè)選手的比賽日程表就可以通過為 n/2=2k-1個(gè)選手設(shè)計(jì)的比賽日程表來決定。遞歸地執(zhí)行這種分割，直到只剩下2 個(gè)選手時(shí)，比賽日程表的制定就變得很簡單：只要讓這2 個(gè)選手進(jìn)行比賽就可以了。(b) 2 k( k=2)個(gè)選手比賽2k( k=3)個(gè)選手比賽顯然，這個(gè)求解過程是自底向上的迭代過程，其中左上角和左下角分別為選手1 至選手 4 以及選手5 至選手 8 前 3 天的比賽日程，據(jù)此，將左上角部分的所有數(shù)字按其對(duì)應(yīng)位置抄到右下角，將左下角的所有數(shù)字按其對(duì)應(yīng)位置抄到右上角，這樣，就分別安排好了選手1 至選手 4 以及選手5至選

34、手 8 在后 4 天的比賽日程，如圖(c) 所示。具有多個(gè)選手的情況可以依此類推。這種解法是把求解2k個(gè)選手比賽日程問題劃分成依次求解21、22、2k 個(gè)選手的比賽日程問題，換言之，2k 個(gè)選手的比賽日程是在2k- 1 個(gè)選手的比賽日程的基礎(chǔ)上通過迭代的方法求得的。在每次迭代中，將問題劃分為 4 部分：（ 1）左上角：左上角為2k- 1 個(gè)選手在前半程的比賽日程；（ 2）左下角：左下角為另2k- 1 個(gè)選手在前半程的比賽日程，由左上角加2k- 1 得到，例如22 個(gè)選手比賽，左下角由左上角直接加2 得到， 23個(gè)選手比賽，左下角由左上角直接加4 得到；（ 3）右上角：將左下角直接抄到右上角得到

35、另2k- 1 個(gè)選手在后半程的比賽日程；（ 4）右下角：將左上角直接抄到右下角得到2k- 1 個(gè)選手在后半程的比賽日程；算法設(shè)計(jì)的關(guān)鍵在于尋找這4 部分元素之間的對(duì)應(yīng)關(guān)系。算法 4.9 循環(huán)賽日程表void GameTable（int k, int a ）/n=2k（ k> 1）個(gè)選手參加比賽，/ 二維數(shù)組a 表示日程安排，數(shù)組下標(biāo)從1 開始n=2;/k=0， 2 個(gè)選手比賽日程可直接求得/ 求解 2 個(gè)選手比賽日程，得到左上角元素a11=1; a12=2;a21=2; a22=1;for （t=1; t<k; t+）/迭代處理，依次處理 22,，2 k個(gè)選手比賽日程temp=n;

36、 n=n*2;/ 填左下角元素for (i=temp+1; i<=n; i+ )for (j=1; j<=temp; j+)aij=ai-tempj+temp;/左下角元素和左上角元素的對(duì)應(yīng)關(guān)系/ 填右上角元素for (i=1; i<=temp; i+)for (j=temp+1; j<=n; j+)aij=ai+temp(j+temp)% n;/ 填右下角元素for (i=temp+1; i<=n; i+)for (j=temp+1; j<=n; j+)aij=ai-tempj-temp;分析算法4.9 的時(shí)間性能，迭代處理的循環(huán)體內(nèi)部有3個(gè)循環(huán)語句，每個(gè)

37、循環(huán)語句都是一個(gè)嵌套的for 循環(huán)，且他們的執(zhí)行次數(shù)相同，基本語句是最內(nèi)層循環(huán)體的賦值語句，即填寫比賽日程表中的元素?；菊Z句的執(zhí)行次數(shù)是：所以，算法4.9 的其時(shí)間復(fù)雜性為O(4 k)4.5 幾何問題中的分治法4.5.1 最近對(duì)問題設(shè) p1=(x1, y1), p2=(x2, y2),，pn=(xn, yn)是平面上 n 個(gè)點(diǎn)構(gòu) 成的集合S,最近對(duì)問題就是找出集合S中距離最近的點(diǎn)對(duì)。嚴(yán)格地講，最接近點(diǎn)對(duì)可能多于一對(duì)，簡單起見，只找出其中的一對(duì)作為問題的解。用分治法解決最近對(duì)問題，很自然的想法就是將集合S分成兩個(gè)子集S1和S2,每個(gè)子集中有n/2個(gè)點(diǎn)。然后在每個(gè)子集中遞歸地求其最接近 的點(diǎn)對(duì)，

38、在求出每個(gè)子集的最接近點(diǎn)對(duì)后，在合并步中，如果集合S 中最接近的兩個(gè)點(diǎn)都在子集S1 或S2 中，則問題很容易解決，如果這兩個(gè)點(diǎn)分別在S1 和S2 中，問題就比較復(fù)雜了。為了使問題易于理解，先考慮一維的情形。此時(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, q

39、3), 其中，p3 是子集S1 中的最大值，q3 是子集S2 中的最小值。按這種分治策略求解最近對(duì)問題的算法效率取決于劃分點(diǎn)m的選取，個(gè)基本的要求是要遵循平衡子問題的原則如果選取m=(maxS+min S)/2 ，則有可能因集合S 中點(diǎn)分布的不均勻而造成子集S1和S2的不平衡，如果用 S中各點(diǎn)坐標(biāo)的中位數(shù)(即 S的中值)作為分割點(diǎn)，則會(huì)得到一個(gè)平衡的分割點(diǎn)mi使得子集S1和S2中有個(gè)數(shù)大致相同的點(diǎn)。下面考慮二維的情形，此時(shí)S 中的點(diǎn)為平面上的點(diǎn)。為了將平面上的點(diǎn)集S 分割為點(diǎn)的個(gè)數(shù)大致相同的兩個(gè)子集S1 和S2,選取垂直線x=m來作為分割線，其中，m為S中各點(diǎn)x坐標(biāo)的中位數(shù)。由此將S分割為S1

40、=pG S | xpwn)和S2=qGS | xq>n。遞歸地在 S1和 S2 上求解最近對(duì)問題，分別得到S1 中的最近距離d1 和 S2 中的最近距離d2,令d=min(d1, d2),若S的最近對(duì)(p, q)之間的距離小于d,則p和q必分屬于S1和S2,不妨設(shè)pG S1, q G S2,則p和q距直線x=m的距離均小于d,所以，可以將求解限制在以 x=m為中心、寬度為2d的垂直帶P1 和 P2 中，垂直帶之外的任何點(diǎn)對(duì)之間的距離都一定大于d。對(duì)于點(diǎn)pG P1,需要考察P2中的各個(gè)點(diǎn)和點(diǎn)p之間的距離是否小于d,顯然，P2 中這樣點(diǎn)的y 軸坐標(biāo)一定位于區(qū)間y- d, y+d 之間，而且，

41、這樣的點(diǎn)不會(huì)超過6 個(gè)。應(yīng)用分治法求解含有n 個(gè)點(diǎn)的最近對(duì)問題，其時(shí)間復(fù)雜性可由下面的遞推式表示：合并子問題的解的時(shí)間f(n)=Q1),根據(jù)1.2.4節(jié)的主定理，可得T( n)= O( nlog2 n) 。4.5.2 凸包問題設(shè) p1=(x1, y1), p2=(x2, y2),，pn=(xn, yn)是平面上 n 個(gè)點(diǎn)構(gòu)成的集合S,并且這些點(diǎn)按照x軸坐標(biāo)升序排列。幾何學(xué)中有這樣一個(gè)明顯的事實(shí)：最左邊的點(diǎn)p1 和最右邊的點(diǎn)pn 一定是該集合的凸包頂點(diǎn)(即極點(diǎn))。設(shè)plpn是從pl到pn的直線，這條直線把集合 S分成兩個(gè)子集：S1 是位于直線左側(cè)和直線上的點(diǎn)構(gòu)成的集合，S2 是位于直線右側(cè)和直線

42、上的點(diǎn)構(gòu)成的集合。S1 的凸包由下列線段構(gòu)成：以 p1 和 pn 為端點(diǎn)的線段構(gòu)成的下邊界，以及由多條線段構(gòu)成的上邊界，這條上邊界稱為上包。類似地，S2中的多條線段構(gòu)成的下邊界稱為下包。整個(gè)集合S的凸包是由上包和下包構(gòu)成的?？彀乃枷胧牵菏紫日业絊1 中的頂點(diǎn)pmax， 它是距離直線p1pn 最遠(yuǎn)的頂點(diǎn)， 則三角形pmaxp1pn 的面積最大。S1 中所有在直線pmaxp1 左側(cè)的點(diǎn)構(gòu)成集合S1,1 , S1中所有在直線pmaxp體側(cè)的點(diǎn)中成集合S1,2 ,包含在三角形pmaxp1pn 之中的點(diǎn)可以不考慮了。遞歸地繼續(xù)構(gòu)造集合S1,1 的上包和集合S1,2 的上包，然后將求解過程中得到的所有最

43、遠(yuǎn)距離的點(diǎn)連接起來，就可以得到集合S1 的上包。接下來的問題是如何判斷一個(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)到該直線的距離第6章動(dòng)態(tài)規(guī)劃法6.1.1最優(yōu)化問題最優(yōu)化問題：有n個(gè)輸入，它的解由這n個(gè)輸入的一個(gè)子集組成，這 個(gè)子集必須滿足某些事先給定的條件，這些

44、條件稱為約束條件，滿足約束 條件的解稱為問題的可行解。滿足約束條件的可行解可能不只一個(gè)，為了 衡量這些可行解的優(yōu)劣，事先給出一定的標(biāo)準(zhǔn)，這些標(biāo)準(zhǔn)通常以函數(shù)的形 式給出，這些標(biāo)準(zhǔn)函數(shù)稱為目標(biāo)函數(shù)，使目標(biāo)函數(shù)取得極值（極大或極?。┑目尚薪夥Q為最優(yōu)解，這類問題就稱為最優(yōu)化問題。例：付款問題：超市的自動(dòng)柜員機(jī)（posM）要找給顧客數(shù)量最少的現(xiàn)金。假定POS機(jī)中有n張面值為pi （1 & i &n）的貨幣，用集合 P=p1, p2,，pn表示，如果POSa需支付白現(xiàn)金為 A,那么，它必須 從P中選取一個(gè)最小子集S,使得（式 6.1 ）如果用向量X=（ x 1, x2,，xn）表示S中所選

45、取的貨幣，則 P-S（式 6.2）0 產(chǎn)S那么，posm支付的現(xiàn)金必須滿足（式 6.3 ）并且（式 6.4 ）在付款問題中，集合P是該問題的輸入，滿足式6.1的解稱為可行解,式6.2是解的表現(xiàn)形式，因?yàn)橄蛄?X中有n個(gè)元素，每個(gè)元素的取值為0或 1 ，所以，可以有2n 個(gè)不同的向量，所有這些向量的全體構(gòu)成該問題的解空間，式6.3 是該問題的約束條件，式6.4 是該問題的目標(biāo)函數(shù)，使式1.1.1 取得極小值的解稱為該問題的最優(yōu)解。1.1.2 最優(yōu)性原理對(duì)于一個(gè)具有n 個(gè)輸入的最優(yōu)化問題，其求解過程往往可以劃分為若干個(gè)階段，每一階段的決策僅依賴于前一階段的狀態(tài)，由決策所采取的動(dòng)作使?fàn)顟B(tài)發(fā)生轉(zhuǎn)移，成

46、為下一階段決策的依據(jù)。從而，一個(gè)決策序列在不斷變化的狀態(tài)中產(chǎn)生。這個(gè)決策序列產(chǎn)生的過程稱為多階段決策過程。在每一階段的決策中有一個(gè)賴以決策的策略或目標(biāo)，這種策略或目標(biāo)是由問題的性質(zhì)和特點(diǎn)所確定，通常以函數(shù)的形式表示并具有遞推關(guān)系，稱為動(dòng)態(tài)規(guī)劃函數(shù)。多階段決策過程滿足最優(yōu)性原理(Optimal Principle ) ：無論決策過程的初始狀態(tài)和初始決策是什么，其余的決策都必須相對(duì)于初始決策所產(chǎn)生的當(dāng)前狀態(tài)，構(gòu)成一個(gè)最優(yōu)決策序列。如果一個(gè)問題滿足最優(yōu)性原理通常稱此問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。1.1.3 動(dòng)態(tài)規(guī)劃法的設(shè)計(jì)思想動(dòng)態(tài)規(guī)劃法將待求解問題分解成若干個(gè)相互重疊的子問題，每個(gè)子問題對(duì)應(yīng)決策過程的一個(gè)

47、階段，一般來說，子問題的重疊關(guān)系表現(xiàn)在對(duì)給定問題求解的遞推關(guān)系（也就是動(dòng)態(tài)規(guī)劃函數(shù)）中，將子問題的解求解一次并填入表中，當(dāng)需要再次求解此子問題時(shí)，可以通過查表獲得該子問題的解而不用再次求解，從而避免了大量重復(fù)計(jì)算。動(dòng)態(tài)規(guī)劃法的求解過程例：計(jì)算斐波那契數(shù)：n=5 時(shí)分治法計(jì)算斐波那契數(shù)的過程。注意到，計(jì)算F（n） 是以計(jì)算它的兩個(gè)重疊子問題F（ n-1） 和F（ n-2） 的形式來表達(dá)的，所以，可以設(shè)計(jì)一張表填入n+1 個(gè)F（ n） 的值。動(dòng)態(tài)規(guī)劃法求解斐波那契數(shù)F（9） 的填表過程：用動(dòng)態(tài)規(guī)劃法求解的問題具有特征：能夠分解為相互重疊的若干子問題；滿足最優(yōu)性原理（也稱最優(yōu)子結(jié)構(gòu)性質(zhì)）：該問題的最

48、優(yōu)解中也包含著其子問題的最優(yōu)解。（用反證法）分析問題是否滿足最優(yōu)性原理：1. 先假設(shè)由問題的最優(yōu)解導(dǎo)出的子問題的解不是最優(yōu)的;2. 然后再證明在這個(gè)假設(shè)下可構(gòu)造出比原問題最優(yōu)解更好的解，從而導(dǎo)致矛盾。動(dòng)態(tài)規(guī)劃法設(shè)計(jì)算法一般分成三個(gè)階段：（ 1）分段：將原問題分解為若干個(gè)相互重疊的子問題；（ 2）分析：分析問題是否滿足最優(yōu)性原理，找出動(dòng)態(tài)規(guī)劃函數(shù)的遞推式；3）求解：利用遞推式自底向上計(jì)算，實(shí)現(xiàn)動(dòng)態(tài)規(guī)劃過程。動(dòng)態(tài)規(guī)劃法利用問題的最優(yōu)性原理，以自底向上的方式從子問題的最優(yōu)解逐步構(gòu)造出整個(gè)問題的最優(yōu)解。6.2 圖問題中的動(dòng)態(tài)規(guī)劃法6.2.1 TSP 問題TSP問題是指旅行家要旅行 n個(gè)城市，要求各個(gè)城

49、市經(jīng)歷且僅經(jīng)歷一 次然后回到出發(fā)城市，并要求所走的路程最短。各個(gè)城市間的距離可以用代價(jià)矩陣來表示。證明TSP問題滿足最優(yōu)性原理設(shè)s, s1, s2,，sp, s是從s出發(fā)的一條路徑長度最短的簡單回路，假設(shè)從s 到下一個(gè)城市s1 已經(jīng)求出，則問題轉(zhuǎn)化為求從s1 到 s 的最短路徑，顯然s1, s2,，sp, s 一定構(gòu)成一條從si到s的最短路徑。如若不然，設(shè)si, ri, r2,，rq, s是一條從si到s的最短 路徑且經(jīng)過n-i個(gè)不同城市，則s, si, ri, r2,，rq, s將是一條從s 出發(fā)的路徑長度最短的簡單回路且比 s, si, s2,，sp, s要短，從而 導(dǎo)致矛盾。所以，TSP

50、問題滿足最優(yōu)性原理。假設(shè)從頂點(diǎn)i出發(fā)，令d(i, V')表示從頂點(diǎn)i出發(fā)經(jīng)過V'中各個(gè)頂 點(diǎn)一次且僅一次，最后回到出發(fā)點(diǎn) i的最短路徑長度，開始時(shí)， V'=V i,于是，TSP問題的動(dòng)態(tài)規(guī)劃函數(shù)為：d(i, V'尸min cik+d(k, V k)( kGV')(式 6.5 )d(k,)= cki(ki)(式 6.6 )從城市 0 出發(fā)經(jīng)城市i 、 2、 3 然后回到城市0 的最短路徑長度是：d(0,1,2, 3)=min c01+d(1, 2, 3), c02+d(2, 1, 3), c03+d(3,1, 2)這是最后一個(gè)階段的決策，而：d(1, 2,

51、 3)=minc12+d(2, 3),c13+ d(3,2)d(2, 1, 3)=minc21+d(1, 3),c23+ d(3,1)d(3, 1, 2)=minc31+d(1, 2),c32+ d(2,1)這一階段的決策又依賴于下面的計(jì)算結(jié)果：d(1, 2)=c 12+d(2, )d(2, 3)=c23+d(3, )d(3, 2)=c 32+d(2, ) d(1, 3)=c 13+d(3, )d(2, 1)=c21+d(1, )d(3, 1)=c31+d(1, )而下式可以直接獲得(括號(hào)中是該決策引起的狀態(tài)轉(zhuǎn)移)d(1, )=c10=5(1 f 0) d(2,)=c20=6(2 f 0) d

52、(3,)=c30=3(3”0)再向前倒推，有：d(1,2)=c12+d(2,)=2+6=8(1f 2)d(1,3)=c13+d(3,)=3+3=6(1 73)d(2,3)=c23+d(3,)=2+3=5(2f 3)d(2,1)=c21+d(1,)=4+5=9(2 f 1)d(3,1)=c31+d(1,)=7+5=12(3 f 1)d(3,2)=c32+d(2,)=5+6=11(3 72)再向前倒退，有：d(1,2,3)=min c12+d(2,3),c13+ d(3,2)=min2+5,3+11=7(1 f 2)d(2,1,3)=minc21+d(1,3),c23+d(3,1)=min4+6,2+12=10(2 f 1)d(3,1,2)=minc31+d(1,2),c32+d(2,1)=min7+8,5+9=14(3 f 2)最后有：d(0, 1, 2, 3)=min c01+ d(1, 2, 3), c02+ d(2, 1, 3),c03+d(3, 1, 2)=min3+7, 6+10, 7+14=10(0f 1)所以，從