奮斗貪心算法奮斗貪心算法PAGEPAGE7奮斗貪心算法貪心算法策略貪心算法（又稱貪婪算法）是指，在對問題求解時,總是做出在當前看來是最好的選擇.也就是說，不從整體最優上加以考慮，他所做出的僅是在某種意義上的局部最優解。貪心算法不是對所有問題都能得到整體最優解，但對范圍相當廣泛的許多問題他能產生整體最優解或者是整體最優解的近似解.貪心法的基本思想是從問題的某一個初始解出發逐步逼近給定的目標，以盡可能快的方式求得更好的解。即當達到算法中的某一步不能再繼續前進時，算法停止,得到問題的一個解，該算法有如下特點：(1）不能保證求得的最終解是最佳的；（2)不能用來求最大或最小等有極值要求的問題的解；（3)只能求得滿足某些約束條件的可行解;（4）在當前狀態下一旦選定一個分量，就不再從試其他的可行性；(5）它并不從整體最優上作出考慮，它的選擇只是在貪心準則下的局部最優選擇。因此，使用貪心算法得到的最優解不一定是整體最優的，卻往往是最優解的很好的近似解。在這里需要注意貪心問題的關鍵是貪心準則的選取。對于同一個問題,貪心準則可能不是唯一的，往往其中很多看起來都是可行的。但是根據其中大部分貪心準則所得到的所謂的最優解并不一定是當前問題的最優解。在一般情況下,要選出最優貪心準則并不是一件容易的事。當然，如果能夠確定當前問題的最優貪心準則,那么用貪心算法求解當前問題就會非常有效.可以用貪心算法求解的問題具有一些共同特征.當遇到一個具體問題的時候，需要判斷這種問題應該用什么方法來求解.那么,怎么判斷是否應該用貪心算法來求解這個問題呢；如果是，那么用貪心算法來求解這個問題能否得到最優解呢.只要證明要求解的問題有如下兩個性質：貪心選擇性質和最優結構性質即可解決問題。（1）貪心選擇性質在求解一個問題的過程中，如果在每一階段的選擇都是當前狀態下的最優選擇，即局部最優選擇,并且最終能夠求得問題的整體最優解,那么說明這個問題可以通過貪心選擇求解，這時就說此問題具有貪心選擇性質.根據前面對貪心選擇性質的定義，要證明一個問題具有貪心選擇性質只要證明通過我們每一步所作的貪心選擇使得在最后得到問題的一個整體最優解就可以了。通常采用如下的證明過程:首先假設問題的一個整體最優解，那么第一步要證明可以把這個最優解修改成貪心選擇開始，此時原問題就簡化成為與原問題相似的一個子問題。接下來，使用數學歸納法證明通過每一步的貪心選擇可以得到問題的一個整體最優解。（2）最優子結構性質當一個問題的最優解包含了這個問題的子問題的最優解時，就說這個問題具有最優子問題結構。這個性質決定了一個問題是否可以使用貪心算法來求解。貪心法可以解決一些最優性問題，如：求圖中的最小生成樹、求哈夫曼編碼……對于其他問題，貪心法一般不能得到我們所要求的答案.一旦一個問題可以通過貪心法來解決，那么貪心法一般是解決這個問題的最好辦法.由于貪心法的高效性以及其所求得的答案比較接近最優結果，貪心法也可以用作輔助算法或者直接解決一些要求結果不特別精確的問題。2、登山機器人問題（1）問題描述:登山機器人可以攜帶有限的能量。在登山過程中,登山機器人需要消耗一定能量，連續攀登的路程越長，其攀登的速度就越慢。在對m種不同類型的機器人進行性能測試時,測定出每個機器人連續攀登1，2，…，n米所用的時間。現在要對這m個機器人進行綜合性能測試，舉行機器人接力連續攀登演習。攀登的總高度為s米。規定每個機器人攀登1次，每次至少攀登1米，最多攀登n米，而且每個機器人攀登的高度必須是整數，即只能在整米處接力.安排每個機器人攀登適當的高度,使完成接力攀登的時間最短。(2）設計要求：給定m個登山機器人接力攀登的總高度s，以及每個機器人連續攀登1，2,…，n米所用的時間，計算最優攀登方案。（3）數據輸入：第1行是正整數m，n和s分別表示機器人的個數、每個機器人最多可以攀登的高度和接力攀登的總高度.接下來的m行中，每行有n個正整數，分別表示機器人連續攀登1，2，…,n米所用的時間。（4）數據輸出:輸出登山機器人接力到達終點的最短攀登時間3、算法分析對于登山機器人問題，假設機器人每步走一米,我們進行一米一米的貪吃辦法來算出機器人走過的米數,即步數.由于每個機器人都要走，所以我們先讓每個機器人走一步，將問題縮小，再在剩下的數據里面選出走下一步用時最少的機器人，讓它走一步，進一步縮小問題規模，依次循環直到走完所有的路程,即可求知各個機器人走的步子，即就是走過的路程，對應給出路程的各個機器人的時間疊加起來就得了最短的時間了。算法中的兩個二維數組，data數組用來存放時間數據，a數組用來存放機器人再走一步所用時間間隔和機器人已經走多少米；算法中的函數init（）是用于將數組a賦初值，第一列用于存放機器人再走一步所用時間間隔，第二列用于存放機器人已經走多少米;函數done（）是用于選擇每走一米時間間隔最小的機器人，且不斷更新數組a中的值，直到不滿足所給條件；在主函數main(）中，先定義二維數組data和a，輸入機器人的個數n、每個機器人最多可以攀登的高度k、攀登的總高度m后，用malloc函數分配存儲空間，然后再輸入時間數據;該算法的時間復雜度和空間復雜度:函數init(）的時間復雜度為，函數done（)的時間復雜度為,主函數main（）的時間復雜度為,故該算法的時間復雜度為++=；空間復雜度為。4、總結在實現該算法的過程中，我們發現如果沒有給數組data和數組a分配存儲空間，在程序運行時就會發生錯誤，當用malloc函數分配存儲空間后運行時發生的錯誤便能解決；在選擇時間間隔最小的機器人時，要注意兩個二維數組下標的變化，稍有不慎便會使結果發生錯誤；我們要弄清問題的約束條件，在編寫代碼時如果約束條件不清楚,我們就很難實現該算法。通過對登山機器人問題的解決，我們了解到了《算法設計與分析》課程的重要性，使我們對算法產生了興趣;希望在以后的學習中，我們能夠接觸到更多有關算法的問題,并能夠熟悉掌握各個算法的要點。5、小組成員冷雙:貪心算法策略和編寫文檔張麗娟：搜索資料和分析算法周姍姍：負責代碼編寫陳晶晶：分析算法和總結算法曹思涵:貪心算法策略和總結算法王忠龍：搜索資料和計算時間復雜度6、附件（1）問題源代碼如下：＃include〈stdio.h>＃include〈stdlib.h>＃include<malloc.h〉＃defineMAXINT1000intn,k，m，mint=0； //n：機器人個數，k:每個機器人最多走多少米，m：總路程//每個機器人都先走第一步voidinit(int*＊data，int**a）{ inti； for(i=0；i<n;i++） ｛ a[i］［0］=data［i][2］-data[i][1］; a[i］[1］=1； }｝voiddone(int*＊data,int＊＊a)｛ inti,j,flag； intmin； m—=n; //每個機器人已經走了一米 while（m—-) ｛ //選擇時間間隔最小的機器人 min=a［0]［0］; flag=0; for（i=1;i<n；i++） { if（a[i］［0]〈min&&a[i][1]〈k) ｛ min=a［i］[0］； flag=i; } } a[flag][1]++; //當前最小時間間隔機器人步數加一 if（a［flag]［1]<k） a［flag]［0］=data［flag］［a[flag］［1]+1]—data[flag]［a［flag］［1］］; else a［flag]［0]=MAXINT; ｝ for(i=0;i<n；i++)mint+=data[i］[a［i］［1]］； printf（”最短攀登時間：%d\n”，mint）；｝voidmain(){ //data讀取時間數據，a數組第一列用于存取機器人再走一步所用時間間隔，第二列用于存取機器人已經走多少米 int＊*data,＊*a; inti,j；printf(”輸入機器人的個數n、每個機器人最多可以攀登的高度k、攀登的總高度m:\n"）； scanf（"％d%d％d”，&n,＆k，&m)； //輸入第一行參數 //分配存儲空間 data=(int＊*）malloc（n*sizeof(int＊)）； a=(int*＊）malloc（n*sizeof（int*)）; for（i=0；i<n；i++） { data[i]=（int＊）malloc((k+1）＊sizeof(int)）； a[i]=(int＊）malloc(2*sizeof(int)）; } //輸入時間數據 printf（