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

《算法概念介紹及舉例說明.ppt》由會員分享，可在線閱讀，更多相關《算法概念介紹及舉例說明.ppt（197頁珍藏版）》請在裝配圖網上搜索。

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

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

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

4、計求解某個具體問題的一系列步驟，并且這些步驟可以通過計算機的各種操作來實現(xiàn)。,輸入：城市數(shù)目n;費用矩陣C=(cij)n*n 輸出：旅行路線TOUR;最小費用MIN,Salesman (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))

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

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

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

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

9、一多項式，與此多項式的最高階nm同階，因此計算時間為m階的多項式的算法，其時間都可用O(nm).例如，若一個算法有數(shù)量級為c1nm1, c2nm2,, cknmk 的k個語句，則此算法的數(shù)量級就是 c1nm1 +c2nm2++cknmk 由定理1.1，它等于O(nm),其中m=maxmi|1i k,例子：假設有解決同一個問題的兩個算法，它們有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,

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

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

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

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

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

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即為其下標，返回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個元素：-15，-6，0，7，9，23，54，82，101。要求檢索下列x的值：101，-14和82是否在A中出現(xiàn)。,,從算法中可以看到,所有的運算基本上都是進行比較和數(shù)據(jù)傳送，前兩條是賦值語句,頻率計數(shù)均為1。在while循環(huán)中，我們集中考慮循環(huán)的次數(shù)，而其他運算的頻率計數(shù)顯然與這些元素比較運算的頻率計數(shù)具有相同的數(shù)量級，找到這九個元素中的每一個所需的元素循環(huán)的次數(shù)如下：,五、時間復雜性分析 (1)

17、 (log n) (log n) (log n) (log n) (log n),分析：對于A中的n個數(shù)，如果x在A中出現(xiàn)，則是成功檢索，所以成功檢索共有n種情況，而不成功的檢索，x將取n+1個區(qū)間中的不同值，因此在計算出x在這2n+1種情況下的執(zhí)行時間后，就可以求出其在各種情況下的時間復雜性了。,例子：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、素比較，用圓形結點表示，在以元素比較為基礎的二分檢索中，每個內結點存放一個mid值； （3） 外結點用方形結點表示，在二分檢索中它表示一次不成功的檢索； （4）x如果在A 中出現(xiàn)，則算法就在一個圓形結點處結束，該結點將指出x在A中的下標； x如果不在A 中出現(xiàn)，則算法就在一個方形結點處結束，如圖所示。,證明：考察以n個結點描述BINSRCH執(zhí)行過程的二元比較樹，所有成功檢索都在內部結點處結束，而所有不成功的檢索都在外部結點處結束。由于2k-1n2k ，因此所有的內部結點在1，2，3，，k級，而所有的外部結點在k,k+1級（注意：根在1 級）。即是，成功檢索在i級終止所需要的元素比較次數(shù)是i,而

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

21、 S（n)=I/n+1 (2),平均情況下成功檢索的時間復雜性分析： 設根到所有內部結點的距離之和稱為內部路徑長度I，由根到所有外部結點的距離之和稱為外部路徑長度E，可以證明：,為什么要+1,令U（n)是不成功檢索的平均情況比較數(shù)，而任何一個外部結點所需要的比較數(shù)是由根到該結點路徑的長度，由此得： U(n)=E/(n+1) (3) 利用（1）-（3）可以得到： S(n)=(1+1/n)U(n)-1 因此：平均情況下成功檢索的時間復雜性為： (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相比較可看出，對于任何一種成功的檢索，BINSEARCH1平均要比BINSEARCH多作

23、 次比較。BINSEARCH1的最好、平均和最壞情況時間對于成功和不成功的檢索都是 。,,,,,六、以比較為基礎檢索的時間下界 1. 什么是以比較為基礎的檢索算法 檢索一給定元素x是否在A中出現(xiàn)。如果只允許進行元素間的比較而不允許對它們實施運算，在這種條件下所設計的算法都稱為是以比較為基礎的算法 。 2. 二分檢索是以比較為基礎的檢索算法中最壞情況下的最優(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 找最大和最小元素,時間復雜性分析： STRAITMAXMIN在最好、平均和最壞情況下均需要作2(n-1)次元素比較。,如果稍做修改： 用下面的語句代替for循環(huán)中的語句： if A(i)max then maxA(i) else if A(i)

25、、用分治法求最大、最小元素 1、問題分析 使用分治策略設計是將任一實例I=(n，A(1)，，A(n))分成一些較小的實例來處理，例如，可以把分成兩個這樣的實例I1=(n/2，A(1)，，A(n/2))和 =(n-n/2,A(n/2+1),,A(n))。如果()和（）是中的最大和最小元素，則（）等于（）和（）中的大者，（）等于（）和（）中的小者。如果只包含一個元素，則不需要作任何分割直接就可得到其解。,,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 ,,,遞歸調用,,利用層次分析法分析此遞歸調用過程。（要求掌握）,考慮如下例子： A：（1） （2） （3） （4） （5） （6） （7） （8） （9） 22 13 -5 -8 15 60 17 31 47,,,?,討論：以上算法是否是最優(yōu)的？ 1）遞歸帶來的額外的空間開銷。 2）當元素A(i)和A(j)的比較時間i和j的比較時間相差不大時，過程maxmin并不可取。,因此：當n是的冪時，3n/2-2是最好，平均及最壞情況的比較數(shù),和直接算法的比較數(shù)n相比，它少了。 可以證明，任何

28、一種以元素比較為基礎的找最大和最小元素的算法，其元素比較下界均為 次。,為說明問題，假設元素比較與i和j間的比較時間相同，又設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,,?,解此關系式可得 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)(包括實現(xiàn)for循環(huán)所要的比較)。盡管它比5n/2-3大些，但由于遞歸算法中i，j，fmax，fmin進出棧所帶來的開銷，因此maxmin在這種情況下反而比STRAITMAXMIN還要慢些。,根據(jù)以上分析可以得出結論：如果A的元素間的比較遠比整數(shù)變量的比較代價昂貴，則分治方法產生效率較高（實際上是最優(yōu)）的算法；反之，就得到一個效率較低的程序。因此，分治策略只能看成是一個較好的然而并不總是能成功的算法設計指導。,2.4斯特拉森矩陣乘法,一、一般的矩陣乘法 設C=A*B, 則利用常規(guī)方法計算，所需時間是,二、分治法求矩陣乘法 設n=2k，則可以將兩個矩陣的乘法

30、做如下劃分：,其中：C11=A11B11+A12B21 C12=A11B12+A12B21 C21=A21B11+A22B21 C22=A21B12+A22B22 可以證明: C=AB=,三.斯特拉森矩陣乘法 斯特拉森矩陣乘法的設計思想:增加加法的次數(shù),減少乘法的次數(shù).,如果分塊矩陣的級大于2,則可以繼續(xù)將這些子矩陣分成更小的方陣,直至每個方陣只含有一個元素,以至可以直接計算其乘積. 時間復雜性分析: n 2 n2 則T(n)=O(n3),,先用七個乘法和十個加（減）法來算出以下的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個加減法算出這些 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),因為：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）當n小于120時，斯特拉森矩陣乘法與普通的乘法沒有太大的區(qū)別 。 （2）斯特拉森矩陣乘法的核心就是降低乘法的次數(shù)而增加加法的次數(shù)，那么是否可以使乘法由

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

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

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

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

37、的總容量不超過M，則把所有物品裝入背包自然獲得最大效益。如果這些物品容量的和大于M，則在這種情況下該如何裝包呢？,由以上敘述，可將這個問題形式描述如下： 約束條件： 目標函數(shù)： 其中：0 xi 1 ,pi0 ,wi0, 0 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） （

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

39、種量度標準下的貪心方法就是按效益值的非增次序將物品一件件放到背包中去。如果正在考慮中的物品放不進去，則可只取其一部分來裝滿背包。,量度標準選取,,此種選擇策略得到的解，總效益值是28.2。它是一個次優(yōu)解。由此例可知，按物品效益值的非增次序裝包不能得到最優(yōu)解。 為什么上述貪心策略不能獲得最優(yōu)解呢？原因在于，背包可用容量消耗過快。由此，很自然地啟發(fā)我們用容量作為量度，讓背包容量盡可能慢地被消耗。,,（2）用容量作為量度標準 在這種量度標準下的貪心方法就是按物品容量的非降次序來把物品放入背包。例3.1的解就是使用這種貪心策略得到的，它仍是一個次優(yōu)解。這種策略也只能得到次優(yōu)解，其原因在于容量雖然慢

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

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//依次考察下一個物品是否可以放入背包； 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; //不能完全裝入的物品的部分裝入量,量度標準,,,值得指出的是：（a）如果把物品事先按效益值的非增次序或容量的非降次序分好類，再使用以上算法就可分別得到量度標準為（2）或（3）（使每次效益增量最大或使容量消耗最慢）的解。 (b)該算法的解的形式為（1，.1,x，0，0）,其中x在0，1。由背包問題量度選取的研究可知，選取最優(yōu)的量度標準實為用貪心方法求解問題的核心。,,小結：貪心方法設計步驟： 找出問題的約束條件和目標函數(shù)。 選取合適的量度標準。 按照“貪心方法的算法設計模式”的步驟進行算法設計.,四、算法分

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

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

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

46、0（它是整數(shù)），當且僅當作業(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） 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)量度標準：目標函數(shù)pi作為量度，即按照pi的非增次序來考慮這些作業(yè)。 使用這一量度，下一個要計入的作業(yè)將是使得在滿足所產生的J是一個可行解的限制條件下讓pi得到最大增加的作業(yè)。,應用以上的量度標準：開始時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也不可行，作業(yè)2被舍棄。最終所留下的是效益值為120的解J=1，4。它是這個問題的最優(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 ,由前面貪心方法的算法設計模式得到,J是一個作業(yè)的集合，而不是調度表,,,四、算法的證明 定理3.2 以上算法所描述的貪心方法對于作業(yè)排序問題總是得到一個最優(yōu)解。,思路：J是由貪心方法所選擇的作業(yè)的集合；I是一個最優(yōu)解的作業(yè)集合。可證明J和I具有相同的效益值，從而J也是最優(yōu)的。（I,J是作業(yè)的集合，而不是作業(yè)的調度表）,

49、證明：假定（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。設a是使得aJ且a I的一個具有最高效益值的作業(yè)。由貪心方法可以得出，對于在I中又不在J中的所有作業(yè)b，都有papb。這是因為若pb pa，則貪心方法會先于作業(yè)a考慮作業(yè)b并且把b計入到J中去。,設SI和SJ分別是I和J的可行調度表。（調度表與作業(yè)集的區(qū)別） (1)設i是既屬于J又屬于I的一個作業(yè),把他們調換到相同的時刻去調度，且盡量將調度時間往后移。,設i在SI中在t到t+1時刻被調度，

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

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

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

53、。連續(xù)使用這一方法， 就可將轉換成且不違反任何一個期限。定理得證。,,算法設計思路：首先將作業(yè)按照效益值的非增次序排列，然后試著將作業(yè)逐個與當前的部分可行解合并，檢查是否可產生新的可行解，（注意當前的部分可行解已經按期限值的非降次序排列），其方法是在部分可行解中，看能否找到新作業(yè)的合適的位置，使加入了新的作業(yè)后，其期限值仍按非降次序排列，且每個作業(yè)均在其截止期限前完成。,算法3.4 帶有限期和效益的單位時間的作業(yè)排序貪心算法 GreedyJob(int n , int d , int ,體現(xià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個作業(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ù)。,七、一種更快的實現(xiàn) 通過使用不相交集合的UNION與FIND算法以及使用一個不同的方法來確定部分解的可行性，可以把JS的計算時間由O（n2）降低到數(shù)量級相當接近于O(n)。,六、時間復雜性分析 經過分析知道，算法JS所需要的總時間是O（sn）。由于sn (s為包含在解中的

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

56、(2,2,1,3,3) 。使用上述可行性規(guī)則，得 J 已分配的時間片 正被考慮的作業(yè) 動作 無 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。,,設計思想： （1）只考慮時間片1，b，其中b=minn,maxdj （2）作出一些以期限值為元素的集合，且使得同一集合中的元素都有一個當前共同可用的最接近的空時間片。

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

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

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

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

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

62、作出的某個決策序列的相應結果。第i次決策就是確定Vi+1中的哪個結點在這條路徑上，1ik-2。 下面證明最優(yōu)性原理對多段圖成立。假設s,v2,v3,,vk-1,t是一條由s到t的最短路徑，還假定從源點s（初始狀態(tài)）開始，已作出了到結點v2的決策（初始決策），因此v2就是初始決策所產生的狀態(tài)。如果把v2看成是原問題的一個子問題的初始狀態(tài)，解這個子問題就是找出一條由v2到t的最短路徑。這條最短路徑顯然是v2,v3,,vk-1,t，如若不 然，設v2,q3,,qk-1,t是一條由v2到t的更短路徑，則s,v2,q3,,qk-1,t是一條比路徑s,v2,v3,,vk-1,t更短的由s到t的路徑。與假設

63、矛盾，故最優(yōu)性原理成立。因此它為使用動態(tài)規(guī)劃方法來解決多段圖問題提供了可能。,六、動態(tài)規(guī)劃方法的形式化描述 能用動態(tài)規(guī)劃求解的問題的最優(yōu)化決策序列可表示如下。設S0是問題的初始狀態(tài)。假定需要作n次決策xi, 1in。設X1=r1,1,r1,2,,r1,p1是X1的可能決策值的集合，而S1, 1是在選取決策值r1,j1以后所產生的狀態(tài), 1j1p1。又設 是相應于狀態(tài)S1,j1的最優(yōu)決策序列。那末，相應于S0的最優(yōu)決策序列就是 |1j1p1中最優(yōu)的序列，記為OPT = 。如果已作了k-1次決策，1k-1n。設x1,,xk-1的最優(yōu)決策值是r1,,rk-1，它們所產生的狀態(tài)為S1,,

64、Sk-1。又設,是xk的可能值的集合。 是選取決策值 后所產生的狀態(tài)，1jkpk。 是相應于 的最優(yōu)決策序列。因此，相應于Sk-1的最優(yōu)決策序列是 。于是相應于S0的最優(yōu)決策序列為r1,,rk-1，rk， 。,,七、兩種求解方法,（1）向前處理法：從最后階段開始，以逐步向前遞推的方式列出求前一階段決策值的遞推關系式，即根據(jù)xi+1,,xn的那些最優(yōu)決策序列來列出求取xi決策值的關系式，即：xi=f(xi+1,xi+2,,xn),例子：在k段圖問題中，設 又設 是由 到t的最短路徑，則s到t的最短路徑是 中最短的那條路徑。若

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

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