算法設(shè)計(jì)與分析 課件 6.3-貪心法應(yīng)用-活動安排問題

信息工程大學(xué)算法設(shè)計(jì)與分析貪心法—活動安排問題國家級實(shí)驗(yàn)教學(xué)示范中心計(jì)算機(jī)學(xué)科組規(guī)劃教材算法設(shè)計(jì)與分析Python案例詳解微課視頻版活動安排問題：

設(shè)有n個活動的集合S={1,2,…,n}，其中每個活動都要求使用同一資源，如教室、會場等，而在同一時間內(nèi)只有一個活動能使用這個資源。si，fi分別為活動i的開始和結(jié)束時間，且si<fi

?；顒觟與j相容

si

fj或sjfi。求：最大的兩兩相容的活動集A。

問題的解需要滿足以下條件：是n個活動的一個子集任何兩個活動都是相容的活動個數(shù)最多活動的屬性：開始時間、結(jié)束時間、持續(xù)時間可能的貪心策略：盡早開始，優(yōu)先安排開始時間早的活動占用時間短，優(yōu)先安排持續(xù)時間短的活動使剩余時間更多，優(yōu)先安排結(jié)束時間早的活動思考：活動安排問題可以用貪心法求解嗎？選擇題。你覺得以下哪種貪心選擇策略可以得到活動安排問題的最優(yōu)解？A.優(yōu)先安排開始時間早的活動B.優(yōu)先安排持續(xù)時間短的活動C.優(yōu)先安排結(jié)束時間早的活動D.以上都不對策略1：優(yōu)先安排開始時間早的活動錯誤該策略得到的解：活動1最優(yōu)解：活動2、活動3策略2：

優(yōu)先安排持續(xù)時間短的活動錯誤該策略得到的解：活動4、5最優(yōu)解：活動1、2、3策略3：優(yōu)先安排結(jié)束時間早的活動問題：該策略對所有實(shí)例都能得到最優(yōu)解嗎？該策略對兩個實(shí)例都得到了最優(yōu)解。

時間復(fù)雜度為O(nlogn)S={1,2,…,n}是活動集，且f1

…

fn

。

定理：算法GreedySelect執(zhí)行到第k步，選擇k項(xiàng)活動i1=1,i2,…,ik，那么存在最優(yōu)解A包含i1=1,i2,…,ik。證明：歸納基礎(chǔ)：k=1,存在最優(yōu)解包含活動1。任取最優(yōu)解A,A中的活動按結(jié)束時間遞增排列。如果A的第一個活動為j，j

1,由于f1

fj，則有A′=(A

{j})

{1}，且A′也是最優(yōu)解，并含有活動1。

j…A1…A’歸納步驟：假設(shè)命題對k為真，證明對k+1也為真。算法執(zhí)行到第k步，選擇了活動i1=1,i2,…,ik，根據(jù)歸納假設(shè)存在最優(yōu)解A包含i1=1,i2,…,ik。

最優(yōu)解A中剩下的活動子集B來自集合S′={i|i

S,si

fk}，且A={i1,i2,…,ik}B。其中B是S′的最優(yōu)解。若不然,設(shè)S′的最優(yōu)解為B*,B*的活動比B多，那么B*

{1,i2,…,ik}是S的最優(yōu)解，且比A的活動多,與A的最優(yōu)性矛盾。待選集合S′1,i2,…,ik不相容活動集BAB*B={ik+1,…}?將S′看做一個子問題，根據(jù)歸納基礎(chǔ)，存在S′的最優(yōu)解B′含有S′中的第一個活動，即ik+1,且|B′|=|B|,于是也是原問題的最優(yōu)解.待選集合S′1,i2,…,ikBB’ik+1活動安