貪心算法大概是算法世界里最容易被低估的一個(gè)。很多人覺(jué)得它不過(guò)就是“每一步都選最好的”而已聽(tīng)起來(lái)簡(jiǎn)單得像是常識(shí)但真正到了面試、競(jìng)賽或者工程優(yōu)化場(chǎng)景里能不能一眼判斷“這題能不能用貪心”能不能給出讓人信服的正確性證明就完全是另一回事了。我見(jiàn)過(guò)不少同學(xué)動(dòng)態(tài)規(guī)劃推得很溜卻在貪心選擇這一步反復(fù)栽跟頭——不是策略選錯(cuò)就是壓根沒(méi)意識(shí)到這里藏著一個(gè)需要嚴(yán)格論證的坎。這篇內(nèi)容我就想從基礎(chǔ)出發(fā)把貪心算法的本質(zhì)、適用條件、經(jīng)典場(chǎng)景和證明思路串一遍特別把“背包問(wèn)題里貪心為什么有時(shí)靈有時(shí)不靈”這件事講透希望能幫正在學(xué)算法的朋友少走一些彎路。1. 貪心算法的直覺(jué)局部最優(yōu)如何一步步逼近全局最優(yōu)貪心算法的核心思想用一句大白話(huà)說(shuō)就是每一步都做出當(dāng)前狀態(tài)下看起來(lái)最優(yōu)的選擇并且絕不回頭。它不像動(dòng)態(tài)規(guī)劃那樣需要記錄一堆子問(wèn)題的狀態(tài)并做比較也不像回溯搜索那樣走不通就退回來(lái)重試它是一條道走到黑的策略——認(rèn)定一個(gè)規(guī)則每次按這個(gè)規(guī)則挑一個(gè)“局部最優(yōu)解”一路挑到最后把得到的解當(dāng)作全局問(wèn)題的答案。這種直覺(jué)從生活里就能找到大量影子。比如你手里有一堆面額不等的紙幣要給顧客湊出一筆錢(qián)你會(huì)本能地先拿最大面額去湊不夠再拿次大的——這就是貪心。再比如趕時(shí)間做項(xiàng)目手頭有好幾個(gè)任務(wù)每個(gè)任務(wù)有截止時(shí)間和收益你通常會(huì)優(yōu)先做收益最高或者最緊急的那個(gè)——這也是貪心。這些直覺(jué)之所以普遍是因?yàn)槿祟?lèi)在大多數(shù)日常決策中天然傾向于“拿當(dāng)下最有利的選項(xiàng)”懶得去窮舉所有未來(lái)的可能性。但作為算法設(shè)計(jì)者你必須清醒地認(rèn)識(shí)到一個(gè)事實(shí)貪心策略的“短視”既是它的優(yōu)點(diǎn)也是它的死穴。優(yōu)點(diǎn)在于效率奇高——不需要枚舉不需要回溯通常一次遍歷或一次排序就能出結(jié)果時(shí)間復(fù)雜度往往能做到O(n log n)甚至O(n)死穴在于它壓根不考慮“這一步選下去之后后續(xù)的路會(huì)不會(huì)被堵死”所以一旦一個(gè)問(wèn)題的全局最優(yōu)解沒(méi)辦法由一系列局部最優(yōu)選擇拼出來(lái)貪心就會(huì)給出錯(cuò)誤答案。舉個(gè)最直觀(guān)的反例。假設(shè)你要找零錢(qián)硬幣面額是1元、5元和11元要湊出15元。如果按“先用最大面額”的貪心策略你第一次選11元剩4元只能拿四個(gè)1元總共用了5枚硬幣。但實(shí)際最優(yōu)解是三個(gè)5元只需要3枚。在這個(gè)問(wèn)題里局部最優(yōu)每次都拿最大面額并沒(méi)有導(dǎo)向全局最優(yōu)因?yàn)槟?1元這一“最優(yōu)步”把后面組合出更優(yōu)解的可能性堵死了。這個(gè)例子極其經(jīng)典也極其重要——它提醒我們貪心不是“憑感覺(jué)選個(gè)規(guī)則就行”你必須先確認(rèn)這種短視行為在這個(gè)特定問(wèn)題里不會(huì)造成損失。那什么樣的局部最優(yōu)策略才算安全呢計(jì)算機(jī)科學(xué)家?guī)臀覀兛偨Y(jié)出了兩個(gè)關(guān)鍵性質(zhì)下一個(gè)部分詳細(xì)拆解。2. 貪心策略成立的兩塊基石貪心選擇性質(zhì)與最優(yōu)子結(jié)構(gòu)2.1 貪心選擇性質(zhì)局部最優(yōu)確實(shí)通向全局最優(yōu)貪心選擇性質(zhì)的嚴(yán)格定義是一個(gè)問(wèn)題如果可以通過(guò)一系列局部最優(yōu)的貪心選擇得到全局最優(yōu)解那這個(gè)問(wèn)題就具備貪心選擇性質(zhì)。換句話(huà)說(shuō)你不需要考慮子問(wèn)題的全局解是什么只需要在每一步按既定規(guī)則選一個(gè)眼前最優(yōu)的剩下的交給遞歸或迭代去處理最終結(jié)果依然是最優(yōu)的。這個(gè)性質(zhì)的驗(yàn)證通常不是靠肉眼觀(guān)察而是需要數(shù)學(xué)證明。常見(jiàn)的證明思路有兩種。第一種叫“交換論證法”先假設(shè)某個(gè)全局最優(yōu)解存在再說(shuō)明貪心策略的第一步選擇即那個(gè)局部最優(yōu)項(xiàng)一定可以出現(xiàn)在某個(gè)全局最優(yōu)解里——如果當(dāng)前最優(yōu)解里的第一個(gè)元素不是貪心選的元素就把它和貪心元素交換證明交換后的解不會(huì)變差。這樣就能證明“這一步貪心選擇不會(huì)排除最優(yōu)解”然后不斷對(duì)剩余子問(wèn)題重復(fù)同樣的論證最終數(shù)學(xué)歸納法收尾整個(gè)貪心策略就被證明了。第二種叫“反證法”假設(shè)貪心得到的解不是全局最優(yōu)那一定存在某個(gè)比貪心解更優(yōu)的解然后順著貪心決策的邏輯推導(dǎo)出一個(gè)與數(shù)據(jù)結(jié)構(gòu)或前提條件矛盾的結(jié)論。相比較換論證法反證法的路徑更依賴(lài)具體問(wèn)題但思路是類(lèi)似的——你要證明“不這么做不會(huì)更好”。2.2 最優(yōu)子結(jié)構(gòu)子問(wèn)題的最優(yōu)解能拼出原問(wèn)題的最優(yōu)解貪心算法成立的第二個(gè)前提是問(wèn)題具備最優(yōu)子結(jié)構(gòu)。這個(gè)概念在動(dòng)態(tài)規(guī)劃里也出現(xiàn)過(guò)——一個(gè)大規(guī)模問(wèn)題的最優(yōu)解可以由其子問(wèn)題的最優(yōu)解組合而成。貪心和動(dòng)態(tài)規(guī)劃都需要這個(gè)性質(zhì)區(qū)別在于動(dòng)態(tài)規(guī)劃要窮舉所有子問(wèn)題然后比較取最優(yōu)貪心則只根據(jù)當(dāng)前選擇規(guī)則鎖定一個(gè)子問(wèn)題直接往里遞歸省掉了全部比較開(kāi)銷(xiāo)。那要怎么判斷一個(gè)問(wèn)題有沒(méi)有最優(yōu)子結(jié)構(gòu)呢最實(shí)用的方法是嘗試把問(wèn)題“切一刀”假設(shè)你已經(jīng)做出了某一步選擇把剩下的輸入看作一個(gè)規(guī)模更小的獨(dú)立子問(wèn)題然后問(wèn)自己——如果這個(gè)子問(wèn)題不是最優(yōu)解整個(gè)問(wèn)題的解還能是最優(yōu)的嗎如果答案是否定的說(shuō)明這個(gè)分法滿(mǎn)足最優(yōu)子結(jié)構(gòu)如果答案是“子問(wèn)題用次優(yōu)解也能拼出全局最優(yōu)”那最優(yōu)子結(jié)構(gòu)就不成立貪心和動(dòng)態(tài)規(guī)劃都用不了。有意思的是在我接觸過(guò)的實(shí)際問(wèn)題中“最優(yōu)子結(jié)構(gòu)成立但貪心選擇性質(zhì)不成立”的情況非常常見(jiàn)剛才說(shuō)的15元找零問(wèn)題就是典型你無(wú)論如何劃分子問(wèn)題剩下的子問(wèn)題依然存在最優(yōu)解比如拿完11元后湊4元的最優(yōu)解確實(shí)存在但貪心的第一步選擇本身就不該做。反過(guò)來(lái)倒很少見(jiàn)到“貪心選擇性質(zhì)成立但最優(yōu)子結(jié)構(gòu)不成立”的情形——如果一個(gè)問(wèn)題的局部最優(yōu)決策能安全地導(dǎo)向全局最優(yōu)那它背后往往天然具備遞歸分解的結(jié)構(gòu)。這個(gè)觀(guān)察幫我在實(shí)戰(zhàn)中快速過(guò)濾問(wèn)題先問(wèn)最優(yōu)子結(jié)構(gòu)再問(wèn)貪心選擇性質(zhì)能省下大量試錯(cuò)時(shí)間。3. 分?jǐn)?shù)背包問(wèn)題為什么這里是貪心算法的完美秀場(chǎng)提到貪心算法背包問(wèn)題是繞不開(kāi)的經(jīng)典場(chǎng)景而“分?jǐn)?shù)背包”又是背包家族里最適合用貪心解決的那個(gè)。所謂分?jǐn)?shù)背包指的是一個(gè)背包容量有限你面對(duì)一堆物品每件物品有重量和價(jià)值但物品可以被切割——你可以裝下一個(gè)物品的一部分獲得該部分對(duì)應(yīng)的那部分價(jià)值。這個(gè)設(shè)定看起來(lái)有點(diǎn)不現(xiàn)實(shí)但它廣泛抽象了食材配比、任務(wù)切分、資源分配等真實(shí)場(chǎng)景也是理解“單位價(jià)值”這個(gè)貪心指標(biāo)的絕佳入口。3.1 分?jǐn)?shù)背包的貪心策略按單位價(jià)值排序裝填分?jǐn)?shù)背包問(wèn)題的貪心策略非常直覺(jué)化永遠(yuǎn)優(yōu)先裝“單位重量?jī)r(jià)值最高”的物品。算法流程可以這樣描述把每件物品按價(jià)值/重量即單位價(jià)值從高到低排序。從高到低依次裝入背包。如果當(dāng)前物品可以完整裝入就全部裝入更新剩余容量如果當(dāng)前物品不能完整裝入就裝入它的一部分把剩余容量用完算法結(jié)束。這個(gè)策略之所以正確可以找一個(gè)很生活化的類(lèi)比你有個(gè)零食袋只能裝500克東西面前有不同價(jià)位的零食擺在貨架上你當(dāng)然會(huì)優(yōu)先把“每克最貴”的零食裝進(jìn)來(lái)裝不下整包時(shí)就買(mǎi)散稱(chēng)的把袋子裝滿(mǎn)為止。這個(gè)決策鏈里每一步都在把剩余容量花在“單價(jià)最高的東西”上沒(méi)有任何理由先裝便宜的再裝貴的——因?yàn)槟且馕吨阍谕热萘肯履玫搅烁俚目們r(jià)值。來(lái)看一個(gè)具體算例。假設(shè)背包容量為50有三件物品物品A重量10價(jià)值60單位價(jià)值6物品B重量20價(jià)值100單位價(jià)值5物品C重量30價(jià)值120單位價(jià)值4按單位價(jià)值排序是A B C。貪心過(guò)程是先裝A剩余容量40再裝B剩余容量20最后裝C的20/30即2/3個(gè)C得到價(jià)值 (60 100 80 240)。我們用窮舉法驗(yàn)證一下因?yàn)槲锲房梢郧懈钊魏畏桨付嫉葍r(jià)于“每個(gè)物品裝了多少比例”。如果裝A的0.5、B的1、C的0.5總體積是 (5201540)總共只裝了40的容量浪費(fèi)了10顯然還可以把更多的C裝進(jìn)來(lái)。任何沒(méi)有把容量用完的方案都可以通過(guò)多加一點(diǎn)當(dāng)前剩余里單位價(jià)值最高的物品來(lái)提升總價(jià)值所以最優(yōu)解一定是容量剛好用完的。在這個(gè)約束下每一步拿的單位價(jià)值最高的物品占比越大總價(jià)值就越高。上面這個(gè)例子里240就是最優(yōu)解。你可以試著把A換成別的物品裝法會(huì)發(fā)現(xiàn)無(wú)論如何總價(jià)值都不會(huì)超過(guò)240。3.2 代碼實(shí)現(xiàn)排序加貪心二十行搞定分?jǐn)?shù)背包的實(shí)現(xiàn)極其樸素我用Python寫(xiě)一個(gè)通用版本方便你直接改成任何語(yǔ)言def fractional_knapsack(weights, values, capacity): # 將物品按單位價(jià)值從高到低排序 items sorted( [(values[i] / weights[i], weights[i], values[i]) for i in range(len(weights))], reverseTrue ) total_value 0.0 for unit_value, weight, value in items: if capacity 0: break if weight capacity: # 整件裝入 capacity - weight total_value value else: # 裝入一部分 fraction capacity / weight total_value value * fraction capacity 0 return total_value weights [10, 20, 30] values [60, 100, 120] capacity 50 print(fractional_knapsack(weights, values, capacity)) # 輸出 240.0這段代碼內(nèi)置了“裝不下整件就裝部分”的邏輯時(shí)間復(fù)雜度主要集中在排序上為O(n log n)遍歷是O(n)。在物品數(shù)量十萬(wàn)級(jí)以?xún)?nèi)時(shí)這個(gè)性能是近乎實(shí)時(shí)的。3.3 為什么分?jǐn)?shù)背包的貪心能被證明正確我在前面說(shuō)過(guò)貪心策略不能靠“感覺(jué)正確”就草率采用分?jǐn)?shù)背包能成為教學(xué)經(jīng)典恰恰在于它的正確性可以被嚴(yán)格證明。這里的核心論據(jù)是交換論證假設(shè)某個(gè)方案不是按照單位價(jià)值排序裝的那一定存在相鄰兩件物品I和JJ的單位價(jià)值高于I卻排在I前面被先裝。如果J和I的裝入量都不為0我們保持總量不變把一部分J的裝入量換成等重量的I。因?yàn)镮的單位價(jià)值更高交換后總價(jià)值只增不減。反復(fù)進(jìn)行這種交換直到所有物品都按單位價(jià)值從高到低排列。任何最優(yōu)方案經(jīng)過(guò)有限次交換都能變?yōu)樨澬姆桨盖铱們r(jià)值不會(huì)下降反過(guò)來(lái)貪心方案就是那個(gè)“怎么交換都不會(huì)變差”的方案所以它一定是最優(yōu)的。這個(gè)證明思路值得細(xì)品——它沒(méi)有直接證明“貪心產(chǎn)生的解是唯一最優(yōu)解”而是證明“任何不是貪心的最優(yōu)解都可以被改造成貪心解且價(jià)值不變差”。這正是貪心證明中常用的形態(tài)你不需要證明貪心策略碾壓一切你只需要證明不存在任何比貪心更好的選擇。4. 0-1背包同一個(gè)背包為什么貪心突然就失靈了如果說(shuō)分?jǐn)?shù)背包是貪心的主場(chǎng)那0-1背包就是貪心的墓地。0-1背包和分?jǐn)?shù)背包幾乎一樣唯一的差別是每個(gè)物品只能整體裝入或不裝入不能切割。就這一個(gè)約束的變化直接導(dǎo)致貪心策略崩塌。來(lái)看一個(gè)經(jīng)典反例。假設(shè)背包容量只有10有兩件物品物品A重量6價(jià)值30單位價(jià)值5物品B重量5價(jià)值25單位價(jià)值5這里兩件物品單位價(jià)值相同按排序任意選一個(gè)先裝。如果先裝A剩余容量4裝不下B總價(jià)值30如果先裝B剩余容量5裝不下A總價(jià)值25。貪心選了A拿到30?？扇绻麚Q一組數(shù)據(jù)——背包容量10物品A重量7價(jià)值42單位價(jià)值6物品B重量6價(jià)值36單位價(jià)值6物品C重量4價(jià)值20單位價(jià)值5按單位價(jià)值排序先裝A剩余容量3什么都裝不下總價(jià)值42。但最優(yōu)解是BC總重量10價(jià)值56。貪心在這里徹底翻車(chē)因?yàn)樗鼉?yōu)先選了A沒(méi)意識(shí)到“A占的重量太大擠掉了B和C組合出的更優(yōu)解”。0-1背包的問(wèn)題出在哪出在物品的不可分割性。在分?jǐn)?shù)背包里拿完貴的還能拿便宜的容量永遠(yuǎn)可以被完美利用但在0-1背包里“拿某件物品”是一個(gè)布爾決策你占了容量卻不一定拿到最優(yōu)的“容量-價(jià)值性?xún)r(jià)比”。貪心只看到了“單位價(jià)值最高”卻忽略了“組合效應(yīng)”——兩件中等單位價(jià)值的物品組合可能遠(yuǎn)遠(yuǎn)勝過(guò)一件高單位價(jià)值但死重的物品。這是個(gè)很重要的認(rèn)知貪心算法對(duì)“連續(xù)資源分配”問(wèn)題非常友好但面對(duì)“離散組合選擇”問(wèn)題時(shí)就要格外警惕。0-1背包的每個(gè)物品都是“全有或全無(wú)”它需要的是動(dòng)態(tài)規(guī)劃——設(shè)dp[i][j]表示前i件物品在容量為j時(shí)能獲得的最大價(jià)值狀態(tài)轉(zhuǎn)移為dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i])時(shí)間復(fù)雜度O(nW)。這個(gè)對(duì)比告訴你同樣是背包問(wèn)題自動(dòng)判斷“能不能貪心”往往比記住算法更重要。我還想補(bǔ)充一個(gè)工程上的實(shí)用判斷法當(dāng)問(wèn)題的可行解由“集合選擇”構(gòu)成并且候選之間互相排斥時(shí)貪心通常不成立當(dāng)問(wèn)題的可行解由“比例分配”構(gòu)成并且候選可以無(wú)損失切分時(shí)貪心往往成立。用這個(gè)標(biāo)準(zhǔn)去套場(chǎng)景“從課程里選若干門(mén)每門(mén)課占用時(shí)間且算學(xué)分”是0-1背包貪心危險(xiǎn)“把有限的廣告預(yù)算分配到不同渠道渠道可以投一部分”是分?jǐn)?shù)背包貪心安全。5. 貪心算法的更多經(jīng)典場(chǎng)景與實(shí)現(xiàn)樣板背包問(wèn)題只是貪心的一個(gè)入口掌握貪心算法還需要熟悉幾個(gè)高頻的經(jīng)典應(yīng)用。這些場(chǎng)景不只是面試題它們的抽象模式在真實(shí)工程中非常常見(jiàn)。5.1 活動(dòng)安排問(wèn)題按結(jié)束時(shí)間貪才是關(guān)鍵假設(shè)你有一間會(huì)議室收到一堆活動(dòng)申請(qǐng)每個(gè)活動(dòng)有開(kāi)始時(shí)間s[i]和結(jié)束時(shí)間f[i]同一時(shí)間只能安排一個(gè)活動(dòng)問(wèn)最多能安排多少個(gè)活動(dòng)。很多初學(xué)者第一反應(yīng)是“按開(kāi)始時(shí)間最早的優(yōu)先”或者“按持續(xù)時(shí)間最短的優(yōu)先”這兩種策略都能輕易構(gòu)造反例。正確的貪心策略是按結(jié)束時(shí)間從早到晚排序優(yōu)先選擇結(jié)束時(shí)間最早且與已選活動(dòng)不沖突的活動(dòng)。直覺(jué)是結(jié)束時(shí)間越早給后續(xù)活動(dòng)留出的時(shí)間就越多也就越可能安排進(jìn)更多活動(dòng)。這個(gè)問(wèn)題的證明同樣可以用交換論證假設(shè)某個(gè)最優(yōu)解里第一個(gè)活動(dòng)不是結(jié)束時(shí)間最早的A而是另一個(gè)活動(dòng)B。因?yàn)锳的結(jié)束時(shí)間不晚于B所以把B替換成A后不會(huì)影響后續(xù)活動(dòng)的安排解仍然合法且數(shù)量相同。于是存在一個(gè)包含A的最優(yōu)解對(duì)剩余活動(dòng)遞歸同樣成立貪心就是最優(yōu)的。實(shí)際實(shí)現(xiàn)只需要一次排序加一次線(xiàn)性?huà)呙鑔ef max_activities(activities): # activities: [(start, end), ...] activities.sort(keylambda x: x[1]) # 按結(jié)束時(shí)間排序 count 0 last_end -1 for start, end in activities: if start last_end: count 1 last_end end return count這個(gè)場(chǎng)景映射到現(xiàn)實(shí)就是會(huì)議室預(yù)訂、單機(jī)任務(wù)調(diào)度、帶寬分配等凡是“一個(gè)資源、多個(gè)帶起止時(shí)間的請(qǐng)求、最大化吞吐量”的問(wèn)題都可以套這個(gè)模板。5.2 哈夫曼編碼頻率越低越要靠近葉子底部數(shù)據(jù)壓縮里的哈夫曼編碼也是貪心的典型代表。它的目標(biāo)是用最短的平均編碼長(zhǎng)度來(lái)無(wú)損表示一批字符做法是每次從字符集合中挑出出現(xiàn)頻率最低的兩個(gè)節(jié)點(diǎn)合并成一個(gè)新節(jié)點(diǎn)新節(jié)點(diǎn)的權(quán)重是二者之和并把合并后的節(jié)點(diǎn)放回集合重復(fù)到只剩一個(gè)根節(jié)點(diǎn)為止。這本質(zhì)上是一種“自底向上建樹(shù)”的貪心——總是在當(dāng)前狀態(tài)下找代價(jià)最小的局部合并。哈夫曼編碼的正確性證明思路是在任意最優(yōu)前綴編碼樹(shù)中頻率最低的兩個(gè)字符一定出現(xiàn)在最深層且互為兄弟。這個(gè)論斷可以用交換論證證明如果頻率最低的兩個(gè)字符不在最底層把一個(gè)更深層的字符和它們中的一個(gè)交換總編碼長(zhǎng)度會(huì)下降從而矛盾。所以貪心選擇每次合并最低頻的兩項(xiàng)并不會(huì)丟失最優(yōu)解。這個(gè)證明我在面試中遇到過(guò)不止一次建議你把它的邏輯理順而不是只背“每次選最小的兩個(gè)”。實(shí)現(xiàn)時(shí)通常用小頂堆優(yōu)先隊(duì)列來(lái)維護(hù)當(dāng)前所有節(jié)點(diǎn)的權(quán)重每次彈出兩個(gè)最小的合并后壓回。復(fù)雜度為O(n log n)是構(gòu)建最優(yōu)前綴編碼的標(biāo)準(zhǔn)方案。5.3 最小生成樹(shù)Kruskal和Prim都是貪心圖論里的最小生成樹(shù)是貪心的另一個(gè)大殺器。Kruskal算法的策略是把邊按權(quán)重從小到大排序從最小的邊開(kāi)始只要這條邊連接的兩個(gè)頂點(diǎn)尚未連通就加入生成樹(shù)。Prim算法則是從一個(gè)起點(diǎn)出發(fā)每次都挑當(dāng)前已選頂點(diǎn)集合到未選頂點(diǎn)集合之間的最小權(quán)邊擴(kuò)展。這兩個(gè)算法能成功的關(guān)鍵在于圖論中的“切割性質(zhì)”如果一條邊是橫跨某個(gè)割的最小權(quán)邊那它一定在某個(gè)最小生成樹(shù)中。這個(gè)性質(zhì)保證了每一步貪心選擇“不會(huì)把最優(yōu)解排除在外”這正是前面說(shuō)的貪心選擇性質(zhì)。Kruskal需要配合并查集來(lái)判斷連通性Prim可以用優(yōu)先隊(duì)列來(lái)快速取最小邊兩者在稀疏圖和稠密圖上各有優(yōu)勢(shì)。工程網(wǎng)絡(luò)設(shè)計(jì)、電路布線(xiàn)、集群拓?fù)鋬?yōu)化里這兩個(gè)算法都是骨灰級(jí)工具。5.4 Dijkstra最短路徑每次都只確認(rèn)眼前最近的一點(diǎn)單源最短路徑的Dijkstra算法同樣內(nèi)置貪心思想。它的策略是維護(hù)一個(gè)“已確定最短路徑頂點(diǎn)集合”每次都從未確定的頂點(diǎn)里挑一個(gè)與源點(diǎn)距離最近的點(diǎn)加入集合并松弛它所有出邊。這個(gè)“最近”是當(dāng)前已算出的暫定距離貪心在每一步固定一個(gè)頂點(diǎn)的最終最短距離。Dijkstra能這么做的前提是邊的權(quán)重非負(fù)。因?yàn)榉秦?fù)權(quán)重保證“當(dāng)前距離最小的未處理頂點(diǎn)”不可能再被其他路徑縮短——所有能到達(dá)它的路徑至少已經(jīng)經(jīng)過(guò)一個(gè)未處理頂點(diǎn)而這個(gè)未處理頂點(diǎn)本身距離就不小于它加上非負(fù)邊權(quán)只會(huì)更遠(yuǎn)。這個(gè)推理一旦遇到負(fù)權(quán)邊就失效了所以Dijkstra不能處理負(fù)權(quán)圖得用Bellman-Ford。這也是一個(gè)理解“貪心策略對(duì)問(wèn)題條件極其敏感”的好例子。這些經(jīng)典案例放在一起看你會(huì)發(fā)現(xiàn)一個(gè)共性貪心算法不是一種“統(tǒng)一的算法”而是一種“策略范式”。每個(gè)具體問(wèn)題都要單獨(dú)設(shè)計(jì)貪心規(guī)則、單獨(dú)證明規(guī)則的安全性不同問(wèn)題的“局部最優(yōu)”定義可能完全不同——活動(dòng)安排看結(jié)束時(shí)間哈夫曼看字符頻率Kruskal看邊權(quán)。這種靈活度既是貪心的魅力也是學(xué)習(xí)時(shí)最容易困惑的地方。6. 如何快速判斷一個(gè)題目能不能用貪心解學(xué)完經(jīng)典案例之后你肯定會(huì)遇到一個(gè)現(xiàn)實(shí)問(wèn)題新題目來(lái)了我怎么知道它能不能貪心在工作或面試中你不可能每次都把教材翻一遍。這里我分享一套自己的快速判斷流程不一定絕對(duì)嚴(yán)密但能大幅降低試錯(cuò)成本。第一步看問(wèn)題是否具備最優(yōu)子結(jié)構(gòu)。把問(wèn)題按“先做一個(gè)選擇然后處理剩下部分”的方式切分問(wèn)自己如果剩下部分不是最優(yōu)解整個(gè)問(wèn)題還能是最優(yōu)解嗎大多數(shù)優(yōu)化類(lèi)問(wèn)題都滿(mǎn)足這個(gè)條件不滿(mǎn)足時(shí)問(wèn)題往往無(wú)法用動(dòng)態(tài)規(guī)劃或貪心這類(lèi)“分而治之”的框架解決需要考慮別的手段。第二步試著構(gòu)造反例。無(wú)論你想出了什么貪心規(guī)則都先逼自己嘗試構(gòu)造一個(gè)反例證明“這個(gè)規(guī)則會(huì)翻車(chē)”。如果你能在幾分鐘內(nèi)構(gòu)造出反例說(shuō)明規(guī)則有問(wèn)題或者這個(gè)問(wèn)題壓根不適合貪心。如果你試了很多組數(shù)據(jù)都沒(méi)找到反例再把題目往已知的經(jīng)典模型上靠——它會(huì)不會(huì)本質(zhì)上是分?jǐn)?shù)背包、活動(dòng)安排、最小生成樹(shù)或者Dijkstra中的某一種第三步如果無(wú)法確定優(yōu)先嘗試動(dòng)態(tài)規(guī)劃。動(dòng)態(tài)規(guī)劃幾乎可以覆蓋所有滿(mǎn)足最優(yōu)子結(jié)構(gòu)的問(wèn)題代價(jià)只是更高的時(shí)間和空間復(fù)雜度。寫(xiě)一個(gè)動(dòng)態(tài)規(guī)劃版本作為baseline再寫(xiě)貪心版本用隨機(jī)生成的測(cè)試數(shù)據(jù)對(duì)拍驗(yàn)證正確性。這也是我強(qiáng)烈建議算法初學(xué)者養(yǎng)成的習(xí)慣——對(duì)拍是驗(yàn)證算法正確性的最實(shí)用方法比任何紙面證明都直接。第四步如果你的貪心版本在大規(guī)模隨機(jī)數(shù)據(jù)上依然與動(dòng)態(tài)規(guī)劃結(jié)果一致它有極大概率是正確的。這時(shí)候再?lài)L試用交換論證或數(shù)學(xué)歸納法補(bǔ)一個(gè)正式證明。很多人把證明放到最后一步會(huì)覺(jué)得很痛苦但當(dāng)你已經(jīng)對(duì)拍過(guò)數(shù)千組數(shù)據(jù)后證明思路往往也會(huì)在測(cè)試中自然浮現(xiàn)。需要強(qiáng)調(diào)的是這個(gè)流程并非數(shù)學(xué)上完備的判定算法但它在工程實(shí)踐中極其有效。真隨機(jī)對(duì)拍能過(guò)濾掉絕大多數(shù)錯(cuò)誤貪心策略而剩下的那些能通過(guò)對(duì)拍的“候選貪心”大多數(shù)時(shí)候確實(shí)會(huì)帶著你找到正確的證明路徑。7. 貪心雖好用但這些坑一定要繞開(kāi)最后按老規(guī)矩把我這些年踩過(guò)的坑和帶學(xué)員時(shí)經(jīng)?？吹降膯?wèn)題集中分享一下。第一個(gè)坑用貪心直接套0-1背包。這個(gè)問(wèn)題我在上面專(zhuān)門(mén)分析過(guò)但現(xiàn)實(shí)里它仍然以各種偽裝出現(xiàn)。比如“給你一筆預(yù)算從若干項(xiàng)目中選幾個(gè)做每個(gè)項(xiàng)目有成本與收益怎么選收益最大”——這就是0-1背包不能用“先做性?xún)r(jià)比最高的項(xiàng)目”來(lái)解。應(yīng)對(duì)方案是要么改用動(dòng)態(tài)規(guī)劃要么如果項(xiàng)目可以部分開(kāi)展投一部分錢(qián)獲得對(duì)應(yīng)比例收益才可以用貪心。區(qū)分清楚“能不能切分”永遠(yuǎn)是第一步。第二個(gè)坑Kruskal算法里忘了處理并查集的路徑壓縮和按秩合并。有些人在小圖上跑得通數(shù)據(jù)一多就超時(shí)不是貪心策略錯(cuò)而是并查集實(shí)現(xiàn)太粗糙。路徑壓縮幾乎是免費(fèi)的一定要加按秩合并不是必須但建議加上極端情況下能顯著降低常數(shù)。寫(xiě)算法題時(shí)貪心部分往往不是瓶頸輔助數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)效率才是。第三個(gè)坑哈夫曼編碼建樹(shù)時(shí)把輸入序列當(dāng)成已排序的忽略了合并產(chǎn)生的新節(jié)點(diǎn)需要重新參與比較的過(guò)程。標(biāo)準(zhǔn)的實(shí)現(xiàn)應(yīng)該用優(yōu)先隊(duì)列否則每次取最小都要掃描一遍復(fù)雜度退化成O(n2)。我見(jiàn)過(guò)有人因?yàn)椤白址淮蟆本屯祽兄钡教幚砩先f(wàn)字符的語(yǔ)料時(shí)才被性能打臉。第四個(gè)坑貪心策略在競(jìng)賽里碰壁后直接否定所有貪心思路。這個(gè)心理陷阱其實(shí)最隱蔽。貪心算法本身沒(méi)有錯(cuò)錯(cuò)的是“這個(gè)問(wèn)題的這個(gè)貪心規(guī)則”不對(duì)。同一個(gè)背包問(wèn)題分?jǐn)?shù)背包貪心對(duì)、0-1背包貪心錯(cuò)同一個(gè)圖論問(wèn)題非負(fù)權(quán)最短路Dijkstra對(duì)、帶負(fù)權(quán)最短路Dijkstra錯(cuò)。不要把問(wèn)題簡(jiǎn)單歸因于“貪心不靠譜”而是要細(xì)化到“當(dāng)前這個(gè)決策規(guī)則為什么不能成立”。還有一個(gè)實(shí)戰(zhàn)習(xí)慣值得培養(yǎng)每當(dāng)你設(shè)計(jì)出一個(gè)貪心規(guī)則立刻寫(xiě)下它的不變量也就是“在每一步?jīng)Q策之后當(dāng)前已選集合一定不劣于任何其他相同規(guī)模的集合”。這個(gè)不變量如果能在整個(gè)算法執(zhí)行過(guò)程中始終保持那貪心策略幾乎必然正確。寫(xiě)不出來(lái)的話(huà)你的貪心大概率有問(wèn)題。以我個(gè)人經(jīng)驗(yàn)來(lái)看貪心算法的學(xué)習(xí)路徑應(yīng)該是一條“從直覺(jué)到證明再到自動(dòng)化判斷”的曲線(xiàn)。一開(kāi)始誰(shuí)都能說(shuō)出“每一步選最好的”這句話(huà)但真正拉開(kāi)差距的是你能不能在五分鐘后給出讓人信服的正確性論證或者高效地構(gòu)造出反例來(lái)否定一個(gè)貌似合理實(shí)則錯(cuò)誤的策略。這兩種能力都不是天生的多寫(xiě)證明、多對(duì)拍、多積累經(jīng)典模型的變形慢慢就會(huì)形成肌肉記憶。希望這篇文章能幫你在貪心算法的地基上站穩(wěn)后面不管是啃動(dòng)態(tài)規(guī)劃還是面對(duì)更復(fù)雜的優(yōu)化問(wèn)題都會(huì)走得順利很多。