中國數(shù)學(xué)建模-編程交流-貪婪算法_1

ID:14206633

大?。?05.00 KB

頁數(shù):24頁

時間:2018-07-26

中國數(shù)學(xué)建模-編程交流-貪婪算法_1_第1頁
中國數(shù)學(xué)建模-編程交流-貪婪算法_1_第2頁
中國數(shù)學(xué)建模-編程交流-貪婪算法_1_第3頁
中國數(shù)學(xué)建模-編程交流-貪婪算法_1_第4頁
中國數(shù)學(xué)建模-編程交流-貪婪算法_1_第5頁
資源描述:

《中國數(shù)學(xué)建模-編程交流-貪婪算法_1》由會員上傳分享,免費在線閱讀,更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、中國數(shù)學(xué)建模-編程交流-貪婪算法_1.txt如果我窮得還剩下一碗飯我也會讓你先吃飽全天下最好的東西都應(yīng)該歸我所有,包括你!!  先說喜歡我能死啊?別鬧,聽話?! ∮斜臼履憔驼疹櫤米约?,不然就老老實實地讓我來照顧你!  中國數(shù)學(xué)建模-編程交流-貪婪算法貪婪算法第1章貪婪算法雖然設(shè)計一個好的求解算法更像是一門藝術(shù),而不像是技術(shù),但仍然存在一些行之有效的能夠用于解決許多問題的算法設(shè)計方法,你可以使用這些方法來設(shè)計算法,并觀察這些算法是如何工作的。一般情況下,為了獲得較好的性能,必須對算法進行細致的調(diào)整。但是在某些情況下,算法經(jīng)過調(diào)整之后性能仍無法達到要求,這時就必須尋求另外的方法

2、來求解該問題。本章首先引入最優(yōu)化的概念,然后介紹一種直觀的問題求解方法:貪婪算法。最后,應(yīng)用該算法給出貨箱裝船問題、背包問題、拓撲排序問題、二分覆蓋問題、最短路徑問題、最小代價生成樹等問題的求解方案。1.1最優(yōu)化問題本章及后續(xù)章節(jié)中的許多例子都是最優(yōu)化問題(optimizationproblem),每個最優(yōu)化問題都包含一組限制條件(constraint)和一個優(yōu)化函數(shù)(optimizationfunction),符合限制條件的問題求解方案稱為可行解(feasiblesolution),使優(yōu)化函數(shù)取得最佳值的可行解稱為最優(yōu)解(optimalsolution)。例1-1[渴嬰問

3、題]有一個非??实?、聰明的小嬰兒,她可能得到的東西包括一杯水、一桶牛奶、多罐不同種類的果汁、許多不同的裝在瓶子或罐子中的蘇打水,即嬰兒可得到n種不同的飲料。根據(jù)以前關(guān)于這n種飲料的不同體驗,此嬰兒知道這其中某些飲料更合自己的胃口,因此,嬰兒采取如下方法為每一種飲料賦予一個滿意度值:飲用1盎司第i種飲料,對它作出相對評價,將一個數(shù)值si作為滿意度賦予第i種飲料。通常,這個嬰兒都會盡量飲用具有最大滿意度值的飲料來最大限度地滿足她解渴的需要,但是不幸的是:具有最大滿意度值的飲料有時并沒有足夠的量來滿足此嬰兒解渴的需要。設(shè)ai是第i種飲料的總量(以盎司為單位),而此嬰兒需要t盎司的

4、飲料來解渴,那么,需要飲用n種不同的飲料各多少量才能滿足嬰兒解渴的需求呢?設(shè)各種飲料的滿意度已知。令xi為嬰兒將要飲用的第i種飲料的量,則需要解決的問題是:找到一組實數(shù)xi(1≤i≤n),使nåi=1sixi最大,并滿足:nåi=1xi=t及0≤xi≤ai。需要指出的是:如果nåi=1ai

5、數(shù))。輸出:實數(shù)xi(1≤i≤n),使nåi=1sixi最大且nåi=1xi=t(0≤xi≤ai)。如果nåi=1ai

6、載重量為c,我們的目的是在貨船上裝入最多的貨物。這個問題可以作為最優(yōu)化問題進行描述:設(shè)存在一組變量xi,其可能取值為0或1。如xi為0,則貨箱i將不被裝上船;如xi為1,則貨箱i將被裝上船。我們的目的是找到一組xi,使它滿足限制條件nåi=1wixi≤c且xiÎ{0,1},1≤i≤n。相應(yīng)的優(yōu)化函數(shù)是nåi=1xi。滿足限制條件的每一組xi都是一個可行解,能使nåi=1xi取得最大值的方案是最優(yōu)解。例1-3[最小代價通訊網(wǎng)絡(luò)]城市及城市之間所有可能的通信連接可被視作一個無向圖,圖的每條邊都被賦予一個權(quán)值,權(quán)值表示建成由這條邊所

7、表示的通信連接所要付出的代價。包含圖中所有頂點(城市)的連通子圖都是一個可行解。設(shè)所有的權(quán)值都非負,則所有可能的可行解都可表示成無向圖的一組生成樹,而最優(yōu)解是其中具有最小代價的生成樹。在這個問題中,需要選擇一個無向圖中的邊集合的子集,這個子集必須滿足如下限制條件:所有的邊構(gòu)成一個生成樹。而優(yōu)化函數(shù)是子集中所有邊的權(quán)值之和。----------------------------------------------1.2算法思想在貪婪算法(greedymethod)中采用逐步構(gòu)造最優(yōu)解的方法。在每個階段,都作出一個看

當(dāng)前文檔最多預(yù)覽五頁,下載文檔查看全文

此文檔下載收益歸作者所有

當(dāng)前文檔最多預(yù)覽五頁,下載文檔查看全文
溫馨提示:
1. 部分包含數(shù)學(xué)公式或PPT動畫的文件,查看預(yù)覽時可能會顯示錯亂或異常,文件下載后無此問題,請放心下載。
2. 本文檔由用戶上傳,版權(quán)歸屬用戶,天天文庫負責(zé)整理代發(fā)布。如果您對本文檔版權(quán)有爭議請及時聯(lián)系客服。
3. 下載前請仔細閱讀文檔內(nèi)容,確認文檔內(nèi)容符合您的需求后進行下載,若出現(xiàn)內(nèi)容與標(biāo)題不符可向本站投訴處理。
4. 下載文檔時可能由于網(wǎng)絡(luò)波動等原因無法下載或下載錯誤,付費完成后未能成功下載的用戶請聯(lián)系客服處理。
关闭