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

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

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

由于

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

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

k

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

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

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