第五章 貪心算法

高級(jí)算法設(shè)計(jì)與分析

第五章貪心算法2本章大綱貪心法活動(dòng)選擇問(wèn)題3最優(yōu)化問(wèn)題貪心算法可用來(lái)解決最優(yōu)化問(wèn)題。最優(yōu)化問(wèn)題：給出一個(gè)問(wèn)題的實(shí)例，一組約束條件和目標(biāo)函數(shù)，找到一個(gè)可行的解決方案，對(duì)于給定的實(shí)例為目標(biāo)函數(shù)的最優(yōu)值?？尚械慕鉀Q方案滿足問(wèn)題的約束條件。解決方案中要詳細(xì)說(shuō)明約束條件中的限制因素。例：在背包問(wèn)題中，我們要求背包中所有物件的質(zhì)量總和不能超過(guò)所能承受的最大重量。4貪心法：基本原理貪心法是設(shè)計(jì)算法中另一種常用的策略，就像分治法、回溯法和動(dòng)態(tài)規(guī)劃算法一樣。經(jīng)典貪心算法基本思想：遵循某些貪心準(zhǔn)則，在當(dāng)前狀態(tài)下做出局部最優(yōu)選擇。這被稱為貪心選擇。我們希望能夠從局部最優(yōu)解中推導(dǎo)出全局最優(yōu)解。貪心選擇屬性：局部最優(yōu)解導(dǎo)出全局最優(yōu)解。在設(shè)計(jì)好的貪心算法的過(guò)程中，找到一個(gè)合適的貪心選擇準(zhǔn)則是很關(guān)鍵的。不同的貪心準(zhǔn)則會(huì)導(dǎo)致不同的結(jié)果。

5貪心法：不足盡管貪心算法能夠得出可行的解決方案，但它得出的可能不總是最優(yōu)解。因此需要證明對(duì)于任何有效的輸入，貪心算法總能找到最優(yōu)解。然而為了反駁貪心算法不能得出最優(yōu)解這種觀點(diǎn)，我們需要反例。60/1背包問(wèn)題假定

：背包能夠承受的重量C>0,N個(gè)物件分別有重量為wi>0，價(jià)值分別為

pi>0fori=1,…n,指出一個(gè)子集A{1,2,…,n}滿足以下公式：這個(gè)問(wèn)題已有的解決方案：回溯法動(dòng)態(tài)規(guī)劃貪心法70/1背包問(wèn)題：貪心法解決方案得到局部最優(yōu)選擇有一些可能的貪心選擇準(zhǔn)則：最大價(jià)值優(yōu)先：選擇可用價(jià)值最高的物件放入背包中。最小重量?jī)?yōu)先：選擇可用重量最小的物件放入背包中。最大重量?jī)?yōu)先：選擇可用重量最大的物件放入背包中。最大性價(jià)比優(yōu)先：選擇可用的、價(jià)值重量比最高的物件放入背包中。不盡人意的是，以上方法沒(méi)有一種能保證是最優(yōu)解決方案——我們能夠找到每一種方案的反例。8選擇準(zhǔn)則：最大價(jià)值優(yōu)先——反例有三個(gè)物件，背包的可承受重量為25：5lb$7010lb$90$140C=25lb

25lbitem1item2item3Knapsack貪心解決方案25lb$140最佳方案10lb5lb$7010lb$90=$140=$1609選擇準(zhǔn)則：最小重量?jī)?yōu)先——反例有三個(gè)物件，背包的可承受重量為30：5lb$15010lb$60$140C=30lb

20lbitem1item2item3Knapsack貪心方案5lb5lb20lb$150$1405lb10lb$60$150最優(yōu)方案=$210=$29010選擇準(zhǔn)則：最大重量?jī)?yōu)先——反例有三個(gè)物件，背包的可承受重量為30：5lb$15010lb$60$140C=30lb

20lbitem1item2item3Knapsack貪心方案5lb5lb20lb$150$14020lb10lb$60$140最優(yōu)方案=$200=$29011選擇準(zhǔn)則：最高性價(jià)比優(yōu)先——反例有三個(gè)物件，背包的可承受重量為30：5lb$50C=30lb5lb5lb20lbitem1$14020lbitem2Knapsack貪心方案10lb20lb$50$140$140$60最優(yōu)方案v/w:$10v/w:$6v/w:$710lb$60item3=$190=$20012背包問(wèn)題的貪心算法對(duì)于0/1背包問(wèn)題沒(méi)有最好的貪心算法。但是對(duì)于部分背包問(wèn)題有最優(yōu)的貪心算法，就是以最大價(jià)值重量比優(yōu)先為基礎(chǔ)的選擇準(zhǔn)則。這種貪心算法的原理如下：根據(jù)價(jià)值/重量比降序排列所有物件。根據(jù)順序依次將這些物件添加到背包中直到?jīng)]有更多的物件或者下一個(gè)物件添加后會(huì)超出背包的承受范圍。如果背包還是沒(méi)有超出承受重量，用未選擇的部分物件填滿它。13更多關(guān)于貪心算法一個(gè)最優(yōu)化問(wèn)題能找到最佳的貪心算法時(shí)，他通常在其他的解決方案中有一些優(yōu)點(diǎn)（例如動(dòng)態(tài)規(guī)劃和回溯）：在尋找局部最優(yōu)解選擇時(shí)通常更有效率。通常易于實(shí)施。14活動(dòng)選擇問(wèn)題：一個(gè)活動(dòng)實(shí)例假設(shè)你在迪士尼主題樂(lè)園，你買(mǎi)了特殊的快速通道票，使得等待游玩項(xiàng)目時(shí)間最短。（兩個(gè)娛樂(lè)設(shè)施之間的快速通道）有很多搭乘車次，每一車次的開(kāi)始和到達(dá)時(shí)間都不同。假設(shè)我們忽略搭乘時(shí)步行和車等待你上車的時(shí)間，也就是說(shuō)在兩趟車次之間趕車的時(shí)間忽略不計(jì)。問(wèn)題：如何讓你盡可能地玩到更多的項(xiàng)目。這就關(guān)于活動(dòng)選擇問(wèn)題。15動(dòng)態(tài)選擇問(wèn)題：定義問(wèn)題:給定一個(gè)

n個(gè)元素的活動(dòng)集合S={a1

,…,an}，其中ai

的時(shí)間間隔[si,fi),si表示開(kāi)始時(shí)間，fi時(shí)間表示結(jié)束時(shí)間，找到一個(gè)最大的兼容子集?；顒?dòng)之間的時(shí)間沒(méi)有重疊表示活動(dòng)之間是兼容的。不失一般性，我們假設(shè)：

f1

f2…fn16動(dòng)態(tài)選擇問(wèn)題：實(shí)例有9個(gè)活動(dòng)的集合:很多實(shí)施方案:{a1

,a3

,a6

,a8

},{a1

,a3

,a7

,a9

},{a1

,a3

,a6

,a9

},{a2

,a5

,a7

,a9

},{a1

,a5

,a7

,a8

},……17活動(dòng)選擇:貪心選擇有幾個(gè)直觀合理的貪心選擇值得考慮：最早開(kāi)始時(shí)間優(yōu)先:選擇一個(gè)最早開(kāi)始時(shí)間的可兼容活動(dòng)最小持續(xù)時(shí)間優(yōu)先:選擇一個(gè)最小時(shí)間間隔的可兼容活動(dòng)。最早完成時(shí)間優(yōu)先:選擇一個(gè)最早結(jié)束時(shí)間的可兼容活動(dòng)問(wèn)題:哪一個(gè)會(huì)有效？18反例1貪心選擇準(zhǔn)則：最早開(kāi)始時(shí)間優(yōu)先時(shí)間0123456789101112131415015141115活動(dòng)12319反例2貪心選擇準(zhǔn)則：最小間隔時(shí)間優(yōu)先時(shí)間01234567891011121314151879815活動(dòng)12320反例3貪心選擇準(zhǔn)則：最早結(jié)束時(shí)間優(yōu)先時(shí)間012345678910111213141502143711153102121113活動(dòng)123456721反例4貪心選擇準(zhǔn)則:最早結(jié)束時(shí)間優(yōu)先此準(zhǔn)則對(duì)這個(gè)例子也使用。需要證明這個(gè)貪心算法的正確性。22活動(dòng)選擇：一個(gè)貪心算法

首先我們更多的以公式的形式表示這個(gè)算法（最早結(jié)束時(shí)間基準(zhǔn)），然后證明它的正確性。

我們假設(shè):f1

f2…fn貪心活動(dòng)選擇(s,f)//s=(s1,…,sn)，

f=(f1,…,fn) n=s.length//活動(dòng)的數(shù)量 A={a1}//A

存儲(chǔ)一個(gè)解決方案,讓

a1=(s1,f1)為第一個(gè) j=1//aj

表示上一個(gè)被添加的活動(dòng) fori=2ton

//選擇下一個(gè)活動(dòng)ifsi

≥fj

//ai

是兼容的

A=A

{ai}

j=i//保存上一個(gè)被添加的活動(dòng) returnA運(yùn)行時(shí)間:(n)當(dāng)包括排序時(shí)間時(shí)為

(nlogn)23證明貪心活動(dòng)選擇的最優(yōu)性(1)論點(diǎn):a1

在所有的活動(dòng)中有最早結(jié)束時(shí)間,則先選擇

a1是一個(gè)最佳的方案。證明:A為最優(yōu)方案。讓活動(dòng)

a1

成為貪心選擇(i即為最早選擇的一個(gè)).如果

a1

A,證明完成。

如果

a1

A,我們需要證明

A*=A–{a}+{a1}是另一個(gè)最優(yōu)方案包括a1,而a是在A中某個(gè)有最早結(jié)束時(shí)間的活動(dòng).在算法中，活動(dòng)根據(jù)結(jié)束時(shí)間進(jìn)行分類。f(a1)

f(a).如果f(a1)

s(a)我們可以添加a1到

A,表明A不是最優(yōu)的.如果

s(a)<f(a1),則a1和

a重疊.f(a1)

f(a),如果我們移除a

并且添加a1,我們得到另一個(gè)最優(yōu)方案A*

，它包括a1，

A*是最優(yōu)的因?yàn)閨A*|=|A|.24證明貪心活動(dòng)選擇的最優(yōu)性(2)法則:貪心活動(dòng)選擇是最優(yōu)的,也就是說(shuō),對(duì)于每一個(gè)活動(dòng)選擇問(wèn)題都能得到一個(gè)最優(yōu)解決方案。證明:讓算法選擇活動(dòng)

a1

。

S*為活動(dòng)的子集且不與a1重疊。S*={ai|i=2,…,n

，si

f(a1)}.讓B為S*的一個(gè)最優(yōu)解決方案.根據(jù)S*的定義,A*={a1}

B

是兼容的,而且是原始問(wèn)題的一個(gè)解決方案.25證明貪心活動(dòng)選擇的最優(yōu)性(3)證明法則(續(xù)):我們可以得出A*是一個(gè)最優(yōu)解決方案是矛盾的.假設(shè)

A*不是原始問(wèn)題的最優(yōu)方案。

讓A是一個(gè)包含a1的最優(yōu)解決方案。

因此|A*|<|A|,|A–{a1}|>|A*–{a1}|=|B|.但是

A–{a1}也是

S*這個(gè)問(wèn)題的一個(gè)方案,和B是S*一個(gè)最優(yōu)方案的假設(shè)相矛盾。這就表明A*必須是原始問(wèn)題的一個(gè)最優(yōu)方案.26活動(dòng)選擇:最優(yōu)子結(jié)構(gòu)假設(shè)a1是最佳方案A中的活動(dòng)，并且有最早的完成時(shí)間，則

我們需要求A–{a1}是問(wèn)題

S*={ai

S|si

f1

}的另一個(gè)最佳解決方案。換句話說(shuō):一旦第一個(gè)活動(dòng)被選擇,該問(wèn)題就可轉(zhuǎn)變?yōu)椋簽榛顒?dòng)選擇找到一個(gè)最優(yōu)的解