貪心算法實(shí)例.ppt

《貪心算法實(shí)例.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、數(shù)學(xué)建模競(jìng)賽中十類常用算法1.蒙特卡羅算法。該算法又稱隨機(jī)性模擬算法，是通過(guò)計(jì)算機(jī)仿真來(lái)解決問(wèn)題的算法，同時(shí)可以通過(guò)模擬來(lái)檢驗(yàn)自己模型的正確性。2.數(shù)據(jù)擬合、參數(shù)估計(jì)、插值等數(shù)據(jù)處理算法。比賽中通常會(huì)遇到大量的數(shù)據(jù)需要處理，而處理數(shù)據(jù)的關(guān)鍵就在于這些算法，通常使用MATLAB作為工具。13.線性規(guī)劃、整數(shù)規(guī)劃、多元規(guī)劃、二次規(guī)劃等規(guī)劃類算法。建模競(jìng)賽大多數(shù)問(wèn)題屬于最優(yōu)化問(wèn)題，很多時(shí)候這些問(wèn)題可以用數(shù)學(xué)規(guī)劃算法來(lái)描述，通常使用Lingo軟件求解。4.圖論算法。這類算法可以分為很多種，包括最短路、網(wǎng)絡(luò)流、二分圖等算法，涉及到圖論的問(wèn)題可以用這些方法解

2、決。5.動(dòng)態(tài)規(guī)劃、回溯搜索、分治算法、分支定界等計(jì)算機(jī)算法。這些算法是算法設(shè)計(jì)中比較常用的方法，競(jìng)賽中很多場(chǎng)合會(huì)用到。26.最優(yōu)化理論的三大非經(jīng)典算法：模擬退火算法、神經(jīng)網(wǎng)絡(luò)算法、遺傳算法。這些問(wèn)題是用來(lái)解決一些較困難的最優(yōu)化問(wèn)題的，對(duì)于有些問(wèn)題非常有幫助，但是算法的實(shí)現(xiàn)比較困難，需慎重使用。7.網(wǎng)格算法和窮舉法。兩者都是暴力搜索最優(yōu)點(diǎn)的算法，在很多競(jìng)賽題中有應(yīng)用，當(dāng)重點(diǎn)討論模型本身而輕視算法的時(shí)候，可以使用這種暴力方案，最好使用一些高級(jí)語(yǔ)言作為編程工具。8.一些連續(xù)數(shù)據(jù)離散化方法。很多問(wèn)題都是實(shí)際來(lái)的，數(shù)據(jù)可以是連續(xù)的，而計(jì)算機(jī)只能處理離散的數(shù)

3、據(jù)，因此將其離散化后進(jìn)行差分代替微分、求和代替積分等思想是非常重要的。39.數(shù)值分析算法。如果在比賽中采用高級(jí)語(yǔ)言進(jìn)行編程的話，那些數(shù)值分析中常用的算法比如方程組求解、矩陣運(yùn)算、函數(shù)積分等算法就需要額外編寫庫(kù)函數(shù)進(jìn)行調(diào)用。10.圖象處理算法。賽題中有一類問(wèn)題與圖形有關(guān)，即使問(wèn)題與圖形無(wú)關(guān)，論文中也會(huì)需要圖片來(lái)說(shuō)明問(wèn)題，這些圖形如何展示以及如何處理就是需要解決的問(wèn)題，通常使用MATLAB進(jìn)行處理。4貪心算法5有下面幾種面值的硬幣：一元、五角、一角、五分、一分，假設(shè)要付給顧客2.89元的零錢，要求用最少的硬幣。問(wèn)題引入：6顧名思義，貪心算法總是作出在

4、當(dāng)前看來(lái)最好的選擇。也就是說(shuō)貪心算法并不從整體最優(yōu)考慮，它所作出的選擇只是在某種意義上的局部最優(yōu)選擇。當(dāng)然，希望貪心算法得到的最終結(jié)果也是整體最優(yōu)的。雖然貪心算法不能對(duì)所有問(wèn)題都得到整體最優(yōu)解，但對(duì)許多問(wèn)題它能產(chǎn)生整體最優(yōu)解。如單源最短路經(jīng)問(wèn)題，最小生成樹問(wèn)題等。在一些情況下，即使貪心算法不能得到整體最優(yōu)解，其最終結(jié)果卻是最優(yōu)解的很好近似。7主要知識(shí)點(diǎn)：活動(dòng)安排問(wèn)題背包問(wèn)題最優(yōu)裝載單源最短路徑最小生成樹8活動(dòng)安排問(wèn)題活動(dòng)安排問(wèn)題就是要在所給的活動(dòng)集合中選出最大的相容活動(dòng)子集合，是可以用貪心算法有效求解的很好例子。該問(wèn)題要求高效地安排一系列爭(zhēng)用某一

5、公共資源的活動(dòng)。貪心算法提供了一個(gè)簡(jiǎn)單、漂亮的方法使得盡可能多的活動(dòng)能兼容地使用公共資源。9活動(dòng)安排問(wèn)題設(shè)有n個(gè)活動(dòng)的集合E={1,2,…,n}，其中每個(gè)活動(dòng)都要求使用同一資源，如演講會(huì)場(chǎng)等，而在同一時(shí)間內(nèi)只有一個(gè)活動(dòng)能使用這一資源。每個(gè)活動(dòng)i都有一個(gè)要求使用該資源的起始時(shí)間si和一個(gè)結(jié)束時(shí)間fi,且si

6、題的貪心算法greedySelector:intgreedySelector(ints[],intf[],booleana[]){intn=s.length-1;a[1]=true;intj=1;intcount=1;for(inti=2;i<=n;i++){if(s[i]>=f[j]){a[i]=true;j=i;count++;}elsea[i]=false;}returncount;}各活動(dòng)的起始時(shí)間和結(jié)束時(shí)間存儲(chǔ)于數(shù)組s和f中且按結(jié)束時(shí)間的非減序排列11活動(dòng)安排問(wèn)題例：設(shè)待安排的11個(gè)活動(dòng)的開始時(shí)間和結(jié)束時(shí)間按結(jié)束時(shí)間的非減序排列如下：i

7、1234567891011S[i]130535688212f[i]456789101112131412活動(dòng)安排問(wèn)題若被檢查的活動(dòng)i的開始時(shí)間Si小于最近選擇的活動(dòng)j的結(jié)束時(shí)間fi，則不選擇活動(dòng)i，否則選擇活動(dòng)i加入集合A中。貪心算法并不總能求得問(wèn)題的整體最優(yōu)解。但對(duì)于活動(dòng)安排問(wèn)題，貪心算法greedySelector卻總能求得的整體最優(yōu)解，即它最終所確定的相容活動(dòng)集合A的規(guī)模最大。這個(gè)結(jié)論可以用數(shù)學(xué)歸納法證明。13給定n種物品和一個(gè)背包。物品i的重量是Wi，其價(jià)值為Vi，背包的容量為C。應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價(jià)值最大?（

8、假定物品可以分割成更小部分，亦即物品可以部分裝入）背包問(wèn)題14例：有5件物品，背包的容量為100，物品的重量和價(jià)值分別如下所示：1234