奮斗貪心算法

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