算法設(shè)計(jì)與分析 課件 第五章 貪心法 5.2.1 活動(dòng)安排問(wèn)題

計(jì)算機(jī)算法設(shè)計(jì)與分析第5章貪心法5.2.1活動(dòng)安排問(wèn)題學(xué)校有n個(gè)分工會(huì)需要進(jìn)行節(jié)目彩排活動(dòng)安排，學(xué)校彩排舞臺(tái)只有一個(gè)。每個(gè)分工會(huì)都有自己的一個(gè)空閑時(shí)間段，即每個(gè)分工會(huì)都給出自己可以進(jìn)行彩排活動(dòng)的一個(gè)起始時(shí)間和結(jié)束時(shí)間。而學(xué)校的舞臺(tái)同一時(shí)間只能安排一個(gè)分工會(huì)入場(chǎng)進(jìn)行活動(dòng)。如何安排這次彩排活動(dòng)，使得被安排的分工會(huì)盡可能多，沒(méi)有能安排的分工會(huì)只能放到下次安排?；顒?dòng)安排問(wèn)題設(shè)學(xué)校分工會(huì)節(jié)目彩排活動(dòng)編號(hào)的集合為E={1,2,...,n}，第i個(gè)分工會(huì)節(jié)目彩排活動(dòng)的起始時(shí)間為si，結(jié)束時(shí)間為fi，且si<fi。如果安排了第i個(gè)分工會(huì)進(jìn)行彩排，則它在半開(kāi)時(shí)間區(qū)間[si，fi)內(nèi)占用舞臺(tái)資源。當(dāng)兩個(gè)活動(dòng)區(qū)間[si，fi)與[sj，fj)不相交，則稱活動(dòng)i和活動(dòng)j是相容的，即si≥fj或sj≥fi，i≠j，活動(dòng)i和活動(dòng)j相容?；顒?dòng)安排問(wèn)題是求解兩兩相容的最大活動(dòng)子集S?；顒?dòng)安排問(wèn)題分工會(huì)i1234567891011起始時(shí)間si130535688212結(jié)束時(shí)間fi4567891011121314貪心策略1：更早的活動(dòng)起始時(shí)間優(yōu)先策略，這樣可以增大舞臺(tái)資源利用率。按照活動(dòng)的起始時(shí)間先后順序選擇活動(dòng)。如表所示的11個(gè)活動(dòng)，先安排活動(dòng)3，則活動(dòng)1、2、4、5、6、10與活動(dòng)3均不相容；之后安排與活動(dòng)3相容的具有更早起始時(shí)間的活動(dòng)7，則活動(dòng)8、9與活動(dòng)7均不相容；之后安排與活動(dòng)7相容的具有更早起始時(shí)間的活動(dòng)11，安排結(jié)束。貪心策略1安排的相容活動(dòng)集合S={3,7,11}。分工會(huì)i1234567891011起始時(shí)間si130535688212結(jié)束時(shí)間fi4567891011121314活動(dòng)安排問(wèn)題貪心策略2：更早的活動(dòng)結(jié)束時(shí)間優(yōu)先策略，這樣可以下一個(gè)活動(dòng)盡早得到安排。按照活動(dòng)結(jié)束時(shí)間從小到大順序選擇活動(dòng)，表中的活動(dòng)已經(jīng)按活動(dòng)結(jié)束時(shí)間順序從小到大排序。選擇活動(dòng)1，之后選擇與活動(dòng)1相容活動(dòng)4，之后選擇與活動(dòng)4相容的活動(dòng)8，最后選擇與活動(dòng)8相容的活動(dòng)11，安排結(jié)束。貪心策略2安排的相容活動(dòng)集合S={1,4,8,11}。分工會(huì)i1234567891011起始時(shí)間si130535688212結(jié)束時(shí)間fi4567891011121314活動(dòng)安排問(wèn)題活動(dòng)安排問(wèn)題貪心策略2的正確性證明：將n個(gè)活動(dòng)按照其結(jié)束時(shí)間fi從小到大排序，排序后的活動(dòng)序列還是按E={1,2,...,n}編號(hào)。第一次先選1號(hào)活動(dòng)，然后接下來(lái)的每一步，從E中按順序選出下一個(gè)相容的活動(dòng)，直到E中所有活動(dòng)都被檢查過(guò)一遍。證明貪心策略2能得到活動(dòng)安排問(wèn)題的最優(yōu)解，即考察如下問(wèn)題：該算法執(zhí)行到第k步時(shí)，選擇了k個(gè)活動(dòng)：i1,i2,...,ik，則存在最優(yōu)解S包含這k個(gè)活動(dòng)，即該算法執(zhí)行的每一步的結(jié)果都是最優(yōu)解的一部分。活動(dòng)安排問(wèn)題（1）設(shè)S是E的一個(gè)最優(yōu)解且S={i1,...,im}。若最優(yōu)解S的第一個(gè)活動(dòng)i1≠1，由于活動(dòng)1的結(jié)束時(shí)間是活動(dòng)集合E中最前面的，因此

。這樣，就將S中的i1換成1，得到S'：

由于

，因此S'中的活動(dòng)也是相容的，而且活動(dòng)數(shù)量與S中一致，故S'也是一個(gè)最優(yōu)解。也即E中的第1步選擇活動(dòng)1肯定可以在一個(gè)最優(yōu)解中?；顒?dòng)安排問(wèn)題（2）采用數(shù)學(xué)歸納法證明，若第k步選擇的活動(dòng)ik在最優(yōu)解中，則第k+1步選擇的活動(dòng)ik+1也在最優(yōu)解中。歸納假設(shè)第

k步選擇的活動(dòng)ik在最優(yōu)解中，可以表述為：前

k

步已經(jīng)選擇的活為i1,i2,...,ik，存在一個(gè)最優(yōu)解S：第k+1步時(shí)，選擇只能在待選活動(dòng)集合E'中選取，所謂待選活動(dòng)集合，即原集合E中去除已判為沖突的活動(dòng)和已選擇的活動(dòng)后剩下的集合?；顒?dòng)安排問(wèn)題①那么，B是E'（子問(wèn)題）的一個(gè)最優(yōu)解。若不是，假設(shè)E'的有解是B*，且B*>B，那么用B*替換B以后得到

，則S'>S，與S是最優(yōu)解矛盾。故

②根據(jù)（1）的證明，貪心策略2的第一步選擇結(jié)束時(shí)間最早的活動(dòng)總是導(dǎo)致問(wèn)題的一個(gè)最優(yōu)解，故對(duì)于子問(wèn)題E'存在一個(gè)最優(yōu)解B'，包含子問(wèn)題E'的第一個(gè)活動(dòng)ik+1。因B'和B都是E'的最優(yōu)解,B'=B，所以：S'和S是包含的活動(dòng)數(shù)量一樣的原問(wèn)題的最優(yōu)解，因此得證第k+1步選擇的活動(dòng)ik+1在最優(yōu)解中。即按貪心策略2進(jìn)行選擇的活動(dòng)必將導(dǎo)