資源描述:
《中國數(shù)學建模-編程交流-貪婪算法new》由會員上傳分享,免費在線閱讀,更多相關內(nèi)容在工程資料-天天文庫。
1、中國數(shù)學建模-編程交流-貪婪算法.txt“我羨慕內(nèi)些老人羨慕他們手牽手一直走到最后。━交話費的時候,才發(fā)現(xiàn)自己的話那么值錢。中國數(shù)學建模-編程交流-貪婪算法第1章貪婪算法雖然設計一個好的求解算法更像是一門藝術,而不像是技術,但仍然存在一些行之有效的能夠用于解決許多問題的算法設計方法,你可以使用這些方法來設計算法,并觀察這些算法是如何工作的。一般情況下,為了獲得較好的性能,必須對算法進行細致的調(diào)整。但是在某些情況下,算法經(jīng)過調(diào)整之后性能仍無法達到要求,這時就必須尋求另外的方法來求解該問題。本章首先引入最優(yōu)化的概念,然后介紹一種直觀
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ù)以前關于這n種飲料的不同體驗,此嬰兒知道這其中某些飲料更合自己的胃口,因此,嬰兒采取如下方法為每一種飲料賦予一個滿意度值:飲用1盎司第i種飲料,對它作出相對評價,將一個數(shù)值si作為滿意度賦予第i種飲料。通常,這個嬰兒都會盡量飲用具有最大滿意度值的飲料來最大限度地滿足她解渴的需要,但是不幸的是:具有最大滿意度值的飲料有時并沒有足夠的量來滿足此嬰兒解渴的需要。設ai是第i種飲料的總量(
4、以盎司為單位),而此嬰兒需要t盎司的飲料來解渴,那么,需要飲用n種不同的飲料各多少量才能滿足嬰兒解渴的需求呢?設各種飲料的滿意度已知。令xi為嬰兒將要飲用的第i種飲料的量,則需要解決的問題是:找到一組實數(shù)xi(1≤i≤n),使nåi=1sixi最大,并滿足:nåi=1xi=t及0≤xi≤ai。需要指出的是:如果nåi=1ai
5、式的描述:輸入:n,t,si,ai(其中1≤i≤n,n為整數(shù),t、si、ai為正實數(shù))。輸出:實數(shù)xi(1≤i≤n),使nåi=1sixi最大且nåi=1xi=t(0≤xi≤ai)。如果nåi=1ai
6、物。所有待裝貨物都裝在貨箱中且所有貨箱的大小都一樣,但貨箱的重量都各不相同。設第i個貨箱的重量為wi(1≤i≤n),而貨船的最大載重量為c,我們的目的是在貨船上裝入最多的貨物。這個問題可以作為最優(yōu)化問題進行描述:設存在一組變量xi,其可能取值為0或1。如xi為0,則貨箱i將不被裝上船;如xi為1,則貨箱i將被裝上船。我們的目的是找到一組xi,使它滿足限制條件nåi=1wixi≤c且xiÎ{0,1},1≤i≤n。相應的優(yōu)化函數(shù)是nåi=1xi。滿足限制條件的每一組xi都是一個可行解,能使n&ar
7、ing;i=1xi取得最大值的方案是最優(yōu)解。例1-3[最小代價通訊網(wǎng)絡]城市及城市之間所有可能的通信連接可被視作一個無向圖,圖的每條邊都被賦予一個權(quán)值,權(quán)值表示建成由這條邊所表示的通信連接所要付出的代價。包含圖中所有頂點(城市)的連通子圖都是一個可行解。設所有的權(quán)值都非負,則所有可能的可行解都可表示成無向圖的一組生成樹,而最優(yōu)解是其中具有最小代價的生成樹。在這個問題中,需要選擇一個無向圖中的邊集合的子集,這個子集必須滿足如下限制條件:所有的邊構(gòu)成一個生成樹。而優(yōu)化函數(shù)是子集中所有邊的權(quán)值之和。------------------
8、----------------------------plot(100+t+15*cos(3.05*t),t=0..200,coords=polar,axes=none,scaling=constrained);1.2算法思想在貪婪算法(greedymetho