貪心算法在活動(dòng)安排中的應(yīng)用研究

劉雷 張永康

摘 要：本文對(duì)活動(dòng)安排問(wèn)題進(jìn)行了討論，提出了不同的活動(dòng)安排策略，并證明了貪心算法在解決該問(wèn)題的優(yōu)越性，并通過(guò)具體的例子進(jìn)行了驗(yàn)證，并給出該算法及對(duì)應(yīng)的時(shí)間復(fù)雜度分析，從而為相關(guān)問(wèn)題的解決給出了一種策略參考。

關(guān)鍵詞：活動(dòng)安排問(wèn)題；貪心算法；局部最優(yōu)解

1 引言

活動(dòng)安排問(wèn)題就是要在所給的活動(dòng)集合中選出最大的相容活動(dòng)子集合，該問(wèn)題要求高效地安排一系列爭(zhēng)用某一公共資源的活動(dòng)。盡管如今計(jì)算機(jī)計(jì)算速度已經(jīng)十分的快，但是對(duì)于近年來(lái)指數(shù)級(jí)增長(zhǎng)的需要處理的數(shù)據(jù)，計(jì)算機(jī)計(jì)算速度的增長(zhǎng)還顯得遠(yuǎn)遠(yuǎn)不夠。因此高效的算法對(duì)于大數(shù)據(jù)的處理顯得格外重要。而貪心算法本身的特點(diǎn)為解決活動(dòng)安排問(wèn)題提供了一種優(yōu)秀的解決方案。

2 方法

2.1 貪心算法及其特點(diǎn)介紹

貪心算法（又稱貪婪算法）是指從當(dāng)前看來(lái)的角度進(jìn)行分析，只是做出對(duì)當(dāng)前來(lái)說(shuō)最好的決策，但并不會(huì)考慮過(guò)去的決策以及對(duì)未來(lái)的影響，是否當(dāng)前的決策會(huì)導(dǎo)致未來(lái)得到最優(yōu)解，這樣通過(guò)每次得到當(dāng)前的最優(yōu)解，最終求得最終的解決方案，但是該方案不一定是全局的最優(yōu)解決方案，但是一定是比較接近最優(yōu)解。

貪心算法的求解過(guò)程：1）從某個(gè)初始的解出發(fā)進(jìn)行問(wèn)題求解。2）采用循環(huán)的方法，每次向最終的求解方向前進(jìn)一步，不斷求出當(dāng)前的最優(yōu)解，直到最終的狀態(tài)。3）新的解建立在原來(lái)的解基礎(chǔ)上，最終得到最終解。

2.2 活動(dòng)安排問(wèn)題求解策略

活動(dòng)安排問(wèn)題可以描述為有n個(gè)活動(dòng)申請(qǐng)使用同一個(gè)禮堂，每個(gè)活動(dòng)都有自己的開(kāi)始活動(dòng)時(shí)間和最終的結(jié)束時(shí)間。希望都?jí)虻玫揭环N安排方案使得盡可能多的活動(dòng)被安排，但是彼此不會(huì)發(fā)生沖突，即每次禮堂只能有一個(gè)活動(dòng)被安排。

假設(shè)m={1，2，...，s}表示被安排的活動(dòng)集合，其中Bi表示活動(dòng)i的開(kāi)始時(shí)間，而Di表示活動(dòng)i的結(jié)束時(shí)間，要保證任意兩個(gè)活動(dòng)i，j相容，即保證DiDj，列出一下三種策略對(duì)問(wèn)題進(jìn)行求解：

策略一：盡早占用的活動(dòng)先安排。

把所有活動(dòng)的開(kāi)始時(shí)間進(jìn)行排序，數(shù)值小的先安排，并且保證被安排的活動(dòng)彼此之前是相容的，最終得到一個(gè)活動(dòng)安排集合。

策略二：根據(jù)時(shí)間占用多少來(lái)安排活動(dòng)。

每個(gè)活動(dòng)都有自己的時(shí)長(zhǎng)，根據(jù)它的時(shí)長(zhǎng)來(lái)進(jìn)行安排。先對(duì)時(shí)長(zhǎng)進(jìn)行排序，時(shí)長(zhǎng)小的活動(dòng)先安排，按照這種策略不斷挑選活動(dòng)，同時(shí)保證活動(dòng)之前彼此是相容的，最終得到一個(gè)活動(dòng)安排集合。

策略三：根據(jù)活動(dòng)結(jié)束時(shí)間來(lái)安排。

每個(gè)活動(dòng)都有自己的結(jié)束時(shí)間，因此根據(jù)結(jié)束時(shí)間來(lái)進(jìn)行排序，結(jié)束時(shí)間早的優(yōu)先安排，都是保證彼此之間的相容性，最終得到一個(gè)活動(dòng)安排集合。

以上三種策略可作為活動(dòng)安排問(wèn)題的求解方案，但是前兩種在某些情況具有較大的局限性，策略一反例：S={1， 2， 3}，a1=<0， 20>， a2=<2， 5>，a3=<8， 15>。

策略二反例S={1， 2， 3}，a1=<0， 8>， a2=<7， 9>， a3=<8， 15>。但策略三因輸入的活動(dòng)以其完成時(shí)間的非減序排列，該方案可以使得每次都是最早結(jié)束的活動(dòng)被安排，使得每次用來(lái)安排其他活動(dòng)的剩余時(shí)間最長(zhǎng)。也就是說(shuō)，該算法的貪心選擇的意義是使剩余的可安排時(shí)間段極大化，以便安排盡可能多的相容活動(dòng)。

2.3 算法實(shí)現(xiàn)

該算法的核心代碼如下：

template

void GreedySelector（int n， Type s[]， Type f[]， bool A[]） {

A[1] = true；

int j = 1；

for （int i=2；i<=n；i++） {

if （s[i]>=f[j]） {

A[i]=true；

j=i；

}

else A[i]=false；

}

}

整個(gè)算法的時(shí)間復(fù)雜度為O（n），預(yù)排序時(shí)間復(fù)雜度為O（nlogn） ，因此該算法具有較低的時(shí)間復(fù)雜度。低復(fù)雜度為大數(shù)據(jù)計(jì)算提供了算法保障。

3 案例應(yīng)用

設(shè)待安排的11個(gè)活動(dòng)的開(kāi)始時(shí)間和結(jié)束時(shí)間按結(jié)束時(shí)間的非減序排列如下：

i 1 2 3 4 5 6 7 8 9 10 11

S[i] 1 3 0 5 3 5 6 6 8 2 12

F[i] 4 5 6 7 8 9 10 11 12 13 14

按照策略一可以安排第3，7，11三個(gè)活動(dòng)，策略二可以安排2，4，11四個(gè)活動(dòng)，策略三可以安排1，4，8，11，可見(jiàn)如果貪心的選擇結(jié)束時(shí)間早的活動(dòng)先安排，可以使安排的相容活動(dòng)個(gè)數(shù)最多。

4 總結(jié)

本文對(duì)活動(dòng)安排問(wèn)題進(jìn)行了探討，論證了貪心算法在求解該問(wèn)題的優(yōu)越性，低復(fù)雜度為求解數(shù)據(jù)較大的問(wèn)題提供了算法支持。但貪心算法并不能對(duì)所有問(wèn)題都得到整體最優(yōu)解，因此對(duì)于不同的問(wèn)題，貪心算法是否能取得最優(yōu)解還需進(jìn)一步探討。

參考文獻(xiàn)

[1]蘇方方，張金玲.貪心算法解決活動(dòng)安排問(wèn)題研究[J].軟件導(dǎo)刊，2011，10（12）：43-44.

[2]劉文強(qiáng)，周波，馬海峰， 等.算法分析與設(shè)計(jì)課程中活動(dòng)安排問(wèn)題的教學(xué)探討[J].高教學(xué)刊，2018，（20）：96-98.

[3]王曉東.計(jì)算機(jī)算法設(shè)計(jì)與分析[M].北京：電子工業(yè)出版社，2007.