貪心算法解決活動(dòng)安排問題報(bào)告

《貪心算法解決活動(dòng)安排問題報(bào)告》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、貪心算法解決活動(dòng)安排問題金瀟UsethegreedyalgorithmtosolvethearrangementforactivitiesJinxiao摘要：貪心算法在當(dāng)前來看是最好的選擇。是用利用啟發(fā)式策略，在不從整體最優(yōu)上加以考慮的情況下，來做出局部最優(yōu)選擇的一種算法。本文通過貪心算法的經(jīng)典案例—活動(dòng)安排問題入手，描述了貪心算法的基本思想和可能產(chǎn)生的問題，并簡述該算法的好處和特點(diǎn)，最后給出幾種經(jīng)典的貪心算法。關(guān)鍵字：貪心算法、局部最優(yōu)選擇Abstract:Agreedyalgorithmisanyalgorithmthatfollowstheproblemsolvingheur

2、isticofmakingthelocallyoptimalchoiceateachstagewiththehopeoffindingtheglobaloptimum.Thisarticlethroughthegreedyalgorithmoftheclassiccase--activitiesproblems,describesthegreedyalgorithmthebasicideasandpossibleproblems,andbrieflyintroducestheadvantagesandcharacteristicsofthealgorithm,andfinallyg

3、ivesseveralclassicthegreedyalgorithm.Keywords：greedyalgorithm、thelocallyoptimalchoice1.引言：貪心法是一種改進(jìn)了的分級(jí)處理方法。用貪心法設(shè)計(jì)算法的特點(diǎn)是一步一步地進(jìn)行，每一步上都要保證能獲得局部最優(yōu)解。每一步只考慮一個(gè)數(shù)據(jù)，它的選取滿足局部優(yōu)化條件。若下一個(gè)數(shù)據(jù)與部分最優(yōu)解連在一起不再是可行解時(shí)，就不把該數(shù)據(jù)添加到部分解中，直到把所有數(shù)據(jù)枚舉完，或者不能再添加為止。這種能夠得到某種度量意義下的最優(yōu)解的分級(jí)處理方法稱為貪心法。其實(shí)，從"貪心"一詞我們便可以看出，貪心算法總是做出在當(dāng)前看來是最優(yōu)的選擇

4、，也就是說貪心算法并不是從整體上加以考慮，它所做出的選擇只是在某種意義上的局部最優(yōu)解，而許多問題自身的特性決定了該題運(yùn)用貪心算法可以得到最優(yōu)解或較優(yōu)解。?許多可以用貪心算法求解的問題一般具有貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)，貪心選擇性質(zhì)是指所求問題的整體最優(yōu)解包含著局部最優(yōu)的選擇，對(duì)于一個(gè)具體問題，關(guān)鍵是證明或驗(yàn)證每一步所作的貪心選擇最終將導(dǎo)致問題的一個(gè)整體最優(yōu)解。2.貪心算法的基本思想及存在問題2.1貪心法的基本思想：從問題的某一個(gè)初始解出發(fā)逐步逼近給定的目標(biāo)，以盡可能快的地求得更好的解。當(dāng)達(dá)到某算法中的某一步不能再繼續(xù)前進(jìn)時(shí)，算法停止。1.建立數(shù)學(xué)模型來描述問題?！　?.把求解的問題分

5、成若干個(gè)子問題?！　?.對(duì)每一子問題求解，得到子問題的局部最優(yōu)解?！　?.把子問題的解局部最優(yōu)解合成原來解問題的一個(gè)解。2.2該算法存在問題：1.不能保證求得的最后解是最佳的；2.不能用來求最大或最小解問題；3.只能求滿足某些約束條件的可行解的范圍。3.活動(dòng)安排問題：3.1貪心算法解決活動(dòng)安排問題活動(dòng)安排問題是用貪心算法有效求解的一個(gè)很好例子。活動(dòng)安排問題要求安排一系列爭用某一公共資源的活動(dòng)。用貪心算法可提供一個(gè)簡單、漂亮的方法，使盡可能多的活動(dòng)能兼容的使用公共資源。設(shè)有n個(gè)活動(dòng)的集合｛0，1，2，…，n-1｝，其中每個(gè)活動(dòng)都要求使用同一資源，如會(huì)場等，而在同一時(shí)間內(nèi)只有一個(gè)活動(dòng)能

6、使用這一資源。每個(gè)活動(dòng)i都有一個(gè)要求使用該資源的起始時(shí)間starti和一個(gè)結(jié)束時(shí)間endi，且starti

7、]≤end[1]≤…≤end[n-1]。算法中用集合a來存儲(chǔ)所選擇的活動(dòng)?；顒?dòng)i被選擇當(dāng)且僅當(dāng)a[i]的值為true。變量j記錄最近一次選擇的活動(dòng)。設(shè)j是當(dāng)前最近選擇的活動(dòng)，也就是所選擇的活動(dòng)中編號(hào)最大的活動(dòng)，即：j=max{i

8、0≤i