貪心算法：任務(wù)調(diào)度問題

1、程序?qū)嵺`報告（2010）數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告貪心算法：任務(wù)調(diào)度問題專業(yè)計算機科學(xué)與技術(shù)（軟件工程）學(xué)生姓名陳亮班級BM計算機091學(xué)號0951401134指導(dǎo)教師吳 素 芹起止日期2011.1.10-2011.1.141目 錄1 簡介12算法說明23測試結(jié)果24分析與探討85小結(jié)11參考文獻11附 錄12附錄1 源程序清單121貪心算法1 簡介 貪心算法通過一系列的選擇來得到一個問題的解。它所做的每一個選擇都是當(dāng)前狀態(tài)下某種意義的最好選擇，即貪心選擇。希望通過每次所做的貪心選擇導(dǎo)致最終結(jié)果是問題的一個最優(yōu)解。這種啟發(fā)式的策略并不總奏效，然而許多情況下確能達到預(yù)期的目的。下面來看一個找硬幣的例子

2、。假設(shè)有四種面值的硬幣：一分、兩分、五分和一角?，F(xiàn)在要找給某顧客四角八分錢。這時，一般都會拿出四個一角、一個五分、一個兩分和一個一分的硬幣遞給顧客。這種找硬幣的方法與其他的方法相比，它所給出的硬幣個數(shù)是最少的。在這里，就是下意思的使用了貪心算法（即盡可能地先考慮大幣值的硬幣）。貪心算法并不是從整體最優(yōu)加以考慮，它所做出的選擇只是局部最優(yōu)選擇。一些問題中，使用貪心算法得到的最后結(jié)果并不是整體的最優(yōu)解，這時算法得到的是一次最優(yōu)解（Suboptimal Solution）。在上述的問題中，使用貪心算法得到的結(jié)果恰好就是問題整體的最優(yōu)解。對于一個具體的問題，怎么知道是否可用貪心算法來解此問題，以及能否

3、得到問題的一個最優(yōu)解呢？這個問題很難給予肯定的回答。但是，許多可以用貪心算法求解的問題中一般具有兩個重要的性質(zhì)：貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)。所謂貪心選擇性質(zhì)是指所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇即貪心選擇來達到，這是貪心算法可行的第一個基本要素。對于一個具體問題，要確定它是否具有貪心選擇性質(zhì)，必須證明每一步所做的貪心選擇最終將會得到問題的一個整體最優(yōu)解。首先考察問題的一個整體最優(yōu)解，并證明可修改這個最優(yōu)解，使其以貪心選擇開始。而且做了貪心選擇后，原問題化簡為一個規(guī)模更小的類似子問題。然后，用數(shù)學(xué)歸納法證明，通過每一步做貪心選擇，最終可得到問題的一個整體最優(yōu)解。其中，證明貪心選擇

4、后的問題簡化為規(guī)模更小的類似子問題的關(guān)鍵在于利用該問題的最優(yōu)結(jié)構(gòu)性質(zhì)。得注意的是，貪心算法并不是完全不可以使用，貪心策略一旦經(jīng)過證明成立后，它就是一種高效的算法。 貪心算法還是很常見的算法之一，這是由于它簡單易行，構(gòu)造貪心策略不是很困難。 可惜的是，它需要證明后才能真正運用到題目的算當(dāng)一個問題的最優(yōu)解包含著它的子問題的最優(yōu)解時，稱此問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)，這個性質(zhì)是該問題可用貪心算法求解的一個關(guān)鍵特征法中。 一般來說，貪心算法的證明圍繞著：整個問題的最優(yōu)解一定由在貪心策略中存在的子問題的最優(yōu)解得來的。2算法說明 有n項任務(wù)，要求按順序執(zhí)行，并設(shè)定第i項任務(wù)需要ti單位時間。如果任務(wù)完成的順序為

5、1，2，。，n，那么第i項任務(wù)完成的時間為ci=t1+.+ti,平均完成時間即為（c1+.+cn）/n.本題要求找到最小的任務(wù)平均完成時間。 輸入要求：輸入數(shù)據(jù)中包含幾個測試案例。每一個案例的第一行給出一個不大于2000000的整數(shù)n，接著下面一行開始列出n個肺負整數(shù)t(t=1000000000),每個數(shù)之間用空格相互隔開，以一個負數(shù)來結(jié)束輸入。 輸出要求：對每一個測試案例，打印它的最小平均完成時間，并精確到0.01。每個案例對應(yīng)的輸出結(jié)果都占一行。若輸入某一個案例中任務(wù)數(shù)目n=0,則對應(yīng)輸出一個空行。 輸入例子： 4 4 2 8 1 -1表示有四個任務(wù)，各自完成需要的時間單位分別是4，2，8

6、，1，第三行輸入-1表示輸入結(jié)束。 輸出例子：要求程序運行后的輸出結(jié)果為：6. 501.貪心選擇性質(zhì) 所謂貪心選擇性質(zhì)是指所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇，即貪心選擇來達到。這是貪心算法可行的第一個基本要素，也是貪心算法與動態(tài)規(guī)劃算法的主要區(qū)別。 動態(tài)規(guī)劃算法通常以自底向上的方式解各子問題，而貪心算法則通常以自頂向下的方式進行，以迭代的方式作出相繼的貪心選擇，每作一次貪心選擇就將所求問題簡化為規(guī)模更小的子問題。 對于一個具體問題，要確定它是否具有貪心選擇性質(zhì)，必須證明每一步所作的貪心選擇最終導(dǎo)致問題的整體最優(yōu)解。2.最優(yōu)子結(jié)構(gòu)性質(zhì) 當(dāng)一個問題的最優(yōu)解包含其子問題的最優(yōu)解時，稱此

7、問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。問題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問題可用動態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征。3.貪心算法與動態(tài)規(guī)劃算法的差異 貪心算法和動態(tài)規(guī)劃算法都要求問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)，這是2類算法的一個共同點。但是，對于具有最優(yōu)子結(jié)構(gòu)的問題應(yīng)該選用貪心算法還是動態(tài)規(guī)劃算法求解?是否能用動態(tài)規(guī)劃算法求解的問題也能用貪心算法求解?下面研究2個經(jīng)典的組合優(yōu)化問題，并以此說明貪心算法與動態(tài)規(guī)劃算法的主要差別。貪心算法思想：顧名思義，貪心算法總是作出在當(dāng)前看來最好的選擇。也就是說貪心算法并不從整體最優(yōu)考慮，它所作出的選擇只是在某種意義上的局部最優(yōu)選擇。當(dāng)然，希望貪心算法得到的最終結(jié)果也是整體最優(yōu)的。雖然貪心

8、算法不能對所有問題都得到整體最優(yōu)解，但對許多問題它能產(chǎn)生整體最優(yōu)解。如單源最短路經(jīng)問題，最小生成樹問題等。在一些情況下，即使貪心算法不能得到整體最優(yōu)解，其最終結(jié)果卻是最優(yōu)解的很好近似。貪心算法的基本要素： 1.貪心選擇性質(zhì)。所謂貪心選擇性質(zhì)是指所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇，即貪心選擇來達到。這是貪心算法可行的第一個基本要素，也是貪心算法與動態(tài)規(guī)劃算法的主要區(qū)別。 動態(tài)規(guī)劃算法通常以自底向上的方式解各子問題，而貪心算法則通常以自頂向下的方式進行，以迭代的方式作出相繼的貪心選擇，每作一次貪心選擇就將所求問題簡化為規(guī)模更小的子問題。 對于一個具體問題，要確定它是否具有貪心選擇性質(zhì)

9、，必須證明每一步所作的貪心選擇最終導(dǎo)致問題的整體最優(yōu)解。 2. 當(dāng)一個問題的最優(yōu)解包含其子問題的最優(yōu)解時，稱此問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。問題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問題可用動態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征。貪心算法的基本思路： 從問題的某一個初始解出發(fā)逐步逼近給定的目標(biāo)，以盡可能快的地求得更好的解。當(dāng)達到算法中的某一步不能再繼續(xù)前進時，算法停止。該算法存在問題：1. 不能保證求得的最后解是最佳的；2. 不能用來求最大或最小解問題；3. 只能求滿足某些約束條件的可行解的范圍。實現(xiàn)該算法的過程：從問題的某一初始解出發(fā)；while 能朝給定總目標(biāo)前進一步 do 求出可行解的一個解元素；由所有解元素組合

10、成問題的一個可行解；貪心算法的理論基礎(chǔ)： 借助于擬陣工具，可建立關(guān)于貪心算法的較一般的理論。這個理論對確定何時使用貪心算法可以得到問題的整體最優(yōu)解十分有用。1. 擬陣 擬陣M定義為滿足下面3個條件的有序?qū)?S,I)： (1)S是非空有限集。 (2)I是S的一類具有遺傳性質(zhì)的獨立子集族，即若BI，則B是S的獨立子集，且B的任意子集也都是S的獨立子集?？占貫镮的成員。 (3)I滿足交換性質(zhì)，即若AI,BI且|A|0，則稱擬陣M為帶權(quán)擬陣。依此權(quán)函數(shù)，S的任一子集A的權(quán)定義為 。2. 關(guān)于帶權(quán)擬陣的貪心算法 許多可以用貪心算法求解的問題可以表示為求帶權(quán)擬陣的最大權(quán)獨立子集問題。 給定帶權(quán)擬陣M=(

11、S,I)，確定S的獨立子集AI使得W(A)達到最大。這種使W(A)最大的獨立子集A稱為擬陣M的最優(yōu)子集。由于S中任一元素x的權(quán)W(x)是正的，因此，最優(yōu)子集也一定是極大獨立子集。 例如，在最小生成樹問題可以表示為確定帶權(quán)擬陣 的最優(yōu)子集問題。求帶權(quán)擬陣的最優(yōu)子集A的算法可用于解最小生成樹問題。 下面給出求帶權(quán)擬陣最優(yōu)子集的貪心算法。該算法以具有正權(quán)函數(shù)W的帶權(quán)擬陣M=(S,I)作為輸入，經(jīng)計算后輸出M的最優(yōu)子集A。Set greedy (M,W)A=; 將S中元素依權(quán)值W（大者優(yōu)先）組成優(yōu)先隊列； while (S!=) S.removeMax(x); if (AI) A=Axx; retur

12、n A；算法greedy的計算時間復(fù)雜性為 。引理1 (擬陣的貪心選擇性質(zhì)) 設(shè)M=(S,I)是具有權(quán)函數(shù)W的帶權(quán)擬陣，且S中元素依權(quán)值從大到小排列。又設(shè)xS是S中第一個使得x是獨立子集的元素，則存在S的最優(yōu)子集A使得x A。 算法greedy在以貪心選擇構(gòu)造最優(yōu)子集A時，首次選入集合A中的元素x是單元素獨立集中具有最大權(quán)的元素。此時可能已經(jīng)舍棄了S中部分元素。可以證明這些被舍棄的元素不可能用于構(gòu)造最優(yōu)子集。3測試結(jié)果圖51為正確的數(shù)據(jù)輸入與其運行結(jié)果： 圖51圖52為異常的數(shù)據(jù)輸入與其運行結(jié)果：。 圖52 圖53為異常的數(shù)據(jù)輸入與其運行結(jié)果： 圖534分析與探討這個題目屬于貪心算法應(yīng)用中的任

13、務(wù)調(diào)度問題。要得到所有任務(wù)的平均完成時間，只需要將各個任務(wù)完成時間從小到大排序，任務(wù)實際完成需要的時間等于它等待的時間與自身執(zhí)行需要的時間之和。這樣給出的調(diào)度三按照最短作業(yè)優(yōu)先進行來安排的。 明確了可以用最短作業(yè)優(yōu)先的思想后，就可以正式來設(shè)計題目的實現(xiàn)了。首先，輸入的測試案例可以有很多組，每一個案例的輸入格式都是第一行輸入任務(wù)的個數(shù)，然后下面一行輸入每一個任務(wù)需要的時間單位，輸入完成另起一行，可以再繼續(xù)輸入下一個案例的數(shù)據(jù)。最后用一個任意的負數(shù)來表示輸入的結(jié)束。這樣，由于案例的個數(shù)開始不得知，所以可以套用一個for循環(huán)，如圖5.13所示。for(n=o; n=0;) /*當(dāng)n小于0的時候，退出

14、程序*/ scanf(“%1d”,&n)； if(n0) 建立一個具有n個元素的數(shù)組；for(i=0;i1），把數(shù)組的全部元素分成d1個組。所以距離為d1的倍數(shù)的記錄放在同一個組中。先在各組內(nèi)進行直接插入排序；然后，取第二個增量d2d1重復(fù)上述的分組和排序，直至所取的增量dt=1(dtdt-1d21;increment0;increment=1)/*每次的步長都是通過n值右移位來得到的*/ for(i= increment;i=increment;j-=increment) if (temp*(a+ (j-increment) *(a+j)=*(a+(j-increment);elsebrea

15、k;*(a+j) =temp;圖5.14 希爾排序的實現(xiàn)（2）計算總的平均完成時間：排序完成后，數(shù)組a中的元素以升序的方式排序，因此總的平均完成時間為ACT=ai (n-i)/n（3）輸出調(diào)度結(jié)果：由于輸出的結(jié)果要求精確到0.01，所以輸出的時候需要采用以下輸出格式。double r100; /*依次存放每個案例的ACT*/printf( “%.sfn”, ri);/*輸出的結(jié)果要求精確到0.01*/圖5.15 要求輸出的精度為0.01另外，程序?qū)崿F(xiàn)的時候，要求用戶一次可以輸入一組或多組測試案例的數(shù)據(jù)，當(dāng)用戶的輸入完成后，程序經(jīng)過計算在屏幕上分行顯示這幾個案例的結(jié)果。因此,在有多個測試案例的情

16、況下，需要設(shè)置一個數(shù)組，用來存放每一組測試案例的計算結(jié)果，如圖5.16所示Double r100; /*用來存放每個測試案例的計算結(jié)果*/J=0; /*記錄測試案例的個數(shù)*/For(對每一個測試案例)把計算機得到的最優(yōu)調(diào)度時間存入rj中；J+;/*當(dāng)輸入的n值為負數(shù)時，跳出上面的for循環(huán)*/For(從0到j(luò))If(ri=-1)printf(“n”); /*輸出一個空行*/Else printf(“ %. 2fn”,ri); /*輸出的結(jié)果要求精確到0.01*/圖5.16 有多個測試案例的處理方法5小結(jié)通過這次課程設(shè)計的學(xué)習(xí)，更加深刻認識了數(shù)據(jù)結(jié)構(gòu)的重要性。在課程設(shè)計過程中，經(jīng)過互相的提問，仔

17、細的思考，學(xué)會了許多數(shù)據(jù)結(jié)構(gòu)里之前不懂的問題。很高興，學(xué)會了新的東西。我做的是貪心算法的課程設(shè)計，對于這個算法它很有趣，即通過一系列的選擇，來選取最好的選擇。而且還有許多的應(yīng)用實例，使我們對算法有了更好的理解。感覺數(shù)據(jù)結(jié)構(gòu)還是蠻好玩的，就是一個算法就可以控制整個的過程。為了把數(shù)據(jù)結(jié)構(gòu)學(xué)好，不僅要弄好理論上的，而且還要把課程設(shè)計學(xué)好，聯(lián)系實際，根據(jù)理論把課程設(shè)計學(xué)好，兩者結(jié)合。相信一定是可以學(xué)好的。通過自己的努力就可以，結(jié)果不是那么重要，學(xué)到了東西才是最好的。相信自己。參考文獻1 劉振安,劉燕君.C程序設(shè)計課程設(shè)計M.北京機械工業(yè)出版社,2004年9月2 譚浩強.C程序設(shè)計（第三版）.清華大學(xué)出

18、版社,2005年7月3 嚴(yán)蔚敏,吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語言版）.清華大學(xué)出版社,1997年4月4Mark Allen Weiss,陳越改編.Data Structures and Algorithm Analysis in C(second edition).北京：人民郵電出版社，20055魏寶剛，陳越，王申康.數(shù)據(jù)結(jié)構(gòu)與算法分析.杭州：浙江大學(xué)出版社，20046書本教材 C語言程序設(shè)計7書本教材 C+程序設(shè)計8書本教材 數(shù)據(jù)庫理論附 錄附錄1 源程序清單#include #include#includeusing namespace std;void Shellsort( long *a, long n );int main() long n,i,j; long *a,*b;double r100;/* 用來存放每個測試案