算法設計與分析 國家級實驗教學示范中心計算機學科組規劃教材學習內容算法基礎分治法貪心法回溯法分支限界法動態規劃法智能算法算法基礎第一章1程序與算法234算法復雜度分析算法復雜度的漸進性態非遞歸算法復雜度分析目

錄CONTENTS算法概述算法與程序What’san

Algorithm?AlgorithmQuestion算法(Algorithm)算法是指解決問題的一種方法或一個過程。算法是若干指令的有窮序列，滿足性質：(1)輸入：有外部提供的量作為算法的輸入。(2)輸出：算法產生至少一個量作為輸出。(3)確定性：組成算法的每條指令是清晰，無歧義的。(4)有限性：算法中每條指令的執行次數是有限的，執行每條指令的時間也是有限的。程序(Program)程序是算法用某種程序設計語言的具體實現。程序可以不滿足算法的性質(4)。例如操作系統，是一個在無限循環中執行的程序，因而不是一個算法。操作系統的各種任務可看成是單獨的問題，每一個問題由操作系統中的一個子程序通過特定的算法來實現。該子程序得到輸出結果后便終止。8算法問題求解基礎理解問題決定：計算方法；精確和近似的解法；數據結構；算法設計技術；設計算法正確性證明分析算法根據算法寫代碼9算法復雜性分析算法分析是對一個算法需要多少計算時間和存儲空間作定量的分析。Timeis

Important不是所有能計算的都有價值，不是所有有價值的都能被計算——阿爾伯特.愛因斯坦算法復雜性分析算法復雜性

=

算法所需要的計算機資源算法的時間復雜性T(n)；算法的空間復雜性S(n)。其中n是問題的規模（輸入大小）。算法的時間復雜性（1）最壞情況下的時間復雜性Tmax(n)=max{T(I)|size(I)=n

}（2）最好情況下的時間復雜性Tmin(n)=min{T(I)|size(I)=n

}（3）平均情況下的時間復雜性Tavg(n)

=其中I是問題的規模為n的實例，p(I)是實例I出現的概率。算法漸近復雜性T(n)

, asn

;(T(n)-t(n))/T(n)

0

，as n

;t(n)是T(n)的漸近性態，為算法的漸近復雜性。在數學上，

t(n)是T(n)的漸近表達式，是T(n)略去低階項留下的主項。它比T(n)

簡單。漸進符號算法效率的主要指標是基本操作次數的增長次數。為了對這些增長次數進行比較和歸類，計算機科學家們使用了3種符號：O（讀“O”）：上界Ω（讀”omega”）：下界Θ（讀”theta”）：近似符號O定義1:

對于足夠大的n，t(n)的上界由g(n)的常數倍來確定，即：t(n)≤cg(n)，c為常數記為t(n)∈O(g(n))n∈O(n2)100n+5

∈O(n2)n(n-1)/2

∈O(n2)符號Ω定義2

:對于足夠大的n，t(n)的下界由g(n)的常數倍來確定，即：t(n)≥

cg(n)，c為常數記為t(n)

∈

Ω(g(n))n3∈Ω(n2)n(n+1)∈Ω(n2)4n2+5∈Ω

(n2)符號Θ定義3

:

對于足夠大的n，t(n)的上界和下界由g(n)的常數倍來確定，即：c2g(n)≤

t(n)≤

c1g(n)，c1,c2為常數記為t(n)∈

Θ(g(n))n2+3n+2∈Θ(n2)n(n-1)/2∈Θ(n2)4n2+5∈Θ

(n2)漸進符號的有用特性定理:如果t1(n)

∈O(g1(n))并且t2(n)

∈O(g2(n))，則t1(n)+t2(n)∈O(max{(g1(n),

g2(n)})對于符號Ω和Θ，該定理也成立。該定理表明：當算法由兩個連續執行部分組成時，該算法的整體效率由具有較大增長次數的那部分所決定。利用極限比較增長次數前兩種情況意味著t(n)

∈O(g(n))后兩種情況意味著t(n)

∈Ω(g(n))第二種情況意味著t(n)

∈Θ(g(n))基本的效率類型常量(1)、對數(logn)、線性(n)、nlogn、平方(n2)、立方(n3)、指數(2n)、階乘(n!)非遞歸的算法分析算法

MaxElement(A[0..n-1]//求給定數組中的最大元素//輸入：實數數組A[0..n-1]//輸出：A中的最大元素maxval

A[0]fori

1ton-1

doifA[i]>

maxvalmaxval

A[i]returnmaxval例1：討論下面這個算法（從n個元素中查找最大元素問題）的效率。考慮：循環中的操作有比較和賦值，取哪一個作為基本操作？輸入規模是多少？基本操作為：比較運算輸入規模就是數組長度n算法的效率為：分析非遞歸算法效率的通用方案決定用那些參數作為輸入規模的度量。找出算法的基本操作。檢查基本操作的執行次數是否只依賴輸入規模。建立一個算法基本操作執行次數的求和表達式。利用求和運算的標準公式和法則來建立一個操作次數的閉合公式，或者至少確定它的增長次數。Example 考慮下面算法的效率例

2

元素唯一性問題算法

UniqueElements(A[0..n-1])//驗證給定數組的元素是否全部唯一//輸入：實數數組A[0..n-1]//輸出：如果唯一，返回True，否則Falsefori

0ton-2

doforj

i+1ton-1

doifA[i]=A[j]return

Falsereturn

True程序段如下j=nwhile(j>=1){ fori=1to

jx=x+1j=j/2}語句x=x+1執行次數找出Θ標記課堂練習求解過程24若令K表示while循環體的執行次數，則x=x+1執行的次數最多為這個式子等于故有所以t(n)=O(n)執行x=x+1次數的賽塔標記Θ（n）課堂練習fori=1to

nforj=1toifork=1to

ix=x+1A Θ(n2)B

Θ(nlgn)C

Θ(n3)DΘ(n)

算法設計與分析 國家級實驗教學示范中心計算機學科組規劃教材遞歸與分治第二章1234遞歸分治算法總體思想分治法復雜度分治法的應用目

錄CONTENTS遞歸遞歸是指一個函數或者過程在其定義或者說明中有直接或者間接調用自身的一種算法。遞歸的基本思想是把一個要求解的問題劃分成一個或者多個規模更小的子問題，這些規模更小的子問題與原問題性質相同，直到子問題容易求得到解。遞歸有兩個要素：邊界條件和遞歸方程，遞歸函數只有具備了這兩個要素，才能在有限計算次數后得出結果。階乘函數可遞歸地定義為：邊界條件遞歸方程邊界條件與遞歸方程是遞歸函數的二個要素，遞歸函數只有具備了這兩個要素，才能在有限次計算后得出結果。階乘函數階乘函數（遞歸）int

fact(int

n) //定義階乘函數{if

(n==1) return

1;//輸入的參數是1，直接返回1else

return

n*fact(n-1);//遞歸算法}遞歸里的基本操作增長次數是？遞歸里的基本操作是？n=1，直接返回1；n>1,

一個乘法運算，一個子問題。算法復雜度是θ(n)無窮數列1，1，2，3，5，8，13，21，34，55，……，稱為Fibonacci數列。它可以遞歸地定義為：邊界條件遞歸方程Fibonacci數列第n個Fibonacci數可遞歸地計算如下：intfibonacci(int

n){if(n<=1)return1;return

fibonacci(n-1)+fibonacci(n-2);}Fibonacci數列遞歸里的基本操作是？n≤1，直接返回1；n>1,

一個加法運算，兩個子問題。遞歸里的基本操作增長次數是？太難推導了Fibonacci數列遞歸的基本操作：n≤1，直接返回1；n>1,

一個加法運算，兩個子問題。一個大問題分解為兩個子問題，將大問題作為根結點，它的左右孩子就是其兩個子問題，從而得到右圖：此二叉樹最多結點個數為2n-1，復雜度為O(2n)遞歸算法復雜度分析的通用方案：決定用那些參數作為輸入規模的度量。找出算法的基本操作。如果遞歸子問題的輸入規模不同，基本操作的執行次數可能不同，則需要對最差復雜度、平均復雜度或者最優復雜度單獨研究。如果遞歸子問題有一個或者相同輸入規模相同，建立一個算法基本操作執行次數的遞推關系以及邊界條件。解這個遞推公式，或者至少確定它的增長次數。開心甜點給你一個裝有16枚硬幣的袋子，其中有1枚是假幣，并且假幣比真比要輕一些。要求快速地找出這枚假幣。不同求解方法12幣相比較第一第二種方法：用其中一枚硬幣與剩余15枚硬種方法：劃分最為多8組可，能每比個較小15組次2枚比較第三種對假幣組繼方法：劃分2組，找出假幣所在的組，續劃分2組，直到找出假幣第四種方法：劃分3組（5，5，6），找出假幣所在的組，對假幣組繼續劃分3組（2，2，1/2），直到找出假幣。最多比較3次1.將要求解的較大規模的問題分割成a個更小規模的子問題。nT(n/b)T(n/b)…T(n/b)T(n)=2.對這a個子問題分別求解。a個子問題nT(n)=n/bT(n/b2) …… T(n/b2)n/bT(n/b2) …… T(n/b2)n/bT(n/b2) …… T(n/b2)…T(n/b2) …… T(n/b2)3.對這a個子問題分別求解。如果子問題的規模仍然不夠小，則再劃分為a個子問題，如此遞歸的進行下去，直到問題規模足夠小，很容易求出其解為止。T(n)=4.將求出的小規模的問題的解合并為一個更大規模的問題的解，自底向上逐步求出原來問題的解。T(n/b2) …… T(n/b2)T(n/b2) …… T(n/b2)T(n/b2) …… T(n/b2)T(n/b2) …… T(n/b2)n/bn/b…n/bnn分治法的設計思想：將一個難以直接解決的大問題，分割成一些規模較小的相同問題，以便各個擊破，分而治之。原問題分解成a個子問題每個子問題的大小是原問題的1/b如果分解該問題和合并解的時間D(n)和C(n)若子問題很小，得到直接解的時間為常量。記Θ(1)疑問分治法適合解決什么問題？根據分治法的分割原則，把原問題分為多少個子問題才合理？子問題的規模是否相同？如何計算算法復雜度？分析：比較x和a的中間元素a[mid]，若x=a[mid]，則x在a中的位假如x在aid]的前置就是mid；如果x<a[mid]，由于a是遞增排序的，因此中的話，x必然排在a[mid]的前面，所以我們只要在a[m面查找x即可；如果x>a[mid]，同理我們只要在a[mid]的后面查找x即可。無論是在前面還是后面查找x，其方法都和在a中查找x一樣，只不過是查找的規模縮小了。這就說明了此問題滿足分治法的第二個和第三個適用條件。分析：很顯然此問題分解出的子問題相互獨立，即在a[mid]的前面或后面查找x是獨立的子問題，因此滿足分治法的第四個適用條件。給定已按升序排好序的n個元素a[0:n-1]，現要在這n個元素中找出一特定元素x。分析：分析：如果n=1即只有一個元素，則只要比較這個元素和x就可以確定x是否在表中。因此這個問題滿足分治法的第一個適用條件給定已按升序排好序的n個元素a[0:n-1]，現要在這n個元素中找出一特定元素x。據此容易設計出二分搜索算法：template<class

Type>intBinarySearch(Typea[],constType&x,intlow,int

high){while(high>=low){intmid=(low+high)/2;if(x==a[mid])return

mid;if(x<a[mid])high=mid-1;elselow=

mid+1;}return-1;}算法復雜度分析：每執行一次算法的while循環，

待搜索數組的大小減少一半。因此，在最壞情況下，while循環被執行了O(logn)

次。循環體內運算需要O(1)

時間，因此整個算法在最壞情況下的計算時間復雜性為O(logn)。問題描述：給定一個m×n二維整數數組（或者說，一個整數矩陣），每行元素從左到右遞增，每列元素從上往下遞增。給定一個目標值k，判斷k是否在這個矩陣內。查找12，返回True查找45，返回False方法一：逐行套用二分查找；查找12，返回True查找45，返回False方法二：將一個矩陣分解為四個小矩陣；當只有一個元素時，可以直接判定。查找12，返回True查找45，返回False方法三：以左下角元素來判定A。如果A>k，去掉該行；如果A<k，去掉該列；如果A==k，則返回True18>12，去掉該行，縮小為4×5矩陣；10<12，去掉該列，縮小為4×4矩陣；13>12，去掉該行，縮小為3×4矩陣；6<12，去掉該列，縮小為3×3矩陣；9<12，去掉該列，縮小為3×2矩陣；16>12，去掉該行，縮小為2×2矩陣；12=12，返回True合并排序2 6 4 8 2 5 1 725合并排序分治模式在每一層遞歸上都有三個步：分解 解決 合并分解：將n個元素分成n/2個元素的子序列解決：用合并法對兩個子序列遞歸地排序。合并：合并兩個已排序的子序列以得到排序結果。在對子序列排序時，其長度為1時遞歸結束。單個元素視為已排好序的。合并過程模擬1 2 2 4 5 6 7 82 4 6 81 3 5 72 64 83

51 726483517mergesort(a,low,high)

對數組a[low..high]排序mergesort(inta[],intlow,int

high){ int

mid;if(low<high){mid=(low+high)/2;mergesort(a,low,high);mergesort(a,mid+1,high);merge(a,low,mid,high);}}合并排序的關鍵步驟在于合并兩個已排序子序列merge(intA[],intlow,intmid,int

high){inti,j,k,tmp_l,tmp_h;intB[],C

[];tmp_1=mid-low+1;tmp_h=high-mid;for

(i=0;i<tmp_1;i++)B[i]=A[low+i];for(j=0;j<tmp_h;j++)C[j]=A[j+mid+1];B[i]=999;C[j]=999;i=0;

j=0;for

(k=low;k<=high;k++)if

(B[i]<=C[j]){A[k]=B[i];i++;

}else{

A[k]=C[j];j++;

}}設置“哨兵牌”（sentinel

card）merge過程的運行時間是Θ(n)n=high-low+1分解：這一步計算出子數組的中間位置，需要常量時間。因此D（n）=Θ（1）解決：遞歸地解兩個規模為n/2的子問題，時間為2T（n/2）合并：merge（）過程的運行時間為Θ(n)，則C（n）=

Θ(n)mergesort(inta[],intlow,int

high){ intmid;if(low<high){mid=(low+high)/2;mergesort(a,low,mid);mergesort(a,mid+1,high);merge(a,low,mid,high);}}合并排序復雜度分析T(n)T(n/2)T(n/2)cnT(n/4)cnT(n/4)T(n/4)T(n/4)cn/2cn/2cn/4cncn/4cn/4cn/4cn/2cn/2c c c cc ccnlogncncncncn從圖的角度理解合并排序復雜度最壞時間復雜度：O(nlogn)平均時間復雜度：O(nlogn)輔助空間：O(n)算法工程師：追求算法的高效和代碼的高質量在一個序列中，如果兩個元素的順序與排序后它們的順序相反，則稱這兩個元素構成一個逆序對。1 4 6 2 8 9（4

，2

） （6，2

）算法分析：借助合并排序來求解逆序對，將整個序列均分成前后兩個部分。將所有的逆序對分成以下三種情況，分別是：（1）逆序對中的兩個數在前一個序列；（2）逆序對中的兩個數在后一個序列；（3）逆序對中的兩個數，一個數在前一個序列，一個數在后一個序列。前兩種情況在遞歸中轉化為第三種情況，因此只需要編寫第三種的情況即可。在合并兩個子序列時統計逆序對的個數，merge_sort函數的返回定義為逆序對的數量。在下圖左右兩個子序列合并中逆序對個數的統計。當前一個序列中的A[i]大于A[j]，那么此時針對A[j]的逆序對的數量為mid-i+1。因2>1，故有4個逆序對(2,1)

(4,1)

(6,1)

(8,1)因6>5，故有2個逆序對

(6,5)

(8,5)因4>3，故有3個逆序對(4,3)

(6,3)

(8,3)因8>7，故有1個逆序對

(8,7)求下面序列的逆序對：2,6,4,8,3,5,1,

7合并排序求逆序對的復雜度是：A:n2 B:n C:nlogn D:2n快速排序385 3 6 4 1 2 8 7分治模式在每一層遞歸上都有三個步：分解 解決 合并快速排序（就地原排）56125以第一個元素為基準7>5；8>5，橙色指針左移2 3 1 4 6 8 752<5，2放到紅色指針位置；右移3<5，紅色指針右移6>5，6填入橙色指針位置；左移1<5，1放到紅色指針位置；右移4<5，紅色指針右移紅色指針和橙色指針重疊2 3 1 4 56 8 7借助于一個

變量實現問題分解，降低空間復雜度快速排序（就地原排）871344以最后一個元素為基準，key=845>4，

6>4，橙色指針右移兩步紅色指針右移，并和橙色指針交換元素2 1 37 5 6 82<4，紅色指針右移，2和2交換，橙色指針右移8>4，7>4，橙色指針右移兩步1<4，紅色指針右移，1和8交換，橙色指針右移3<4，紅色指針右移，7和3交換，橙色指針右移2 1 347 5 6 8快速排序的性能對于數組a[low:high]，partition的計算時間為(high-low-1)最壞的情況

(數組為完全有序或完全倒序---

冒泡排序)在劃分過程產生的兩個數組分別包含n-1個元素和0個元素的時候。假設算法的每一次遞歸調用中都出現了這種不對稱劃分，劃分的時間代價為Ｏ(n)。因此算法的運行時間可以遞歸地表示為：快速排序的性能對于數組a[low:high]，partition的計算時間為(high-low-1)最佳劃分（對稱）在partition()可能做的最平衡的劃分中，得到的兩個子問題的大小都n/2，一個為

，另一個為

表達其運行時間的遞歸式為快速排序的性能隨機排序的期望運行時間第一調用分區，需時間n-1對數組的每個元素是遞歸調用隨機排序，因此，如果分區元素放在下標p處由于所有的下標p都有同等的被選機會，所以由于T(0),…T(n-1)

會出現兩次建立遞推關系寫出T(n-1)將兩個上式相減，得快速排序的性能化簡：除以n(n+1)用n代替n-1迭代：用n代替2(n-1)得到：求下列第3小的元素2,6,4,8,3,5,1,

7需要排序？與排序算法類似，K選擇問題的效率與選擇基準有關。如果每次劃分的左右子數組是均衡的，選擇其中一個子數組進行下一次劃分，此時的算法復雜度表達式為：如果每次劃分的基準元素總是最大值，使得子數組的元素個數比劃分前少

1。此時的算法

復雜度表達式為在一個2k×2k

個方格組成的棋盤中，恰有一個方格與其它方格不同，稱該方格為一特殊方格，且稱該棋盤為一特殊棋盤。在棋盤覆蓋問題中，要用圖示的4種不同形態的L型骨牌覆蓋給定的特殊棋盤上除特殊方格以外的所有方格，且任何2個L型骨牌不得重疊覆蓋。當k>0時，將2k×2k棋盤分割為4個2k-1×2k-1

子棋盤(a)所示。特殊方格必位于4個較小子棋盤之一中，其余3個子棋盤中無特殊方格。為了將這3個無特殊方格的子棋盤轉化為特殊棋盤，可以用一個L型骨牌覆蓋這3個較小棋盤的會合處，如

(b)所示，從而將原問題轉化為4個較小規模的棋盤覆蓋問題。遞歸地使用這種分割，直至棋盤簡化為棋盤1×1。voidchessBoard(inttr,inttc,intdr,intdc,int

size){if(size==1)

return;int

t

=

tile++,

//

L型骨牌號s

=

size/2;

//

分割棋盤//覆蓋左上角子棋盤if(dr<tr+

s//特殊方格chessBoardelse

{//

此棋//

用

t

號Lboard[tr+

s//覆蓋其余方格chessBoard(tr,tc,tr+s-1,tc+s-1,

s);}//覆蓋右上角子棋盤if(dr<tr+s&&dc>=tc+

s)//特殊方格在此棋盤中chessBoard(tr,tc+s,dr,dc,

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&&dc<tc+

s)dc,

s);蓋右上角=

t;&&dc<tc

+s) //

特殊方格在此棋盤中在此棋盤中 chessBoard(tr+s,tc,

dr,(tr,tc,dr,

dc,

s); else

{//

用

t

號L型骨牌覆盤中無特殊方格 board[tr+s][tc+s-

1]型骨牌覆蓋右下角 //

覆蓋其余方格-1][tc+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

號L型骨牌覆蓋左上角board[tr+s][tc+s]=

t;//覆蓋其余方格chessBoard(tr+s,tc+s,tr+s,tc+s,

s);}}0第一次任務劃分左上角右上角左下角00此此此格格格有無無特特特殊殊殊方方方格格格，，，繼將將續左右調下上用角角的的方方格格標標記記為為0，0，繼繼續續調調用用右下角此格無特殊方格，將左上角的方格標記為0，繼續調用第一次任務劃分左上角右上角左下角右下角標記， 標記，返回 返回標記，返回122110230043344標記，返回題目描述：an即n

個a

相乘。通常解法：算法復雜度：O(n)按照n

的二進制表示來劃分成子問題的，即n

的二進制數中每一位代表一個子問題，這種分治方法簡稱二進制快速冪。下面以a13為例說明二進制劃分子問題的原理十進制的13轉換為二進制得（1101）2，故：因此計算a13

，只需將對應二進制位為1的對應項a8

、a4

、

a1累乘即可得到。采用位運算來優化求解二進制快速冪擴展內容擴展內容擴展內容當把矩陣冪中的矩陣當作一個整數時，可以直接套用快速冪的算法策略。設X和Y是兩個

n

位十進制數，求X×Y一般情況下，計算

的過程：將X中的每位數分別乘以

來計算“部分積”，然后將所有部分相加。由于有n部分的積，這種計算的復雜度為

O(n2)對于任意給定的2階方陣B和C，求B×C的積D對兩個2×2矩陣相乘時，Strassen算法執行了7次乘法和18次加減法對于任意給定的n階方陣B和C，求B×C的積D多項式乘法：系數表示法：多項式乘法：點值表示法：多項式從點值表示轉換為系數表示多項式從點值表示轉換為系數表示補充知識定理對所有n，有補充知識定理根據前面的定理，如果n>2，有主遞推定理(Main

Recurrence

Theorem)令a、b、k是滿足a≥1、b≥2、k

≥0的整數。b/n

向下取整

T(0)=u,

b/n

向上取整

T(1)=u。課程小結分治法的設計思想分治法的特點：最優子結構和子問題獨立性分治法的適用條件復雜度分析算法設計與分析

算法設計與分析 國家級實驗教學示范中心計算機學科組規劃教材貪心算法第三章3教學內容3.1

貪心算法的思想3.2

貪心算法的要素3.3

活動選擇問題3.4

任務調度問題3.5

最小生成樹問題單源最短路徑問題哈夫曼編碼問題貪心算法3.1

貪心算法的思想3.1

貪心算法思想假定要用最少硬幣來兌換總金額為A的人民幣，可用硬幣的面額是1、5和10，兌換的金額A=18。最優的解硬幣5Why?3.1

貪心算法實例3.1

貪心算法實例假定要用最少硬幣來兌換總金額為A的人民幣，可用硬幣的面額是1、5和10，兌換的金額A=18。3.1

貪心算法實例3.1

貪心算法實例3.1

貪心算法實例【練習】假定要用最少硬幣來兌換總金額為A的人民幣，可用硬幣的面額是1、2和5，但硬幣的數量是有限的，三種硬幣的數量分別為5，3，2，兌換的金額A=18。最優的解硬幣73.1

貪心算法實例貪心算法3.2

貪心算法的要素3.2

貪心算法的要素1.

貪心選擇性質所謂貪心選擇性質是指所求問題的整體最優解可以通過一系列局部最優的選擇，即貪心選擇來達到。這是貪心算法可行的第一個基本要素，也是貪心算法與動態規劃算法的主要區別。動態規劃算法通常以自底向上的方式解各子問題，而貪心算法則通常以自頂向下的方式進行，以迭代的方式作出相繼的貪心選擇，每作一次貪心選擇就將所求問題簡化為規模更小的子問題。對于一個具體問題，要確定它是否具有貪心選擇性質，必須證明每一步所作的貪心選擇最終導致問題的整體最優，通常采用數學歸納法證明。2.

最優子結構性質當一個問題的最優解包含其子問題的最優解時，稱此問題具有最優子結構性質，通常采用反證法證明。問題的最優子結構性質是該問題可用動態規劃算法或貪心算法求解的關鍵特征。3.2

貪心算法的要素0-1背包問題：給定n種物品和一個背包。物品i的重量是Wi，其價值為Vi，背包的容量為C。應如何選擇裝入背包的物品，使得裝入背包中物品的總價值最大?3.2

貪心算法的要素分數背包問題：與0-1背包問題類似，所不同的是在選擇物品i裝入背包時，可以選擇物品i的一部分，而不一定要全部裝入背包，1≤i≤n。這2類問題都具有最優子結構性質，極為相似，但分數背包問題可以用貪心算法求最優解，而0-1背包問題卻不能用貪心算法求最優解。3.2

貪心算法的要素對于0-1背包問題，貪心選擇之所以不能得到最優解是因為在這種情況下，它無法保證最終能將背包裝滿，部分閑置的背包空間使每公斤背包空間的價值降低了，即無法滿足貪心選擇性質。事實上，在考慮0-1背包問題時，應比較選擇該物品和不選擇該物品所導致的最終方案，然后再作出最好選擇。因此，動態規劃算法的確可以有效地解 0-1背包問題。貪心算法與動態規劃算法的差異3.2

貪心算法的要素貪心算法選擇問題：能用動態規劃算法求解的問題也能用貪心算法求最優解？不一定能用貪心算法求解的問題也能用動態規劃算法求解？可以不滿足貪心算法性質的問題可以用貪心算法求解？可以能用貪心算法求解的問題一定可以找到最優解？不一定3.2

貪心算法的要素用貪心算法解分數背包問題的基本步驟：計算每種物品單位重量的價值Vi/Wi依貪心選擇策略，將盡可能多的單位重量價值最高的物品裝入背包。若將這種物品全部裝入背包后，背包內的物品總重量未超過C，則選擇單位重量價值次高的物品并盡可能多地裝入背包。依此策略一直地進行下去，直到背包裝滿為止。3.2

貪心算法的要素貪心算法3.3

活動選擇問題活動選擇問題就是要在所給的活動集合中選出最大的相容活動子集合，是可以用貪心算法有效求解的很好例子。該問題要求高效地安排一系列爭用某一公共資源的活動。貪心算法提供了一個簡單、漂亮的方法使得盡可能多的活動能兼容地使用公共資源。3.3

活動選擇問題無法讓這些課都在同一間教室上，因為有些課存在時間沖突。假設有如下課程表，你希望將盡可能多的課程安排在某間教室上課程上課時間下課時間美術9:0010:00英語9:3010:30數學10:0011:00計算機10:3011:30音樂11:0012:003.3

活動選擇問題（1）選出最早結束的課，它就是在這個教室的第一節課。（2）選出第一節課結束時間后的最早結束的課（3）以此類推為什么不選擇開始時間最早的？√×√×√課程上課時間下課時間美術9:0010:00英語9:3010:30數學10:0011:00計算機10:3011:30音樂11:0012:003.3

活動選擇問題3.3

活動選擇問題算法步驟1、建立活動表，添加進所有的活動，將所有活動按照結束時間進行排序。2、建立活動子集A，從活動表中選擇結束時間最早的活動，將其添加到活動子集A中，并從原來的活動表中刪除。3、從活動表剩下的活動中選擇開始時間大于或等于上一個被選擇活動的結束時間的活動，將其添加到活動子集A中。4、重復步驟

3，直到所有的活動都被考慮過。3.3

活動選擇問題#

Python的索引從0開始，所以我們需要n+1個元素#選擇第1個活動defgreedy_selector(n,s,f):A=[False]*(n+

1)A[1]=

Truej=

1foriinrange(2,n+

1):ifs[i]>=f[j]:A[i]=

Truej=

ielse:A[i]=

Falsereturn

A各活動的起始時間和結束時間存儲于列表s和f中且按結束時間的非減序排列3.3

活動選擇問題由于輸入的活動以其完成時間的非減序排列，所以算法greedySelector每次總是選擇具有最早完成時間的相容活動加入集合A中。直觀上，按這種方法選擇相容活動為未安排活動留下盡可能多的時間。也就是說，該算法的貪心選擇的意義是使剩余的可安排時間段極大化，以便安排盡可能多的相容活動。這個算法的時間復雜度是O(nlogn)，主要是需要對所有的活動進行排序。如果活動已經按結束時間排序，則選擇活動的過程是線性的，即O(n)。3.3

活動選擇問題【例題】：廣東某所學校正在籌備一系列的慶祝活動來慶祝建國75周年，由于排練表演節目的需要，周末學校活動中心收到了11個班級的使用申請。因為排練場地有限，同一時間段內只能有1個排練活動。每個排練活動i都有一個開始時間s[i]和結束時間f[i]。通過安排不同排練活動的開始時刻和結束時刻，使得這些活動不會在時間上沖突。所有排練活動的開始時間和結束時間如下：i1234567891011s[i]130535688212f[j]45679910111214163.3

活動選擇問題所有活動的甘特圖如圖所示。√√√√√3.3

活動選擇問題接下來遍歷取出活動。i1234567891011s[i]130535688212f[j]4567991011121416最終得到的活動順序列表是[(1,

4),

(5,

7),

(8,

11),

(12,

16)]或[(1,

4),

(5,

7),

(8,

12),

(12,

16)]

。3.3

活動選擇問題class

Activity:def

init

(self,start,finish):self.start=

startself.finish=finishdefselect(a,

coin_counts):#

定義活動列表activities=

[Activity(1,4),Activity(3,5),Activity(0,6),Activity(5,

7),Activity(3,9),Activity(5,9),Activity(6,10),Activity(8,

11),Activity(8,12),Activity(2,14),Activity(12,

16)]定義活動類定義活動列表算法步驟：3.3

活動選擇問題defgreedy_activity_selector(activities):#

對活動按結束時間進行排序activities.sort(key=lambdax:x.finish)i=

0forjinrange(1,

len(activities)):ifactivities[j].start>=activities[i].finish:print(f"({activities[j].start},{activities[j].finish})",end=",")i=

j定義活動類定義活動列表貪心算法框架算法步驟：3.3

活動選擇問題貪心算法3.4

任務調度問題任務調度問題是計算機科學中的一類經典問題，它涉及到如何有效地安排和分配任務，以達到某種優化目標，如最小化完成時間、最大化利潤等。在現實生活中，任務調度問題廣泛存在，如工廠生產調度、項目管理、CPU任務調度等。活動選擇問題是任務調度問題的一種特殊情況，它關注的是如何在一系列的活動中選擇出最多的互不沖突的活動。而任務調度問題考慮的是如何最短時間內完成所有任務，并且任務調度問題通常需要考慮更多的約束條件或更多的優化目標，如任務的利潤或任務的截止時間。3.4

任務調度問題【問題描述】設有n個獨立的作業{1，2，…，n}，由m臺相同的機器{1，2，

…，m}進行加工處理，作業i所需的處理時間為ti（1≤i≤n），每個作業均可在任何一臺機器上加工處理，但未完工前不允許中斷，任何作業也不能拆分成更小的子作業。多機調度問題要求給出一種作業調度方案，使所給的n個作業在盡可能短的時間內由m臺機器加工處理完成。3.4

任務調度問題【問題求解】貪心法求解多機調度問題的貪心策略是最長處理時間作業優先，即把處理時間最長的作業分配給最先空閑的機器，這樣可以保證處理時間長的作業優先處理，從而在整體上獲得盡可能短的處理時間。按照最長處理時間作業優先的貪心策略，當m≥n時，只要將機器i的[0，ti)時間區間分配給作業i即可；當m<n時，首先將n個作業依其所需的處理時間從大到小排序，然后依此順序將作業分配給空閑的處理機。3.4

任務調度問題優先規則數量眾多：1、最長處理時間作業優先（LPT:

longest

processingtime）2、最短處理時間作業優先（SPT:

shortest

processing

time）3、最早開始時間作業優先（EST:

earliest

start

time）4、最早完工時間作業優先（EST:

earliest

start

time）5、最晚開始時間作業優先（LST:

latest

start

time）6、最晚完工時間作業優先（LFT:

latest

finishtime）7、考慮工期、緊前緊后、資源受限、混合規則等其他情況……沒有一個規則在所有的情況下都是最佳的。3.4

任務調度問題例如，有7個獨立的作業{1，2，3，4，5，6，7}，由3臺機器{1，2，3}加工處理，各作業所需的處理時間如下：（1）7個作業按處理時間遞減排序，其結果如下表所示。作業編號1234567作業的處理時間214416653作業編號4256371作業的處理時間1614654323.4

任務調度問題（2）先將排序后的前3個作業分配給3臺機器。此時機器的分配情況為{{4}，{2}，{5}}，對應的總處理時間為{16，14，6}。機器1機器2機器3作業4:16作業2:14作業5:6作業編號4256371作業的處理時間1614654323.4

任務調度問題（3）分配余下的作業：4256371作業編號作業的處理時間機器1機器2機器3作業2，總時間14作業5，總時間6作業5、6，總時間11作業5、6、3，總時間1516 14 6 5 4 3 2作業4，總時間16作業2、7，總時間17作業5、6、3、1，總時間17作

業

調

度

方

案3.4

任務調度問題class

NodeType:def

init

(self,no,

t):self.no=

no#作業時間#分配的機器編號self.t=tself.mno=

Nonen=

7m=

3A=[NodeType(1,2),NodeType(2,14),NodeType(3,4),

NodeType(4,16),NodeType(5,6),NodeType(6,5),NodeType(7,

3)]1.

定義作業類及初始化算法步驟：3.4

任務調度問題defsolve(A,n,m):A.sort(key=lambdax:x.t,

reverse=True)#按執行時間

t

排序#

初始化每臺機器的結束時間machine_end_times=[0]*mforiin

range(n):#

找到當前結束時間最早的機器min_end_time=min(machine_end_times)machine_index=

machine_end_times.index(min_end_time)A[i].mno=machine_index

+

1 #Python從0開始print(f"

給機器{A[i].mno}分配作業{A[i].no},執行時間為{A[i].t:2},占用時間段:[{min_end_time},{min_end_time

+

A[i].t}]")machine_end_times[machine_index]+=

A[i].t定義作業類及初始化貪心算法框架算法步驟：3.4

任務調度問題【練習】設7個獨立作業{1,2,3,4,5,6,7}由3臺機器M1，M2和M3加工處理。各作業所需的處理時間分別為{2,14,4,16,6,5,3}。請寫出每臺機器分別加工哪些作業（按加工先后順序），并計算所需的最少加工時間。3.4

任務調度問題設7個獨立作業{1,2,3,4,5,6,7}由3臺機器M1，M2和M3加工處理。各作業所需的處理時間分別為{2,14,4,16,6,5,3}。按貪心算法產生的作業調度如下圖所示，所需的加工時間為17。3.4

任務調度問題3.4

任務調度問題3.4

任務調度問題當處理單元存在先后順序時，調度問題變得更加復雜。這個問題是NP完全問題，到目前為止還沒有有效的解法。在問題規模比較小時貪心算法往往可以找到最優解。問題規模較大時，貪心算法雖然可能不是全局最優的，但是在實際應用中往往非常接近全局最優解，而且計算效率高。3.4

任務調度問題【問題描述】有n個作業（編號為1～n）要在由兩臺機器M1和M2組成的流水線上完成加工。每個作業加工的順序都是先在M1上加工，然后在M2上加工。M1和M2加工作業i所需的時間分別為ai和bi（1≤i≤n）。要求確定這n個作業的最優加工順序，使得從第一個作業在機器M1上開始加工，到最后一個作業在機器M2上加工完成所需的時間最少。針對兩臺機器的情況，常常可以使用稱為Johnson貪心算法。3.4

任務調度問題【問題求解】采用歸納思路。當只有一個作業（a1，b1），顯然最少時間Tmin=a1+b1。當有兩個作業（a1，b1）和（a2，b2）時，若（a1，b1）在前，（a2，b2）在后執行：(a)作業2在M2上執行沒有等待的情況Tmin=a1+a2+b2（b1<a2）(b)作業2在M2上執行有等待的情況Tmin=a1+b1+b2（a2<b1）Tmin=a1+b1+a2+b2-min(a2，b1)。3.4

任務調度問題【問題求解】同理，若（a2，b2）在前，（a1，b1）在后執行：(a)作業1在M2上執行有等待的情況(b)作業1在M2上執行沒有等待的情況Tmin=a2+b2+b1（a1<b2） Tmin=a2+a1+b1（b2<a1）Tmin=a1+b1+a2+b2-min(a1，b2)。3.4

任務調度問題將兩種執行順序合并起來有：Tmin=a1+b1+a2+b2-max(min(a2，b1)，min(a1，b2))由此可以得到一個結論：對于(a1，b1)和(a2，b2)中的元素若min(a1，b2)≤min(a2，b1)，則(a1，b1)放在(a2，b2)前面反之，若min(a2，b1)≥min(a1，b2)

(a2，b2)放在(a1，b1)前面讓(a,b)中a比較小的盡可能先執行，(a,b)中b比較小的盡可能后執行！3.4

任務調度問題當作業數量n小于機器數量m時，只要將機器i的[0, ti]時間區間分配給作業i即可，算法只需要O(1)時間。當作業數量n遠大于機器數量m時，一般采用最長處理時間作業優先的貪心選擇策略可以設計出解多機調度問題的較好的近似算法。首先將n個作業依其所需的處理時間從大到小排序，然后依此順序將作業分配給空閑的處理機。算法所需的計算時間為O(nlogn)。3.4

任務調度問題貪心算法3.5

最小生成樹問題3.5

最小生成樹問題最小生成樹的概念在無向圖G中，若從頂點v到頂點w有路徑存在，則稱v和w是連通的。如果

G

是有向圖，那么連接v和w的路徑中所有的邊都必須同向。如果圖中任意兩點都是連通的，那么圖被稱作連通圖。如果此圖是有向圖，則稱為強連通圖（注意：需要雙向都有路徑）。圖的連通性是圖的基本性質。最小生成樹的概念無向圖G的一個極大連通子圖稱為G的一個連通分量（或連通分支）。連通圖只有一個連通分量，即其自身；非連通的無向圖有多個連通分量。3.5

最小生成樹問題最小生成樹的概念生成樹是包含圖中全部頂點的一個極小連通子圖。極小連通子圖：該子圖是G的連通子圖，在該子圖中刪除任何一條邊，子圖不再連通。若圖中頂點數為n，則它的生成樹含有n-1條邊。3.5

最小生成樹問題最小生成樹的概念設G=(V,E)是無向連通帶權圖，E中每條邊(v,w)的權為c[v][w]。如果G的子圖G’

為G的生成樹，則生成樹上各邊權的總和稱為該生成樹的耗費。在G的所有生成樹中，耗費最小的生成樹稱為G的最小生成樹。3.5

最小生成樹問題最小生成樹性質設G=(V,E)是連通帶權圖，U是V的真子集。如果(u,v)是一條具有最小權值的邊，其中u屬于U

，v屬于V

－

U

，則必存在一棵包含邊(u,v)的最小生成樹。這個性質有時也稱為MST性質。反證法可以證明。3.5

最小生成樹問題最小生成樹性質這個性質告訴我們，對于任何分割（將圖的頂點集分為兩個非空子集的過程），連接這兩個子集的權值最小的邊一定屬于圖的最小生成樹。這個性質為Prim和Kruskal算法的正確性提供了理論支持。這兩種算法都是通過選擇權值最小的邊來逐步構建最小生成樹的。3.5

最小生成樹問題最小生成樹性質最小生成樹的最優子結構指的是一個圖的最小生成樹的任意子圖也是該子圖的最小生成樹。換句話說，如果從最小生成樹中移除某些邊，剩下的部分仍然是其所在子圖的最小生成樹。這個性質意味著最小生成樹可以通過逐步添加邊的方式構建，每一步都添加一條連接兩個不同集合的最小權重邊。3.5

最小生成樹問題對于下圖中的帶權圖，按Prim算法構筑最小生成樹。1.

初始化：選擇任意一個頂點作為起始點，將其加入最小生成樹的集合中。3.5

最小生成樹問題對于下圖中的帶權圖，按Prim算法構筑最小生成樹。2.

在圖中找到一條連接已在最小生成樹集合中的頂點和不在集合中的頂點的權重最小的邊。3.5

最小生成樹問題對于下圖中的帶權圖，按Prim算法構筑最小生成樹。3.

將這條邊的另一端點（不在最小生成樹集合中的頂點）加入到最小生成樹的集合中。3.5

最小生成樹問題對于下圖中的帶權圖，按Prim算法構筑最小生成樹。4.

重復這個過程。3.5

最小生成樹問題5.

當所有的頂點都被加入到最小生成樹的集合中時，算法結束，得到的集合即為圖的最小生成樹3.5

最小生成樹問題構造最小生成樹的Prim算法的基本步驟是：初始化：選擇任意一個頂點作為起始點，將其加入最小生成樹的集合中。邊的選擇：在圖中找到一條連接已在最小生成樹集合中的頂點和不在集合中的頂點的權重最小的邊。頂點的添加：將這條邊的另一端點（不在最小生成樹集合中的頂點）加入到最小生成樹的集合中。重復步驟：重復步驟2和3，直到所有的頂點都被加入到最小生成樹的集合中。完成：當所有的頂點都被加入到最小生成樹的集合中時，算法結束，得到的集合即為圖的最小生成樹3.5

最小生成樹問題#

示例圖的鄰接矩陣表示，使用

float('inf')

表示不相連graph=

[[0,6,1,5,float('inf'),float('inf')],[6,0,5,float('inf'),3,float('inf')],[1,5,0,5,6,

4],[5,float('inf'),5,0,float('inf'),2],[float('inf'),3,6,float('inf'),0,6],[float('inf'),float('inf'),4,2,6,0]]1.

表示圖算法步驟：3.5

最小生成樹問題defprim_no_queue(graph,start)：num_vertices=

len(graph)in_mst

=

[False]

*

num_vertices#

是否已包含在最小生成樹中edge_to=[None]*num_vertices#

連接到樹中的邊weight_to=[float('inf')]*num_vertices#

邊的權重mst_edges

=

[]#

最小生成樹的邊total_cost

=

0

#

最小生成樹的總權重weight_to[start]=

0#

從起始頂點開始表示圖初始化定義起始頂點算法步驟：3.5

最小生成樹問題defprim_no_queue(graph,

start)：……for_in

range(num_vertices):#

找到權重最小的未加入最小生成樹的頂點currentifcurrentis

None:break

#

所有頂點都已處理完畢#

將頂點加入到最小生成樹中current_vertex=weight_to.index(current)in_mst[current_vertex]=

Truetotal_cost+=

current表示圖初始化定義起始頂點找頂點把頂點加入最小生成樹中算法步驟：3.5

最小生成樹問題defprim_no_queue(graph,

start)：……for_in

range(num_vertices):……#

如果當前頂點有連接到最小生成樹的邊ifedge_to[current_vertex]isnotNone:#

將該邊加入到最小生成樹的邊列表中mst_edges.append((edge_to[current_vertex],

current_vertex))表示圖初始化定義起始頂點找頂點把頂點加入最小生成樹中把頂點與最小生成樹所連的邊也統計算法步驟：3.5

最小生成樹問題defprim_no_queue(graph,

start)：……for_in

range(num_vertices):……#

更新連接邊和權重fornext_vertexin

range(num_vertices):#

如果當前頂點到

next_vertex

的邊的權重小于已記錄的權重，并且

next_vertex

還未加入最小生成樹:#

更新權重和連接邊returnmst_edges,

total_cost表示圖初始化定義起始頂點找頂點把頂點加入最小生成樹中把頂點與最小生成樹所連的邊也統計更新算法步驟：3.5

最小生成樹問題Prim算法的時間復雜度取決于它的實現方式。①鄰接矩陣：如果使用鄰接矩陣表示圖并使用簡單的線性搜索來查找權重最小的邊，Prim算法的時間復雜度為O(V^2)，其中V是頂點的數量。②優先隊列：如果使用優先隊列，如二叉堆來加速權重最小的邊的查找過程，并使用鄰接表表示圖，Prim算法的時間復雜度可以降低到O(ElogV)，其中E是邊的數量。很多語言都提供了優先級隊列的實現。比如，Java的PriorityQueue，C++的priority_queue，Python中的heapq等。在實際應用中，為了獲得更好的性能，通常會選擇使用優先隊列和鄰接表的組合來實現Prim算法。3.5

最小生成樹問題【練習】找出下圖的最小生成樹504136218676534250413621663423.5

最小生成樹問題對于下圖中的帶權圖，按Kruskal算法構筑最小生成樹。1、排序：將圖中的所有邊按權重從小到大排序。3.5

最小生成樹問題對于下圖中的帶權圖，按Kruskal算法構筑最小生成樹。2、初始化：創建一個空集合，用于存放最小生成樹中的邊。同時，為每個頂點創建一個單獨的集合，表示它們所屬的連通分量。3.5

最小生成樹問題對于下圖中的帶權圖，按Kruskal算法構筑最小生成樹。3、按權重從小到大的順序考慮每條邊。對于每條邊，檢查它連接的兩個頂點是否屬于同一個連通分量。3.5

最小生成樹問題對于下圖中的帶權圖，按Kruskal算法構筑最小生成樹。5、繼續選擇邊，判斷是否連通分量，合并。3.5

最小生成樹問題對于下圖中的帶權圖，按Kruskal算法構筑最小生成樹。6、繼續選擇邊，判斷是否連通分量，合并。3.5

最小生成樹問題對于下圖中的帶權圖，按Kruskal算法構筑最小生成樹。7、繼續選擇邊，判斷是否連通分量，合并。3.5

最小生成樹問題對于下圖中的帶權圖，按Kruskal算法構筑最小生成樹。8、繼續選擇邊，判斷是否連通分量，合并。3.5

最小生成樹問題對于下圖中的帶權圖，按Kruskal算法構筑最小生成樹。9、當最小生成樹中的邊數達到V-1（其中V是頂點的數量）或所有的邊都被考慮過時，算法結束。3.5

最小生成樹問題3.5

最小生成樹問題Kruskal算法的算法步驟說明如下：1、排序：將圖中的所有邊按權重從小到大排序。2、初始化：創建一個空集合，用于存放最小生成樹中的邊。同時，為每個頂點創建一個單獨的集合，表示它們所屬的連通分量。3、邊的選擇：按權重從小到大的順序考慮每條邊。對于每條邊，檢查它連接的兩個頂點是否屬于同一個連通分量。4、合并：如果兩個頂點不在同一個連通分量中，將這條邊加入到最小生成樹的集合中，并合并兩個頂點所在的連通分量。5、完成：當最小生成樹中的邊數達到V-1（其中V是頂點的數量）或所有的邊都被考慮過時，算法結束。3.5

最小生成樹問題#

示例圖的鄰接矩陣表示，使用

float('inf')

表示不相連graph=

[[0,6,1,5,float('inf'),float('inf')],[6,0,5,float('inf'),3,float('inf')],[1,5,0,5,6,

4],[5,float('inf'),5,0,float('inf'),2],[float('inf'),3,6,float('inf'),0,6],[float('inf'),float('inf'),4,2,6,0]]1.

表示圖算法步驟：3.5

最小生成樹問題n

=

len(matrix)#

頂點的數量edges

=

[]#

所有邊的列表mst

=

[]#

存放最小生成樹中的邊total_cost

=

0

#

最小生成樹的總權重#

創建連通分量集合，初始時每個頂點自成一個集合connected_components={i:iforiin

range(n)}表示圖初始化：創建一個空集合，用于存放最小生成樹中的邊。同時，為每個頂點創建一個單獨的集合，表示它們所屬的連通分量。算法步驟：3.5

最小生成樹問題#

獲取圖中所有的邊和權重foriin

range(n):forjinrange(i+1,n):ifmatrix[i][j]!=

INF:edges.append((i,j,matrix[i][j]))#

將所有邊按權重從小到大排序edges.sort(key=lambdaedge:edge[2])表示圖初始化排序：將圖中的所有邊按權重從小到大排序算法步驟：3.5

最小生成樹問題foredgeinedges:u,v,weight=

edge#

如果兩個頂點不屬于同一個連通分量，添加這條邊iffind(u)

!=

find(v): #

定義find方法判斷union(u,

v) #

定義union方法合并兩個頂點的連通分量mst.append(edge)total_cost+=

weight#

如果最小生成樹中的邊數已經達到頂點數減一，結