算法設(shè)計與分析-貪婪算法.doc

ID:56810781

大小:339.00 KB

頁數(shù):88頁

時間:2020-07-12

算法設(shè)計與分析-貪婪算法.doc_第1頁
算法設(shè)計與分析-貪婪算法.doc_第2頁
算法設(shè)計與分析-貪婪算法.doc_第3頁
算法設(shè)計與分析-貪婪算法.doc_第4頁
算法設(shè)計與分析-貪婪算法.doc_第5頁
資源描述:

《算法設(shè)計與分析-貪婪算法.doc》由會員上傳分享,免費在線閱讀,更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫。

1、第1章貪婪算法雖然設(shè)計一個好的求解算法更像是一門藝術(shù),而不像是技術(shù),但仍然存在一些行之有效的能夠用于解決許多問題的算法設(shè)計方法,你可以使用這些方法來設(shè)計算法,并觀察這些算法是如何工作的。一般情況下,為了獲得較好的性能,必須對算法進行細(xì)致的調(diào)整。但是在某些情況下,算法經(jīng)過調(diào)整之后性能仍無法達(dá)到要求,這時就必須尋求另外的方法來求解該問題。本章首先引入最優(yōu)化的概念,然后介紹一種直觀的問題求解方法:貪婪算法。最后,應(yīng)用該算法給出貨箱裝船問題、背包問題、拓?fù)渑判騿栴}、二分覆蓋問題、最短路徑問題、最小代價生成樹等問題的

2、求解方案。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盎司的飲料來解渴,那么,需要飲用n種不同的飲料各多少量才能滿

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

5、1≤i≤n),使n?i=1sixi最大且n?i=1xi=t(0≤xi≤ai)。如果n?i=1ai

6、貨船上裝入最多的貨物。這個問題可以作為最優(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)值都非負(fù),則所有可能的可行解都可表示成無向圖的一組生成樹,而最優(yōu)解是其中具有最小代價的生成樹。在這個問題中,需要選擇一個無向圖中的邊集合的子集,這個子集必須滿足如下限制條件:所有的邊構(gòu)成一個生成樹。而優(yōu)化函數(shù)是子集中所有邊的權(quán)值之和。1.2算法思想在貪婪算法(greedymethod)中采用逐步構(gòu)造最優(yōu)解的方法。在每個階段,都作出一個看上去最優(yōu)的決策(在一定的標(biāo)準(zhǔn)下)。決策一旦作出,就不可再更改。作出貪婪決策的依據(jù)稱為貪婪準(zhǔn)

8、則(greedycriterion)。例1-4[找零錢]一個小孩買了價值少于1美元的糖,并將1美元的錢交給售貨員。售貨員希望用數(shù)目最少的硬幣找給小孩。假設(shè)提供了數(shù)目不限的面值為25美分、10美分、5美分、及1美分的硬幣。售貨員分步驟組成要找的零錢數(shù),每次加入一個硬幣。選擇硬幣時所采用的貪婪準(zhǔn)則如下:每一次選擇應(yīng)使零錢數(shù)盡量增大。為保證解法的可行性(即:所給的零錢等于要找的零錢數(shù)),所選擇的硬幣不應(yīng)使零錢總數(shù)超過最

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

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

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