算法概念介紹及舉例說(shuō)明.ppt

上傳人:max****ui 文檔編號(hào):14938509 上傳時(shí)間:2020-08-01 格式:PPT 頁(yè)數(shù):197 大?。?.46MB
收藏 版權(quán)申訴 舉報(bào) 下載
算法概念介紹及舉例說(shuō)明.ppt_第1頁(yè)
第1頁(yè) / 共197頁(yè)
算法概念介紹及舉例說(shuō)明.ppt_第2頁(yè)
第2頁(yè) / 共197頁(yè)
算法概念介紹及舉例說(shuō)明.ppt_第3頁(yè)
第3頁(yè) / 共197頁(yè)

下載文檔到電腦,查找使用更方便

14.9 積分

下載資源

還剩頁(yè)未讀,繼續(xù)閱讀

資源描述:

《算法概念介紹及舉例說(shuō)明.ppt》由會(huì)員分享,可在線閱讀,更多相關(guān)《算法概念介紹及舉例說(shuō)明.ppt(197頁(yè)珍藏版)》請(qǐng)?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ū)別: 程序:與某種語(yǔ)言有關(guān),能直接在機(jī)器上運(yùn)行。 算法:與特定的語(yǔ)言無(wú)關(guān),可用任何語(yǔ)言實(shí)現(xiàn) ,甚至可以用自然語(yǔ)言實(shí)現(xiàn),但是一般為了避免二義性,本書(shū)采用類C語(yǔ)言描述。,一個(gè)算法總是在執(zhí)行了有窮步驟的運(yùn)算后終止,否則就是一個(gè)計(jì)算過(guò)程。,有窮性與有效性的關(guān)系:,三、評(píng)價(jià)算法的標(biāo)準(zhǔn),有窮性是對(duì)算法的基本要求,如果一個(gè)算法要能使用,必須具有有效性。有效性是指算法在規(guī)定的時(shí)間里終止。,時(shí)間復(fù)雜性和空間復(fù)雜性,1.2 算法設(shè)計(jì)的步驟,一、問(wèn)題的描述,例:貨郎擔(dān)問(wèn)題 設(shè)售貨員在一天內(nèi)要到5個(gè)城市去推銷貨物,已知從一個(gè)城市到其他城市的費(fèi)用,求總費(fèi)用最少

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

4、計(jì)求解某個(gè)具體問(wèn)題的一系列步驟,并且這些步驟可以通過(guò)計(jì)算機(jī)的各種操作來(lái)實(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è)排列的子過(guò)程 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)問(wè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),用以比較同一問(wèn)題的不同算法。,時(shí)間是固定量,時(shí)間是變化量,,2、確定能反映出算法在各種情況下工作的數(shù)據(jù)集構(gòu)造出能產(chǎn)生最好、最壞和有代表性情況的數(shù)據(jù)配置。,,三、算法分析的兩個(gè)階段,1、事前分析求出該算法的一個(gè)時(shí)間限界函數(shù)。,,2、事后測(cè)試收集此算法的執(zhí)行時(shí)間和實(shí)際占用空間的統(tǒng)計(jì)資料。,,就算法分析而言,一條語(yǔ)句的數(shù)量級(jí)指的是執(zhí)行它的頻率,而一個(gè)算法的數(shù)量級(jí)則指的是它所有語(yǔ)句執(zhí)行頻率的和。 確定一個(gè)算法的數(shù)量級(jí)是十分重要的,它在本質(zhì)上反映了一個(gè)算法所需要的計(jì)算時(shí)間。,,四、計(jì)算時(shí)間的漸進(jìn)表示 假設(shè)某種算法的計(jì)算時(shí)間

7、是f(n),其中變量n可以是輸入或輸出量,也可以是兩者之和,還可以是它們之一的某種測(cè)度(例如,數(shù)組的維數(shù),圖的邊數(shù)等等)。g(n)是在事前分析中確定的某個(gè)形式很簡(jiǎn)單的函數(shù),例如,nm,logn,2n,,n!等。它是獨(dú)立于機(jī)器和語(yǔ)言的函數(shù),而f(n)則與機(jī)器和語(yǔ)言有關(guān)。,定義1.2 如果存在兩個(gè)正常數(shù)c和n0,對(duì)于所有的nn0, |f(n)|c|g(n)| 則記作f(n)=(g(n)). 因此,當(dāng)說(shuō)一個(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ù)是問(wèn)題規(guī)模n的某個(gè)函數(shù)f(n),算法的時(shí)間度量記作:T(n)O(f(n)) 隨著問(wèn)題規(guī)模n的增大,算法執(zhí)行時(shí)間的增長(zhǎng)率和f(n)的增長(zhǎng)率相同,稱作算法的漸近時(shí)間復(fù)雜度,簡(jiǎn)稱時(shí)間復(fù)雜度。,證明:取n0=1,當(dāng)n=n0時(shí),利用A(n)的定義和 一個(gè)簡(jiǎn)單的不等式,有 取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è)語(yǔ)句,則此算法的數(shù)量級(jí)就是 c1nm1 +c2nm2++cknmk 由定理1.1,它等于O(nm),其中m=maxmi|1i k,例子:假設(shè)有解決同一個(gè)問(wèn)題的兩個(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)式來(lái)對(duì)其計(jì)算時(shí)間界限的算法。 指數(shù)時(shí)間算法:計(jì)算時(shí)間用指數(shù)函數(shù)界限的算法。,以下六種計(jì)算時(shí)間的多項(xiàng)式時(shí)間算法是最為常見(jiàn)的,其關(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è)問(wèn)題分成若干個(gè)小問(wèn)題后,分而治之。 2、適用條件: 問(wèn)題規(guī)模很大; 可以分成若干個(gè)與原問(wèn)題性質(zhì)相同的子問(wèn)題,并可以分別求解。 子問(wèn)題的解通過(guò)整合可以得到原問(wèn)題的解。 3、設(shè)計(jì)方法:使用遞歸策略。,4、 設(shè)計(jì)步驟 (1)分解:將原問(wèn)題分解為若干個(gè)相互獨(dú)立、與原問(wèn)題形式相同的子問(wèn)題; (2)求解:若子問(wèn)題容易被解決則直接解,否則再繼續(xù)分解為更小的子問(wèn)題,直到容易解決; (3)合并:將已求解的各個(gè)子問(wèn)題的解,逐步合并以得到原問(wèn)題的解。,二、分治法的算法

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

13、(y1,y2,...,yk)是該分治法中的合并子算法,用于將P的子問(wèn)題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è)子問(wèn)題的輸入規(guī)模大致相等,則Divide-and-Conquer總的計(jì)算時(shí)間可以用下面的遞推關(guān)系來(lái)表示: (n足夠小) (否則),,,2.2 二 分 檢 索,一、問(wèn)題描述 已知一個(gè)按非降次序排列的元素表a1,a

14、2,an,要求判定某給定元素x是否在該表中出現(xiàn)。若是,則找出x在表中的位置,并將此下標(biāo)值賦給變量j;若非,則將j置成0。,,,,,對(duì)于I2,通過(guò)比較x和ak容易得到解決。如果x= ak,則j=k且不需再對(duì)I1和I3求解;否則,在I2 子問(wèn)題的j=0,此時(shí)若xak,只有I3留待求解,在I1子問(wèn)題中的j=0。在ak作了比較之后,留待求解的問(wèn)題(如果有的話)可以再一次使用分治法來(lái)求解。如果對(duì)所求解的問(wèn)題(或子問(wèn)題)所選的下標(biāo)k都是其元素的中間元素下標(biāo)(例如,對(duì)于I,k=(n+1)/2),則所產(chǎn)生的算法就是通常所說(shuō)的二分檢索。,三、二分檢索算法 算法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中沒(méi)有找到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ù)傳送,前兩條是賦值語(yǔ)句,頻率計(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í)行過(guò)程的二元比較樹(shù),所有成功檢索都在內(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)部路徑長(zhǎng)度I,由根到所有外部結(jié)點(diǎn)的距離之和稱為外部路徑長(zhǎng)度E,可以證明:,為什么要+1,令U(n)是不成功檢索的平均情況比較數(shù),而任何一個(gè)外部結(jié)點(diǎn)所需要的比較數(shù)是由根到該結(jié)點(diǎn)路徑的長(zhǎng)度,由此得: 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)次元素比較。,如果稍做修改: 用下面的語(yǔ)句代替for循環(huán)中的語(yǔ)句: if A(i)max then maxA(i) else if A(i)

25、、用分治法求最大、最小元素 1、問(wèn)題分析 使用分治策略設(shè)計(jì)是將任一實(shí)例I=(n,A(1),,A(n))分成一些較小的實(shí)例來(lái)處理,例如,可以把分成兩個(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)用過(guò)程。(要求掌握),考慮如下例子: A:(1) (2) (3) (4) (5) (6) (7) (8) (9) 22 13 -5 -8 15 60 17 31 47,,,?,討論:以上算法是否是最優(yōu)的? 1)遞歸帶來(lái)的額外的空間開(kāi)銷。 2)當(dāng)元素A(i)和A(j)的比較時(shí)間i和j的比較時(shí)間相差不大時(shí),過(guò)程maxmin并不可取。,因此:當(dāng)n是的冪時(shí),3n/2-2是最好,平均及最壞情況的比較數(shù),和直接算法的比較數(shù)n相比,它少了。 可以證明,任何

28、一種以元素比較為基礎(chǔ)的找最大和最小元素的算法,其元素比較下界均為 次。,為說(shuō)明問(wèn)題,假設(shè)元素比較與i和j間的比較時(shí)間相同,又設(shè)maxmin的頻率計(jì)數(shù)為C(n) ,n=2k,,k是某個(gè)正整數(shù),并且對(duì)前兩種情況,用ij-1來(lái)代替i==j和i==j-1這兩次比較,這樣,只用對(duì)i和j-1作一次比較就足以實(shí)現(xiàn)被修改過(guò)的語(yǔ)句。于是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)出棧所帶來(lái)的開(kāi)銷,因此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è)加(減)法來(lái)算出以下的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í),斯特拉森矩陣乘法與普通的乘法沒(méi)有太大的區(qū)別 。 (2)斯特拉森矩陣乘法的核心就是降低乘法的次數(shù)而增加加法的次數(shù),那么是否可以使乘法由

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

34、貪心方法 31方法概述,例:考慮下列情況下的背包問(wèn)題: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)解,正是貪心方法要解決的問(wèn)題。,2、 適用條件: (1)有n個(gè)輸入; (2)它的解就由這n個(gè)輸入的某個(gè)子集組成; (3)這個(gè)子集必須滿足一定的約束條件---可行解; (4)可行解一般不止一個(gè),但是要求的是最優(yōu)解即使目標(biāo)函數(shù)取

35、得極值的解。,3有關(guān)概念 (1) 約束條件:把子集必須滿足的基本條件稱為約束條件。 (2) 可行解:把滿足約束條件的子集稱為該問(wèn)題的可行解。 (3) 目標(biāo)函數(shù):(可行解一般來(lái)說(shuō)是不唯一的)為了衡量可行解的優(yōu)劣,事先也給出了一定的標(biāo)準(zhǔn),這些標(biāo)準(zhǔn)一般以用函數(shù)形式給出,這些函數(shù)稱為目標(biāo)函數(shù)。 (4) 最優(yōu)解:那些使目標(biāo)函數(shù)取極值(極大或極?。┑目尚薪猓Q為最優(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)生問(wèn)題最優(yōu)解的最優(yōu)量度標(biāo)準(zhǔn)是使用貪心法設(shè)計(jì)求解的核心問(wèn)題。,3.2 背包問(wèn)題 一、問(wèn)題的描述 背包問(wèn)題:已知有n種物品和一個(gè)容量為M的背包,每種物品i的容量為wi,效益為pi ,假定將物品i的一部分xi放入背包就會(huì)得到pixi的效益,這里,0<=xi<=1,pi0。采用怎樣的裝包方法才會(huì)使裝入背包物品的總效益最大呢?顯然,由于背包容量是M,因此,要求所有選中要裝入背包的物品總?cè)萘坎坏贸^(guò)M。如果這n件物品

37、的總?cè)萘坎怀^(guò)M,則把所有物品裝入背包自然獲得最大效益。如果這些物品容量的和大于M,則在這種情況下該如何裝包呢?,由以上敘述,可將這個(gè)問(wèn)題形式描述如下: 約束條件: 目標(biāo)函數(shù): 其中:0 xi 1 ,pi0 ,wi0, 0 in M背包的容量 n物品種類 wi第i物品的容量 pi第i種物品價(jià)值 顯然,滿足約束條件的任一集合 是 一個(gè)可行解,使目標(biāo)函數(shù)取最大值的可行解是最優(yōu)解。,,例31考慮下列情況下的背包問(wèn)題: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è)解是背包問(wèn)題在這一情況下的最優(yōu)解。,,二、問(wèn)題的分析 為了獲取背包問(wèn)題的最優(yōu)解,必須要把物品放滿背包。由于可以只放物品i的一部分到背包中,因此這一要求是可以達(dá)到的。如果用貪心策略來(lái)求解背包問(wèn)題則正如31節(jié)中所說(shuō)的一樣,首先要選出最優(yōu)的量度標(biāo)準(zhǔn)。 以下不妨分三種情況進(jìn)行分析: (1) 取效益值作為量度標(biāo)準(zhǔn)。 即每裝入一件物品就使背包獲得最大可能的效益值增量。在這

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

40、慢地被消耗,但效益值沒(méi)能迅速地增加。 以上策略也只能得到次優(yōu)解,其原因在于容量雖然慢慢地被消耗,但效益值沒(méi)能迅速地增加。這又啟發(fā)我們應(yīng)采用在效益值的增長(zhǎng)速率和容量的消耗速率之間取得平衡的量度標(biāo)準(zhǔn)。即每裝入一件物品應(yīng)使它占用的每一單位容量獲得當(dāng)前最大的效益。,,三、算法設(shè)計(jì) 算法3.3 背包問(wèn)題的貪心算法,(3) 用效益和容量的比值作為量度標(biāo)準(zhǔn)。(即 ) 這就需使物品的裝入次序按 比值的非增次序來(lái)考慮,在這種策略下的量度是已裝入物品的累計(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無(wú)法全部放入背包, 退出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。由背包問(wèn)題量度選取的研究可知,選取最優(yōu)的量度標(biāo)準(zhǔn)實(shí)為用貪心方法求解問(wèn)題的核心。,,小結(jié):貪心方法設(shè)計(jì)步驟: 找出問(wèn)題的約束條件和目標(biāo)函數(shù)。 選取合適的量度標(biāo)準(zhǔn)。 按照“貪心方法的算法設(shè)計(jì)模式”的步驟進(jìn)行算法設(shè)計(jì).,四、算法分

43、析 如果將物體事先按Pi/wi的非增次序分好類,則過(guò)程Knapsack就得出這一策略下背包問(wèn)題的解。如果將物品分類的時(shí)間不算在內(nèi),則此算法所用時(shí)間為O(n)。,五、算法的證明 證明的基本思想是:把這貪心解與任一最優(yōu)解相比較,如果這兩個(gè)解不同,就去找開(kāi)始不同的第一個(gè)xi,然后設(shè)法用貪心解的這個(gè)xi去代換最優(yōu)解的那個(gè)xi,并證明最優(yōu)解在分量代換前后的總效益無(wú)任何變化。反復(fù)進(jìn)行這種代換,直到新產(chǎn)生的最優(yōu)解與貪心解完全一樣,從而證明了貪心解是最優(yōu)解。,,,掌握,定理31 如果p1/wl p2/w2 pn/wn。則算法GREEDYKNAPSACK對(duì)于給定的背包問(wèn)題實(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ù)以上過(guò)程,直到X=Z為止,可得X為最優(yōu)解。,,,討論:,3.3帶有限期的作業(yè)排序 一、問(wèn)題的描述 假定只能在一臺(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,二、問(wèn)題的分析 最優(yōu)量度標(biāo)準(zhǔn):目標(biāo)函數(shù)pi作為量度,即按照pi的非增次序來(lái)考慮這些作業(yè)。 使用這一量度,下一個(gè)要計(jì)入的作業(yè)將是使得在滿足所產(chǎn)生的J是一個(gè)可行解的限制條件下讓pi得到最大增加的作業(yè)。,應(yīng)用以上的量度標(biāo)準(zhǔn):開(kāi)始時(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è)問(wèn)題的最優(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è)排序問(wèn)題總是得到一個(gè)最優(yōu)解。,思路:J是由貪心方法所選擇的作業(yè)的集合;I是一個(gè)最優(yōu)解的作業(yè)集合。可證明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í)刻沒(méi)有作業(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,如何確定它是否為可行解的問(wèn)題,一個(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的可行性可以通過(guò)只檢驗(yàn)J中作業(yè)的一種特殊的排列來(lái)確定,這個(gè)排列是按期限的非降次序來(lái)完成的。,定理3.3 設(shè)J是k個(gè)作業(yè)的集合, =i1i2i3ik是J中作業(yè)的一種排列,它使得di1di2dik。J是一個(gè)可行解,當(dāng)且僅當(dāng)J中的作業(yè)可以按照的次序而又不違反任何一個(gè)期限的情況下來(lái)處理。(說(shuō)明了什么),證明:現(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) 通過(guò)使用不相交集合的UNION與FIND算法以及使用一個(gè)不同的方法來(lái)確定部分解的可行性,可以把JS的計(jì)算時(shí)間由O(n2)降低到數(shù)量級(jí)相當(dāng)接近于O(n)。,六、時(shí)間復(fù)雜性分析 經(jīng)過(guò)分析知道,算法JS所需要的總時(shí)間是O(sn)。由于sn (s為包含在解中的

55、作業(yè)數(shù)),因此JS的最壞計(jì)算時(shí)間為O(n2)。,分析:該方法較前方法的不同之處在于如何確定部分解的可行性方面,兩者的量度標(biāo)準(zhǔn)是一樣的。其方法是:如果J是作業(yè)的可行子集,那么可以使用下述規(guī)則來(lái)確定這些作業(yè)中的每一個(gè)作業(yè)的處理時(shí)間:若還沒(méi)給作業(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)作 無(wú) 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í),表示樹(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)用了過(guò)程Union和Find,其算法分別描述如下描述如下: 算法Union(i,j)的概略

58、描述:,Union(int i,int j) 1 x Parent(i) + Parent(j);//計(jì)算兩棵樹(shù)的總結(jié)點(diǎn)數(shù); 4 if Parent(i) Parent(j) //注意這里比較的是兩個(gè)負(fù)數(shù); 5then//樹(shù)i的結(jié)點(diǎn)數(shù)比j的少,則把i連到以j為根的樹(shù)上; 6 Parent(i) j 7 Parent(j) x; 8 9else//樹(shù)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)。,一、適用條件 多階段決策過(guò)程 實(shí)際問(wèn)題中,常有這樣一類活動(dòng),它們的活動(dòng)過(guò)程可以分為若干個(gè)階段,而且在任一階段i后的行為都依賴于i階段的過(guò)程狀態(tài),而與i階段之前的過(guò)程如何達(dá)到這種狀態(tài)的方式無(wú)關(guān)。當(dāng)各個(gè)階段決策確定后,就組成了一個(gè)決策序列,因而也就確定了整個(gè)過(guò)程的一條活動(dòng)路線。這種把一個(gè)問(wèn)題看作是一個(gè)前后關(guān)聯(lián)的具有鏈狀結(jié)構(gòu)的多階段過(guò)程被稱為多階段決策過(guò)程

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

61、、生產(chǎn)計(jì)劃等。 五、應(yīng)用實(shí)例分析,例4.1 多段圖問(wèn)題多段圖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的一條路徑成本是這條路徑上邊的成本和。多段圖問(wèn)題是求由s到t的最小成本路徑。每個(gè)集合Vi定義圖中的一段。由于E的約束,每條從s到t的路徑都是從第1段開(kāi)始,在第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))開(kāi)始,已作出了到結(jié)點(diǎn)v2的決策(初始決策),因此v2就是初始決策所產(chǎn)生的狀態(tài)。如果把v2看成是原問(wèn)題的一個(gè)子問(wèn)題的初始狀態(tài),解這個(gè)子問(wèn)題就是找出一條由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ī)劃方法來(lái)解決多段圖問(wèn)題提供了可能。,六、動(dòng)態(tài)規(guī)劃方法的形式化描述 能用動(dòng)態(tài)規(guī)劃求解的問(wèn)題的最優(yōu)化決策序列可表示如下。設(shè)S0是問(wèn)題的初始狀態(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)向前處理法:從最后階段開(kāi)始,以逐步向前遞推的方式列出求前一階段決策值的遞推關(guān)系式,即根據(jù)xi+1,,xn的那些最優(yōu)決策序列來(lái)列出求取xi決策值的關(guān)系式,即:xi=f(xi+1,xi+2,,xn),例子:在k段圖問(wèn)題中,設(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) .,下例是說(shuō)明向前處理法在多段圖中的使用,見(jiàn)黑板,小結(jié):無(wú)論是使用向前處理法還是使用向后處理法,都將所有子問(wèn)題的最優(yōu)解保存下來(lái)。這樣做的目的是為了便于逐步遞推得到原問(wèn)題的最優(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)自頂向下的分析,測(cè)試問(wèn)題本身是否滿足最優(yōu)化原理; (3)從底向上的計(jì)算,實(shí)現(xiàn)動(dòng)態(tài)規(guī)劃過(guò)程。,,一、問(wèn)題的描述 例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 多段圖,二、問(wèn)題分析:使用向前處理法 求各階段的遞推關(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(

展開(kāi)閱讀全文
溫馨提示:
1: 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
2: 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3.本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 裝配圖網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

相關(guān)資源

更多
正為您匹配相似的精品文檔
關(guān)于我們 - 網(wǎng)站聲明 - 網(wǎng)站地圖 - 資源地圖 - 友情鏈接 - 網(wǎng)站客服 - 聯(lián)系我們

copyright@ 2023-2025  zhuangpeitu.com 裝配圖網(wǎng)版權(quán)所有   聯(lián)系電話:18123376007

備案號(hào):ICP2024067431號(hào)-1 川公網(wǎng)安備51140202000466號(hào)


本站為文檔C2C交易模式,即用戶上傳的文檔直接被用戶下載,本站只是中間服務(wù)平臺(tái),本站所有文檔下載所得的收益歸上傳人(含作者)所有。裝配圖網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)上載內(nèi)容本身不做任何修改或編輯。若文檔所含內(nèi)容侵犯了您的版權(quán)或隱私,請(qǐng)立即通知裝配圖網(wǎng),我們立即給予刪除!