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

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

2、blem solving heuristic of making the locally optimal choice at each stage with the hope of finding the global optimum. This article through the greedy algorithm of the classic case-activities problems, describes the greedy algorithm the basic ideas and possible problems, and briefly introduces the a

3、dvantages and characteristics of the algorithm, and finally gives several classic the greedy algorithm.Keywords： greedy algorithm、the locally optimal choice引言:貪心法是一種改進(jìn)了的分級處理方法。用貪心法設(shè)計(jì)算法的特點(diǎn)是一步一步地進(jìn)行，每一 步上都要保證能獲得局部最優(yōu)解。每一步只考慮一個(gè)數(shù)據(jù)，它的選取滿足局部優(yōu)化條件。若 下一個(gè)數(shù)據(jù)與部分最優(yōu)解連在一起不再是可行解時(shí)，就不把該數(shù)據(jù)添加到部分解中，直到把 所有數(shù)據(jù)枚舉完，或者不能再添加為止。這

4、種能夠得到某種度量意義下的最優(yōu)解的分級處理 方法稱為貪心法。其實(shí)，從貪心”一詞我們便可以看出，貪心算法總是做出在當(dāng)前看來是最優(yōu)的選擇，也就 是說貪心算法并不是從整體上加以考慮，它所做出的選擇只是在某種意義上的局部最優(yōu)解， 而許多問題自身的特性決定了該題運(yùn)用貪心算法可以得到最優(yōu)解或較優(yōu)解。許多可以用貪 心算法求解的問題一般具有貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)，貪心選擇性質(zhì)是指所求問題的整體 最優(yōu)解包含著局部最優(yōu)的選擇，對于一個(gè)具體問題，關(guān)鍵是證明或驗(yàn)證每一步所作的貪心選 擇最終將導(dǎo)致問題的一個(gè)整體最優(yōu)解。貪心算法的基本思想及存在問題2.1貪心法的基本思想：從問題的某一個(gè)初始解出發(fā)逐步逼近給定的目標(biāo)，以盡

5、可能快的地求得更好的解。當(dāng)達(dá)到 某算法中的某一步不能再繼續(xù)前進(jìn)時(shí)，算法停止。建立數(shù)學(xué)模型來描述問題。把求解的問題分成若干個(gè)子問題。對每一子問題求解，得到子問題的局部最優(yōu)解。把子問題的解局部最優(yōu)解合成原來解問題的一個(gè)解。2.2該算法存在問題：不能保證求得的最后解是最佳的；不能用來求最大或最小解問題；只能求滿足某些約束條件的可行解的范圍?；顒?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，其中

6、每個(gè)活動(dòng)都要求使用同一資源，如會場 等，而在同一時(shí)間內(nèi)只有一個(gè)活動(dòng)能使用這一資源。每個(gè)活動(dòng)i都有一個(gè)要求使用該資源的 起始時(shí)間starti和一個(gè)結(jié)束時(shí)間endi，且startiendi。如選擇了活動(dòng)i，則它在半開時(shí)間區(qū)間 starti,endi）內(nèi)占用資源。若區(qū)間starti,endi）與區(qū)間startj,endj）不相交，稱活動(dòng)i與活動(dòng)j是 相容的。也就是說，當(dāng)startjendi或startiAendj時(shí)，活動(dòng)i與活動(dòng)j相容?；顒?dòng)安排 問題就是在所給的活動(dòng)集合中選出最大的相容子活動(dòng)集合。在下面所給出的解活動(dòng)安排問題的貪心算法中，設(shè)各活動(dòng)的起始時(shí)間和結(jié)束時(shí)間存儲于數(shù) 組start：和end中

7、，不失一般性，假設(shè)結(jié)束時(shí)間安非遞減排列：end0 Wend1 WW endn-1。算法中用集合a來存儲所選擇的活動(dòng)?；顒?dòng)i被選擇當(dāng)且僅當(dāng)ai的值為true。 變量j記錄最近一次選擇的活動(dòng)。設(shè)j是當(dāng)前最近選擇的活動(dòng)，也就是所選擇的活動(dòng)中編號 最大的活動(dòng)，即：j=maxi|0Wi0，則我們設(shè)b=a-kU0。由于end0 Wendk，且a中活動(dòng)是互為相容的， 故b中的活動(dòng)也是互為相容的。又由于b中的活動(dòng)個(gè)數(shù)與a中活動(dòng)個(gè)數(shù)相同，且a是最優(yōu)的， 故b也是最優(yōu)的。也就是說b是一個(gè)以貪心選擇活動(dòng)0開始的最優(yōu)活動(dòng)安排。因此，證明了 總存在一個(gè)以貪心選擇開始的最優(yōu)活動(dòng)安排方案，也就是算法具有貪心選擇性質(zhì)。4貪心算法解決活動(dòng)安排問題的好處運(yùn)用該算法解決活動(dòng)安排問題的效率極高。當(dāng)輸入的活動(dòng)已按結(jié)束時(shí)間的非減序排列，算法 只需O（n）的時(shí)間安排n個(gè)活動(dòng)，使最多的活動(dòng)能相容地使用公共資源。如果所給出的活動(dòng) 未按非減序排列，可以用O（nlogn）的時(shí)間重排。幾種經(jīng)典的貪心算法庫魯斯卡爾（Kruskal）算法普林（Prim）算法戴克斯德拉（Dijkstra）算法結(jié)束語貪心策略是指從問題的初始狀態(tài)出發(fā)，通過若干次