算法概念介紹及舉例說明課件

1、例子:給定兩個正整數(shù)m和n,求它們的最大公因子算法:歐幾里德算法輸入:正整數(shù)m、n輸出：m和n的最大公因子第一章 算法引論1.1 算法的基本概念一、什么是算法及其與程序的區(qū)別S1:保證m=n,如果mn，則m、n的值互換，否則轉(zhuǎn)S2.S2:求余數(shù)。令r=m mod n,（0=rn)S3:判斷余數(shù)r是否為0。如果r是0，則算法終止，n為答案，否則轉(zhuǎn)S4.S4:置換。即mn,nr,轉(zhuǎn)S2.什么是算法？ 它是一組有窮規(guī)則的集合，它規(guī)定了解決某一特定類型問題的一系列運算。 二、算法的特征 1、確定性 2、能行性 3、輸入 4、輸出 5、有窮性:一個算法總是在有限步之后結(jié)束，且每一步都可在有窮時間內(nèi)完成.

2、 算法與程序的區(qū)別： 程序：與某種語言有關(guān)，能直接在機器上運行。 算法：與特定的語言無關(guān)，可用任何語言實現(xiàn) ，甚至可以用自然語言實現(xiàn)，但是一般為了避免二義性，本書采用類C語言描述。 一個算法總是在執(zhí)行了有窮步驟的運算后終止，否則就是一個計算過程。 有窮性與有效性的關(guān)系：三、評價算法的標準 有窮性是對算法的基本要求，如果一個算法要能使用，必須具有有效性。有效性是指算法在規(guī)定的時間里終止。時間復(fù)雜性和空間復(fù)雜性1.2 算法設(shè)計的步驟一、問題的描述例:貨郎擔(dān)問題 設(shè)售貨員在一天內(nèi)要到5個城市去推銷貨物，已知從一個城市到其他城市的費用，求總費用最少的路線。給出的信息主要有五個城市的關(guān)系圖及相應(yīng)的費用矩

3、陣。二、模型的擬制 建模階段至少要考慮以下兩個基本問題： 1）最適合于這個問題的數(shù)學(xué)結(jié)構(gòu)是什么？ 2）有沒有已經(jīng)解決了的類似問題可供借鑒？ 在模型建立好了以后，應(yīng)該依據(jù)所選定的模型對問題重新陳述,并考慮下列問題: (1)模型是否清楚地表達了與問題有關(guān)的所有重要的信息?(2)模型中是否存在與要求的結(jié)果相關(guān)的數(shù)學(xué)量?(3)模型是否正確反映了輸入、輸出的關(guān)系?(4)對這個模型處理起來困難嗎？152434724335211 對于貨郎擔(dān)問題，其數(shù)學(xué)模型是帶權(quán)圖，與此圖相關(guān)的是費用矩陣。以貨郎擔(dān)問題為例：采用枚舉法。分析：三、算法的詳細設(shè)計 算法的詳細設(shè)計是指設(shè)計求解某個具體問題的一系列步驟，并且這些步驟

4、可以通過計算機的各種操作來實現(xiàn)。輸入：城市數(shù)目n;費用矩陣C=(cij)n*n輸出：旅行路線TOUR;最小費用MINSalesman (n) i 1;tour0;min while i=(n-1)! do pPHRMUTI(n-1,i); / PHRMUTI(n-1,i)是生成1到n-1的第i個排列的子過程 cost(T(p)EFP(c,T(p)； / EFP(c,T)是由費用矩陣c及路線T(p)所算得的總費用 if cost(T(p)=n0時，利用A(n)的定義和 一個簡單的不等式，有取c=|am|+.+|a0| 定理得證.事實上，只要將n0取得足夠大，可以證明只要c是比|am|大的任意一個

5、常數(shù)，此定理都成立。定理1.1 若A(n)=amnm+ a1n+ a0是一個m次多項式，則A(n)=O(nm)。 此定理表明，變量n的固定階數(shù)為m的任一多項式，與此多項式的最高階nm同階，因此計算時間為m階的多項式的算法，其時間都可用O(nm).例如，若一個算法有數(shù)量級為c1nm1, c2nm2, cknmk 的k個語句，則此算法的數(shù)量級就是 c1nm1 +c2nm2+cknmk 由定理1.1，它等于O(nm),其中m=maxmi|1i kn2nlognn=1024104857610240時間（n=1024)1.05s0.01sn=2048419430422528時間（n=2048)4.2s0

6、.02s例子：假設(shè)有解決同一個問題的兩個算法，它們有n個輸 入，分別要求n2和nlogn次運算。定義1.3 如果存在兩個正常數(shù)c和n0,對于所有n n0,有 |f(n)| c|g(n)| 則記為f(n)=(g(n)。定義1.4 如果存在兩個正常數(shù)c1 ,c2,和n0,對于所有的n n0,有 則記為f(n)=(g(n)。 一個算法的f(n)=(g(n)意味著該算法在最好和最壞情況下的計算時間就一個常因子范圍內(nèi)而言是相同的。五、算法分類（按時間） 多項式時間算法：凡可用多項式來對其計算時間界限的算法。 指數(shù)時間算法：計算時間用指數(shù)函數(shù)界限的算法。以下六種計算時間的多項式時間算法是最為常見的，其關(guān)系

7、為： O(1) O(logn) O(n) O(nlogn) O(n2) O(n3)指數(shù)時間算法一般有O(2n)、O(n!) 和O(nn)等。其關(guān)系為 O(2n) O(n!) O(nn) 注意：當(dāng)數(shù)據(jù)集的規(guī)模很大時，要在現(xiàn)代計算機上運行具有比O（nlogn)復(fù)雜度高的算法往往是很困難的。六、最好、最壞和平均情況以順序檢索為例第二章 分治法2.1 方法概述一、基本思想 1、設(shè)計思想：將整個問題分成若干個小問題后,分而治之。 2、適用條件： 問題規(guī)模很大； 可以分成若干個與原問題性質(zhì)相同的子問題，并可以分別求解。 子問題的解通過整合可以得到原問題的解。 3、設(shè)計方法：使用遞歸策略。4、 設(shè)計步驟(1

8、)分解：將原問題分解為若干個相互獨立、與原問題形式相同的子問題； (2)求解：若子問題容易被解決則直接解，否則再繼續(xù)分解為更小的子問題，直到容易解決； (3)合并：將已求解的各個子問題的解，逐步合并以得到原問題的解。二、分治法的算法設(shè)計模式Divide-and-Conquer(n) /n為問題規(guī)模1if n = n0 /n0 為可解子問題的規(guī)模2then 3 4 解子問題5 return( 子問題的解 )64for i 1 to k /分解為k個子問題5 do yi Divide-and-Conquer(|Pi|)/遞歸解決Pi6 T MERGE(y1,y2,.,yk) /合并子問題7 ret

9、urn T遞歸過程注意：分治法可以用遞歸實現(xiàn)，也可以用循環(huán)實現(xiàn)。 其中：其中|P|表示問題P的規(guī)模；n0為一閾值，表示當(dāng)問題P的規(guī)模不超過n0時，問題已容易直接解出，不必再繼續(xù)分解。算法MERGE(y1,y2,.,yk)是該分治法中的合并子算法，用于將P的子問題P1 ,P2 ,.,Pk的相應(yīng)的解y1,y2,.,yk合并為P的解。時間復(fù)雜性分析： 其中，T(n)是輸入規(guī)模為n的Divide-and-Conquer的時間，g(n)是對足夠小的輸入規(guī)模能直接計算出答案的時間，f(n)是MERGE的時間。 倘若所分成的兩個子問題的輸入規(guī)模大致相等，則Divide-and-Conquer總的計算時間可以

10、用下面的遞推關(guān)系來表示： (n足夠小) (否則) 2.2 二 分 檢 索一、問題描述 已知一個按非降次序排列的元素表a1,a2,an,要求判定某給定元素x是否在該表中出現(xiàn)。若是，則找出x在表中的位置，并將此下標值賦給變量j；若非，則將j置成0。二、問題分析 設(shè)該問題用I=(n, a1,a2,an,x)來表示，可以將它分解成一些子問題，一種可能的做法是，選取一個下標k，由此得到三個子問題：I1=(k-1, a1,a2,ak-1,x),I2=(1,ak,x)和I3=(n-k, ak+1,an,x)。 對于I2，通過比較x和ak容易得到解決。如果x= ak,則j=k且不需再對I1和I3求解；否則，在

11、I2 子問題的j=0，此時若xak,只有I3留待求解，在I1子問題中的j=0。在ak作了比較之后，留待求解的問題（如果有的話）可以再一次使用分治法來求解。如果對所求解的問題（或子問題）所選的下標k都是其元素的中間元素下標（例如，對于I，k=(n+1)/2）,則所產(chǎn)生的算法就是通常所說的二分檢索。三、二分檢索算法 算法2.3 二分檢索 /給定一個按非降次序排列的元素數(shù)組A(1:n),n1,判 斷x是否出現(xiàn)。若是，置j，使得x=A(j),若非，j=0/BINSEARCH(A,n,x)1 low 12 high n 3 while lowhigh，數(shù)組A中沒有找到x，返回j04 do5 6 /取處于

12、low和high之間的中間值7 if x=Amid/找到值為x的元素，mid即為其下標，返回mid8 thenreturn mid9 else if x Amid/如果x Amid，則x可能位于low與mid之間，10 /否則x可能位于mid與high之間11 then high mid - 112 else low mid + 113 14 retrun 0 非遞歸形式四、算法的證明假定在A9中順序存放著以下9個元素：-15，-6，0，7，9，23，54，82，101。要求檢索下列x的值：101，-14和82是否在A中出現(xiàn)。 X=101low high midX=-14low high mi

13、dX=82low high mid19519519569714269789811199921找不到898找到找到A（1）（2）（3）（4）（5）（6）（7）（8）（9）元素-15-6079235482101比較次數(shù)323413234從算法中可以看到,所有的運算基本上都是進行比較和數(shù)據(jù)傳送，前兩條是賦值語句,頻率計數(shù)均為1。在while循環(huán)中，我們集中考慮循環(huán)的次數(shù)，而其他運算的頻率計數(shù)顯然與這些元素比較運算的頻率計數(shù)具有相同的數(shù)量級，找到這九個元素中的每一個所需的元素循環(huán)的次數(shù)如下： 五、時間復(fù)雜性分析 (1) (log n) (log n) (log n) (log n) (log n) 分

14、析：對于A中的n個數(shù)，如果x在A中出現(xiàn)，則是成功檢索，所以成功檢索共有n種情況，而不成功的檢索，x將取n+1個區(qū)間中的不同值，因此在計算出x在這2n+1種情況下的執(zhí)行時間后，就可以求出其在各種情況下的時間復(fù)雜性了。例子：A： （1） （2） （3） （4） （5） （6） （7） （8 ） （9 ） 元素： -15 -6 0 7 9 23 54 82 101 比較次數(shù)： 3 2 3 4 1 3 2 3 4 成功檢索的比較次數(shù)是25/92.77。 不成功檢索有10種，如果xA（1）,A(1)xA(2), A(2)xA(3), A(5)xA(6),A(6)xA(7),A(7)xA(8) ，為了判斷

15、x不在A中，算法要比較3次，而其余的情況要比較4次，因此一次不成功檢索的元素平均比較次數(shù)就是（3+3+3+4+4+3+3+3+4+4）/10=3.4 。 由于算法的執(zhí)行過程實質(zhì)上是x與一系列中間元素A（mid）的比較過程，所以可以用一個二元比較樹來描述。二元比較樹： （1）此樹的結(jié)點由內(nèi)結(jié)點和外結(jié)點組成； （2）每個內(nèi)結(jié)點表示一次元素比較，用圓形結(jié)點表示，在以元素比較為基礎(chǔ)的二分檢索中，每個內(nèi)結(jié)點存放一個mid值； （3） 外結(jié)點用方形結(jié)點表示，在二分檢索中它表示一次不成功的檢索； （4）x如果在A 中出現(xiàn)，則算法就在一個圓形結(jié)點處結(jié)束，該結(jié)點將指出x在A中的下標； x如果不在A 中出現(xiàn)，則算

16、法就在一個方形結(jié)點處結(jié)束，如圖所示。529713486xA(1)A(1)xA(2)A(3)xA(4)A(2)xA(3)A(6)xA(7)A(5)xA(6)A(4)xA(5)A(8)xA(9)A(7)xA(8)證明：考察以n個結(jié)點描述BINSRCH執(zhí)行過程的二元比較樹，所有成功檢索都在內(nèi)部結(jié)點處結(jié)束，而所有不成功的檢索都在外部結(jié)點處結(jié)束。由于2k-1n2k ，因此所有的內(nèi)部結(jié)點在1，2，3，k級，而所有的外部結(jié)點在k,k+1級（注意：根在1 級）。即是，成功檢索在i級終止所需要的元素比較次數(shù)是i,而不成功檢索在i級外部結(jié)點終止的元素比較數(shù)是i-1.因此定理得證。 定理2.1 若n在區(qū)域2k-1,

17、 2k)中，則對于一次成功的檢索，BINSRCH 至多作k次比較，而對于一次不成功的檢索，或者作k-1次比較或者作k次比較。 由此：最壞情況下的成功檢索和不成功檢索的計算時間是（logn）,最好情況下的成功檢索在根結(jié)點處到達，時間是（1），而最好情況的不成功檢索要logn次元素比較，所以時間是（logn）。由于外部節(jié)點都在k和k+1級，因此，每種不成功檢索的時間都是（logn），故平均情況下不成功檢索的計算時間是（logn）。 E=I+2n (1)令S(n)是成功檢索的平均比較數(shù)，則 S（n)=I/n+1 (2) 平均情況下成功檢索的時間復(fù)雜性分析： 設(shè)根到所有內(nèi)部結(jié)點的距離之和稱為內(nèi)部路徑長

18、度I，由根到所有外部結(jié)點的距離之和稱為外部路徑長度E，可以證明：為什么要+1 令U（n)是不成功檢索的平均情況比較數(shù)，而任何一個外部結(jié)點所需要的比較數(shù)是由根到該結(jié)點路徑的長度，由此得： U(n)=E/(n+1) (3)利用（1）-（3）可以得到： S(n)=(1+1/n)U(n)-1因此：平均情況下成功檢索的時間復(fù)雜性為： (log n)。五、一種二分檢索的變形BINSEARCH1。 BINSEARCH1的while循環(huán)中x和Amid之間只用作一次比較。 BINSEARCH1(A,n,x,j)1 low 12 high n+13 while low high4do56 mid (low + h

19、igh) / 27 if (x Amid)/在循環(huán)中只比較一次8 then high mid9else lowmid10 11 if x = Alow12 then j low/x出現(xiàn)13 else j=0 / x不出現(xiàn)14 return j BINSEARCH和BINSEARCH1相比較可看出，對于任何一種成功的檢索，BINSEARCH1平均要比BINSEARCH多作 次比較。BINSEARCH1的最好、平均和最壞情況時間對于成功和不成功的檢索都是 。 六、以比較為基礎(chǔ)檢索的時間下界 1. 什么是以比較為基礎(chǔ)的檢索算法 檢索一給定元素x是否在A中出現(xiàn)。如果只允許進行元素間的比較而不允許對它們

20、實施運算，在這種條件下所設(shè)計的算法都稱為是以比較為基礎(chǔ)的算法 。 2. 二分檢索是以比較為基礎(chǔ)的檢索算法中最壞情況下的最優(yōu)算法. 定理2.3 設(shè)A（1：n）含有n個不同的元素，n1，它們被排序為A(1)A(2)A(n)。又設(shè)用以比較為基礎(chǔ)去判斷是否xA（1：n）的任何算法在最壞情況下所需的最小比較次數(shù)是FIND（n），那么FIND（n） 結(jié)論：由于二分檢索所產(chǎn)生的比較樹中所有的外部結(jié)點都在相鄰接的兩個級上，不難證明這樣的二元樹使得由根到結(jié)點的最長路徑減至最小，因此，二分檢索是解決檢索問題在最壞情況下的最優(yōu)算法。證明：通過考慮模擬求解檢索問題的各種算法的比較樹可知，F(xiàn)IND（n）不大于樹中根到一

21、個葉子最長路徑的距離。在這所有的樹中都必定有n個內(nèi)結(jié)點與x在A中可能的n種出現(xiàn)相對應(yīng)，如果一棵二元樹的所有內(nèi)結(jié)點所在的級數(shù)小于級數(shù)k，則最多有2k-1個內(nèi)結(jié)點，因此n 2k-1,即FIND（n）=k 一、直接求最大、最小元素算法2.5 直接找最大和最小元素maxmin(A,n) /將A(1:n)中的最大元素置于max，最小元素置于min/1 max A12 min A1;3 for i 2 to n4 do5 6 if max Ai 7 then min Ai8 2.3 找最大和最小元素 時間復(fù)雜性分析： STRAITMAXMIN在最好、平均和最壞情況下均需要作2(n-1)次元素比較。 如果稍

22、做修改： 用下面的語句代替for循環(huán)中的語句： if A(i)max then maxA(i) else if A(i)min then minA(i) endif endif 最好情況將在元素按遞增次序排列時出現(xiàn)，元素比較數(shù)是n-1；最壞情況將在遞減次序時出現(xiàn)，元素比較是 2（n-1）；至于在平均情況下,A(i)將有一半的時間比max大，因此平均比較數(shù)是3/2(n-1)。二、用分治法求最大、最小元素 1、問題分析 使用分治策略設(shè)計是將任一實例I=(n，A(1)，A(n)分成一些較小的實例來處理，例如，可以把分成兩個這樣的實例I1=(n/2，A(1)，A(n/2)和 =(n-n/2,A(n/2

23、+1),A(n)。如果()和（）是中的最大和最小元素，則（）等于（）和（）中的大者，（）等于（）和（）中的小者。如果只包含一個元素，則不需要作任何分割直接就可得到其解。 2.算法算法.遞歸求取最大和最小元素float An;maxmin（i, j, fmax, fmin）/最大和最小元素賦給fmax和fmin1 if i = j 2 then3 4 fmax Ai;5 fmin Ai; 7 else if i = j-18 then if Ai rmax25 then fmax lmax;26 else fmax rmax27 if lmin rmin28 then fmin rmin;29

24、else fmin lmin;30 遞歸調(diào)用利用層次分析法分析此遞歸調(diào)用過程。（要求掌握）考慮如下例子：A：（1） （2） （3） （4） （5） （6） （7） （8） （9） 22 13 -5 -8 15 60 17 31 473.時間復(fù)雜性分析 0 n=1 (n)= 1 n=2 n2當(dāng)n是的冪時，即對于某個正整數(shù)k，nk ，有 T(n)=2T(n/2)+2=2(2T(n/4)+2)+2=4T(n/4)+4+2 =k-1 T(2)+ =k-1 T+k-2 =3n/2-2?討論：以上算法是否是最優(yōu)的？1）遞歸帶來的額外的空間開銷。2）當(dāng)元素A(i)和A(j)的比較時間i和j的比較時間相差不大

25、時，過程maxmin并不可取。因此：當(dāng)n是的冪時，3n/2-2是最好，平均及最壞情況的比較數(shù),和直接算法的比較數(shù)n相比，它少了。 可以證明，任何一種以元素比較為基礎(chǔ)的找最大和最小元素的算法，其元素比較下界均為 次。 為說明問題，假設(shè)元素比較與i和j間的比較時間相同，又設(shè)maxmin的頻率計數(shù)為C(n) ，n=2k，,k是某個正整數(shù)，并且對前兩種情況，用ij-1來代替i=j和i=j-1這兩次比較，這樣，只用對i和j-1作一次比較就足以實現(xiàn)被修改過的語句。于是maxmin頻率計數(shù) C(n)= n=2 n2?解此關(guān)系式可得 C(n)=2C(n/2)+3=4C(n/4)+6+3 =2k-1C(2)+

26、=2k+3*2k-1-3 =5n/2-3分析：STRAITMAXMIN的比較數(shù)是3(n-1)(包括實現(xiàn)for循環(huán)所要的比較)。盡管它比5n/2-3大些，但由于遞歸算法中i，j，fmax，fmin進出棧所帶來的開銷，因此maxmin在這種情況下反而比STRAITMAXMIN還要慢些。 根據(jù)以上分析可以得出結(jié)論：如果A的元素間的比較遠比整數(shù)變量的比較代價昂貴，則分治方法產(chǎn)生效率較高（實際上是最優(yōu)）的算法；反之，就得到一個效率較低的程序。因此，分治策略只能看成是一個較好的然而并不總是能成功的算法設(shè)計指導(dǎo)。2.4斯特拉森矩陣乘法一、一般的矩陣乘法 設(shè)C=A*B, 則利用常規(guī)方法計算，所需時間是 二、分

27、治法求矩陣乘法 設(shè)n=2k，則可以將兩個矩陣的乘法做如下劃分：其中：C11=A11B11+A12B21 C12=A11B12+A12B21 C21=A21B11+A22B21 C22=A21B12+A22B22可以證明: C=AB= 三.斯特拉森矩陣乘法 斯特拉森矩陣乘法的設(shè)計思想:增加加法的次數(shù),減少乘法的次數(shù). 如果分塊矩陣的級大于2,則可以繼續(xù)將這些子矩陣分成更小的方陣,直至每個方陣只含有一個元素,以至可以直接計算其乘積.時間復(fù)雜性分析: n 2 n2則T(n)=O(n3)先用七個乘法和十個加（減）法來算出以下的P-VP=(A11+A22)(B11+B22) ，Q=(A21+A22)B1

28、1R=A11(B12-B22)， S=A22(B21-B11)T=(A11+A12)B22 ，U=(A21-A11)(B11+B12)V=(A12-A22)(B21+B22)然后用8個加減法算出這些 Cij C11=P+S-T+VC12=R+TC21=Q+SC22=P+R-Q+U 以上共用了7次乘法,18次加減法. n 2 n2 其中a和b是常數(shù)。解：T(n)=7T(n/2)+an2=72T(n2/4)+(7/4)an2+an2 =73T(n3/8)+(7/4)2an2+(7/4)an2+an2 =an2(1+(7/4)+(7/4)2+.+(7/4)k-1)+7kT(1)cn2(7/4)log

29、n+7logn(1)因為：7logn =nlog7 cn2(7/4)logn=cnlog4*nlog7-log4=cnlog4+log7-log4=cnlog7因此上式(1)=cnlog7+7logn=cnlog7+nlog7=(c+1)nlog7=O(nlog7)O(n2.81).注意：（1）當(dāng)n小于120時，斯特拉森矩陣乘法與普通的乘法沒有太大的區(qū)別 。（2）斯特拉森矩陣乘法的核心就是降低乘法的次數(shù)而增加加法的次數(shù)，那么是否可以使乘法由7次降低為6次呢？已經(jīng)證明7次是必須的，這一方面改進只能從更高維數(shù)如3*3，或4*4并用遞歸分治的合并方法來實現(xiàn)，現(xiàn)在可以達到o(n2.495364).一、

30、基本方法1例子：背包問題：已知有n種物品和一個容量大小為M的背包，每種物品i的容量為wi。假定將物品i的一部分xi放入背包就會得到pixi的效益，這里，0 xi1，pi0。采用怎樣的裝包方法才會使裝入背包物品的總效益最大呢？顯然，由于背包容量是M，因此，要求所有選中要裝入背包的物品總?cè)萘坎坏贸^M。如果這n件物品的總?cè)萘坎怀^M，則把所有物品裝入背包自然獲得最大效益。如果這些物品容量的和大于M，則在這種情況下該如何裝包呢？第三章貪心方法31方法概述例:考慮下列情況下的背包問題：n=3，M20， (25，24，15）, =(18,15,10)。其中的四個可行解是: （1/2,1/3,1/4） 1

31、6.5 24.25（1，2/15，0） 20 28.2（0，23，1） 20 31（0，1，12） 20 31.5在這些可行解中，如何得到最優(yōu)解，正是貪心方法要解決的問題。2、 適用條件：（1）有n個輸入；（2）它的解就由這n個輸入的某個子集組成；（3）這個子集必須滿足一定的約束條件-可行解；（4）可行解一般不止一個，但是要求的是最優(yōu)解即使目標函數(shù)取得極值的解。 3有關(guān)概念（1） 約束條件：把子集必須滿足的基本條件稱為約束條件。（2） 可行解：把滿足約束條件的子集稱為該問題的可行解。（3） 目標函數(shù)：（可行解一般來說是不唯一的）為了衡量可行解的優(yōu)劣，事先也給出了一定的標準，這些標準一般以用函數(shù)

32、形式給出，這些函數(shù)稱為目標函數(shù)。（4） 最優(yōu)解：那些使目標函數(shù)取極值（極大或極?。┑目尚薪?，稱為最優(yōu)解。4基本方法： 貪心方法是一種改進了的分級處理方法。它首先根據(jù)題意，選取一種量度標準。然后按這種量度標準對這n個輸入排序，并按序一次輸入一個量。如果這個輸入和當(dāng)前已構(gòu)成在這種量度意義下的部分最優(yōu)解加在一起不能產(chǎn)生一個可行解，則不把此輸入加到這部分解中。這種能夠得到某種量度意義下的最優(yōu)解的分級處理方法稱為貪心方法。注意：對于一個給定的問題，往往可能有好幾種量度標準(貪心準則)。選擇能產(chǎn)生問題最優(yōu)解的最優(yōu)量度標準是使用貪心法設(shè)計求解的核心問題。二、貪心方法的算法設(shè)計模式GREEDY（A，n）/An

33、 包含n個輸入/1 solution /將解向量solution初始化為空/2 for i1 to n do3 xSELECT（A）/按最優(yōu)量度標準在A中選擇一個輸入4 if FEASIBLE（solution，x） then solutionUNION（solution，x） return（solution） 三、設(shè)計要點： 選擇能產(chǎn)生問題最優(yōu)解的最優(yōu)量度標準是使用貪心法設(shè)計求解的核心問題。3.2 背包問題一、問題的描述 背包問題：已知有n種物品和一個容量為M的背包，每種物品i的容量為wi，效益為pi ，假定將物品i的一部分xi放入背包就會得到pixi的效益，這里，0=xi0 ,wi0, 0

34、 in M背包的容量n物品種類wi第i物品的容量pi第i種物品價值 顯然，滿足約束條件的任一集合 是一個可行解，使目標函數(shù)取最大值的可行解是最優(yōu)解。例31考慮下列情況下的背包問題：n=3，M20，（pl，p2，p3）（25，24，15），（w1，w2，w3）=(18,15,10)。其中的四個可行解是:（x1，x2，x3） （12，13，14） 16.5 24.25（1，2/15，0） 20 28.2（0，23，1） 20 31（0，1，12） 20 31.5在這四個可行解中，第個解的效益值最大。下面將可看到，這個解是背包問題在這一情況下的最優(yōu)解。二、問題的分析 為了獲取背包問題的最優(yōu)解，必須要

35、把物品放滿背包。由于可以只放物品i的一部分到背包中，因此這一要求是可以達到的。如果用貪心策略來求解背包問題則正如31節(jié)中所說的一樣，首先要選出最優(yōu)的量度標準。以下不妨分三種情況進行分析：(1) 取效益值作為量度標準。 即每裝入一件物品就使背包獲得最大可能的效益值增量。在這種量度標準下的貪心方法就是按效益值的非增次序?qū)⑽锲芬患诺奖嘲腥ァＨ绻诳紤]中的物品放不進去，則可只取其一部分來裝滿背包。量度標準選取此種選擇策略得到的解，總效益值是28.2。它是一個次優(yōu)解。由此例可知，按物品效益值的非增次序裝包不能得到最優(yōu)解。 為什么上述貪心策略不能獲得最優(yōu)解呢？原因在于，背包可用容量消耗過快。由此，

36、很自然地啟發(fā)我們用容量作為量度，讓背包容量盡可能慢地被消耗。 （2）用容量作為量度標準 在這種量度標準下的貪心方法就是按物品容量的非降次序來把物品放入背包。例3.1的解就是使用這種貪心策略得到的，它仍是一個次優(yōu)解。這種策略也只能得到次優(yōu)解，其原因在于容量雖然慢慢地被消耗，但效益值沒能迅速地增加。 以上策略也只能得到次優(yōu)解，其原因在于容量雖然慢慢地被消耗，但效益值沒能迅速地增加。這又啟發(fā)我們應(yīng)采用在效益值的增長速率和容量的消耗速率之間取得平衡的量度標準。即每裝入一件物品應(yīng)使它占用的每一單位容量獲得當(dāng)前最大的效益。三、算法設(shè)計算法3.3 背包問題的貪心算法（3） 用效益和容量的比值作為量度標準。(

37、即 ) 這就需使物品的裝入次序按 比值的非增次序來考慮，在這種策略下的量度是已裝入物品的累計效益值與所用容量之比。其量度標準是每次裝入要使累計效益值與所用容量的比值有最多的增加或最少的減?。ǖ诙魏鸵院蟮难b入可能使此比值減?。⒋素澬牟呗詰?yīng)用于例3.l的數(shù)據(jù)，得到解。Knapsack(ElemtypeW pn, ElemtypeP wn, float yn, ElemtypeW C, int n) /pn和wn分別含有按piwi，pi1wi+1排序的n件物品的效益值和容量。M是背包的容量大小，而yn是解向量/1 for i1 to n 2 do yi0;/將解向量初始化為0；3 cu C;/

38、cu是背包中剩余的空間；4 for i1 to n 5 do/依次考察下一個物品是否可以放入背包；6 if wi cu break;/物品i無法全部放入背包, 退出for循環(huán)；7 then yi1; 8 cu cu - wi;9 10 if in 11 then yi cu/wi; /不能完全裝入的物品的部分裝入量量度標準 值得指出的是：（a）如果把物品事先按效益值的非增次序或容量的非降次序分好類，再使用以上算法就可分別得到量度標準為（2）或（3）（使每次效益增量最大或使容量消耗最慢）的解。(b)該算法的解的形式為（1，.1,x，0，0）,其中x在0，1。由背包問題量度選取的研究可知，選取最優(yōu)

39、的量度標準實為用貪心方法求解問題的核心。小結(jié)：貪心方法設(shè)計步驟：找出問題的約束條件和目標函數(shù)。選取合適的量度標準。按照“貪心方法的算法設(shè)計模式”的步驟進行算法設(shè)計.四、算法分析 如果將物體事先按Pi/wi的非增次序分好類，則過程Knapsack就得出這一策略下背包問題的解。如果將物品分類的時間不算在內(nèi)，則此算法所用時間為O（n）。五、算法的證明 證明的基本思想是：把這貪心解與任一最優(yōu)解相比較，如果這兩個解不同，就去找開始不同的第一個xi，然后設(shè)法用貪心解的這個xi去代換最優(yōu)解的那個xi，并證明最優(yōu)解在分量代換前后的總效益無任何變化。反復(fù)進行這種代換，直到新產(chǎn)生的最優(yōu)解與貪心解完全一樣，從而證明

40、了貪心解是最優(yōu)解。 掌握定理31 如果p1/wl p2/w2 pn/wn。則算法GREEDYKNAPSACK對于給定的背包問題實例生成一個最優(yōu)解。證明：設(shè)X=（x1，xn）是GREEDYKNAPSACK所生成的解。如果所有的xi等于1，顯然這個解就是最優(yōu)解。于是，設(shè)j是使xj 1的最小下標。由算法可知，對于1ij，xi=1；對于jin，xi=0。對于j，0 xj1。 如果X不是一個最優(yōu)解，則必定存在一個可行解Y=(y1,y2,yn),使得 ；不失一般性，可以假定wiyi=M。設(shè)k是使得yk xk的最小下標。顯然，這樣的k必定存在。由上面的假設(shè)，可以推得ykxk。這可從三種可能發(fā)生的情況，即kj

41、分別得證明：若kj，則xk=1。因yk xk。從而ykxk。若k=j,由于wixi =M，且對于1i xk，顯然有wiyiM,與Y是可行解矛盾。若yk=xk,與假設(shè)yk xk矛盾，故ykj，則wiyiM,這是不可能的。 現(xiàn)在，假定把yk增加到xk，那末必須從（yk1，yn）中減去同樣多的量，使得所用的總?cè)萘咳允荕。這導(dǎo)致一個新的解Z=（z1，z2，,zn），其中zi=xi,1ik,且 ，因此，對于Z有：關(guān)鍵若 0時，則Y不是最優(yōu)解，此與假設(shè)矛盾，所以不可能，即 =0。當(dāng)=0時，則Z=X或ZX，則若Z=X，則pizi= piyi，由于Y是最優(yōu)解，因此Z也是最優(yōu)解，X也是最優(yōu)解。若ZX，重復(fù)上面的

42、討論，用Z代替Y，則又可求得相應(yīng)的 0，重復(fù)以上過程，直到X=Z為止，可得X為最優(yōu)解。討論：3.3帶有限期的作業(yè)排序 一、問題的描述 假定只能在一臺機器上處理n個作業(yè)，每個作業(yè)均可在單位時間內(nèi)完成；又假定每個作業(yè)i都有一個截止期限di0（它是整數(shù)），當(dāng)且僅當(dāng)作業(yè)i在它的期限截止以前被完成時，則獲得pi0的效益 ，求具有最大效益值的可行解,也就是最優(yōu)解。分析：約束條件：每個作業(yè)均要在截止期限前完成。 目標函數(shù)：例子：n=4,(p1,p2,p3,p4)=(100,10,15,20)和(d1,d2,d3,d4)=(2,1,2,1)?？尚薪?處理順序 效益值 （1） 1 100 （2） 2 10 （3

43、） 3 15 （4） 4 20 （1，2） 2，1 110 （1，3） 1，3或3，1 115（1，4） 4，1 120（2，3） 2，3 25（3，4） 4，3 35二、問題的分析 最優(yōu)量度標準：目標函數(shù)pi作為量度，即按照pi的非增次序來考慮這些作業(yè)。 使用這一量度，下一個要計入的作業(yè)將是使得在滿足所產(chǎn)生的J是一個可行解的限制條件下讓pi得到最大增加的作業(yè)。 應(yīng)用以上的量度標準：開始時J=0， 由于作業(yè)1有最大效益且J=1是一個可行解，于是把作業(yè)1計入J。下一步考慮作業(yè)4，J=1，4也是可行解。然后考慮作業(yè)3，因為1，3，4不是可行解，故作業(yè)3被舍棄。最后考慮作業(yè)2，由于1，2，4也不可行

44、，作業(yè)2被舍棄。最終所留下的是效益值為120的解J=1，4。它是這個問題的最優(yōu)解。三、算法的粗略描述 GREEDY-JOB(D,J,n)/作業(yè)按p1p2pn的次序輸入，它們的期限值Di1,1in,n1.J是在它們的截止期限前完成的作業(yè)的集合/1 J12 for i2 to n do3 if Ji的所有作業(yè)都有能在它們的截止期限前完成 then JJi4 endif5 由前面貪心方法的算法設(shè)計模式得到J是一個作業(yè)的集合，而不是調(diào)度表四、算法的證明定理3.2 以上算法所描述的貪心方法對于作業(yè)排序問題總是得到一個最優(yōu)解。 思路：J是由貪心方法所選擇的作業(yè)的集合；I是一個最優(yōu)解的作業(yè)集合。可證明J和I

45、具有相同的效益值，從而J也是最優(yōu)的。（I,J是作業(yè)的集合，而不是作業(yè)的調(diào)度表）證明：假定（1）IJ，因為若I=J，則J即為最優(yōu)解。（2）如果I J，則I就不可能是最優(yōu)的。（3）由貪心法的工作方式也排斥了J I。因此，至少存在這樣的兩個作業(yè)a和b，使得aJ且a I，bI且b J。設(shè)a是使得aJ且a I的一個具有最高效益值的作業(yè)。由貪心方法可以得出，對于在I中又不在J中的所有作業(yè)b，都有papb。這是因為若pb pa，則貪心方法會先于作業(yè)a考慮作業(yè)b并且把b計入到J中去。 設(shè)SI和SJ分別是I和J的可行調(diào)度表。（調(diào)度表與作業(yè)集的區(qū)別）(1)設(shè)i是既屬于J又屬于I的一個作業(yè),把他們調(diào)換到相同的時刻去

46、調(diào)度，且盡量將調(diào)度時間往后移。設(shè)i在SI中在t到t+1時刻被調(diào)度，而在SJ中則在t到t+1時刻被調(diào)度。如果tt，則可以將SI中t，t+1時刻所調(diào)度的那個作業(yè)（如果有的話）與i相交換。如果J中在t，t+1時刻沒有作業(yè)被調(diào)度，則將i移到t，t+1調(diào)度。所形成的這個調(diào)度表也是可行的。如果tt，則可在和SI中作類似的調(diào)換。 （2）對于I,J中不同的作業(yè)，則以J為標準，將其中不屬于I的那些作業(yè)找出，設(shè)a是這樣的作業(yè)，它在SJ 中 時刻被調(diào)度。設(shè)作業(yè)b在I中的這一時刻被調(diào)度。根據(jù)對a的選擇 在SI 的 時刻去掉作業(yè)b而去調(diào)度作業(yè)a，這就給出了一張關(guān)于作業(yè)集合I=I-ba可行的調(diào)度表。 顯然I的效益值不小于

47、I的效益值，并且I比I少一個與J不同的作業(yè)。重復(fù)使用上述的轉(zhuǎn)換，將使I能在不減效益值的情況下轉(zhuǎn)換成J，因此J也必定是最優(yōu)解，證畢。 五、算法的實現(xiàn) 考慮對于一個給定的J，如何確定它是否為可行解的問題，一個明顯的方法是檢驗J中作業(yè)的所有可能的排列。對于任一種次序排列的作業(yè)序列，判斷這些作業(yè)是否能在其限期前完成。J是作業(yè)集，不是調(diào)度表假定J中有k個作業(yè)，這就需要檢查k！個排列。對于所給出的一個排列=i1i2i3ik，由于完成作業(yè)ij（1jk）的最早時間是j，因此，只要判斷出排列中的每個作業(yè)的dijj，就可得知是一個允許的調(diào)度序列，從而J就是一個可行解。反之，如果排列中有一個dijj，則是一個行不通

48、的調(diào)度序列，因為至少作業(yè)ij不會在它的限期前完成，故必須去檢查J的另外形式的排列。事實上，對于J的可行性可以通過只檢驗J中作業(yè)的一種特殊的排列來確定，這個排列是按期限的非降次序來完成的。定理3.3 設(shè)J是k個作業(yè)的集合， =i1i2i3ik是J中作業(yè)的一種排列，它使得di1di2dik。J是一個可行解，當(dāng)且僅當(dāng)J中的作業(yè)可以按照的次序而又不違反任何一個期限的情況下來處理。(說明了什么)證明：現(xiàn)證，若J是可行解，則表示可以處理這些作業(yè)的一種允許的調(diào)度序列。由于J可行，則必存在， 使得 假設(shè)，那末，令a是使得 的最小下標。設(shè) ，顯然ba。在中將 與 相交換，因為 ，故作業(yè)可依新產(chǎn)生的排列 的次序處

49、理而不違反任何一個期限。連續(xù)使用這一方法，就可將轉(zhuǎn)換成且不違反任何一個期限。定理得證。 算法設(shè)計思路：首先將作業(yè)按照效益值的非增次序排列，然后試著將作業(yè)逐個與當(dāng)前的部分可行解合并，檢查是否可產(chǎn)生新的可行解，（注意當(dāng)前的部分可行解已經(jīng)按期限值的非降次序排列），其方法是在部分可行解中，看能否找到新作業(yè)的合適的位置，使加入了新的作業(yè)后，其期限值仍按非降次序排列，且每個作業(yè)均在其截止期限前完成。算法3.4 帶有限期和效益的單位時間的作業(yè)排序貪心算法GreedyJob(int n , int d , int &J)/d1,dn是期限值。n1。作業(yè)已按p1p2pn被排序。Ji是最優(yōu)解中的第i個作業(yè)，1ik

50、。終止時，dJi dJi+1，1ik/1k1;2d0 0;3J0 0;4J1 1;/首先將作業(yè)1插入第一個位置；5for i2 to n/按p的非增次序依次考慮剩下的作業(yè)；6 do7 rk;8 while dJr di and dJr r9 do/while循環(huán)用來確定正在考慮的作業(yè)可能要插入的位置；10rr - 1; 體現(xiàn)了量度標準11 12if dJrdi and di r/判斷此作業(yè)是否可以插入J；13then14 for j k to r+1 /j是遞減的15 do/將第k到第r+1個作業(yè)依次后移一位以插入新的作業(yè)；16 Jj + 1 Jj;17 18Jr + 1 i;/將作業(yè)插入位置

51、r+1；19k k + 1;/記入J的作業(yè)數(shù)加1;20 21 22return k;/返回記入J中的作業(yè)數(shù)。？七、一種更快的實現(xiàn) 通過使用不相交集合的UNION與FIND算法以及使用一個不同的方法來確定部分解的可行性，可以把JS的計算時間由O（n2）降低到數(shù)量級相當(dāng)接近于O(n)。 六、時間復(fù)雜性分析 經(jīng)過分析知道，算法JS所需要的總時間是O（sn）。由于sn (s為包含在解中的作業(yè)數(shù))，因此JS的最壞計算時間為O（n2）。 分析：該方法較前方法的不同之處在于如何確定部分解的可行性方面，兩者的量度標準是一樣的。其方法是：如果J是作業(yè)的可行子集，那么可以使用下述規(guī)則來確定這些作業(yè)中的每一個作業(yè)的

52、處理時間：若還沒給作業(yè)i分配處理時間，則分配給它時間片1, ，其中應(yīng)盡量取大且時間片1, 是空的。此規(guī)則就是盡可能推遲對作業(yè)的處理。于是，在將作業(yè)一個一個地裝配到J中時，就不必為接納新作業(yè)而去移動J中那些已分配了時間片的作業(yè)。如果正被考慮的新作業(yè)不存在像上面那樣定義的 ，這個作業(yè)就不能計入J。例33 設(shè)n=5,(p1,p5)=(20,15,10,5,1)和(d1, ,d5)=(2,2,1,3,3) 。使用上述可行性規(guī)則，得J 已分配的時間片 正被考慮的作業(yè) 動作 無 1 分配1,21 1,2 2 分配0,11,2 0,1,1,2 3 不適合,舍棄1,2 0,1,1,2 4 分配2,3 1,2,

53、4 0,1,1,2,2,3 5 舍棄最優(yōu)解是J=1,2,4。設(shè)計思想：（1）只考慮時間片1，b，其中b=minn,maxdj（2）作出一些以期限值為元素的集合，且使得同一集合中的元素都有一個當(dāng)前共同可用的最接近的空時間片。（3）用F(i)表示期限為i的作業(yè)當(dāng)前最接近的空時間片ni，初始時， F(i)=i 且有b+1個集合與b+1個期限值相對應(yīng)。（4）p(i) :i為根時，表示樹中結(jié)點數(shù)的負值， i不為根時，表示i 的父結(jié)點。 初始時： p(i)= -1（5）若要調(diào)度具有期限值是d的作業(yè)，則去找包含期限值min(n,d)的那個根，若根為j且只要F(j) 0,則F(j) 是最接近的空時間片，在使用

54、完此時間片后，其根為 j的集合與包含期限值F(j) 1的集合合并。核心 在算法FasterJob中調(diào)用了過程Union和Find，其算法分別描述如下描述如下：算法Union(i,j)的概略描述：Union(int i,int j)1 x Parent(i) + Parent(j);/計算兩棵樹的總結(jié)點數(shù)；4 if Parent(i) Parent(j) /注意這里比較的是兩個負數(shù)；5then/樹i的結(jié)點數(shù)比j的少,則把i連到以j為根的樹上；6 Parent(i) j7 Parent(j) x;8 9else/樹j的結(jié)點數(shù)比i的少；11 Parent(j) i12 Parent(i) x;13

55、此算法的功能是合并根為i,j的兩個集合.函數(shù)Find(i)算法描述如下：Find(i)1ji;2while Parent(j)0/尋找根結(jié)點j；3do jParent(j);4ki;5while kj 6 do/使用壓縮規(guī)則，壓縮結(jié)點i到其根結(jié)點之間的路徑上的結(jié)點；7 tParent(k);8 Parent(k)j;9 kt;10 11return j;/返回根結(jié)點。一、適用條件 多階段決策過程 實際問題中,常有這樣一類活動,它們的活動過程可以分為若干個階段，而且在任一階段i后的行為都依賴于i階段的過程狀態(tài)，而與i階段之前的過程如何達到這種狀態(tài)的方式無關(guān)。當(dāng)各個階段決策確定后，就組成了一個決策

56、序列，因而也就確定了整個過程的一條活動路線。這種把一個問題看作是一個前后關(guān)聯(lián)的具有鏈狀結(jié)構(gòu)的多階段過程被稱為多階段決策過程. 滿足最優(yōu)性原理 第四章 動態(tài)規(guī)劃 41 方法概述狀態(tài)0 決策1 決策2 決策n 狀態(tài)n狀態(tài)1狀態(tài)n-1狀態(tài)2 最優(yōu)性原理：過程的最優(yōu)決策序列具有如下性質(zhì)：無論過程的初始狀態(tài)和初始決策是什么，其余的決策都必須相對于初始決策所產(chǎn)生的狀態(tài)構(gòu)成一個最優(yōu)決策序列。 如果所求解問題的最優(yōu)性原理成立，則說明用動態(tài)規(guī)劃方法有可能解決該問題。因為只有滿足最優(yōu)性原理，才能使用各階段的遞推公式求解。二、最優(yōu)性原理 在多階段決策過程的每一階段，都可能有多種可供選擇的決策，但必須從中選取一種決策

57、。一旦各個階段的決策選定之后，就構(gòu)成了解決這一問題的一個決策序列，決策序列不同，所導(dǎo)致的問題的結(jié)果也不同。動態(tài)規(guī)劃的目標就是要在所有容許選擇的決策序列中選取一個會獲得問題最優(yōu)解的決策序列，即最優(yōu)決策序列。 三、動態(tài)規(guī)劃方法的關(guān)鍵 關(guān)鍵在于獲取各階段間的遞推關(guān)系式。 四、可解決的問題 最短路徑問題、設(shè)備更新問題、資源分配問題、貨物裝 運排序、生產(chǎn)計劃等。五、應(yīng)用實例分析例4.1 多段圖問題多段圖G=（V，E）是一個有向圖。它具有如下特性：圖中的結(jié)點被劃分成k2個不相交的集合Vi,1ik，其中V1和Vk分別有一個結(jié)點s（源點）和t（匯點）。圖中所有的邊(u,v)均具有如下性質(zhì)：若uVi，則vVi+

58、1，1ik-1,且每條邊(u,v)均附有成本c(u,v)。從s到t的一條路徑成本是這條路徑上邊的成本和。多段圖問題是求由s到t的最小成本路徑。每個集合Vi定義圖中的一段。由于E的約束，每條從s到t的路徑都是從第1段開始，在第k段終止。圖4.1所示的就是一個5段圖。123456789101112ts97322271111815435642546 對于每一條由s到t的路徑，可以把它看成在k-2個階段中作出的某個決策序列的相應(yīng)結(jié)果。第i次決策就是確定Vi+1中的哪個結(jié)點在這條路徑上，1ik-2。下面證明最優(yōu)性原理對多段圖成立。假設(shè)s,v2,v3,vk-1,t是一條由s到t的最短路徑，還假定從源點s（

59、初始狀態(tài)）開始，已作出了到結(jié)點v2的決策（初始決策），因此v2就是初始決策所產(chǎn)生的狀態(tài)。如果把v2看成是原問題的一個子問題的初始狀態(tài)，解這個子問題就是找出一條由v2到t的最短路徑。這條最短路徑顯然是v2,v3,vk-1,t，如若不 然，設(shè)v2,q3,qk-1,t是一條由v2到t的更短路徑，則s,v2,q3,qk-1,t是一條比路徑s,v2,v3,vk-1,t更短的由s到t的路徑。與假設(shè)矛盾，故最優(yōu)性原理成立。因此它為使用動態(tài)規(guī)劃方法來解決多段圖問題提供了可能。六、動態(tài)規(guī)劃方法的形式化描述 能用動態(tài)規(guī)劃求解的問題的最優(yōu)化決策序列可表示如下。設(shè)S0是問題的初始狀態(tài)。假定需要作n次決策xi, 1in

60、。設(shè)X1=r1,1,r1,2,r1,p1是X1的可能決策值的集合，而S1, 1是在選取決策值r1,j1以后所產(chǎn)生的狀態(tài), 1j1p1。又設(shè) 是相應(yīng)于狀態(tài)S1,j1的最優(yōu)決策序列。那末，相應(yīng)于S0的最優(yōu)決策序列就是 |1j1p1中最優(yōu)的序列，記為OPT = 。如果已作了k-1次決策，1k-1n。設(shè)x1,xk-1的最優(yōu)決策值是r1,rk-1，它們所產(chǎn)生的狀態(tài)為S1,Sk-1。又設(shè) 是xk的可能值的集合。 是選取決策值 后所產(chǎn)生的狀態(tài)，1jkpk。 是相應(yīng)于 的最優(yōu)決策序列。因此，相應(yīng)于Sk-1的最優(yōu)決策序列是 。于是相應(yīng)于S0的最優(yōu)決策序列為r1,rk-1，rk， 。七、兩種求解方法（1）向前處理