資源描述:
《中國(guó)數(shù)學(xué)建模-編程交流-貪婪算法_1》由會(huì)員上傳分享,免費(fèi)在線閱讀,更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。
1、中國(guó)數(shù)學(xué)建模-編程交流-貪婪算法貪婪算法第1章貪婪算法雖然設(shè)計(jì)一個(gè)好的求解算法更像是一門(mén)藝術(shù),而不像是技術(shù),但仍然存在一些行之有效的能夠用于解決許多問(wèn)題的算法設(shè)計(jì)方法,你可以使用這些方法來(lái)設(shè)計(jì)算法,并觀察這些算法是如何工作的。一般情況下,為了獲得較好的性能,必須對(duì)算法進(jìn)行細(xì)致的調(diào)整。但是在某些情況下,算法經(jīng)過(guò)調(diào)整之后性能仍無(wú)法達(dá)到要求,這時(shí)就必須尋求另外的方法來(lái)求解該問(wèn)題。本章首先引入最優(yōu)化的概念,然后介紹一種直觀的問(wèn)題求解方法:貪婪算法。最后,應(yīng)用該算法給出貨箱裝船問(wèn)題、背包問(wèn)題、拓?fù)渑判騿?wèn)題、二分覆蓋問(wèn)題、最短
2、路徑問(wèn)題、最小代價(jià)生成樹(shù)等問(wèn)題的求解方案。1.1最優(yōu)化問(wèn)題本章及后續(xù)章節(jié)中的許多例子都是最優(yōu)化問(wèn)題(optimizationproblem),每個(gè)最優(yōu)化問(wèn)題都包含一組限制條件(constraint)和一個(gè)優(yōu)化函數(shù)(optimizationfunction),符合限制條件的問(wèn)題求解方案稱(chēng)為可行解(feasiblesolution),使優(yōu)化函數(shù)取得最佳值的可行解稱(chēng)為最優(yōu)解(optimalsolution)。例1-1[渴嬰問(wèn)題]有一個(gè)非常渴的、聰明的小嬰兒,她可能得到的東西包括一杯水、一桶牛奶、多罐不同種類(lèi)的果汁、許多不
3、同的裝在瓶子或罐子中的蘇打水,即嬰兒可得到n種不同的飲料。根據(jù)以前關(guān)于這n種飲料的不同體驗(yàn),此嬰兒知道這其中某些飲料更合自己的胃口,因此,嬰兒采取如下方法為每一種飲料賦予一個(gè)滿(mǎn)意度值:飲用1盎司第i種飲料,對(duì)它作出相對(duì)評(píng)價(jià),將一個(gè)數(shù)值si作為滿(mǎn)意度賦予第i種飲料。通常,這個(gè)嬰兒都會(huì)盡量飲用具有最大滿(mǎn)意度值的飲料來(lái)最大限度地滿(mǎn)足她解渴的需要,但是不幸的是:具有最大滿(mǎn)意度值的飲料有時(shí)并沒(méi)有足夠的量來(lái)滿(mǎn)足此嬰兒解渴的需要。設(shè)ai是第i種飲料的總量(以盎司為單位),而此嬰兒需要t盎司的飲料來(lái)解渴,那么,需要飲用n種不同的飲
4、料各多少量才能滿(mǎn)足嬰兒解渴的需求呢?設(shè)各種飲料的滿(mǎn)意度已知。令xi為嬰兒將要飲用的第i種飲料的量,則需要解決的問(wèn)題是:找到一組實(shí)數(shù)xi(1≤i≤n),使nåi=1sixi最大,并滿(mǎn)足:nåi=1xi=t及0≤xi≤ai。需要指出的是:如果nåi=1ai
5、,t、si、ai為正實(shí)數(shù))。輸出:實(shí)數(shù)xi(1≤i≤n),使nåi=1sixi最大且nåi=1xi=t(0≤xi≤ai)。如果nåi=1ai
6、一樣,但貨箱的重量都各不相同。設(shè)第i個(gè)貨箱的重量為wi(1≤i≤n),而貨船的最大載重量為c,我們的目的是在貨船上裝入最多的貨物。這個(gè)問(wèn)題可以作為最優(yōu)化問(wèn)題進(jìn)行描述:設(shè)存在一組變量xi,其可能取值為0或1。如xi為0,則貨箱i將不被裝上船;如xi為1,則貨箱i將被裝上船。我們的目的是找到一組xi,使它滿(mǎn)足限制條件nåi=1wixi≤c且xiÎ{0,1},1≤i≤n。相應(yīng)的優(yōu)化函數(shù)是nåi=1xi。滿(mǎn)足限制條件的每一組xi都是一個(gè)可行解,能使nåi=1xi取得最大值的方
7、案是最優(yōu)解。例1-3[最小代價(jià)通訊網(wǎng)絡(luò)]城市及城市之間所有可能的通信連接可被視作一個(gè)無(wú)向圖,圖的每條邊都被賦予一個(gè)權(quán)值,權(quán)值表示建成由這條邊所表示的通信連接所要付出的代價(jià)。包含圖中所有頂點(diǎn)(城市)的連通子圖都是一個(gè)可行解。設(shè)所有的權(quán)值都非負(fù),則所有可能的可行解都可表示成無(wú)向圖的一組生成樹(shù),而最優(yōu)解是其中具有最小代價(jià)的生成樹(shù)。在這個(gè)問(wèn)題中,需要選擇一個(gè)無(wú)向圖中的邊集合的子集,這個(gè)子集必須滿(mǎn)足如下限制條件:所有的邊構(gòu)成一個(gè)生成樹(shù)。而優(yōu)化函數(shù)是子集中所有邊的權(quán)值之和。---------------------------
8、-------------------1.2算法思想在貪婪算法(greedymethod)中采用逐步構(gòu)造最優(yōu)解的方法。在每個(gè)階段,都作出一個(gè)看上去最優(yōu)的決策(在一定的標(biāo)準(zhǔn)下)。決策一旦作出,就不可再更改。作出貪婪決策的依據(jù)稱(chēng)為貪婪準(zhǔn)則(greedycriterion)。例1-4[找零錢(qián)]一個(gè)小孩買(mǎi)了價(jià)值少于1美元的糖,并將1美元的錢(qián)交給售貨員。售貨員希望用數(shù)