奮斗貪心算法

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