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

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

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

。活動(dòng)i與j相容

si

fj或sjfi。求：最大的兩兩相容的活動(dòng)集A。

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

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

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

…

fn

。

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

1,由于f1

fj，則有A′=(A

{j})

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

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

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

S,si

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

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