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

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

1、1.引言：貪心法是一種改進(jìn)了的分級(jí)處理方法。用貪心法設(shè)計(jì)算法的特點(diǎn)是一步一步地進(jìn)行，每一步上都要保證能獲得局部最優(yōu)解。每一步只考慮一個(gè)數(shù)據(jù)，它的選取滿足局部?jī)?yōu)化條件。若下一個(gè)數(shù)據(jù)與部分最優(yōu)解連在一起不再是可行解時(shí)，就不把該數(shù)據(jù)添加到部分解中，直到把所有數(shù)據(jù)枚舉完，或者不能再添加為止。這種能夠得到某種度量意義下的最優(yōu)解的分級(jí)處理方法稱為貪心法。貪心算法總是做出在當(dāng)前看來(lái)是最優(yōu)的選擇，也就是說(shuō)貪心算法并不是從整體上加以考慮，它所做出的選擇只是在某種意義上的局部最優(yōu)解，而許多問(wèn)題自身的特性決定了該題運(yùn)用貪心算法可

2、以得到最優(yōu)解或較優(yōu)解。2.貪心算法的基本思想及存在問(wèn)題貪心法的基本思想：從問(wèn)題的某一個(gè)初始解出發(fā)逐步逼近給定的目標(biāo)，以盡可能快的地求得更好的解。當(dāng)達(dá)到某算法中的某一步不能再繼續(xù)前進(jìn)時(shí)，算法停止。1.建立數(shù)學(xué)模型來(lái)描述問(wèn)題。　　2.把求解的問(wèn)題分成若干個(gè)子問(wèn)題。　　3.對(duì)每一子問(wèn)題求解，得到子問(wèn)題的局部最優(yōu)解?！　?.把子問(wèn)題的解局部最優(yōu)解合成原來(lái)解問(wèn)題的一個(gè)解。3.活動(dòng)安排問(wèn)題：3.1貪心算法解決活動(dòng)安排問(wèn)題學(xué)校舉辦活動(dòng)的安排問(wèn)題是用貪心算法有效求解的一個(gè)很好例子。活動(dòng)安排問(wèn)題要求安排一系列爭(zhēng)用某一公共資源

3、的活動(dòng)。用貪心算法可使盡可能多的活動(dòng)能兼容的使用公共資源。設(shè)有n個(gè)活動(dòng)的集合｛0，1，2，…，n-1｝，其中每個(gè)活動(dòng)都要求使用同一資源，如會(huì)場(chǎng)等，而在同一時(shí)間內(nèi)只有一個(gè)活動(dòng)能使用這一資源。每個(gè)活動(dòng)i都有一個(gè)要求使用該資源的起始時(shí)間starti和一個(gè)結(jié)束時(shí)間endi，且starti

4、endj時(shí)，活動(dòng)i與活動(dòng)j相容?；顒?dòng)安排問(wèn)題就是在所給的活動(dòng)集合中選出最大的相容子活動(dòng)集合。設(shè)各活動(dòng)的起始時(shí)間和結(jié)束時(shí)間存儲(chǔ)于數(shù)組start[]和end[]中，不失一般性，假設(shè)結(jié)束時(shí)間安非遞減排列：end[0]≤end[1]≤…≤end[n-1]。算法中用集合a來(lái)存儲(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

5、0≤i

6、依次檢查活動(dòng)i是否與當(dāng)前已選擇的所有活動(dòng)相容。如相容則安排活動(dòng)i，否則不安排活動(dòng)i，再繼續(xù)檢查下一活動(dòng)與所有已選擇活動(dòng)的相容性。由于k是當(dāng)前已選擇活動(dòng)的最大結(jié)束時(shí)間，故活動(dòng)i與當(dāng)前所有選擇活動(dòng)相容的充分且必要條件是其開(kāi)始時(shí)間start[i]不早于最近選擇的活動(dòng)j的結(jié)束時(shí)間end[j]，即start[i]≥end[j]。若活動(dòng)i滿足此條件，則活動(dòng)i被選擇，因而取代活動(dòng)j的位置。由于活動(dòng)是以其完成時(shí)間的非減序排列的，所以算法每次總是選擇具有最早完成時(shí)間的相容活動(dòng)i。這種方法選擇相容活動(dòng)就使剩余活動(dòng)留下盡可能多的

7、時(shí)間。也就是該算法的貪心選擇的意義是使剩余的可安排時(shí)間段極大化，以便安排盡可能多的相容活動(dòng)。3.2活動(dòng)安排實(shí)例設(shè)待安排的11個(gè)活動(dòng)的開(kāi)始時(shí)間和結(jié)束時(shí)間按結(jié)束時(shí)間的非減序排列如下：i1234567891011Starti130535688212Endi4567891011121314算法的計(jì)算過(guò)程如下圖所示。圖中每行相應(yīng)于算法的一次迭代。陰影長(zhǎng)條表示的活動(dòng)是已選入集合的活動(dòng)，而空白長(zhǎng)條表示的活動(dòng)是當(dāng)前正在檢查相容性的活動(dòng)。若被檢查的活動(dòng)i的開(kāi)始時(shí)間starti小于最近選擇的活動(dòng)j的結(jié)束時(shí)間endj，則不選擇活

8、動(dòng)i，否則選擇活動(dòng)i加入集合中。選擇的活動(dòng)有：1，4，8和11。6.結(jié)束語(yǔ)?貪心策略是指從問(wèn)題的初始狀態(tài)出發(fā)，通過(guò)若干次的貪心選擇而得出最優(yōu)值(或較優(yōu)解)的一種解題方法，本文通過(guò)活動(dòng)安排問(wèn)題這一經(jīng)典案例對(duì)貪心算法進(jìn)行簡(jiǎn)要分析，利用圖表給出較直觀實(shí)例，得到了貪心算法是一種高效算法的結(jié)論。