算法概念介紹及舉例說明.ppt

《算法概念介紹及舉例說明.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《算法概念介紹及舉例說明.ppt（197頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1、例子:給定兩個(gè)正整數(shù)m和n,求它們的最大公因子 算法:歐幾里德算法 輸入:正整數(shù)m、n 輸出：m和n的最大公因子,第一章 算法引論,1.1 算法的基本概念,一、什么是算法及其與程序的區(qū)別,S1:保證m=n,如果m

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

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

4、計(jì)求解某個(gè)具體問題的一系列步驟，并且這些步驟可以通過計(jì)算機(jī)的各種操作來實(shí)現(xiàn)。,輸入：城市數(shù)目n;費(fèi)用矩陣C=(cij)n*n 輸出：旅行路線TOUR;最小費(fèi)用MIN,Salesman (n) i 1;tour0;min while i<=(n-1)! do pPHRMUTI(n-1,i); // PHRMUTI(n-1,i)是生成1到n-1的第i個(gè)排列的子過程 cost(T(p))EFP(c,T(p))； // EFP(c,T)是由費(fèi)用矩陣c及路線T(p)所算得的總費(fèi)用 if cost(T(p))

5、 ii+1; print min, tour,四、算法的正確性 可以分兩步考慮: (1)算法的終止性； (2)算法的每一步是否都正確 算法的正確性并不蘊(yùn)涵算法的有效性。,,五、算法分析 時(shí)間復(fù)雜性和空間復(fù)雜性 以上貨郎擔(dān)問題的時(shí)間復(fù)雜性是：O(n!),六、文檔的編制,,（1）注釋 （2）算法的流程圖 （3）對(duì)輸入/輸出的要求 （4）正確性證明 （5）時(shí)間復(fù)雜性和空間復(fù)雜性的分析,,二、算法分析的要點(diǎn) 1、確定使用的運(yùn)算和執(zhí)行這些運(yùn)算所用的時(shí)間。 運(yùn)算分為兩類 (1)基本運(yùn)算；(2)“組合”運(yùn)算由基本運(yùn)算組成。,,1.3 算法分析,一、算法分析的原因 1、為了對(duì)算法的某些特定的輸

6、入，估計(jì)或限界該算法所需要的空間和運(yùn)行時(shí)間。 2、為了建立衡量算法優(yōu)劣的標(biāo)準(zhǔn)，用以比較同一問題的不同算法。,時(shí)間是固定量,時(shí)間是變化量,,2、確定能反映出算法在各種情況下工作的數(shù)據(jù)集構(gòu)造出能產(chǎn)生最好、最壞和有代表性情況的數(shù)據(jù)配置。,,三、算法分析的兩個(gè)階段,1、事前分析求出該算法的一個(gè)時(shí)間限界函數(shù)。,,2、事后測試收集此算法的執(zhí)行時(shí)間和實(shí)際占用空間的統(tǒng)計(jì)資料。,,就算法分析而言，一條語句的數(shù)量級(jí)指的是執(zhí)行它的頻率，而一個(gè)算法的數(shù)量級(jí)則指的是它所有語句執(zhí)行頻率的和。 確定一個(gè)算法的數(shù)量級(jí)是十分重要的，它在本質(zhì)上反映了一個(gè)算法所需要的計(jì)算時(shí)間。,,四、計(jì)算時(shí)間的漸進(jìn)表示 假設(shè)某種算法的計(jì)算時(shí)間

7、是f(n),其中變量n可以是輸入或輸出量，也可以是兩者之和，還可以是它們之一的某種測度（例如，數(shù)組的維數(shù)，圖的邊數(shù)等等）。g(n)是在事前分析中確定的某個(gè)形式很簡單的函數(shù)，例如，nm,logn,2n,,n!等。它是獨(dú)立于機(jī)器和語言的函數(shù)，而f(n)則與機(jī)器和語言有關(guān)。,定義1.2 如果存在兩個(gè)正常數(shù)c和n0，對(duì)于所有的nn0， |f(n)|c|g(n)| 則記作f(n)=(g(n)). 因此，當(dāng)說一個(gè)算法具有O(g(n))的計(jì)算時(shí)間時(shí)，指的是如果此算法用n值不變的同一類數(shù)據(jù)在某臺(tái)機(jī)器上運(yùn)行時(shí)，所用的時(shí)間總是小于|g(n))|的一個(gè)常數(shù)倍。所以g(n)是計(jì)算時(shí)間f(n)的一個(gè)上界函數(shù)，

8、f(n)的數(shù)量級(jí)就是g(n)。,定義1.1：算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個(gè)函數(shù)f(n)，算法的時(shí)間度量記作:T(n)O(f(n)) 隨著問題規(guī)模n的增大，算法執(zhí)行時(shí)間的增長率和f(n)的增長率相同，稱作算法的漸近時(shí)間復(fù)雜度，簡稱時(shí)間復(fù)雜度。,證明：取n0=1,當(dāng)n=n0時(shí)，利用A(n)的定義和 一個(gè)簡單的不等式，有 取c=|am|+.+|a0| 定理得證. 事實(shí)上，只要將n0取得足夠大，可以證明只要c是比|am|大的任意一個(gè)常數(shù)，此定理都成立。,定理1.1 若A(n)=amnm++ a1n+ a0是一個(gè)m次多項(xiàng)式，則A(n)=O(nm)。,此定理表明，變量n的固定階數(shù)為m的任

9、一多項(xiàng)式，與此多項(xiàng)式的最高階nm同階，因此計(jì)算時(shí)間為m階的多項(xiàng)式的算法，其時(shí)間都可用O(nm).例如，若一個(gè)算法有數(shù)量級(jí)為c1nm1, c2nm2,, cknmk 的k個(gè)語句，則此算法的數(shù)量級(jí)就是 c1nm1 +c2nm2++cknmk 由定理1.1，它等于O(nm),其中m=maxmi|1i k,例子：假設(shè)有解決同一個(gè)問題的兩個(gè)算法，它們有n個(gè)輸 入，分別要求n2和nlogn次運(yùn)算。,定義1.3 如果存在兩個(gè)正常數(shù)c和n0,對(duì)于所有n n0,有 |f(n)| c|g(n)| 則記為f(n)=(g(n))。 定義1.4 如果存在兩個(gè)正常數(shù)c1 ,c2,和n0,對(duì)于所有的n n0,

10、有 則記為f(n)=(g(n))。 一個(gè)算法的f(n)=(g(n))意味著該算法在最好和最壞情況下的計(jì)算時(shí)間就一個(gè)常因子范圍內(nèi)而言是相同的。,五、算法分類（按時(shí)間） 多項(xiàng)式時(shí)間算法：凡可用多項(xiàng)式來對(duì)其計(jì)算時(shí)間界限的算法。 指數(shù)時(shí)間算法：計(jì)算時(shí)間用指數(shù)函數(shù)界限的算法。,以下六種計(jì)算時(shí)間的多項(xiàng)式時(shí)間算法是最為常見的，其關(guān)系為： O(1)< O(logn)< O(n)< O(nlogn)< O(n2)< O(n3) 指數(shù)時(shí)間算法一般有O(2n)、O(n!) 和O(nn)等。其關(guān)系為 O(2n)< O(n!)< O(nn),注意：當(dāng)數(shù)據(jù)集的規(guī)模很大時(shí)，要在現(xiàn)代計(jì)算機(jī)上運(yùn)行具有比O（nlogn

11、)復(fù)雜度高的算法往往是很困難的。,六、最好、最壞和平均情況 以順序檢索為例,第二章 分治法 2.1 方法概述,一、基本思想 1、設(shè)計(jì)思想：將整個(gè)問題分成若干個(gè)小問題后,分而治之。 2、適用條件： 問題規(guī)模很大； 可以分成若干個(gè)與原問題性質(zhì)相同的子問題，并可以分別求解。 子問題的解通過整合可以得到原問題的解。 3、設(shè)計(jì)方法：使用遞歸策略。,4、 設(shè)計(jì)步驟 (1)分解：將原問題分解為若干個(gè)相互獨(dú)立、與原問題形式相同的子問題； (2)求解：若子問題容易被解決則直接解，否則再繼續(xù)分解為更小的子問題，直到容易解決； (3)合并：將已求解的各個(gè)子問題的解，逐步合并以得到原問題的解。,二、分治法的算法

12、設(shè)計(jì)模式 Divide-and-Conquer(n) //n為問題規(guī)模 1if n <= n0 //n0 為可解子問題的規(guī)模 2then 3 4 解子問題 5 return( 子問題的解 ) 6 4for i 1 to k //分解為k個(gè)子問題5 do yi Divide-and-Conquer(|Pi|)//遞歸解決Pi6 T MERGE(y1,y2,...,yk) //合并子問題 7 return T,,遞歸過程,注意：分治法可以用遞歸實(shí)現(xiàn)，也可以用循環(huán)實(shí)現(xiàn)。,其中：其中|P|表示問題P的規(guī)模；n0為一閾值，表示當(dāng)問題P的規(guī)模不超過n0時(shí)，問題已容易直接解出，不必再繼續(xù)分解。算法MERGE

13、(y1,y2,...,yk)是該分治法中的合并子算法，用于將P的子問題P1 ,P2 ,...,Pk的相應(yīng)的解y1,y2,...,yk合并為P的解。,時(shí)間復(fù)雜性分析：,其中，T(n)是輸入規(guī)模為n的Divide-and-Conquer的時(shí)間，g(n)是對(duì)足夠小的輸入規(guī)模能直接計(jì)算出答案的時(shí)間，f(n)是MERGE的時(shí)間。,倘若所分成的兩個(gè)子問題的輸入規(guī)模大致相等，則Divide-and-Conquer總的計(jì)算時(shí)間可以用下面的遞推關(guān)系來表示： (n足夠小) (否則),,,2.2 二 分 檢 索,一、問題描述 已知一個(gè)按非降次序排列的元素表a1,a

14、2,an,要求判定某給定元素x是否在該表中出現(xiàn)。若是，則找出x在表中的位置，并將此下標(biāo)值賦給變量j；若非，則將j置成0。,,,,,對(duì)于I2，通過比較x和ak容易得到解決。如果x= ak,則j=k且不需再對(duì)I1和I3求解；否則，在I2 子問題的j=0，此時(shí)若xak,只有I3留待求解，在I1子問題中的j=0。在ak作了比較之后，留待求解的問題（如果有的話）可以再一次使用分治法來求解。如果對(duì)所求解的問題（或子問題）所選的下標(biāo)k都是其元素的中間元素下標(biāo)（例如，對(duì)于I，k=(n+1)/2）,則所產(chǎn)生的算法就是通常所說的二分檢索。,三、二分檢索算法 算法2.3 二分檢索 //給定一個(gè)按非降次序排列的元素

15、數(shù)組A(1:n),n1,判 斷x是否出現(xiàn)。若是，置j，使得x=A(j),若非，j=0// BINSEARCH(A,n,x) 1 low 1 2 high n,,3 while lowhigh，數(shù)組A中沒有找到x，返回j0 4 do 5 6 //取處于low和high之間的中間值 7 if x==Amid//找到值為x的元素，mid即為其下標(biāo)，返回mid 8 thenreturn mid 9 else if x < Amid//如果x < Amid，則x可能位于low與mid之間， 10 //否則x可能位于mid與high之間 11 then high mid - 1 12 else

16、 low mid + 1 13 14 retrun 0,非遞歸形式,,,四、算法的證明 假定在A9中順序存放著以下9個(gè)元素：-15，-6，0，7，9，23，54，82，101。要求檢索下列x的值：101，-14和82是否在A中出現(xiàn)。,,從算法中可以看到,所有的運(yùn)算基本上都是進(jìn)行比較和數(shù)據(jù)傳送，前兩條是賦值語句,頻率計(jì)數(shù)均為1。在while循環(huán)中，我們集中考慮循環(huán)的次數(shù)，而其他運(yùn)算的頻率計(jì)數(shù)顯然與這些元素比較運(yùn)算的頻率計(jì)數(shù)具有相同的數(shù)量級(jí)，找到這九個(gè)元素中的每一個(gè)所需的元素循環(huán)的次數(shù)如下：,五、時(shí)間復(fù)雜性分析 (1)

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

18、 4 1 3 2 3 4,成功檢索的比較次數(shù)是25/92.77。 不成功檢索有10種，如果x

19、素比較，用圓形結(jié)點(diǎn)表示，在以元素比較為基礎(chǔ)的二分檢索中，每個(gè)內(nèi)結(jié)點(diǎn)存放一個(gè)mid值； （3） 外結(jié)點(diǎn)用方形結(jié)點(diǎn)表示，在二分檢索中它表示一次不成功的檢索； （4）x如果在A 中出現(xiàn)，則算法就在一個(gè)圓形結(jié)點(diǎn)處結(jié)束，該結(jié)點(diǎn)將指出x在A中的下標(biāo)； x如果不在A 中出現(xiàn)，則算法就在一個(gè)方形結(jié)點(diǎn)處結(jié)束，如圖所示。,證明：考察以n個(gè)結(jié)點(diǎn)描述BINSRCH執(zhí)行過程的二元比較樹，所有成功檢索都在內(nèi)部結(jié)點(diǎn)處結(jié)束，而所有不成功的檢索都在外部結(jié)點(diǎn)處結(jié)束。由于2k-1n2k ，因此所有的內(nèi)部結(jié)點(diǎn)在1，2，3，，k級(jí)，而所有的外部結(jié)點(diǎn)在k,k+1級(jí)（注意：根在1 級(jí)）。即是，成功檢索在i級(jí)終止所需要的元素比較次數(shù)是i,而

20、不成功檢索在i級(jí)外部結(jié)點(diǎn)終止的元素比較數(shù)是i-1.因此定理得證。,定理2.1 若n在區(qū)域2k-1, 2k)中，則對(duì)于一次成功的檢索，BINSRCH 至多作k次比較，而對(duì)于一次不成功的檢索，或者作k-1次比較或者作k次比較。,由此：最壞情況下的成功檢索和不成功檢索的計(jì)算時(shí)間是（logn）,最好情況下的成功檢索在根結(jié)點(diǎn)處到達(dá)，時(shí)間是（1），而最好情況的不成功檢索要logn次元素比較，所以時(shí)間是（logn）。由于外部節(jié)點(diǎn)都在k和k+1級(jí)，因此，每種不成功檢索的時(shí)間都是（logn），故平均情況下不成功檢索的計(jì)算時(shí)間是（logn）。,E=I+2n (1) 令S(n)是成功檢索的平均比較數(shù)，則

21、 S（n)=I/n+1 (2),平均情況下成功檢索的時(shí)間復(fù)雜性分析： 設(shè)根到所有內(nèi)部結(jié)點(diǎn)的距離之和稱為內(nèi)部路徑長度I，由根到所有外部結(jié)點(diǎn)的距離之和稱為外部路徑長度E，可以證明：,為什么要+1,令U（n)是不成功檢索的平均情況比較數(shù)，而任何一個(gè)外部結(jié)點(diǎn)所需要的比較數(shù)是由根到該結(jié)點(diǎn)路徑的長度，由此得： U(n)=E/(n+1) (3) 利用（1）-（3）可以得到： S(n)=(1+1/n)U(n)-1 因此：平均情況下成功檢索的時(shí)間復(fù)雜性為： (log n)。,五、一種二分檢索的變形BINSEARCH1。 BINSEARCH1的while循環(huán)中x和Ami

22、d之間只用作一次比較。,BINSEARCH1(A,n,x,j) 1 low 1 2 high n+1 3 while low < high 4do 5 6 mid (low + high) / 2 7 if (x < Amid)//在循環(huán)中只比較一次 8 then high mid 9else lowmid 10 11 if x == Alow 12 then j low//x出現(xiàn) 13 else j=0 // x不出現(xiàn) 14 return j,BINSEARCH和BINSEARCH1相比較可看出，對(duì)于任何一種成功的檢索，BINSEARCH1平均要比BINSEARCH多作

23、 次比較。BINSEARCH1的最好、平均和最壞情況時(shí)間對(duì)于成功和不成功的檢索都是 。,,,,,六、以比較為基礎(chǔ)檢索的時(shí)間下界 1. 什么是以比較為基礎(chǔ)的檢索算法 檢索一給定元素x是否在A中出現(xiàn)。如果只允許進(jìn)行元素間的比較而不允許對(duì)它們實(shí)施運(yùn)算，在這種條件下所設(shè)計(jì)的算法都稱為是以比較為基礎(chǔ)的算法 。 2. 二分檢索是以比較為基礎(chǔ)的檢索算法中最壞情況下的最優(yōu)算法.,一、直接求最大、最小元素 算法2.5 直接找最大和最小元素 maxmin(A,n) //將A(1:n)中的最大元素置于max，最小元素置于min// 1 max A1 2 min A1;3 for i 2 to n 4 do 5

24、6 if max Ai 7 then min Ai 8 ,2.3 找最大和最小元素,時(shí)間復(fù)雜性分析： STRAITMAXMIN在最好、平均和最壞情況下均需要作2(n-1)次元素比較。,如果稍做修改： 用下面的語句代替for循環(huán)中的語句： if A(i)max then maxA(i) else if A(i)

25、、用分治法求最大、最小元素 1、問題分析 使用分治策略設(shè)計(jì)是將任一實(shí)例I=(n，A(1)，，A(n))分成一些較小的實(shí)例來處理，例如，可以把分成兩個(gè)這樣的實(shí)例I1=(n/2，A(1)，，A(n/2))和 =(n-n/2,A(n/2+1),,A(n))。如果()和（）是中的最大和最小元素，則（）等于（）和（）中的大者，（）等于（）和（）中的小者。如果只包含一個(gè)元素，則不需要作任何分割直接就可得到其解。,,2.算法 算法.遞歸求取最大和最小元素 float An; maxmin（i, j, fmax, fmin）//最大和最小元素賦給fmax和fmin 1 if i == j 2 then 3

26、 4 fmax Ai; 5 fmin Ai; ,,,7 else if i == j-1 8 then if Ai

27、min rmin 28 then fmin rmin; 29 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 47,,,?,討論：以上算法是否是最優(yōu)的？ 1）遞歸帶來的額外的空間開銷。 2）當(dāng)元素A(i)和A(j)的比較時(shí)間i和j的比較時(shí)間相差不大時(shí)，過程maxmin并不可取。,因此：當(dāng)n是的冪時(shí)，3n/2-2是最好，平均及最壞情況的比較數(shù),和直接算法的比較數(shù)n相比，它少了。 可以證明，任何

28、一種以元素比較為基礎(chǔ)的找最大和最小元素的算法，其元素比較下界均為 次。,為說明問題，假設(shè)元素比較與i和j間的比較時(shí)間相同，又設(shè)maxmin的頻率計(jì)數(shù)為C(n) ，n=2k，,k是某個(gè)正整數(shù)，并且對(duì)前兩種情況，用ij-1來代替i==j和i==j-1這兩次比較，這樣，只用對(duì)i和j-1作一次比較就足以實(shí)現(xiàn)被修改過的語句。于是maxmin頻率計(jì)數(shù) C(n)= n=2 n2,,?,解此關(guān)系式可得 C(n)=2C(n/2)+3=4C(n/4)+6+3 =2k-1C(2)+ =2k+3*2k-1-3 =5n/2-3,,分析：STRA

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

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

31、11+B22) ，Q=(A21+A22)B11 R=A11(B12-B22)， S=A22(B21-B11) T=(A11+A12)B22 ，U=(A21-A11)(B11+B12) V=(A12-A22)(B21+B22) 然后用8個(gè)加減法算出這些 Cij C11=P+S-T+V C12=R+T C21=Q+S C22=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/

32、4)2an2+(7/4)an2+an2 =an2(1+(7/4)+(7/4)2+.+(7/4)k-1)+7kT(1)cn2(7/4)logn+7logn(1),因?yàn)椋?logn =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時(shí)，斯特拉森矩陣乘法與普通的乘法沒有太大的區(qū)別 。 （2）斯特拉森矩陣乘法的核心就是降低乘法的次數(shù)而增加加法的次數(shù)，那么是否可以使乘法由

33、7次降低為6次呢？已經(jīng)證明7次是必須的，這一方面改進(jìn)只能從更高維數(shù)如3*3，或4*4并用遞歸分治的合并方法來實(shí)現(xiàn)，現(xiàn)在可以達(dá)到o(n2.495364).,一、基本方法 1例子： 背包問題：已知有n種物品和一個(gè)容量大小為M的背包，每種物品i的容量為wi。假定將物品i的一部分xi放入背包就會(huì)得到pixi的效益，這里，0 xi1，pi0。采用怎樣的裝包方法才會(huì)使裝入背包物品的總效益最大呢？顯然，由于背包容量是M，因此，要求所有選中要裝入背包的物品總?cè)萘坎坏贸^M。如果這n件物品的總?cè)萘坎怀^M，則把所有物品裝入背包自然獲得最大效益。 如果這些物品容量的和大于M，則在這種情況下該如何裝包呢？,,第三章

34、貪心方法 31方法概述,例:考慮下列情況下的背包問題：n=3，M20， (25，24，15）, =(18,15,10)。其中的四個(gè)可行解是: （1/2,1/3,1/4） 16.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個(gè)輸入； （2）它的解就由這n個(gè)輸入的某個(gè)子集組成； （3）這個(gè)子集必須滿足一定的約束條件---可行解； （4）可行解一般不止一個(gè)，但是要求的是最優(yōu)解即使目標(biāo)函數(shù)取

35、得極值的解。,3有關(guān)概念 （1） 約束條件：把子集必須滿足的基本條件稱為約束條件。 （2） 可行解：把滿足約束條件的子集稱為該問題的可行解。 （3） 目標(biāo)函數(shù)：（可行解一般來說是不唯一的）為了衡量可行解的優(yōu)劣，事先也給出了一定的標(biāo)準(zhǔn)，這些標(biāo)準(zhǔn)一般以用函數(shù)形式給出，這些函數(shù)稱為目標(biāo)函數(shù)。 （4） 最優(yōu)解：那些使目標(biāo)函數(shù)取極值（極大或極?。┑目尚薪?，稱為最優(yōu)解。,,,,二、貪心方法的算法設(shè)計(jì)模式 GREEDY（A，n） //An 包含n個(gè)輸入// 1 solution //將解向量solution初始化為空// 2 for i1 to n do 3 xSELECT（A）//按最優(yōu)量度標(biāo)準(zhǔn)在A中選擇

36、一個(gè)輸入 4 if FEASIBLE（solution，x） then solutionUNION（solution，x） return（solution）,三、設(shè)計(jì)要點(diǎn)： 選擇能產(chǎn)生問題最優(yōu)解的最優(yōu)量度標(biāo)準(zhǔn)是使用貪心法設(shè)計(jì)求解的核心問題。,3.2 背包問題 一、問題的描述 背包問題：已知有n種物品和一個(gè)容量為M的背包，每種物品i的容量為wi，效益為pi ，假定將物品i的一部分xi放入背包就會(huì)得到pixi的效益，這里，0<=xi<=1，pi0。采用怎樣的裝包方法才會(huì)使裝入背包物品的總效益最大呢？顯然，由于背包容量是M，因此，要求所有選中要裝入背包的物品總?cè)萘坎坏贸^M。如果這n件物品

37、的總?cè)萘坎怀^M，則把所有物品裝入背包自然獲得最大效益。如果這些物品容量的和大于M，則在這種情況下該如何裝包呢？,由以上敘述，可將這個(gè)問題形式描述如下： 約束條件： 目標(biāo)函數(shù)： 其中：0 xi 1 ,pi0 ,wi0, 0 in M背包的容量 n物品種類 wi第i物品的容量 pi第i種物品價(jià)值 顯然，滿足約束條件的任一集合 是 一個(gè)可行解，使目標(biāo)函數(shù)取最大值的可行解是最優(yōu)解。,,例31考慮下列情況下的背包問題：n=3，M20，（pl，p2，p3）（25，24，15），（w1，w2，w3）=(18,15,10)。其中的四個(gè)可行解是: （x1，x2，x3） （

38、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 在這四個(gè)可行解中，第個(gè)解的效益值最大。下面將可看到，這個(gè)解是背包問題在這一情況下的最優(yōu)解。,,二、問題的分析 為了獲取背包問題的最優(yōu)解，必須要把物品放滿背包。由于可以只放物品i的一部分到背包中，因此這一要求是可以達(dá)到的。如果用貪心策略來求解背包問題則正如31節(jié)中所說的一樣，首先要選出最優(yōu)的量度標(biāo)準(zhǔn)。 以下不妨分三種情況進(jìn)行分析： (1) 取效益值作為量度標(biāo)準(zhǔn)。 即每裝入一件物品就使背包獲得最大可能的效益值增量。在這

39、種量度標(biāo)準(zhǔn)下的貪心方法就是按效益值的非增次序?qū)⑽锲芬患诺奖嘲腥ァＨ绻诳紤]中的物品放不進(jìn)去，則可只取其一部分來裝滿背包。,量度標(biāo)準(zhǔn)選取,,此種選擇策略得到的解，總效益值是28.2。它是一個(gè)次優(yōu)解。由此例可知，按物品效益值的非增次序裝包不能得到最優(yōu)解。 為什么上述貪心策略不能獲得最優(yōu)解呢？原因在于，背包可用容量消耗過快。由此，很自然地啟發(fā)我們用容量作為量度，讓背包容量盡可能慢地被消耗。,,（2）用容量作為量度標(biāo)準(zhǔn) 在這種量度標(biāo)準(zhǔn)下的貪心方法就是按物品容量的非降次序來把物品放入背包。例3.1的解就是使用這種貪心策略得到的，它仍是一個(gè)次優(yōu)解。這種策略也只能得到次優(yōu)解，其原因在于容量雖然慢

40、慢地被消耗，但效益值沒能迅速地增加。 以上策略也只能得到次優(yōu)解，其原因在于容量雖然慢慢地被消耗，但效益值沒能迅速地增加。這又啟發(fā)我們應(yīng)采用在效益值的增長速率和容量的消耗速率之間取得平衡的量度標(biāo)準(zhǔn)。即每裝入一件物品應(yīng)使它占用的每一單位容量獲得當(dāng)前最大的效益。,,三、算法設(shè)計(jì) 算法3.3 背包問題的貪心算法,（3） 用效益和容量的比值作為量度標(biāo)準(zhǔn)。(即 ) 這就需使物品的裝入次序按 比值的非增次序來考慮，在這種策略下的量度是已裝入物品的累計(jì)效益值與所用容量之比。其量度標(biāo)準(zhǔn)是每次裝入要使累計(jì)效益值與所用容量的比值有最多的增加或最少的減?。ǖ诙魏鸵院蟮难b入可能使此比值減?。?。將此貪心策略應(yīng)

41、用于例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;//cu是背包中剩余的空間； 4 for i1 to n 5 do//依次考察下一個(gè)物品是否可以放入背包； 6 if wi cu break;//物品i無法全部放入背包, 退出for循環(huán)； 7 then yi1; 8

42、 cu cu - wi; 9 10 if in 11 then yi cu/wi; //不能完全裝入的物品的部分裝入量,量度標(biāo)準(zhǔn),,,值得指出的是：（a）如果把物品事先按效益值的非增次序或容量的非降次序分好類，再使用以上算法就可分別得到量度標(biāo)準(zhǔn)為（2）或（3）（使每次效益增量最大或使容量消耗最慢）的解。 (b)該算法的解的形式為（1，.1,x，0，0）,其中x在0，1。由背包問題量度選取的研究可知，選取最優(yōu)的量度標(biāo)準(zhǔn)實(shí)為用貪心方法求解問題的核心。,,小結(jié)：貪心方法設(shè)計(jì)步驟： 找出問題的約束條件和目標(biāo)函數(shù)。 選取合適的量度標(biāo)準(zhǔn)。 按照“貪心方法的算法設(shè)計(jì)模式”的步驟進(jìn)行算法設(shè)計(jì).,四、算法分

43、析 如果將物體事先按Pi/wi的非增次序分好類，則過程Knapsack就得出這一策略下背包問題的解。如果將物品分類的時(shí)間不算在內(nèi)，則此算法所用時(shí)間為O（n）。,五、算法的證明 證明的基本思想是：把這貪心解與任一最優(yōu)解相比較，如果這兩個(gè)解不同，就去找開始不同的第一個(gè)xi，然后設(shè)法用貪心解的這個(gè)xi去代換最優(yōu)解的那個(gè)xi，并證明最優(yōu)解在分量代換前后的總效益無任何變化。反復(fù)進(jìn)行這種代換，直到新產(chǎn)生的最優(yōu)解與貪心解完全一樣，從而證明了貪心解是最優(yōu)解。,,,掌握,定理31 如果p1/wl p2/w2 pn/wn。則算法GREEDYKNAPSACK對(duì)于給定的背包問題實(shí)例生成一個(gè)最優(yōu)解。 證明：設(shè)X=（

44、x1，，xn）是GREEDYKNAPSACK所生成的解。如果所有的xi等于1，顯然這個(gè)解就是最優(yōu)解。于是，設(shè)j是使xj 1的最小下標(biāo)。由算法可知，對(duì)于1i

45、yk1，，yn）中減去同樣多的量，使得所用的總?cè)萘咳允荕。,這導(dǎo)致一個(gè)新的解Z=（z1，z2，,zn），其中zi=xi,1ik,且 ，因此，對(duì)于Z有：,,若 0時(shí)，則Y不是最優(yōu)解，此與假設(shè)矛盾，所以不可能，即 =0。 當(dāng)=0時(shí)，則Z=X或ZX，則 若Z=X，則pizi= piyi，由于Y是最優(yōu)解，因此Z也是最優(yōu)解，X也是最優(yōu)解。 若ZX，重復(fù)上面的討論，用Z代替Y，則又可求得相應(yīng)的 0，重復(fù)以上過程，直到X=Z為止，可得X為最優(yōu)解。,,,討論：,3.3帶有限期的作業(yè)排序 一、問題的描述 假定只能在一臺(tái)機(jī)器上處理n個(gè)作業(yè)，每個(gè)作業(yè)均可在單位時(shí)間內(nèi)完成；又假定每個(gè)作業(yè)i都有一個(gè)截止期限di

46、0（它是整數(shù)），當(dāng)且僅當(dāng)作業(yè)i在它的期限截止以前被完成時(shí)，則獲得pi0的效益 ，求具有最大效益值的可行解,也就是最優(yōu)解。 分析：約束條件：每個(gè)作業(yè)均要在截止期限前完成。 目標(biāo)函數(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） 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

47、 25 （3，4） 4，3 35,二、問題的分析 最優(yōu)量度標(biāo)準(zhǔn)：目標(biāo)函數(shù)pi作為量度，即按照pi的非增次序來考慮這些作業(yè)。 使用這一量度，下一個(gè)要計(jì)入的作業(yè)將是使得在滿足所產(chǎn)生的J是一個(gè)可行解的限制條件下讓pi得到最大增加的作業(yè)。,應(yīng)用以上的量度標(biāo)準(zhǔn)：開始時(shí)J=0， 由于作業(yè)1有最大效益且J=1是一個(gè)可行解，于是把作業(yè)1計(jì)入J。下一步考慮作業(yè)4，J=1，4也是可行解。然后考慮作業(yè)3，因?yàn)?，3，4不是可行解，故作業(yè)3被舍棄。最后考慮作業(yè)2，由于1，2，4也不可行，作業(yè)2被舍棄。最終所留下的是效益值為120的解J=1，4。它是這個(gè)問題的最優(yōu)解。,三、算法的粗略描述 GREEDY-J

48、OB(D,J,n) //作業(yè)按p1p2pn的次序輸入，它們的期限值Di1,1in,n1.J是在它們的截止期限前完成的作業(yè)的集合// 1 J1 2 for i2 to n do 3 if Ji的所有作業(yè)都有能在它們的截止期限前完成 then JJi 4 endif 5 ,由前面貪心方法的算法設(shè)計(jì)模式得到,J是一個(gè)作業(yè)的集合，而不是調(diào)度表,,,四、算法的證明 定理3.2 以上算法所描述的貪心方法對(duì)于作業(yè)排序問題總是得到一個(gè)最優(yōu)解。,思路：J是由貪心方法所選擇的作業(yè)的集合；I是一個(gè)最優(yōu)解的作業(yè)集合?？勺C明J和I具有相同的效益值，從而J也是最優(yōu)的。（I,J是作業(yè)的集合，而不是作業(yè)的調(diào)度表）,

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

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

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

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

53、。連續(xù)使用這一方法， 就可將轉(zhuǎn)換成且不違反任何一個(gè)期限。定理得證。,,算法設(shè)計(jì)思路：首先將作業(yè)按照效益值的非增次序排列，然后試著將作業(yè)逐個(gè)與當(dāng)前的部分可行解合并，檢查是否可產(chǎn)生新的可行解，（注意當(dāng)前的部分可行解已經(jīng)按期限值的非降次序排列），其方法是在部分可行解中，看能否找到新作業(yè)的合適的位置，使加入了新的作業(yè)后，其期限值仍按非降次序排列，且每個(gè)作業(yè)均在其截止期限前完成。,算法3.4 帶有限期和效益的單位時(shí)間的作業(yè)排序貪心算法 GreedyJob(int n , int d , int ,體現(xiàn)了量度標(biāo)準(zhǔn),,,,11 12if dJrdi and di r//判斷此作業(yè)是否可以插入J； 13th

54、en 14 for j k to r+1 //j是遞減的 15 do//將第k到第r+1個(gè)作業(yè)依次后移一位以插入新的作業(yè)； 16 Jj + 1 Jj; 17 18Jr + 1 i;//將作業(yè)插入位置r+1； 19k k + 1;//記入J的作業(yè)數(shù)加1; 20 21 22return k;//返回記入J中的作業(yè)數(shù)。,七、一種更快的實(shí)現(xiàn) 通過使用不相交集合的UNION與FIND算法以及使用一個(gè)不同的方法來確定部分解的可行性，可以把JS的計(jì)算時(shí)間由O（n2）降低到數(shù)量級(jí)相當(dāng)接近于O(n)。,六、時(shí)間復(fù)雜性分析 經(jīng)過分析知道，算法JS所需要的總時(shí)間是O（sn）。由于sn (s為包含在解中的

55、作業(yè)數(shù))，因此JS的最壞計(jì)算時(shí)間為O（n2）。,分析：該方法較前方法的不同之處在于如何確定部分解的可行性方面，兩者的量度標(biāo)準(zhǔn)是一樣的。其方法是：如果J是作業(yè)的可行子集，那么可以使用下述規(guī)則來確定這些作業(yè)中的每一個(gè)作業(yè)的處理時(shí)間：若還沒給作業(yè)i分配處理時(shí)間，則分配給它時(shí)間片1, ，其中應(yīng)盡量取大且時(shí)間片1, 是空的。此規(guī)則就是盡可能推遲對(duì)作業(yè)的處理。于是，在將作業(yè)一個(gè)一個(gè)地裝配到J中時(shí)，就不必為接納新作業(yè)而去移動(dòng)J中那些已分配了時(shí)間片的作業(yè)。如果正被考慮的新作業(yè)不存在像上面那樣定義的 ，這個(gè)作業(yè)就不能計(jì)入J。,例33 設(shè)n=5,(p1,,p5)=(20,15,10,5,1)和(d1, ,d5)=

56、(2,2,1,3,3) 。使用上述可行性規(guī)則，得 J 已分配的時(shí)間片 正被考慮的作業(yè) 動(dòng)作 無 1 分配1,2 1 1,2 2 分配0,1 1,2 0,1,1,2 3 不適合,舍棄 1,2 0,1,1,2 4 分配2,3 1,2,4 0,1,1,2,2,3 5 舍棄 最優(yōu)解是J=1,2,4。,,設(shè)計(jì)思想： （1）只考慮時(shí)間片1，b，其中b=minn,maxdj （2）作出一些以期限值為元素的集合，且使得同一集合中的元素都有一個(gè)當(dāng)前共同可用的最接近的空時(shí)間片。

57、（3）用F(i)表示期限為i的作業(yè)當(dāng)前最接近的空時(shí)間片ni， 初始時(shí)， F(i)=i 且有b+1個(gè)集合與b+1個(gè)期限值相對(duì)應(yīng)。 （4）p(i) :i為根時(shí)，表示樹中結(jié)點(diǎn)數(shù)的負(fù)值， i不為根時(shí)，表示i 的父結(jié)點(diǎn)。 初始時(shí)： p(i)= -1,,,,（5）若要調(diào)度具有期限值是d的作業(yè)，則去找包含期限值min(n,d)的那個(gè)根，若根為j且只要F(j) 0,則F(j) 是最接近的空時(shí)間片，在使用完此時(shí)間片后，其根為 j的集合與包含期限值F(j) 1的集合合并。,核心,,,,,在算法FasterJob中調(diào)用了過程Union和Find，其算法分別描述如下描述如下： 算法Union(i,j)的概略

58、描述：,Union(int i,int j) 1 x Parent(i) + Parent(j);//計(jì)算兩棵樹的總結(jié)點(diǎn)數(shù)； 4 if Parent(i) Parent(j) //注意這里比較的是兩個(gè)負(fù)數(shù)； 5then//樹i的結(jié)點(diǎn)數(shù)比j的少,則把i連到以j為根的樹上； 6 Parent(i) j 7 Parent(j) x; 8 9else//樹j的結(jié)點(diǎn)數(shù)比i的少； 11 Parent(j) i 12 Parent(i) x; 13,此算法的功能是合并根為i,j的兩個(gè)集合.,函數(shù)Find(i)算法描述如下：,Find(i) 1ji; 2while Parent(j)0//尋找根結(jié)點(diǎn)j；

59、3do jParent(j); 4ki; 5while kj 6 do//使用壓縮規(guī)則，壓縮結(jié)點(diǎn)i到其根結(jié)點(diǎn)之間的路徑上的結(jié)點(diǎn)； 7 tParent(k); 8 Parent(k)j; 9 kt; 10 11return j;//返回根結(jié)點(diǎn)。,一、適用條件 多階段決策過程 實(shí)際問題中,常有這樣一類活動(dòng),它們的活動(dòng)過程可以分為若干個(gè)階段，而且在任一階段i后的行為都依賴于i階段的過程狀態(tài)，而與i階段之前的過程如何達(dá)到這種狀態(tài)的方式無關(guān)。當(dāng)各個(gè)階段決策確定后，就組成了一個(gè)決策序列，因而也就確定了整個(gè)過程的一條活動(dòng)路線。這種把一個(gè)問題看作是一個(gè)前后關(guān)聯(lián)的具有鏈狀結(jié)構(gòu)的多階段過程被稱為多階段決策過程

60、. 滿足最優(yōu)性原理,第四章 動(dòng)態(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)性原理 在多階段決策過程的每一階段，都可能有多種可供選擇的決策，但必須從中選取一種決策。一旦各個(gè)階段的決策選定之后，就構(gòu)成了解決這一問題的一個(gè)決策序列，決策序列不同，所導(dǎo)致的問題的結(jié)果也不同。動(dòng)態(tài)規(guī)劃的目標(biāo)就是要在所有容許選擇的決策序列中選取一個(gè)會(huì)獲得問題最優(yōu)解的決策序列，即最優(yōu)決策序列。,三、動(dòng)態(tài)規(guī)劃方法的關(guān)鍵 關(guān)鍵在于獲取各階段間的遞推關(guān)系式。 四、可解決的問題 最短路徑問題、設(shè)備更新問題、資源分配問題、貨物裝 運(yùn)排序

61、、生產(chǎn)計(jì)劃等。 五、應(yīng)用實(shí)例分析,例4.1 多段圖問題多段圖G=（V，E）是一個(gè)有向圖。它具有如下特性：圖中的結(jié)點(diǎn)被劃分成k2個(gè)不相交的集合Vi,1ik，其中V1和Vk分別有一個(gè)結(jié)點(diǎn)s（源點(diǎn)）和t（匯點(diǎn)）。圖中所有的邊(u,v)均具有如下性質(zhì)：若uVi，則vVi+1，1ik-1,且每條邊(u,v)均附有成本c(u,v)。從s到t的一條路徑成本是這條路徑上邊的成本和。多段圖問題是求由s到t的最小成本路徑。每個(gè)集合Vi定義圖中的一段。由于E的約束，每條從s到t的路徑都是從第1段開始，在第k段終止。圖4.1所示的就是一個(gè)5段圖。,4,6,,,,,對(duì)于每一條由s到t的路徑，可以把它看成在k-2個(gè)階段中

62、作出的某個(gè)決策序列的相應(yīng)結(jié)果。第i次決策就是確定Vi+1中的哪個(gè)結(jié)點(diǎn)在這條路徑上，1ik-2。 下面證明最優(yōu)性原理對(duì)多段圖成立。假設(shè)s,v2,v3,,vk-1,t是一條由s到t的最短路徑，還假定從源點(diǎn)s（初始狀態(tài)）開始，已作出了到結(jié)點(diǎn)v2的決策（初始決策），因此v2就是初始決策所產(chǎn)生的狀態(tài)。如果把v2看成是原問題的一個(gè)子問題的初始狀態(tài)，解這個(gè)子問題就是找出一條由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è)

63、矛盾，故最優(yōu)性原理成立。因此它為使用動(dòng)態(tài)規(guī)劃方法來解決多段圖問題提供了可能。,六、動(dòng)態(tài)規(guī)劃方法的形式化描述 能用動(dòng)態(tài)規(guī)劃求解的問題的最優(yōu)化決策序列可表示如下。設(shè)S0是問題的初始狀態(tài)。假定需要作n次決策xi, 1in。設(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,,

64、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）向前處理法：從最后階段開始，以逐步向前遞推的方式列出求前一階段決策值的遞推關(guān)系式，即根據(jù)xi+1,,xn的那些最優(yōu)決策序列來列出求取xi決策值的關(guān)系式，即：xi=f(xi+1,xi+2,,xn),例子：在k段圖問題中，設(shè) 又設(shè) 是由 到t的最短路徑，則s到t的最短路徑是 中最短的那條路徑。若

65、設(shè) 是s 到t的一條最短路徑， 是路徑上的中間結(jié)點(diǎn)，則 就應(yīng)分別是由s到vi和由vi到t的最短路徑。,（2）向后處理法：根據(jù)x1,,xi-1的那些最優(yōu)決策序列列出求xi的遞推關(guān)系式。即：xi=f(x1,x2,,xi-1) .,下例是說明向前處理法在多段圖中的使用,見黑板,小結(jié)：無論是使用向前處理法還是使用向后處理法，都將所有子問題的最優(yōu)解保存下來。這樣做的目的是為了便于逐步遞推得到原問題的最優(yōu)解并避免對(duì)它們的重復(fù)計(jì)算。由枚舉法可知，不同決策序列的總數(shù)就其所取決策值而言是指數(shù)級(jí)的（如果決策序列由n次決策構(gòu)成，而每次決策有p種選擇，那末可能的決策序列就有pn個(gè)），而動(dòng)態(tài)規(guī)

66、劃算法則可能有多項(xiàng)式的復(fù)雜度。,八、動(dòng)態(tài)規(guī)劃算法的求解步驟,(1)段化； (2)自頂向下的分析，測試問題本身是否滿足最優(yōu)化原理； (3)從底向上的計(jì)算，實(shí)現(xiàn)動(dòng)態(tài)規(guī)劃過程。,,一、問題的描述 例4.1給出了多段圖的定義，并且指出一個(gè)k段圖的每一條由源點(diǎn)s到匯點(diǎn)t的路徑可以看成是在k-2個(gè)階段中作出的某個(gè)決策序列的相應(yīng)結(jié)果。第i次決策就是確定Vi+1中的哪個(gè)結(jié)點(diǎn)在這條路徑上，1ik-2。進(jìn)而還證明了最優(yōu)性原理對(duì)多段圖成立，因此用動(dòng)態(tài)規(guī)劃方法有可能找到由s到t的最小成本路徑。,4.2 多段圖,二、問題分析：使用向前處理法 求各階段的遞推關(guān)系式： （1） （2）若E，有COST(k-1,j)=c(j,t)，若 E， 有COST(k-1,j)=， 設(shè)： P(i,j) 是一條從Vi中的結(jié)點(diǎn)j到匯點(diǎn)t的最小成本路徑， COST(i,j)是這條路的成本。,關(guān)鍵,,例子：對(duì)圖4.1的5段圖給出具體實(shí)現(xiàn)這一系列計(jì)算的步驟： COST(3,6)=min6+COST(4,9),5+COST(4,10)=7 COST(3,7)=min4+COST(4,9),3+COST(4,10)=5 COST(