第4章貪心方法PPT課件

1、2021-11-4本章教學(xué)要求及重點(diǎn)難點(diǎn) 理解貪心方法的基本思想 掌握背包問(wèn)題的求解方法 掌握帶有限期的作業(yè)排序的基本方法 掌握用貪心方法求解單源點(diǎn)最短路徑的基本方法。 重點(diǎn)：用貪心方法求背包問(wèn)題及帶有限期作業(yè)排序； 難點(diǎn)：用貪心方法求單源點(diǎn)最短路徑。 第1頁(yè)/共82頁(yè)2021-11-4 一般方法1. 問(wèn)題的一般特征 問(wèn)題有n個(gè)輸入，問(wèn)題的解是由這n個(gè)輸入的某個(gè)子集組成，這個(gè)子集必須滿(mǎn)足某些事先給定的條件。 約束條件：子集必須滿(mǎn)足的條件； 可行解：滿(mǎn)足約束條件的子集；可行解可能不唯一； 目標(biāo)函數(shù)：用來(lái)衡量可行解優(yōu)劣的標(biāo)準(zhǔn)，一般以函數(shù)的形式給出； 最優(yōu)解：能夠使目標(biāo)函數(shù)取極值（極大或極?。┑目尚?/p>

2、解。 分類(lèi)：根據(jù)描述問(wèn)題約束條件和目標(biāo)函數(shù)的數(shù)學(xué)模型的特性和問(wèn)題的求解方法的不同，可分為：線(xiàn)性規(guī)劃、整數(shù)規(guī)劃、非線(xiàn)性規(guī)劃、動(dòng)態(tài)規(guī)劃等。 最優(yōu)化問(wèn)題求解 貪心方法：一種改進(jìn)的分級(jí)的處理方法，可對(duì)滿(mǎn)足上述特征的某些問(wèn)題方便地求解。第2頁(yè)/共82頁(yè)2021-11-4例找零錢(qián) 一個(gè)小孩買(mǎi)了價(jià)值少于1元的糖，并將1元的錢(qián)交給售貨員。售貨員希望用數(shù)目最少的硬幣找給小孩。假設(shè)提供數(shù)目不限的面值為25分、10分、5分及1分的硬幣。售貨員分步驟組成要找的零錢(qián)數(shù)，每次加入一個(gè)硬幣。 選擇硬幣時(shí)所采用的貪心算法如下：每一次選擇應(yīng)使零錢(qián)數(shù)盡量增大。為確保解法的可行性（即：所給的零錢(qián)等于要找的零錢(qián)數(shù)），所選擇的硬幣不應(yīng)

3、使零錢(qián)總數(shù)超過(guò)最終所需的數(shù)目。 假設(shè)需要找給小孩67分，首先入選的是兩枚25分的硬幣，第三枚入選的不能是25分的硬幣，否則將不可行（零錢(qián)總數(shù)超過(guò)67分），第三枚應(yīng)選擇10分的硬幣，然后是5分的，最后加入兩個(gè)1分的硬幣。 貪心算法有種直覺(jué)的傾向，在找零錢(qián)時(shí)，直覺(jué)告訴我們應(yīng)使找出的硬幣數(shù)目最少（至少是接近最少的數(shù)目）第3頁(yè)/共82頁(yè)2021-11-42. 貪心方法的一般策略貪心方法的一般策略 問(wèn)題的一般特征：?jiǎn)栴}的解是由問(wèn)題的一般特征：?jiǎn)栴}的解是由n個(gè)輸入的、滿(mǎn)足某些事先個(gè)輸入的、滿(mǎn)足某些事先給定的條件的子集組成。給定的條件的子集組成。 1）一般方法）一般方法 根據(jù)題意，選取一種根據(jù)題意，選取一種

4、度量標(biāo)準(zhǔn)度量標(biāo)準(zhǔn)。然后按照這種度量標(biāo)準(zhǔn)對(duì)。然后按照這種度量標(biāo)準(zhǔn)對(duì)n個(gè)輸入個(gè)輸入排序排序，并按序一次輸入一個(gè)量。，并按序一次輸入一個(gè)量。 如果這個(gè)輸入和當(dāng)前已構(gòu)成在這種量度意義下的如果這個(gè)輸入和當(dāng)前已構(gòu)成在這種量度意義下的部分最優(yōu)部分最優(yōu)解解加在一起不能產(chǎn)生一個(gè)可行解，則不把此輸入加到這部分解中。加在一起不能產(chǎn)生一個(gè)可行解，則不把此輸入加到這部分解中。否則，將當(dāng)前輸入合并到部分解中從而得到包含當(dāng)前輸入的否則，將當(dāng)前輸入合并到部分解中從而得到包含當(dāng)前輸入的新的新的部分解部分解。 2）貪心方法）貪心方法 這種能夠得到某種量度意義下的最優(yōu)解的這種能夠得到某種量度意義下的最優(yōu)解的分級(jí)處理分級(jí)處理方法稱(chēng)為

5、方法稱(chēng)為貪心方法貪心方法注：注： 貪心解貪心解 最優(yōu)解最優(yōu)解 直接將目標(biāo)函數(shù)作為直接將目標(biāo)函數(shù)作為量度標(biāo)準(zhǔn)量度標(biāo)準(zhǔn)也不一定能夠得到問(wèn)題的也不一定能夠得到問(wèn)題的最優(yōu)解最優(yōu)解 3）使用貪心策略求解的關(guān)鍵）使用貪心策略求解的關(guān)鍵 選取能夠得到問(wèn)題最優(yōu)解的量度標(biāo)準(zhǔn)。選取能夠得到問(wèn)題最優(yōu)解的量度標(biāo)準(zhǔn)。？第4頁(yè)/共82頁(yè)2021-11-43. 貪心方法的抽象化控制描述 procedure GREEDY(A,n) /A(1:n)包含n個(gè)輸入/ solution /將解向量solution初始化為空/ for i1 to n do xSELECT(A) /按照度量標(biāo)準(zhǔn)，從A中選擇一個(gè)輸入，其值賦予x 并將之從

6、A中刪除/ if FEASIBLE(solution,x) then /判定x是否可以包含在解向量中， 即是否能共同構(gòu)成可行解/ solutionUNION(solution,x) /將x和當(dāng)前的解向量合并成新的解 向量，并修改目標(biāo)函數(shù)/ endif repeat return(solution) end GREEDY 第5頁(yè)/共82頁(yè)2021-11-4 背包問(wèn)題1.問(wèn)題的描述 已知n種物品具有重量(w1,w2,wn)和效益值(p1,p2,pn) ，及一個(gè)可容納M重量的背包；設(shè)當(dāng)物品i全部或一部分xi放入背包將得到pi xi的效益，這里，0 xi 1, pi 0。 問(wèn)題：采用怎樣的裝包方法才能

7、使裝入背包的物品的總效益最大？ 分析： 裝入背包的總重量不能超過(guò)M 如果所有物品的總重量不超過(guò)M，即 M，則把所有的物品都裝入背包中將獲得最大可能的效益值 如果物品的總重量超過(guò)了M，則將有物品不能（全部）裝 入背包中。由于0 xi1，所以可以把物品的一部分裝入背包，所以最終背包中可剛好裝入重量為M的若干物品（整個(gè)或一部分） 目標(biāo)：使裝入背包的物品的總效益達(dá)到最大。niiixw1第6頁(yè)/共82頁(yè)2021-11-4問(wèn)題的形式描述問(wèn)題的形式描述 目標(biāo)函數(shù)目標(biāo)函數(shù)： 約束條件約束條件： 可可 行行 解解：滿(mǎn)足上述約束條件的：滿(mǎn)足上述約束條件的任一集合任一集合(x1,x2,xn) 都是問(wèn)都是問(wèn)題題 的一

8、個(gè)可行解的一個(gè)可行解可行解可能為多個(gè)?？尚薪饪赡転槎鄠€(gè)。 (x1,x2,xn)稱(chēng)為問(wèn)題的一個(gè)稱(chēng)為問(wèn)題的一個(gè)解向量解向量 最最 優(yōu)優(yōu) 解解：能夠使目標(biāo)函數(shù)取：能夠使目標(biāo)函數(shù)取最大值最大值的可行解是問(wèn)題的的可行解是問(wèn)題的 最優(yōu)解最優(yōu)解最優(yōu)解也可能為多個(gè)。最優(yōu)解也可能為多個(gè)。niiixp1niwpxMxwiiiniii1 , 0, 0, 101第7頁(yè)/共82頁(yè)2021-11-4例 背包問(wèn)題的實(shí)例 設(shè)，n=3，M=20， (p1,p2,p3) = (25,24,15)， (w1,w2,w3) = (18,15,10)。 可能的可行解如下： (x1,x2,x3) (1/2,1/3,1/4) 24.25

9、/沒(méi)有放滿(mǎn)背包/ (0, 2/3, 1) 20 31 (0, 1, 1/2) 20 iixpiixw第8頁(yè)/共82頁(yè)2021-11-42. 貪心策略求解 度量標(biāo)準(zhǔn)的選擇：三種不同的選擇1）以目標(biāo)函數(shù)作為度量標(biāo)準(zhǔn) 即，每裝入一件物品，就使背包背包獲得最大可能的效益增量。 該度量標(biāo)準(zhǔn)下的 處理規(guī)則： 按效益值的非增次序?qū)⑽锲芬患胤湃氲奖嘲?如果正在考慮的物品放不進(jìn)去，則只取其一部分裝滿(mǎn)背包：如果該物品的一部分不滿(mǎn)足獲得最大效益增量的度量標(biāo)準(zhǔn)，則在剩下的物品種選擇可以獲得最大效益增量的其它物品，將它或其一部分裝入背包。 如：若M=2,背包外還剩兩件物品i,j，且有(pi 4，wi4) 和(pj

10、 3，wj2)，則下一步應(yīng)選擇j而非i放入背包： pi/2 = 2 pj 3第9頁(yè)/共82頁(yè)2021-11-4實(shí)例分析（例)(p1,p2,p3) = (25,24,15)， (w1,w2,w3) = (18,15,10) p1p2 p3 首先將物品1放入背包，此時(shí)x11，背包獲得p125的效益增量，同時(shí)背包容量減少w118個(gè)單位，剩余空間M=2。 其次考慮物品2和3。就M=2而言有，只能選擇物品2或3的一部分裝入背包。 物品2： 若 x22/15， 則 p2 x216/5 物品3： 若 x32/10， 則 p3 x33 為使背包的效益有最大的增量，應(yīng)選擇物品2的2/15裝包，即 x22/15

11、最后，背包裝滿(mǎn)， M=0，故物品3將不能裝入背包，x30 。 背包最終可以獲得效益值 x1 p1 x2 p2x3 p3 28.2 (次優(yōu)解,非問(wèn)題的最優(yōu)解)第10頁(yè)/共82頁(yè)2021-11-42）以容量作為度量標(biāo)準(zhǔn) 以目標(biāo)函數(shù)作為度量標(biāo)準(zhǔn)所存在的問(wèn)題：盡管背包的效益值每次得到了最大的增加，但背包容量也過(guò)快地被消耗掉了，從而不能裝入“更多”的物品。 改進(jìn)：讓背包容量盡可能慢地消耗，從而可以盡量裝入“更多”的物品。 即，新的標(biāo)準(zhǔn)是：以容量作為度量標(biāo)準(zhǔn) 該度量標(biāo)準(zhǔn)下的處理規(guī)則： 按物品重量的非降次序?qū)⑽锲费b入到背包； 如果正在考慮的物品放不進(jìn)去，則只取其一部分裝滿(mǎn)背包；第11頁(yè)/共82頁(yè)2021-1

12、1-4實(shí)例分析（例)(p1,p2,p3) = (25,24,15)， (w1,w2,w3) = (18,15,10) w3w2 w1 首先將物品3放入背包，此時(shí)x31，背包容量減少w310個(gè)單位，還剩余空間M=10。同時(shí)，背包獲得p315的效益增量。 其次考慮物品1和2。就M=10而言有，也只能選擇物品1或2的一部分裝入背包。為使背包的按照“統(tǒng)一”的規(guī)則，下一步將放入物品2的10/15裝包，即 x210/152/3 最后，背包裝滿(mǎn)M=0，故物品1將不能裝入背包，x10 。 背包最終可以獲得效益值 x1 p1 x2 p2x3 p3 31 (次優(yōu)解,非問(wèn)題的最優(yōu)解) 存在的問(wèn)題：效益值沒(méi)有得到“最

13、大”的增加第12頁(yè)/共82頁(yè)2021-11-43）最優(yōu)的度量標(biāo)準(zhǔn) 影響背包效益值得因素： 背包的容量M 放入背包中的物品的重量及其可能帶來(lái)的效益值 可能的策略是：在背包效益值的增長(zhǎng)速率和背包容量消耗速率之間取得平衡，即每次裝入的物品應(yīng)使它所占用的每一單位容量能獲得當(dāng)前最大的單位效益。 在這種策略下的量度是：已裝入的物品的累計(jì)效益值與所用容量之比。 故，新的量度標(biāo)準(zhǔn)是：每次裝入要使累計(jì)效益值與所用容量的比值有最多的增加（首次裝入）和最小的減小（其后的裝入）。 此時(shí)，將按照物品的單位效益值：pi/wi 比值（密度）的非增次序考慮。第13頁(yè)/共82頁(yè)2021-11-4實(shí)例分析（例)(p1,p2,p3

14、) = (25,24,15)， (w1,w2,w3) = (18,15,10) p1/w1p3/w3 p2/w2 首先將物品2放入背包，此時(shí)x21，背包容量減少w215個(gè)單位，還剩余空間M=5。同時(shí)，背包獲得p224的效益增量。 其次考慮物品1和3。此時(shí)，應(yīng)選擇物品3,且就M=5而言有，也只能放入物品3的一部分到背包中 。即 x35/101/2 最后，背包裝滿(mǎn)M=0，故物品1將不能裝入背包，x10 。 背包最終可以獲得效益值 x1 p1 x2 p2x3 p3 31.5 (最優(yōu)解)第14頁(yè)/共82頁(yè)2021-11-43. 背包問(wèn)題的貪心求解算法算法 背包問(wèn)題的貪心算法 procedure GRE

15、EDYKNAPSACK(P,W,M,X,n) /p(1:n)和w(1:n)分別含有按P(i)/W(i)P(i1)/W(i1)排序的n 件物品的效益值和重量。M是背包的容量大小，而x(1:n)是解 向量/ real P(1:n),W(1:n),X(1:n),M,cu; integer I,n X0 /將解向量初始化為空/ cuM /cu是背包的剩余容量/ for i1 to n do if W(i) cu then exit endif X(i) 1 cu cu-W(i) repeat if in then X(i) cu/W(i) endif end GREEDY-KNAPSACK第15頁(yè)/共

16、82頁(yè)2021-11-44. 最優(yōu)解的證明 即證明：由第三種策略所得到的貪心解是問(wèn)題的最優(yōu)解。 最優(yōu)解的含義：在滿(mǎn)足約束條件的情況下，可使目標(biāo)函數(shù)取極（大或?。┲档目尚薪狻Ｘ澬慕馐强尚薪?，故只需證明：貪心解可使目標(biāo)函數(shù)取得極值。 證明的基本思想：將此貪心解與（假設(shè)中的）任一最優(yōu)解相比較。 如果這兩個(gè)解相同，則顯然貪心解就是最優(yōu)解。否則， 這兩個(gè)解不同，就去找開(kāi)始不同的第一個(gè)分量位置i，然后設(shè)法用貪心解的這個(gè)xi去替換最優(yōu)解的那個(gè)xi ，并證明最優(yōu)解在分量代換前后總的效益值沒(méi)有任何變化。 可反復(fù)進(jìn)行代換，直到新產(chǎn)生的最優(yōu)解與貪心解完全一樣。這一代換過(guò)程中，最優(yōu)解的效益值沒(méi)有任何損失，從而證明貪心

17、解的效益值與代換前后最優(yōu)解的效益值相同。即，貪心解如同最優(yōu)解一樣可取得目標(biāo)函數(shù)的最大/最小值。 從而得證：該貪心解也即問(wèn)題的最優(yōu)解。第16頁(yè)/共82頁(yè)2021-11-4 定理定理 如果如果p1/w1 p2/w2 pn/wn,則算法則算法GREEDY-KNAPSACK對(duì)于給定的背包問(wèn)題實(shí)例生成一個(gè)最優(yōu)解。對(duì)于給定的背包問(wèn)題實(shí)例生成一個(gè)最優(yōu)解。證明證明： 設(shè)設(shè)X=(x1, x2, , xn)是是GRDDDY-KNAPSACK所生成的所生成的貪貪心解心解。 如果所有的如果所有的xi都等于都等于1,則顯然則顯然X就是問(wèn)題的就是問(wèn)題的最優(yōu)解最優(yōu)解。否則，。否則， 設(shè)設(shè)j是使是使xi1的最小下標(biāo)。由算法可

18、知，的最小下標(biāo)。由算法可知，l xi=1 1ij,l 0 xj 1l xi=0 jin 若若X不是問(wèn)題的最優(yōu)解，則必定存在一個(gè)可行解不是問(wèn)題的最優(yōu)解，則必定存在一個(gè)可行解 Y=(y1, y2, , yn),使得：使得： 且應(yīng)有：且應(yīng)有： iiiixpyp Mywii第17頁(yè)/共82頁(yè)2021-11-4 設(shè)設(shè)k是使得是使得yk xk的最小下標(biāo)，則有的最小下標(biāo)，則有yk xk: a) 若若k0,當(dāng)且僅當(dāng)作業(yè)當(dāng)且僅當(dāng)作業(yè)i在其截至在其截至期限以前被完成時(shí)，則獲得期限以前被完成時(shí)，則獲得pi0的效益。的效益。 問(wèn)題問(wèn)題：求這：求這n個(gè)作業(yè)的一個(gè)子集個(gè)作業(yè)的一個(gè)子集J，其中的所有作業(yè)都可在其截，其中的所

19、有作業(yè)都可在其截至期限內(nèi)完成。至期限內(nèi)完成。J是問(wèn)題的一個(gè)可行解。是問(wèn)題的一個(gè)可行解。 可行解可行解J中的中的 所有作業(yè)的效益之和是所有作業(yè)的效益之和是 ，具有，具有最大效益最大效益值的值的可行解是該問(wèn)題的最優(yōu)解?？尚薪馐窃搯?wèn)題的最優(yōu)解。 如果所有的作業(yè)都能在其期限之內(nèi)完成則顯然可以獲得當(dāng)前最如果所有的作業(yè)都能在其期限之內(nèi)完成則顯然可以獲得當(dāng)前最大效益值；否則，將有作業(yè)無(wú)法完成大效益值；否則，將有作業(yè)無(wú)法完成決策應(yīng)該執(zhí)行哪些作業(yè)，以決策應(yīng)該執(zhí)行哪些作業(yè)，以獲得最大可能的效益值。獲得最大可能的效益值。 目標(biāo)函數(shù)：目標(biāo)函數(shù)： 約束條件：約束條件：所有的作業(yè)都應(yīng)在其期限之前完成所有的作業(yè)都應(yīng)在其期限

20、之前完成JiipJiip第20頁(yè)/共82頁(yè)2021-11-4例例 n=4，(p1，p2，p3，p4)(100,10,15,20)和和(d1，d2，d3，d4)(2,1,2,1)?？尚薪馊缦卤硭荆?。可行解如下表所示： 問(wèn)題的最優(yōu)解是問(wèn)題的最優(yōu)解是。所允許的處理次序是：先處理。所允許的處理次序是：先處理作業(yè)作業(yè)4 4再處理作業(yè)再處理作業(yè)1 1?？尚薪饪尚薪馓幚眄樞蛱幚眄樞蛐б嬷敌б嬷担?）1100（2）210（3）315（4）420（1,2）2,1110（1,3）1,3或或3,1115（1,4）4,1120（2,3）2,325（3,4）4,335第21頁(yè)/共82頁(yè)2021-11-41. 帶有限期

21、的作業(yè)排序算法1) 度量標(biāo)準(zhǔn)的選擇度量標(biāo)準(zhǔn)的選擇 以目標(biāo)函數(shù)以目標(biāo)函數(shù) 作為量度。作為量度。 量度標(biāo)準(zhǔn)：下一個(gè)要計(jì)入的作業(yè)將是使得在滿(mǎn)足量度標(biāo)準(zhǔn)：下一個(gè)要計(jì)入的作業(yè)將是使得在滿(mǎn)足所所 產(chǎn)生的產(chǎn)生的J是一個(gè)可行解的限制條件是一個(gè)可行解的限制條件下讓下讓 得到最大增加的作業(yè)。得到最大增加的作業(yè)。 處理規(guī)則：按處理規(guī)則：按pi的非增次序來(lái)考慮這些作業(yè)。的非增次序來(lái)考慮這些作業(yè)。JiipJiip第22頁(yè)/共82頁(yè)2021-11-4例：例求解例：例求解 (p1，p2，p3，p4)(100,10,15,20) (d1，d2，d3，d4)(2,1,2,1) 首先令首先令J=, 作業(yè)作業(yè)1具有當(dāng)前的最大效益值

22、，且具有當(dāng)前的最大效益值，且1是可是可行解，所以作業(yè)行解，所以作業(yè)1計(jì)入計(jì)入J； 在剩下的作業(yè)中，作業(yè)在剩下的作業(yè)中，作業(yè)4具有最大效益值，具有最大效益值，且且1,4也是可行解，故作業(yè)也是可行解，故作業(yè)4計(jì)入計(jì)入J，即，即J=1,4； 考慮考慮1,3,4和和1,2,4均不能構(gòu)成新的可行均不能構(gòu)成新的可行解，作業(yè)解，作業(yè)3和和2將被舍棄。將被舍棄。 故最后的故最后的J=1,4，最終效益值，最終效益值120（問(wèn)題（問(wèn)題的的最優(yōu)解最優(yōu)解）0Jiip第23頁(yè)/共82頁(yè)2021-11-42)作業(yè)排序算法的概略描述 算法 procedure GREEDY-JOB(D,J,n) /作業(yè)按p1p2pn的次序輸

23、入，它們的期限值D(i)1, 1in,n1。J是在它們的截止期限完成的作業(yè)的集合/ J1 for i2 to n do if Ji的所有作業(yè)能在它們的截止期限前完成 then JJi endif repeat end GREEDY-JOB第24頁(yè)/共82頁(yè)2021-11-42. 最優(yōu)解證明 定理定理 算法對(duì)于作業(yè)排序問(wèn)題總是得到問(wèn)題的一個(gè)算法對(duì)于作業(yè)排序問(wèn)題總是得到問(wèn)題的一個(gè)最最優(yōu)解優(yōu)解證明證明： 設(shè)設(shè)J是由算法所得的是由算法所得的貪心解貪心解作業(yè)集合，作業(yè)集合，I是一個(gè)是一個(gè)最優(yōu)解最優(yōu)解的作業(yè)集合。的作業(yè)集合。 若若I=J，則，則J就是最優(yōu)解；否則就是最優(yōu)解；否則 ，即至少存在兩個(gè)作業(yè)，即至

24、少存在兩個(gè)作業(yè)a和和b，使得，使得aJ且且 ,bI且且 。 并設(shè)并設(shè)a是這樣的一個(gè)具有是這樣的一個(gè)具有最高效益值最高效益值的作業(yè)，且由算的作業(yè)，且由算法的處理規(guī)則可得：對(duì)于在法的處理規(guī)則可得：對(duì)于在I中而不在中而不在J中的作業(yè)所有中的作業(yè)所有b，有：有： papbIaJbIJJI 且第25頁(yè)/共82頁(yè)2021-11-4 設(shè)SJ和SI分別是J和I的可行的調(diào)度表。因?yàn)镴和I都是可行解，故這樣的調(diào)度表一定存在； 設(shè)i是既屬于J又屬于I的一個(gè)作業(yè)，并i設(shè)在調(diào)度表SJ中的調(diào)度時(shí)刻是t，t+1，而在SI中的調(diào)度時(shí)刻是t，t+1。 在SJ和SI中作如下調(diào)整： 若tt，則將SJ中在t，t+1時(shí)刻調(diào)度的那個(gè)作業(yè)

25、（如果有的話(huà)）與i相交換。如果J中在t，t+1時(shí)刻沒(méi)有作業(yè)調(diào)度，則直接將i移到t，t+1調(diào)度。新的調(diào)度表也是可行的。反之， 若tt，則在SI中作類(lèi)似的調(diào)換，即將SI中在t，t+1時(shí)刻調(diào)度的那個(gè)作業(yè)（如果有的話(huà)）與i相交換。如果I中在t，t+1時(shí)刻沒(méi)有作業(yè)調(diào)度，則直接將i移到t，t+1調(diào)度。同樣，新的調(diào)度表也是可行的。 對(duì)J和I中共有的所有作業(yè)作上述的調(diào)整。設(shè)調(diào)整后得到的調(diào)度表為SJ和SI，則在SJ和SI中J和I中共有的所有作業(yè)將在相同的時(shí)間被調(diào)度。第26頁(yè)/共82頁(yè)2021-11-4 設(shè)a在SJ中的調(diào)度時(shí)刻是ta, ta+1， b是SI中該時(shí)刻調(diào)度的作業(yè)。根據(jù)以上的討論有：papb。 在SI中

26、，去掉作業(yè)b，而去調(diào)度作業(yè)a，得到的是作業(yè)集合I=I-b a的 一個(gè)可行的調(diào)度表，且I的效益值不小于I的效益值。而I中比I少了一個(gè)與J不同的作業(yè)。 重復(fù)上述的轉(zhuǎn)換，可使I在不減效益值的情況下轉(zhuǎn)換成J。從而J至少有和I一樣的效益值。所以J也是最優(yōu)解。證畢。第27頁(yè)/共82頁(yè)2021-11-43. 如何判斷J的可行性方法一：檢驗(yàn)J中作業(yè)所有可能的排列，對(duì)于任一種次序排列的作 業(yè)排列，判斷這些作業(yè)是否能夠在其期限前完成若J 中有k個(gè)作業(yè)，則將要檢查k!個(gè)序列方法二：檢查J中作業(yè)的一個(gè)特定序列就可判斷J的可行性： 對(duì)于所給出的一個(gè)排列i1i2ik,由于作業(yè)ij完成的 最早時(shí)間是j，因此只要判斷出排列中

27、的每個(gè)作業(yè) dijj，就可得知是一個(gè)允許的調(diào)度序列，從而J是一個(gè) 可行解。反之，如果排列中有一個(gè)dijj,則將是一個(gè) 行不通的調(diào)度序列，因?yàn)橹辽僮鳂I(yè)ij不能在其期限之前完 成。 這一檢查過(guò)程可以只通過(guò)檢驗(yàn)J中作業(yè)的一種特殊的排列：按照作業(yè)期限的非降次序排列的作業(yè)序列即可完成。第28頁(yè)/共82頁(yè)2021-11-4 定理 設(shè)J是k個(gè)作業(yè)的集合，i1i2ik是J中作業(yè)的一種排列，它使得di1di2dik。J是一個(gè)可行解，當(dāng)且僅當(dāng)J中的作業(yè)可以按照的次序而又不違反任何一個(gè)期限的情況來(lái)處理。證明： 如果J中的作業(yè)可以按照的次序而又不違反任何一個(gè)期限的情況來(lái)處理，則J是一個(gè)可行解 若J是一個(gè)可行解，則必存

28、在序列r1r2rk，使得drjj, 1jk。 若，則即是可行解。否則， ，令a是使得raia的最小下標(biāo)，并設(shè)rb=ia。則有： ba 且 dradrb (為什么?) 在中調(diào)換ra與rb，所得的新序列 s1s2sk的處理次序不違反任何一個(gè)期限。 重復(fù)上述過(guò)程，則可將轉(zhuǎn)換成且不違反任何一個(gè)期限。故是一個(gè)可行的調(diào)度序列 故定理得證。第29頁(yè)/共82頁(yè)2021-11-4 i1 i2 ia ic ikr1 r2 ra rb rk ab dradrb第30頁(yè)/共82頁(yè)2021-11-45. 帶有限期的作業(yè)排序算法的實(shí)現(xiàn) 對(duì)當(dāng)前正在考慮的作業(yè)j，按限期大小采用一種“插入排序”的方式，嘗試將其“插入”到一個(gè)按

29、限期從小到大順序構(gòu)造的作業(yè)調(diào)度序列中，以此判斷是否能夠合并到當(dāng)前部分解J中。如果可以，則插入到序列中，形成新的可行解序列。否則，舍棄該作業(yè)。具體如下： 假設(shè)n個(gè)作業(yè)已經(jīng)按照效益值從大到小的次序，即p1p2pn的順序排列好，每個(gè)作業(yè)可以在單位時(shí)間內(nèi)完成，并具有相應(yīng)的時(shí)間期限；且至少有一個(gè)單位時(shí)間可以執(zhí)行作業(yè) 首先，將作業(yè)1存入部分解J中，此時(shí)J是可行的； 然后，依次考慮作業(yè)2到n。假設(shè)已經(jīng)處理了i-1個(gè)作業(yè)，其中有k個(gè)作業(yè)計(jì)入了部分解J中：J(1),J(2),J(k)，且有 D(J(1)D(J(2)D(J(k)第31頁(yè)/共82頁(yè)2021-11-4 對(duì)當(dāng)前正在考慮的作業(yè)i,將D(i)依次和D(J(

30、k), D(J(k-1),，D(J(1)相比較，直到找到位置q：使得 D(i) D(J(l)，qlk，且 D(J(q) D(i) 此時(shí)，若D(J(l)l, qlk,即說(shuō)明q位置之后的所有作業(yè)均可推遲一個(gè)單位時(shí)間執(zhí)行，而又不違反各自的執(zhí)行期限。 最后，將q位置之后的所有作業(yè)后移一位，將作業(yè)i插入到位置q1處，從而得到一個(gè)包含k+1個(gè)作業(yè)的新的可行解。 若找不到這樣的q，作業(yè)i將被舍棄。 對(duì)i之后的其它作業(yè)重復(fù)上述過(guò)程直到n個(gè)作業(yè)處理完畢。最后J中所包含的作業(yè)集合是此時(shí)算法的貪心解，也是問(wèn)題的最優(yōu)解。第32頁(yè)/共82頁(yè)2021-11-4算法 帶有限期和效益的單位時(shí)間的作業(yè)排序貪心算法 proced

31、ure JS(D,J,n,k) /D(1),D(n)是期限值。n1。作業(yè)已按p1p2pn的順序排序。J(i)是最優(yōu)解中的第i個(gè)作 業(yè)，1ik。終止時(shí)， D(J(i)D(J(i1)， 1ik/ integer D(0:n),J(0:n),i,k,n,r D(0)J(0)0 /初始化/ k1;J(1)1 /計(jì)入作業(yè)1/ for i2 to n do /按p的非增次序考慮作業(yè)。找i的位置并檢查插入的可行性/ rk while D(J(r)D(i) and D(J(r) r do rr-1 repeat If D(J(r)D(i) and D(i)r then /把i插入到J中/ for ik to

32、r+1 by -1 do J(i+1) J(i) /將插入點(diǎn)的作業(yè)后移一位/ repeat J(r+1) i;kk+1 endif repeat end JS第33頁(yè)/共82頁(yè)2021-11-4計(jì)算時(shí)間分析 for i2 to n do 將循環(huán)n-1次 rk while D(J(r)D(i) and D(J(r) r do 至多循環(huán)k次， k是當(dāng)前計(jì)入J中的作業(yè)數(shù) rr-1 repeat If D(J(r)D(i) and D(i)r then for ik to r+1 by -1 do 循環(huán)k-r次，r是插入點(diǎn)的位置 J(i+1) J(i) repeat J(r+1) I;kk+1 end

33、if repeat設(shè)s是最終計(jì)入J中的作業(yè)數(shù)，則算法JS所需要的總時(shí)間是O(sn)。sn，故最壞情況：TJS = (n2)，特例情況：pi=di=n-i+1,1in最好情況：TJS = (n)，特例情況：di=i,1in第34頁(yè)/共82頁(yè)2021-11-46. 一種“更快”的作業(yè)排序問(wèn)題 使用不相交集合的 UNION和FIND算法（見(jiàn)節(jié)），可以將JS的計(jì)算時(shí)間降低到數(shù)量級(jí)接近(n)。 （略）第35頁(yè)/共82頁(yè)2021-11-4例 設(shè)n=5,(p1,p5)=(20,15,10,5,1),(d1,d5)=(2,2,1,3,3)。J已分配時(shí)間片已分配時(shí)間片正被考正被考慮作業(yè)慮作業(yè)動(dòng)作動(dòng)作0無(wú)無(wú)1分配

34、分配1,211,22分配分配0,11,20,1,1,23不適合，舍棄不適合，舍棄1,20,1,1,24分配分配2,31,2,4 0,1,1,2,2,35舍棄舍棄最優(yōu)解是J1,2,4第36頁(yè)/共82頁(yè)2021-11-4 最優(yōu)歸并模式1. 問(wèn)題的描述1）兩個(gè)文件的歸并問(wèn)題 兩個(gè)已知文件的一次歸并所需的計(jì)算時(shí)間O(兩個(gè)文件的元素總數(shù)) 例： n個(gè)記錄的文件 (n+m) 個(gè)記錄的文件 m個(gè)記錄的文件 (n+m) 2）多個(gè)文件的歸并 已知n個(gè)文件，將之歸并成一個(gè)單一的文件 例：假定文件X1，X2， X3， X4，采用兩兩歸并的方式，可能的歸并模式有： X1+X2=Y1+X3= Y2+X4= Y3 X1+

35、X2 = Y1 + Y3 X3+X4=Y2 第37頁(yè)/共82頁(yè)2021-11-4 二路歸并模式：每次僅作兩個(gè)文件的歸并；當(dāng)有多個(gè)文件時(shí)，采用兩兩歸并的模式，最終得到一個(gè)完整的記錄文件。 二元?dú)w并樹(shù)：二路歸并模式的歸并過(guò)程可以用一個(gè)二元樹(shù)的形式描述，稱(chēng)之為二元?dú)w并樹(shù)。如 歸并樹(shù)的構(gòu)造 外結(jié)點(diǎn)：n個(gè)原始文件 內(nèi)結(jié)點(diǎn)：一次歸并后得到的文件 在兩路歸并模式下，每個(gè)內(nèi)結(jié)點(diǎn)剛好有兩個(gè)兒子，代表把它的兩個(gè)兒子表示的文件歸并成其本身所代表的文件6050302010X1Z1XX3X2第38頁(yè)/共82頁(yè)2021-11-4不同的歸并順序帶來(lái)的計(jì)算時(shí)間是不同的。 例 已知X1,X2,X3是分別為30、20、10個(gè)記錄

36、長(zhǎng)度的已分類(lèi)文件。將這3個(gè)文件歸并成長(zhǎng)度為60的文件?？赡艿臍w并過(guò)程和相應(yīng)的記錄移動(dòng)次數(shù)如下： 問(wèn)題：采用怎樣的歸并順序才能使歸并過(guò)程中元素的移動(dòng)次數(shù)最小（或執(zhí)行的速度最快）XX3X2X1移動(dòng)50次移動(dòng)60次XX1X2X3移動(dòng)30次移動(dòng)60次總移動(dòng)次數(shù)：110次總移動(dòng)次數(shù)：90次第39頁(yè)/共82頁(yè)2021-11-42. 貪心求解1) 度量標(biāo)準(zhǔn)的選擇 任意兩個(gè)文件的歸并所需的元素移動(dòng)次數(shù)與這兩個(gè)文件的長(zhǎng)度之和成正比； 度量標(biāo)準(zhǔn)：每次選擇需要移動(dòng)次數(shù)最少的兩個(gè)集合進(jìn)行歸并； 處理規(guī)則：每次選擇長(zhǎng)度最小的兩個(gè)文件進(jìn)行歸并。95355203060301510F4F3Z1Z2Z4Z3F1F5F2(F1,

37、F2,F3,F4,F5) = (20,30,10,5,30)第40頁(yè)/共82頁(yè)2021-11-42) 目標(biāo)函數(shù)目標(biāo)函數(shù) 目標(biāo)目標(biāo)：元素移動(dòng)的次數(shù)最少：元素移動(dòng)的次數(shù)最少 實(shí)例：為得到歸并樹(shù)根結(jié)點(diǎn)表示的歸并文件，外部結(jié)點(diǎn)中實(shí)例：為得到歸并樹(shù)根結(jié)點(diǎn)表示的歸并文件，外部結(jié)點(diǎn)中每個(gè)文件記錄需要移動(dòng)的次數(shù)該外部結(jié)點(diǎn)到根的距離，即根每個(gè)文件記錄需要移動(dòng)的次數(shù)該外部結(jié)點(diǎn)到根的距離，即根到該外部結(jié)點(diǎn)路徑的長(zhǎng)度。如，到該外部結(jié)點(diǎn)路徑的長(zhǎng)度。如， F4 ： 則則F4中所有記錄在整個(gè)歸并過(guò)程中移動(dòng)的總量中所有記錄在整個(gè)歸并過(guò)程中移動(dòng)的總量|F4|*3 帶權(quán)外部路徑長(zhǎng)度帶權(quán)外部路徑長(zhǎng)度：記：記di是由根到代表文件是由

38、根到代表文件Fi的外部結(jié)點(diǎn)的外部結(jié)點(diǎn)的距離，的距離，qi是是Fi的長(zhǎng)度，則這棵樹(shù)的代表的歸并過(guò)程的元素移的長(zhǎng)度，則這棵樹(shù)的代表的歸并過(guò)程的元素移動(dòng)總量是：動(dòng)總量是： 最優(yōu)的二路歸并模式最優(yōu)的二路歸并模式：與一棵具有：與一棵具有最小外部帶權(quán)路徑長(zhǎng)度最小外部帶權(quán)路徑長(zhǎng)度的二元樹(shù)相對(duì)應(yīng)。的二元樹(shù)相對(duì)應(yīng)。F4Z1Z2Z4niiidq1第41頁(yè)/共82頁(yè)2021-11-4算法 生成二元?dú)w并樹(shù)的算法 procedure TREE(L,n) /L是n個(gè)單結(jié)點(diǎn)的二元樹(shù)表/ for i1 to n-1 do call GETNODE(T) /構(gòu)造一顆新樹(shù)T/ LCHILD(T) LEAST(L) /從表L中選當(dāng)

39、前根WEIGHT最小的樹(shù)， 并從中刪除/ RCHILD(T) LEAST(L) WEIGHT(T) WEIGHT(LCHILD(T)+WEIGHT(RCHILD(T) call INSERT(L,T) /將歸并的樹(shù)T加入到表L中/ repeat return (LEAST(L) /此時(shí)，L中的樹(shù)即為歸并的結(jié)果/ end TREE第42頁(yè)/共82頁(yè)2021-11-4例 已知六個(gè)初始文件，長(zhǎng)度分別為：2,3,5,7,9,13。 采用算法TREE，各階段的工作狀態(tài)如圖所示：L迭代2357913023579131523579132510第43頁(yè)/共82頁(yè)2021-11-4235791335101623

40、579134510162323579135510162339第44頁(yè)/共82頁(yè)2021-11-4時(shí)間分析 1) 循環(huán)體：n-1次 2) L以有序序列表示 LEAST(L): (1) INSERT(L,T): (n) 總時(shí)間： (n2) 3) L以min-堆表示 LEAST(L): (logn) INSERT(L,T): (logn) 總時(shí)間： (nlogn)第45頁(yè)/共82頁(yè)2021-11-43. 最優(yōu)解的證明 定理3.4 若L最初包含n1個(gè)單結(jié)點(diǎn)的樹(shù)，這些樹(shù)有WEIGHT值為(q1,q2,qn)，則算法TREE對(duì)于具有這些長(zhǎng)度的n個(gè)文件生成一棵最優(yōu)的二元?dú)w并樹(shù)。證明：歸納法證明 當(dāng)n=1時(shí)，

41、返回一棵沒(méi)有內(nèi)部結(jié)點(diǎn)的樹(shù)。定理得證。 假定算法對(duì)所有的(q1,q2,qn)，1mn,生成一棵最優(yōu)二元?dú)w并樹(shù)。 對(duì)于n,假定q1q2qn,則q1和q2將是在for循環(huán)的第一次迭代中首先選出的具有最小WEIGHT值的兩棵樹(shù)（的WEIGHT值）；如圖所示，T是由這樣的兩棵樹(shù)構(gòu)成的子樹(shù)：q1q2q1+q2T第46頁(yè)/共82頁(yè)2021-11-4 設(shè)T是一棵對(duì)于(q1,q2,qn)的最優(yōu)二元?dú)w并樹(shù)。 設(shè)P是T中距離根最遠(yuǎn)的一個(gè)內(nèi)部結(jié)點(diǎn)。 若P的兩棵子樹(shù)不是q1和q2，則用q1和q2代換P當(dāng)前的子樹(shù)而不會(huì)增加T的帶權(quán)外部路徑長(zhǎng)度。 故，T應(yīng)是最優(yōu)歸并樹(shù)中的子樹(shù)。 則在T中用一個(gè)權(quán)值為q1q2的外部結(jié)點(diǎn)代換T

42、，得到的是一棵關(guān)于(q1q2,qn)最優(yōu)歸并樹(shù)T”。 而由歸納假設(shè)，在用權(quán)值為q1q2的外部結(jié)點(diǎn)代換了T之后，過(guò)程TREE將針對(duì)(q1q2,qn)得到一棵最優(yōu)歸并樹(shù)。將T帶入該樹(shù)，根據(jù)以上討論，將得到關(guān)于(q1,q2,qn)的最優(yōu)歸并樹(shù)。 故，TREE生成一棵關(guān)于(q1,q2,qn)的最優(yōu)歸并樹(shù)。第47頁(yè)/共82頁(yè)2021-11-45. k路歸并模式 每次同時(shí)歸并k個(gè)文件。 k元?dú)w并樹(shù)：可能需要增加“虛”結(jié)點(diǎn)，以補(bǔ)充不足的外部結(jié)點(diǎn)。 如果一棵樹(shù)的所有內(nèi)部結(jié)點(diǎn)的度都為k，則外部結(jié)點(diǎn)數(shù)n滿(mǎn)足 n mod (k-1) = 1 對(duì)于滿(mǎn)足 n mod (k1) =1的整數(shù)n，存在一棵具有n個(gè)外部結(jié)點(diǎn)的k

43、元樹(shù)T，且T中所有結(jié)點(diǎn)的度為k。 至多需要增加k-2個(gè)外部結(jié)點(diǎn)。 k路最優(yōu)歸并模式得貪心規(guī)則：每一步選取k棵具有最小長(zhǎng)度的子樹(shù)歸并。第48頁(yè)/共82頁(yè)2021-11-4 最小生成樹(shù)1. 問(wèn)題的描述 生成樹(shù)：設(shè)G=(V,E)是一個(gè)無(wú)向連通圖。如果G的生 成子圖T=(V,E)是一棵樹(shù)，則稱(chēng)T是G的一棵 生成樹(shù)(spanning tree) 最小生成樹(shù):2. 貪心策略 度量標(biāo)準(zhǔn)：選擇能使迄今為止所計(jì)入的邊的成本和有最小 增加的那條邊。 Prim算法 Kruskal算法 第49頁(yè)/共82頁(yè)2021-11-43. Prim算法 策略：使得迄今所選擇的邊的集合A構(gòu)成一棵樹(shù)；對(duì)將要計(jì)入到A中的下一條邊(u,

44、v)，應(yīng)是E中一條當(dāng)前不在A中且使得A(u,v)也是一棵樹(shù)的最小成本邊。1462531030204525 554050153512162162316234邊(1,2)(2,6)(3,6)(6,4)成本10251520第50頁(yè)/共82頁(yè)2021-11-41462531020251535邊(3,5)成本35V(TP) = 1,2,3,4,5,6E(TP) = (1,2),(2,6),(3,5),(4,6),(3,6) 第51頁(yè)/共82頁(yè)2021-11-4算法 Prim最小生成樹(shù)算法 procedure PRIM(E,COST,n,T,mincost) /E是G的邊集。COST(n,n)是n結(jié)點(diǎn)圖G

45、的成本鄰接矩陣，矩陣元素COST(i,j)是一個(gè)正實(shí)數(shù)，如果不存在邊(i,j)，則為。計(jì)算一棵最小生成樹(shù)并把它作為一個(gè)集合存放到數(shù)組T(1:n-1,2)中(T(i,1),T(i,2)是最小成本生成樹(shù)的一條邊。最小成本生成樹(shù)的總成本最后賦給mincost/ real COST(n,n), mincost integer NEAR(n), n, i, k, l, T(1:n-1,2) (k,l)具有最小成本的邊 mincostCOST(k,l) (T(l,1),T(l,2) (k,l) for i1 to n do /將NEAR置初值/ if COST(i,l) COST(i,k) then NE

46、AR(i)l else NEAR(i) k endif repeat第52頁(yè)/共82頁(yè)2021-11-4 NEAR(k)NEAR(l)0 for i2 to n-1 do /找找T的其余的其余n-2條邊條邊/ 設(shè)設(shè)j是是NEAR(j)0 且且COST(j,NEAR(j)最小的下標(biāo)最小的下標(biāo) (T(i,1),T(i,2)(j,NEAR(j) mincostmincost+COST(j,NEAR(j) NEAR(j)0 for k1 to n do /修改修改NEAR/ if NEAR(k)0 and COST(k,NEAR(k)COST(k,j) then NEAR(k)j endif repe

47、at repeat if mincost then print(no spanning tree) endif end PRIM第53頁(yè)/共82頁(yè)2021-11-4計(jì)算復(fù)雜性： 第3行花費(fèi)(e)(e=|E|)時(shí)間，第4行花費(fèi)(1)時(shí)間；第69行的循環(huán)花費(fèi)(n)時(shí)間；第12行和第1620行的循環(huán)要求(n)時(shí)間，因此第1121行循環(huán)要花費(fèi)(n)時(shí)間。 所以PRIM算法具有 的時(shí)間復(fù)雜度)(2n第54頁(yè)/共82頁(yè)2021-11-4另一種PRIM算法 最小生成樹(shù)中包含了與每個(gè)結(jié)點(diǎn)v相關(guān)的一條最小成本邊 證明略 方法：從一棵包含任何一個(gè)隨意指定的結(jié)點(diǎn)而沒(méi)有邊的樹(shù)開(kāi)始這一算法，然后再逐條增加邊。第55頁(yè)/

48、共82頁(yè)2021-11-44. Kruskal算法 （連通）圖的邊按成本的非降次序排列，下一條計(jì)入生成樹(shù)T中的邊是還沒(méi)有計(jì)入的邊中具有最小成本、且和T中現(xiàn)有的邊不會(huì)構(gòu)成環(huán)路的邊。1462531030204525 554050153512162162316234邊(1,2)(3,6)(4,6)(2,6)成本101520251623456345345455第56頁(yè)/共82頁(yè)2021-11-41462531020251535邊(1,4)(3,5)成本30 舍棄35V(TK) = 1,2,3,4,5,6E(TK) = (1,2),(2,6),(3,5),(4,6),(3,6) 第57頁(yè)/共82頁(yè)202

49、1-11-4算法 Kruskal算法 procedure KRUSKAL(E,COST,N,T,mincost) /G有n個(gè)結(jié)點(diǎn)，E是G的邊集。COST(u,v)是邊(u,v)的成本。T是最小成本生成樹(shù)的邊集，mincost是它的成本/ real mincost, COST(1:n,1:n); integer PARENT(1:n), T(1:n-1,2),n 以邊成本為元素構(gòu)造一個(gè)min堆 PARENT1/每個(gè)結(jié)點(diǎn)都在不同的集合中/ imincost0 while in-1 and 堆非空 do 從堆中刪去最小成本邊(u,v)并重新構(gòu)造堆 jFIND(u); kFIND(v) if( jk)

50、 then ii+1 T(i,1) u; T(i,2) v mincostmincost + COST(u,v) call UNION( j,k) endif repeat if in-1 then print(no spanning tree) endif return end KRUSKAL第58頁(yè)/共82頁(yè)2021-11-4注： 邊集以min-堆的形式保存，一條當(dāng)前最小成本邊可以在(loge)的時(shí)間內(nèi)找到； 當(dāng)且僅當(dāng)圖G是不連通的，in-1；此時(shí)算法具有最壞的執(zhí)行時(shí)間； 算法的計(jì)算時(shí)間是(eloge)第59頁(yè)/共82頁(yè)2021-11-4 單源點(diǎn)最短路徑1. 問(wèn)題描述 最短路徑問(wèn)題： 每對(duì)

51、結(jié)點(diǎn)之間的路徑問(wèn)題 特定線(xiàn)路下的最短路徑問(wèn)題 單源最短路徑問(wèn)題等 單源最短路徑問(wèn)題 已知一個(gè)n結(jié)點(diǎn)有向圖G=(V,E)和邊的權(quán)函數(shù)c(e)，求由G中某指定結(jié)點(diǎn)v0到其它各結(jié)點(diǎn)的最短路徑。 假定邊的權(quán)值為正。第60頁(yè)/共82頁(yè)2021-11-4 例 如圖所示。設(shè)v0是起始點(diǎn)，求v0到其它各結(jié)點(diǎn)的最短路徑。 路徑路徑 長(zhǎng)度長(zhǎng)度(1) v0v2 10(2) v0v2v3 25(3) v0v2v3v1 45(4) v0v4 45注：路徑按照長(zhǎng)度的注：路徑按照長(zhǎng)度的非降次序非降次序給出給出v0v1v4v5v3v2454510152010153352030第61頁(yè)/共82頁(yè)2021-11-42. 貪心策略

52、求解1) 度量標(biāo)準(zhǔn) 量度的選擇：迄今已生成的所有路徑長(zhǎng)度之和為使之達(dá)到最小，其中任意一條路徑都應(yīng)具有最小長(zhǎng)度： 假定已經(jīng)構(gòu)造了i條最短路徑，則下一條要構(gòu)造的路徑應(yīng)是下一條最短的路徑。 處理規(guī)則：按照路徑長(zhǎng)度的非降次序依次生成從結(jié)點(diǎn)v0到其它各結(jié)點(diǎn)的最短路徑。 例： v0v2 v0v2v3 v0v2v3v1 v0v4 第62頁(yè)/共82頁(yè)2021-11-42) 貪心算法貪心算法 設(shè)設(shè)S是已經(jīng)對(duì)其生成了最短路徑的是已經(jīng)對(duì)其生成了最短路徑的結(jié)點(diǎn)集合結(jié)點(diǎn)集合（包（包括括v0)。 對(duì)于當(dāng)前不在對(duì)于當(dāng)前不在S中的結(jié)點(diǎn)中的結(jié)點(diǎn)w，記，記DIST(w)是從是從v0開(kāi)始，開(kāi)始，只經(jīng)過(guò)只經(jīng)過(guò)S中的結(jié)點(diǎn)而在中的結(jié)點(diǎn)而

53、在w結(jié)束的那條最短路徑的長(zhǎng)結(jié)束的那條最短路徑的長(zhǎng)度。度。則有，則有，SW第63頁(yè)/共82頁(yè)2021-11-4 如果下一條最短路徑是到結(jié)點(diǎn)u，則這條路徑是從結(jié)點(diǎn)v0出發(fā)在u處終止，且只經(jīng)過(guò)那些在S中的結(jié)點(diǎn),即由v0至u的這條最短路徑上的所有中間結(jié)點(diǎn)都是S中的結(jié)點(diǎn): 設(shè)w是這條路徑上的任意中間結(jié)點(diǎn)，則從v0到u的路徑也包含了一條從v0到w的路徑，且其長(zhǎng)度小于從v0到u的路徑長(zhǎng)度。 v0,s1,s2,w,sm-1,u 均在S中 根據(jù)生成規(guī)則：最短路徑是按照路徑長(zhǎng)度的非降次序生成的，因此從v0到w的最短路徑應(yīng)該已經(jīng)生成。從而w也應(yīng)該在S中。 故,不存在不在S中的中間結(jié)點(diǎn)。 所生成的下一條路徑的終點(diǎn)u必

54、定是所有不在S內(nèi)的結(jié)點(diǎn)中且具有最小距離DIST(u)的結(jié)點(diǎn)。第64頁(yè)/共82頁(yè)2021-11-4如果選出了這樣結(jié)點(diǎn)u并生成了從v0到u的最短路徑之后，結(jié)點(diǎn)u將成為S中的一個(gè)成員。此時(shí)，那些從v0出發(fā)，只經(jīng)過(guò)S中的結(jié)點(diǎn)并且在S外的結(jié)點(diǎn)w處結(jié)束的最短路徑可能會(huì)減少DIST(w)的值變?。?如果這樣的路徑的長(zhǎng)度發(fā)生了改變，則這些路徑必定是一條從v0開(kāi)始，經(jīng)過(guò)u然后到w的更短的路所致。 根據(jù)DIST(w)的定義，它所表示的v0至w的最短路徑上的所有中間結(jié)點(diǎn)都在S中； 只考慮E和 的情況 u是從v0至w的最短路徑上所經(jīng)過(guò)的結(jié)點(diǎn)。 則有：DIST(w) = DIST(u) + c(u,w)Ewu ,SWu

55、v0第65頁(yè)/共82頁(yè)2021-11-4算法算法 生成最短路徑的貪心算法生成最短路徑的貪心算法 procedure SHORTEST-PATHS(v,COST,DIST,n) /G是一個(gè)是一個(gè)n結(jié)點(diǎn)有向圖，它由其成本鄰接矩陣結(jié)點(diǎn)有向圖，它由其成本鄰接矩陣COST(n,n)表示表示DIST(j)被置被置 以結(jié)點(diǎn)以結(jié)點(diǎn)v到結(jié)點(diǎn)到結(jié)點(diǎn)j的最短路徑長(zhǎng)度，這里的最短路徑長(zhǎng)度，這里1jn。DIST(v)被置成零被置成零/ boolean S(1:n);real COST(1:n,1:n),DIST(1:n) integer u,v,n,num,I,w for i1 to n do /將集合將集合S初始化為

56、空初始化為空/ S(i) 0;DIST(i) COST(v,i) repeat S(v) 1;DIST(v) 0 /結(jié)點(diǎn)結(jié)點(diǎn)v計(jì)入計(jì)入S/ for num2 to n-1 do /確定由結(jié)點(diǎn)確定由結(jié)點(diǎn)v出發(fā)的出發(fā)的n-1條路條路/ 選取結(jié)點(diǎn)選取結(jié)點(diǎn)u,它使得它使得DIST(u)= S(u) 1 /結(jié)點(diǎn)結(jié)點(diǎn)u計(jì)入計(jì)入S/ for 所有所有S(w)0的結(jié)點(diǎn)的結(jié)點(diǎn)w do /修改修改DIST(w)/ DIST(w) = min(DIST(w), DIST(u) + COST(u,w) repeat repeat end SHORTEST-PATHS)(min0)(wDISTwS第66頁(yè)/共82頁(yè)20

57、21-11-43) 計(jì)算時(shí)間計(jì)算時(shí)間 算法的計(jì)算時(shí)間是：算法的計(jì)算時(shí)間是：(n2) for i1 to n do S(i) 0;DIST(i) COST(v,i) repeat for num2 to n-1 do 選取結(jié)點(diǎn)選取結(jié)點(diǎn)u,它使得它使得DIST(u)= S(u) 1 for 所有所有S(w)0的結(jié)點(diǎn)的結(jié)點(diǎn)w do DIST(w) = min(DIST(w), DIST(u) + COST(u,w) repeat repeat最短路徑算法的時(shí)間復(fù)雜度最短路徑算法的時(shí)間復(fù)雜度 由于任何一條邊由于任何一條邊都有可能都有可能是最短路徑中的邊，所以求任是最短路徑中的邊，所以求任何最短路徑的算

58、法都必須至少檢查圖中的每條邊一次，所以何最短路徑的算法都必須至少檢查圖中的每條邊一次，所以這樣的算法的最小時(shí)間是這樣的算法的最小時(shí)間是(e)。 鄰接矩陣表示的圖：鄰接矩陣表示的圖： (n2) )(min0)(wDISTwS)(n)2( n)(n)(n第67頁(yè)/共82頁(yè)2021-11-4例 求下圖中從v1出發(fā)到其余各結(jié)點(diǎn)的最短路徑v1v2v4v3v5v6v7205025705070105055403025圖的成本鄰接矩陣：圖的成本鄰接矩陣： 0 20 50 30 + + + 0 25 + + 70 + + 0 40 25 50 + + + 0 55 + + + + + 0 10 70+ + +

59、+ + 0 50+ + + + + + 0第68頁(yè)/共82頁(yè)2021-11-4算法的執(zhí)行軌跡描述算法的執(zhí)行軌跡描述迭代迭代選取的選取的結(jié)點(diǎn)結(jié)點(diǎn)S DIST (1) (2) (3) (4) (5) (6) (7)置初值置初值123452435611,21,2,41,2,4,31,2,4,3,51,2,4,3,5,6 0 20 50 30 + + + 0 20 45 30 + 90 + 0 20 45 30 85 90 + 0 20 45 30 70 90 + 0 20 45 30 70 90 140 0 20 45 30 70 90 130算法的執(zhí)行在有算法的執(zhí)行在有n-1個(gè)結(jié)點(diǎn)加入到個(gè)結(jié)點(diǎn)加入到S中后終止中后終止第69頁(yè)/共82頁(yè)2021-11-43. 最短路徑生成樹(shù) 對(duì)于無(wú)向連通圖G，由結(jié)點(diǎn)v到其余各結(jié)點(diǎn)的最短路徑的邊構(gòu)成G的一棵生成樹(shù)，稱(chēng)為最短路徑生成樹(shù)。 注：不同起點(diǎn)v的生成樹(shù)可能不同。21356748555254035151050204530213567485254015102030213567485552515104530 原始圖原始圖 由結(jié)點(diǎn)由結(jié)點(diǎn)1出發(fā)的最短路徑生成樹(shù)出發(fā)的最短路徑生成樹(shù) 最小成本生成樹(shù)最小成本生