算法分析與設(shè)計課程設(shè)計--貪心算法解決活動安排問題

1、<p><b>　　算法分析與設(shè)計</b></p><p>　　課 程 設(shè) 計 報 告 </p><p>　　課程名稱 算 法 分 析 與 設(shè) 計</p><p>　　實驗學(xué)期 2013 年至 2014 年 第 1 學(xué)期</p><p>　　所在學(xué)院 理學(xué)院 年級 <

2、/p><p>　　專業(yè)班級 信息與計算科學(xué)3班 </p><p>　　《算法分析與設(shè)計》課程設(shè)計報告</p><p><b>　　目 錄</b></p><p><b>　　1課程實驗概述4</b></p><p>　　1.1 問題概述4</p>

3、<p>　　1.2 目的與任務(wù)4</p><p>　　1.3 開發(fā)環(huán)境4</p><p>　　1.4 參考資料4</p><p>　　1.5 任務(wù)完成的一般過程4</p><p>　　1.6 軟件配置5</p><p>　　2 個人的構(gòu)思與創(chuàng)意5</p><p><b

4、>　　2.1 構(gòu)思5</b></p><p><b>　　2.2 特色5</b></p><p>　　3 用貪心算法解決活動安排的問題的實驗及其結(jié)果分析5</p><p>　　3.1 貪心算法簡介5</p><p>　　3.2 貪心算法思路6</p><p>　　3.3

5、 貪心算法實現(xiàn)6</p><p>　　3.4 算法結(jié)果7</p><p>　　3.4.1 實驗結(jié)果8</p><p>　　3.4.2 結(jié)果分析8</p><p>　　3.5 算法分析9</p><p>　　3.5.1 關(guān)鍵代碼及解釋9</p><p>　　3.5.2 算法流程圖10

6、</p><p>　　3.5.3 時間復(fù)雜度分析11</p><p>　　4 實驗個人小結(jié)11</p><p>　　4.1總體實驗分析總結(jié)11</p><p>　　4.2 個人經(jīng)驗總結(jié)11</p><p>　　4.2.1 收獲11</p><p>　　4.2.2 不足12</p

7、><p><b>　　1課程實驗概述 </b></p><p><b>　　1.1 問題概述</b></p><p>　　設(shè)有n個活動的集合E={1,2，……，n}，其中每個活動都要求使用同一資源，如演講會場等，而在同一時間內(nèi)只有一個活動能使用這一資源。每個活動i都有一個要求使用該資源的起始時間si和一個結(jié)束時間fi，且si&

8、lt;fi。如果選擇了活動i，則它在時間區(qū)間[si,fi]內(nèi)占用資源。若區(qū)間[si,fi]與區(qū)間[sj,fj]不相交，則稱活動i與活動j是相容的。也就是說，當(dāng)si>=fj或者sj>=fi時，活動i與活動j相容?；顒影才艈栴}就是要在所給的活動集合中選出最大的相容活動子集合。</p><p><b>　　1.2 目的與任務(wù)</b></p><p>　　利用貪心

9、算法的性質(zhì)，通過選擇適當(dāng)?shù)呢澬牟呗缘呢澬乃惴ń鉀Q活動安排問題，且能求得活動安排的最優(yōu)解。</p><p><b>　　1.3 開發(fā)環(huán)境</b></p><p>　　平臺：Windows 7； 編程語言：C語言；</p><p><b>　　1.4 參考資料</b></p><p>　　[1]

10、算法設(shè)計與分析（第二版） 王曉東 編著 清華大學(xué)出版社 2011</p><p>　　[2] 標(biāo)準(zhǔn)C語言基礎(chǔ)教程（第四版） [美]Gary J.Bronson 電子工業(yè)出版社 2011</p><p>　　1.5 任務(wù)完成的一般過程</p><p>　　完成過程如下圖1所示：</p><p>　　圖1 任務(wù)完成的一般過程</p>

11、<p><b>　　1.6 軟件配置</b></p><p>　　編程工具：C-Free5.0</p><p>　　2 個人的構(gòu)思與創(chuàng)意</p><p><b>　　2.1 構(gòu)思</b></p><p>　　此次課程設(shè)計的構(gòu)思過程的核心是：貪心算法并不總能求得問題的整體最優(yōu)解。但對于活

12、動安排問題，貪心算法卻總能求得的整體最優(yōu)解，即它最終所確定的相容活動集合A的規(guī)模最大。因此，這個方向非常明確，就是用貪心算法解決活動安排問題。</p><p>　　首先，貪心算法最大的難度在于選擇貪心策略，只要選擇正確的貪心策略就能通過貪心算法求得最優(yōu)解，對于活動安排，以選擇結(jié)束時間最早的活動為貪心策略是可以得到最優(yōu)解的。</p><p>　　其次，既然是按照一定的順序來選擇活動，那么必將

13、先要對活動按結(jié)束時間遞增進(jìn)行排序，因為排序后，編寫貪心算法程序會變得十分簡潔。</p><p>　　最后，在對所有活動進(jìn)行選擇完畢后，要程序中顯示選擇結(jié)果，以確實是否正確。</p><p><b>　　2.2 特色</b></p><p>　　本次編程，個人覺得最大的特色就是把貪心選擇算法程序和結(jié)果顯示程序分離開成單獨的模塊，這樣會使得貪心選擇

14、算法變得更加簡潔易懂，便于瀏覽閱讀。</p><p>　　其次，在界面設(shè)計上，為了讓前后銜接的更加美觀，也設(shè)置的兩個表格，以便顯示輸入是的活動表和排序后的活動表，這樣可以很直觀的看出此次設(shè)計的運行過程。</p><p>　　再者，我是通過設(shè)置全局變量，一次賦值或者排序后都可以在所有函數(shù)中調(diào)用，這也使得個模塊的連接更加簡單，沒有復(fù)雜的地址調(diào)用，是代碼更具易讀性。</p><

15、;p>　　3 用貪心算法解決活動安排的問題的實驗及其結(jié)果分析</p><p>　　3.1 貪心算法簡介</p><p>　　貪心算法（又稱貪婪算法）是指，在對問題求解時，總是做出在當(dāng)前看來是最好的選擇。也就是說，不從整體最優(yōu)上加以考慮，他所做出的僅是在某種意義上的局部最優(yōu)解。貪心算法不是對所有問題都能得到整體最優(yōu)解，但對范圍相當(dāng)廣泛的許多問題他能產(chǎn)生整體最優(yōu)解或者是整體最優(yōu)解的近似解

16、。</p><p>　　3.2 貪心算法思路</p><p>　　活動安排運用貪心算法的思路為，盡可能多的使更多的事件得到資源的安排。按這種方法選擇相容活動為未安排活動留下盡可能多的時間。也就是說，該算法的貪心選擇的意義是使剩余的可安排時間段極大化，以便安排盡可能多的相容活動。實現(xiàn)方法是在滿足相容的條件下，使結(jié)束時間靠前的活動得到資源，這樣就為后續(xù)時間留下更多的安排時間，以使更多的活動得到

17、安排。</p><p>　　3.3 貪心算法實現(xiàn)</p><p>　　貪心算法并不總能求得問題的整體最優(yōu)解。但對于活動安排問題，貪心算法卻總能求得的整體最優(yōu)解，即它最終所確定的相容活動集合A的規(guī)模最大。這個結(jié)論可以用數(shù)學(xué)歸納法證明。事實上，設(shè)E=｛1，2，...，n｝為所給的活動集合。由于E中活動按結(jié)束時間的非減序列排列，故活動1具有最早的完成時間。首先證明活動安排問題有一個最優(yōu)解以貪心選

18、擇開始，即該最優(yōu)解中包含活動1。設(shè)是所給的活動安排問題的一個最優(yōu)解，且A中活動也按結(jié)束時間非減序排序，A中的第一個活動是活動k。若k=1，則A就是以貪心選擇開始的最優(yōu)解；若k>1，則設(shè)。由于f1fk，且A中活動是相容的。又由于B中活動個數(shù)與A中活動個數(shù)相同，且A是最優(yōu)的，故B也是最優(yōu)的。由此可見，此貪心策略能得到最優(yōu)解。</p><p>　　由于貪心算法解決安排問題要考慮么個活動的結(jié)束時間，所以先將活動按照

19、結(jié)束時間長短進(jìn)行遞增排序。本貪心算法在處理非減序排列活動隊列時可以達(dá)到極高的效率。</p><p>　　例：設(shè)待安排的11個活動的開始時間和結(jié)束時間按結(jié)束時間的非減序排列如下：</p><p>　　表1 已排序活動安排</p><p>　　貪心算法的計算過程如下圖所示。圖中每行相應(yīng)于算法的一次迭代。陰影長條表示的活動是已選入集合A的活動，而空白長條表示的活動是當(dāng)前

20、正在檢查相容性的活動。</p><p>　　圖2貪心算法的計算過程圖</p><p>　　若被檢查的活動i的開始時間Si小于最近選擇的活動j的結(jié)束時間fi，則不選擇活動i，否則選擇活動i加入集合A中。</p><p><b>　　3.4 算法結(jié)果</b></p><p>　　若所需安排的活動為：</p>&

21、lt;p><b>　　表2 活動安排</b></p><p>　　3.4.1 實驗結(jié)果</p><p><b>　　圖3 運行結(jié)果</b></p><p>　　3.4.2 結(jié)果分析</p><p>　　首先對以上數(shù)據(jù)以結(jié)束時間遞增順序進(jìn)行排序得到以下隊列：</p><p

22、>　　表3 對數(shù)據(jù)以結(jié)束時間遞增順序進(jìn)行排序得到的隊列</p><p>　　然后按照貪心算法取結(jié)束時間提前的活動以為后續(xù)活動提供更多時間，同時在保證選擇的活動的結(jié)束時間提前還要保證該活動與前一個活動相容。依次選擇的活動為2、4、8、10。</p><p><b>　　3.5 算法分析</b></p><p>　　3.5.1 關(guān)鍵代碼及解釋

23、</p><p>　　void greedySelect(int n)//活動的貪心選擇 </p><p><b>　　{</b></p><p>　　a[num[1]]=true;</p><p><b>　　int j=1;</b></p><p>　　for(int i

24、=2;i<=n;i++)</p><p>　　if(s[i]>=f[j])</p><p><b>　　{</b></p><p>　　a[num[i]]=true;</p><p><b>　　j=i;</b></p><p><b>　　}</

25、b></p><p><b>　　else</b></p><p>　　a[num[i]]=false; </p><p><b>　　}</b></p><p>　　這是整個貪心算法的核心，一個for循環(huán)，根據(jù)已經(jīng)選擇的貪心策略，對活動進(jìn)行選擇，其中布爾型數(shù)組a[]用與保存活動是否被選

26、擇，若被選擇則保存為true，否則保存為false。</p><p>　　void greedySort(int n)//將活動按結(jié)束時間遞增排序 </p><p><b>　　{</b></p><p>　　int i,j,m;</p><p>　　for(i=1;i<=n;i++)</p><

27、;p>　　for(j=i;j<=n-1;j++)</p><p>　　if(f[j]>f[j+1])</p><p><b>　　{</b></p><p><b>　　m=f[j];</b></p><p>　　f[j]=f[j+1];</p><p>&

28、lt;b>　　f[j+1]=m;</b></p><p><b>　　m=s[j];</b></p><p>　　s[j]=s[j+1];</p><p><b>　　s[j+1]=m;</b></p><p><b>　　m=num[j];</b></

29、p><p>　　num[j]=num[j+1];</p><p>　　num[j+1]=m;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　這是一個排序函數(shù)，這是也算法的主要部分，因為此貪心算法的貪心策略為：選擇結(jié)束時間最早

30、的活動；所以為了讓核心算法更簡便更容易進(jìn)行，首先對活動按結(jié)束時間遞增排序。主要是通過冒泡排序。</p><p>　　3.5.2 算法流程圖</p><p>　　核心算法流程圖如圖4所示：</p><p><b>　　圖4 算法流程圖</b></p><p>　　3.5.3 時間復(fù)雜度分析</p><p

31、>　　貪心算法的效率極高，當(dāng)輸入的活動已按結(jié)束時間的非減序排列，算法只需O(n)的時間安排n個活動，使最多的活動能相容地使用公共資源。如果所給出的活動未按非減序排列，只需要對隊列進(jìn)行遞增排序，最簡只要用O(nlogn)的時間。</p><p><b>　　4 實驗個人小結(jié)</b></p><p>　　4.1總體實驗分析總結(jié)</p><p>

32、;　　可以看出，在解決一個活動安排的問題是，只需要兩個步驟。一、對活動隊列進(jìn)行排序，二、用貪心算法對隊列進(jìn)行安排。運用貪心算法只要很少的時間便能實現(xiàn)地問題的解決。貪心算法貪心算法并不總能求得問題的整體最優(yōu)解。但對于活動安排問題，貪心算法r卻總能求得的整體最優(yōu)解。所以對于某些問題貪心算法可以給出極漂亮的解決。</p><p>　　4.2 個人經(jīng)驗總結(jié)</p><p><b>　　4

33、.2.1 收獲</b></p><p>　　通過對活動安排問題的分析和最終解決這個問題，我確實學(xué)到了不少東西。在這個過程中，我了解到貪心算法貪心算法并不總能求得問題的整體最優(yōu)解。但對于活動安排問題，貪心算法r卻總能求得的整體最優(yōu)解。所以對于某些問題貪心算法可以給出極漂亮的解決。不僅如此，我還知道，不同的貪心選擇策略會導(dǎo)致不同的結(jié)果，而結(jié)果可能是最優(yōu)也可能不是最優(yōu)的，使我進(jìn)一步了解了貪心算法；</

34、p><p>　　這次課程設(shè)計更多的收獲是：C語言是計算機程序語言的基礎(chǔ)語言，內(nèi)容是比較簡單，但它的實踐操作還是比較強的，平時上機課較少，空閑時間又沒想過去編程，通過這次課程設(shè)計，每一步的實踐操作，提高了自我動手編程的能力，將在課本中許多學(xué)到的知識和很多想法都在編程過程中一一實踐。</p><p><b>　　4.2.2 不足</b></p><p>

35、;　　因為這次是一個人做一個題目，所以在選題方面也會偏向簡單一點的，這對于課程設(shè)計鍛煉個人編程能力的效果大打折扣。其次，因為是單人編程，雖然不用和別人討論，有想法就寫上去，但是少了討論，就很難找到會比自己想法更好更簡單的方法，也不能鍛煉到自己的團隊合作能力，這對于以后參加較大型項目開發(fā)所需的團隊合作能力鍛煉有一定的不好，所以，個人覺得，不管簡單還是難，如果可以，團隊運行是最好的。</p><p>　　個人覺得，這

36、個課程設(shè)計最不好的地方就是缺少對照的貪心策略。本來是有想到要選擇其他貪心策略（比如以選擇最早開始的活動的策略、以選擇活動持續(xù)時間最短的策略等等）進(jìn)行比較實驗的，但是因為自己怕麻煩，所以沒有這樣做，這是非常不好的，這使得這個課程設(shè)計顯得比較平凡，特色不大。</p><p>　　我覺得我對C語言的掌握還是不夠熟悉的，因為在這次編程中沒能用到比較高級的數(shù)據(jù)結(jié)構(gòu)（比如棧，隊列等等），只是用C語言的一些較為簡單的基礎(chǔ)語法等