算法導(dǎo)論第十六章——貪心算法

求解最優(yōu)化問題要經(jīng)過一系列步驟戈鲁，每個(gè)步驟中有多種選擇帚称，有時(shí)使用動(dòng)態(tài)規(guī)劃來求解會(huì)十分復(fù)雜，此時(shí)可以使用更高效更簡單的算法蓬痒，如貪心算法泻骤。
貪心算法總是在每一步做出局部最優(yōu)的選擇，寄希望與這樣的選擇能夠達(dá)到全局最優(yōu)解。
貪心算法并不能保證得到最優(yōu)解狱掂，但部分問題使用貪心策略足以達(dá)到最優(yōu)解演痒。

1. 活動(dòng)選擇問題

我們的第一個(gè)例子是一個(gè)調(diào)度競爭共享資源的多個(gè)活動(dòng)的問題，目標(biāo)是選出一個(gè)最大的趋惨，互相兼容的活動(dòng)集合鸟顺。
假定有一個(gè)n個(gè)活動(dòng)的集合 $S={\{a1,a2..an\}}$ ,這些活動(dòng)使用同一個(gè)資源，而這些資源在某個(gè)時(shí)刻只能供一個(gè)活動(dòng)使用器虾。每個(gè)活動(dòng) $a_i$ 都有開始時(shí)間 $s_i$ 和結(jié)束時(shí)間 $f_i$ 诊沪，如果被選中，任務(wù)占據(jù)該資源 $[s_i,fi)$ 期間曾撤。如果兩個(gè)活動(dòng)的區(qū)間不重疊端姚，則稱他們是兼容的。在活動(dòng)選擇問題中挤悉，我們希望選擇出一個(gè)最大兼容活動(dòng)集渐裸。
我們可以通過動(dòng)態(tài)規(guī)劃算法將這個(gè)問題分解為兩個(gè)子問題，然后將兩個(gè)子問題的最優(yōu)解合并為原問題的解装悲。

活動(dòng)選擇問題的最優(yōu)子結(jié)構(gòu)

令 $S_{ij}$ 表示在 $a_i$ 結(jié)束之后開始昏鹃，且在 $a_j$ 開始之前結(jié)束的那些活動(dòng)集合。我們希望求 $S_{ij}$ 的最大兼容子集诀诊。進(jìn)一步洞渤，我們假定 $A_{ij}$ 就是這樣一個(gè)子集，且包含活動(dòng)k属瓣。如此我們便得到兩個(gè)子問題载迄，尋找 $S_{ik}$ 中的兼容活動(dòng)以及尋找 $S_{kj}$ 中的兼容活動(dòng)。即我們可得到 $A_{ij}=A_{ik}∪{\{a_k\}}∪A_{k,j}$
我們用 $c[i,j]$ 表示集合 $S_{ij}$ 的大小抡蛙，則可得到
$c[i,j]=c[i,k]+c[k,j]+1$

貪心選擇

事實(shí)上护昧，對(duì)于活動(dòng)選擇問題，我們無需考慮所有子選擇粗截，只需要考慮一個(gè)選擇:貪心選擇
對(duì)于活動(dòng)選擇問題惋耙，如何貪心選擇？直覺上熊昌，我們應(yīng)該選擇這樣一個(gè)活動(dòng)绽榛，選出它后剩下的資源應(yīng)該被盡可能多的其他任務(wù)利用。現(xiàn)在考慮可選的活動(dòng)婿屹，其中必然有一個(gè)最先結(jié)束灭美，我們應(yīng)該選擇S中最早結(jié)束的活動(dòng)，因?yàn)槭Ｏ碌馁Y源可供他之后盡可能多的活動(dòng)使用选泻。
現(xiàn)在的問題是冲粤，我們的策略是正確的嗎？下面的定理證明了這一點(diǎn)页眯。

考慮任意非空子問題 $S_k$ 梯捕，令 $a_m$ 是 $S_k$ 中最早結(jié)束的活動(dòng)，則 $a_m$ 在 $S_k$ 的最大兼容活動(dòng)子集中窝撵。

證明
令 $A_k$ 是 $S_k$ 中的一個(gè)最大兼容活動(dòng)子集傀顾，且 $a_j$ 是 $A_k$ 中結(jié)束時(shí)間最早的活動(dòng)。若 $a_j=a_m$ ,則已證明 $a_m$ 在 $S_k$ 的最大兼容活動(dòng)子集中碌奉。否則,令集合 $A_{k}^{'} = A_{k}-\{a_j\}∪\{a_m\}$
$A_{k}^{'}$ 中的活動(dòng)都是不相交的短曾，而 $a_m比a_j$ 結(jié)束更早，因此得出 $A_{k}^{'}$ 也是Sk的一個(gè)最大兼容活動(dòng)子集赐劣，且包含 $a_m$

由此得到代碼如下

偽碼描述

2.貪心算法原理

本節(jié)探究貪心算法的一般性質(zhì)嫉拐。
在上一節(jié)設(shè)計(jì)貪心算法的過程比通常繁瑣一些，我們當(dāng)時(shí)經(jīng)過了如下步驟：

設(shè)計(jì)問題的最優(yōu)子結(jié)構(gòu)
設(shè)計(jì)一個(gè)遞歸算法
證明如果我們做出了貪心選擇魁兼，則只剩下一個(gè)子問題婉徘。
證明貪心算法是有效的。
設(shè)計(jì)算法實(shí)現(xiàn)貪心策略咐汞。

一般的盖呼，我們可以根據(jù)如下步驟設(shè)計(jì)貪心算法：

將最優(yōu)化問題轉(zhuǎn)化為:對(duì)其做出一次選擇后，只剩下一個(gè)子問題需要求解
證明做出貪心選擇后化撕，原問題總是存在最優(yōu)解几晤。
證明做出貪心選擇后，剩余的子問題滿足性質(zhì):即最優(yōu)解與貪心選擇組合即可得到原問題的最優(yōu)解植阴。

問題的關(guān)鍵在于貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)

貪心選擇性質(zhì)
當(dāng)進(jìn)行選擇時(shí)蟹瘾，我們直接做出在當(dāng)前問題中看來最優(yōu)的選擇，而不必考慮子問題的解掠手。
我們必須證明每個(gè)步驟做出貪心選擇能生成全局最優(yōu)解热芹，這種證明通常首先考察某個(gè)子問題的最優(yōu)解，然后用貪心選擇替換某個(gè)其他選擇來修改此解惨撇，從而得到一個(gè)相似但更小的子問題伊脓。

最后編輯于：2020.11.14 09:47:17

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者

人面猴
序言：七十年代末，一起剝皮案震驚了整個(gè)濱河市魁衙，隨后出現(xiàn)的幾起案子报腔，更是在濱河造成了極大的恐慌，老刑警劉巖剖淀，帶你破解...
沈念sama閱讀 221,820評(píng)論 6贊 515
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件纯蛾，死亡現(xiàn)場離奇詭異，居然都是意外死亡纵隔，警方通過查閱死者的電腦和手機(jī)翻诉，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 94,648評(píng)論 3贊 399
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門炮姨，熙熙樓的掌柜王于貴愁眉苦臉地迎上來，“玉大人碰煌，你說我怎么就攤上這事舒岸。” “怎么了芦圾？”我有些...
開封第一講書人閱讀 168,324評(píng)論 0贊 360
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵蛾派，是天一觀的道長。經(jīng)常有香客問我个少，道長洪乍，這世上最難降的妖魔是什么？我笑而不...
開封第一講書人閱讀 59,714評(píng)論 1贊 297
?港島之戀（遺憾婚禮）
正文為了忘掉前任夜焦，我火速辦了婚禮壳澳，結(jié)果婚禮上，老公的妹妹穿的比我還像新娘茫经。我一直安慰自己钾埂，他們只是感情好，可當(dāng)我...
茶點(diǎn)故事閱讀 68,724評(píng)論 6贊 397
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布科平。她就那樣靜靜地躺著褥紫，像睡著了一般。火紅的嫁衣襯著肌膚如雪瞪慧。梳的紋絲不亂的頭發(fā)上髓考，一...
開封第一講書人閱讀 52,328評(píng)論 1贊 310
城市分裂傳說
那天，我揣著相機(jī)與錄音弃酌，去河邊找鬼氨菇。笑死，一個(gè)胖子當(dāng)著我的面吹牛妓湘，可吹牛的內(nèi)容都是我干的查蓉。我是一名探鬼主播，決...
沈念sama閱讀 40,897評(píng)論 3贊 421
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼榜贴，長吁一口氣：“原來是場噩夢(mèng)啊……” “哼豌研！你這毒婦竟也來了？” 一聲冷哼從身側(cè)響起唬党，我...
開封第一講書人閱讀 39,804評(píng)論 0贊 276
萬榮殺人案實(shí)錄
序言：老撾萬榮一對(duì)情侶失蹤鹃共，失蹤者是張志新（化名）和其女友劉穎，沒想到半個(gè)月后驶拱，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體霜浴，經(jīng)...
沈念sama閱讀 46,345評(píng)論 1贊 318
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 38,431評(píng)論 3贊 340
?白月光啟示錄
正文我和宋清朗相戀三年蓝纲，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了阴孟。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片晌纫。...
茶點(diǎn)故事閱讀 40,561評(píng)論 1贊 352
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡，死狀恐怖永丝，靈堂內(nèi)的尸體忽然破棺而出锹漱，到底是詐尸還是另有隱情，我是刑警寧澤类溢，帶...
沈念sama閱讀 36,238評(píng)論 5贊 350
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布凌蔬，位于F島的核電站露懒，受9級(jí)特大地震影響闯冷，放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜懈词，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 41,928評(píng)論 3贊 334
男人毒藥：我在死后第九天來索命
文/蒙蒙一蛇耀、第九天我趴在偏房一處隱蔽的房頂上張望。院中可真熱鬧坎弯，春花似錦纺涤、人聲如沸。這莊子的主人今日做“春日...
開封第一講書人閱讀 32,417評(píng)論 0贊 24
一樁弒父案撩炊，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽。三九已至崎脉，卻和暖如春拧咳，著一層夾襖步出監(jiān)牢的瞬間，已是汗流浹背囚灼。一陣腳步聲響...
開封第一講書人閱讀 33,528評(píng)論 1贊 272
情欲美人皮
我被黑心中介騙來泰國打工骆膝，沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留，地道東北人灶体。一個(gè)月前我還...
沈念sama閱讀 48,983評(píng)論 3贊 376
代替公主和親
正文我出身青樓阅签，卻偏偏與公主長得像，于是被迫代替她去往敵國和親蝎抽。傳聞我的和親對(duì)象是個(gè)殘疾皇子政钟，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 45,573評(píng)論 2贊 359

算法導(dǎo)論第十六章——貪心算法

1. 活動(dòng)選擇問題

活動(dòng)選擇問題的最優(yōu)子結(jié)構(gòu)

貪心選擇

2.貪心算法原理

推薦閱讀更多精彩內(nèi)容