貪心算法在活動安排中的應用研究

劉雷 張永康

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

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

1 引言

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

2 方法

2.1 貪心算法及其特點介紹

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

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

2.2 活動安排問題求解策略

活動安排問題可以描述為有n個活動申請使用同一個禮堂，每個活動都有自己的開始活動時間和最終的結(jié)束時間。希望都夠得到一種安排方案使得盡可能多的活動被安排，但是彼此不會發(fā)生沖突，即每次禮堂只能有一個活動被安排。

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

策略一：盡早占用的活動先安排。

把所有活動的開始時間進行排序，數(shù)值小的先安排，并且保證被安排的活動彼此之前是相容的，最終得到一個活動安排集合。

策略二：根據(jù)時間占用多少來安排活動。

每個活動都有自己的時長，根據(jù)它的時長來進行安排。先對時長進行排序，時長小的活動先安排，按照這種策略不斷挑選活動，同時保證活動之前彼此是相容的，最終得到一個活動安排集合。

策略三：根據(jù)活動結(jié)束時間來安排。

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

以上三種策略可作為活動安排問題的求解方案，但是前兩種在某些情況具有較大的局限性，策略一反例：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>。但策略三因輸入的活動以其完成時間的非減序排列，該方案可以使得每次都是最早結(jié)束的活動被安排，使得每次用來安排其他活動的剩余時間最長。也就是說，該算法的貪心選擇的意義是使剩余的可安排時間段極大化，以便安排盡可能多的相容活動。

2.3 算法實現(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；

}

}

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

3 案例應用

設待安排的11個活動的開始時間和結(jié)束時間按結(jié)束時間的非減序排列如下：

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三個活動，策略二可以安排2，4，11四個活動，策略三可以安排1，4，8，11，可見如果貪心的選擇結(jié)束時間早的活動先安排，可以使安排的相容活動個數(shù)最多。

4 總結(jié)

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

參考文獻

[1]蘇方方，張金玲.貪心算法解決活動安排問題研究[J].軟件導刊，2011，10（12）：43-44.

[2]劉文強，周波，馬海峰， 等.算法分析與設計課程中活動安排問題的教學探討[J].高教學刊，2018，（20）：96-98.

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