第五章 貪心算法

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

第五章貪心算法2本章大綱貪心法活動選擇問題3最優(yōu)化問題貪心算法可用來解決最優(yōu)化問題。最優(yōu)化問題：給出一個問題的實例，一組約束條件和目標(biāo)函數(shù)，找到一個可行的解決方案，對于給定的實例為目標(biāo)函數(shù)的最優(yōu)值。可行的解決方案滿足問題的約束條件。解決方案中要詳細(xì)說明約束條件中的限制因素。例：在背包問題中，我們要求背包中所有物件的質(zhì)量總和不能超過所能承受的最大重量。4貪心法：基本原理貪心法是設(shè)計算法中另一種常用的策略，就像分治法、回溯法和動態(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è)計好的貪心算法的過程中，找到一個合適的貪心選擇準(zhǔn)則是很關(guān)鍵的。不同的貪心準(zhǔn)則會導(dǎo)致不同的結(jié)果。

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

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

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

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

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

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

n個元素的活動集合S={a1

,…,an}，其中ai

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

f1

f2…fn16動態(tài)選擇問題：實例有9個活動的集合:很多實施方案:{a1

,a3

,a6

,a8

},{a1

,a3

,a7

,a9

},{a1

,a3

,a6

,a9

},{a2

,a5

,a7

,a9

},{a1

,a5

,a7

,a8

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

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

我們假設(shè):f1

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

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

存儲一個解決方案,讓

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

表示上一個被添加的活動 fori=2ton

//選擇下一個活動ifsi

≥fj

//ai

是兼容的

A=A

{ai}

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

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

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

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

a1

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

a1

A,證明完成。

如果

a1

A,我們需要證明

A*=A–{a}+{a1}是另一個最優(yōu)方案包括a1,而a是在A中某個有最早結(jié)束時間的活動.在算法中，活動根據(jù)結(jié)束時間進行分類。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,我們得到另一個最優(yōu)方案A*

，它包括a1，

A*是最優(yōu)的因為|A*|=|A|.24證明貪心活動選擇的最優(yōu)性(2)法則:貪心活動選擇是最優(yōu)的,也就是說,對于每一個活動選擇問題都能得到一個最優(yōu)解決方案。證明:讓算法選擇活動

a1

。

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

，si

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

B

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

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

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

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

A–{a1}也是

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

我們需要求A–{a1}是問題

S*={ai

S|si

f1

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