貪心法

??我在當(dāng)前情況下，我把我做到最好。我也不管全局如何，整體如何。我就考慮我現(xiàn)在的這一個(gè)，或者這一小部分怎樣最好。

• 貪心技術(shù)是一種設(shè)計(jì)算法的通用策略。
• 貪心技術(shù)的基本思想：
  • 基于貪心選擇準(zhǔn)則，每次得到局部最優(yōu)的選擇。
  • 希望利用局部最后得到全局最優(yōu)解。
  • 貪心選擇性質(zhì)：局部最優(yōu)可以得到全局最優(yōu)。
• 找到正確的貪心選擇準(zhǔn)則是設(shè)計(jì)貪心算法的關(guān)鍵。
  • 不同的貪心選擇準(zhǔn)則可以得到不同的結(jié)果。

打個(gè)比方，我現(xiàn)在有幾種選擇：

學(xué)編程、打游戲、讀書(shū)、去外面玩、去兼職、……

如果我的目的是提高自己的知識(shí)水平，那起碼對(duì)于現(xiàn)在的這些選擇來(lái)說(shuō)，我選擇“學(xué)編程”或者“讀書(shū)”就是最優(yōu)的。

只是說(shuō)當(dāng)前這一步怎么走是最優(yōu)的，也并沒(méi)有去管后面的路怎么走。

比如你說(shuō)選擇“打游戲”，后面可能也會(huì)更成功，但是不管這個(gè)。

找零問(wèn)題（change-making problem）

• 給定無(wú)限多不同面額的硬幣$d_1>...>d_m$，對(duì)于總額$n$，如何找到最少的硬幣數(shù)目？
• 問(wèn)題：目標(biāo)函數(shù)和約束條件是什么？

例如：

$d_1=25c,d_2=10c,d_3=5c,d_4=1c，而且n=48c$。

我們可能想，要使得硬幣數(shù)目最少，那簡(jiǎn)單啊。

先緊著面額最大的來(lái)湊就行了。

先拿個(gè)25c的、再拿兩個(gè)10c的，5c的沒(méi)法拿，于是再拿3個(gè)1c的。

于是得到貪婪解：<1,2,0,3>。

我們這個(gè)策略就是，很簡(jiǎn)單，先緊著最大的拿。

但是我們雖然這樣做了，而且貌似可行。

但是實(shí)際上，它對(duì)于大多數(shù)情況而言，這樣可能是沒(méi)問(wèn)題的；但是沒(méi)法保證所有情況啊，你沒(méi)法保證對(duì)于所有情況、任意某一種情況，這樣都沒(méi)問(wèn)題。

有一些情況，你這樣做，可能就壓根不是最優(yōu)解了。

但是：

• 對(duì)大多數(shù)常用的硬幣面額都可以得到最優(yōu)解。
• 對(duì)任意硬幣面額，有可能不是最優(yōu)解。

例如：

$d_1=25c,d_2=10c,d_3=1c而且n=30c$。

那么你還按照上面的規(guī)則，

先拿個(gè)25c的，然后拿五個(gè)1c的?！藭r(shí)是6個(gè)硬幣。

但實(shí)際上我們可以看出，直接拿三個(gè)10c的就夠了，而且只用3個(gè)硬幣。

所以可見(jiàn)，我們剛才的那種簡(jiǎn)單的想法：先緊著大面額的拿。

這種方法，可能在某些情況下沒(méi)毛病，但是在有些情況下就不對(duì)了、不是最優(yōu)解了。

**那咋辦呢。**是不是我的想法、我的策略設(shè)計(jì)的有問(wèn)題呢？

那到底咋樣弄，才能對(duì)于所有情況都能得到最優(yōu)解呢？

我們可以用回溯法。（不是講貪心嗎，咋又說(shuō)回溯了？——后面再說(shuō)這個(gè)問(wèn)題）

---

• **貪婪法：**建議通過(guò)一系列步驟來(lái)構(gòu)造問(wèn)題的解，每一步對(duì)目前構(gòu)造的部分解做一個(gè)擴(kuò)展，直到獲得問(wèn)題的完全解。（完全解，不是最優(yōu)解）
• 必須滿(mǎn)足：可行、局部最優(yōu)、不可取消。

貪心算法要求

• 可行的：即它必須滿(mǎn)足問(wèn)題的約束。
• 局部最優(yōu)：它是當(dāng)前步驟中所有可行選擇中最佳的局部選擇。
• 不可取消：即選擇一旦做出，在算法的后面步驟中就無(wú)法改變了。

就像人生中的一些選擇一樣，就是貪心算法么，每次選的是局部最優(yōu)，而且選了之后就沒(méi)法取消了。

??在每一步中，它要求“貪婪”地選擇最佳操作，并希望通過(guò)一系列局部的最優(yōu)選擇，能夠產(chǎn)生一個(gè)整個(gè)問(wèn)題的（全局的）最優(yōu)解。

基本思想

• 從問(wèn)題的某一個(gè)初始解出發(fā)，通過(guò)一系列的貪心選擇（當(dāng)前狀態(tài)下的局部最優(yōu)選擇），逐步逼近給定的目標(biāo)，盡可能快地求得更好的解。
• 在貪心算法（greedy method）中也采用逐步構(gòu)造最優(yōu)解的方法。在每個(gè)階段，都做出一個(gè)按某個(gè)評(píng)價(jià)函數(shù)最優(yōu)的決策，該評(píng)價(jià)函數(shù)最優(yōu)稱(chēng)為貪心準(zhǔn)則（greedy criterion）。
• 貪心算法的正確性，就是要證明按貪心準(zhǔn)則求得的解是全局最優(yōu)解。
• 貪心算法不能對(duì)所有問(wèn)題都得到全局最優(yōu)解。
• 但是對(duì)于許多問(wèn)題，它能夠產(chǎn)生全局最優(yōu)解。如單源最短路徑問(wèn)題，最小生成樹(shù)問(wèn)題等。

適合求解問(wèn)題的特征

• **貪心選擇性質(zhì)：**可通過(guò)局部最優(yōu)（貪心）選擇達(dá)到全局最優(yōu)解。
  • 通常以自頂向下的方式進(jìn)行，每次選擇后將問(wèn)題轉(zhuǎn)化為規(guī)模更小的子問(wèn)題。
  • 該性質(zhì)是貪心法使用成功的保障，否則得到的是近優(yōu)解。
• 最優(yōu)子結(jié)構(gòu)性質(zhì)：問(wèn)題的最優(yōu)解包含它的子問(wèn)題的最優(yōu)解。
  • 并不是所有具有最優(yōu)子結(jié)構(gòu)性質(zhì)的問(wèn)題都可以采用貪心策略。
  • 往往可以利用最優(yōu)子結(jié)構(gòu)性質(zhì)來(lái)證明貪心選擇性質(zhì)。

背包問(wèn)題

• 0-1背包問(wèn)題

??給定n種物品和一個(gè)背包。物品i的重量是$W_i$，其價(jià)值為$V_i$，背包的容量為C。應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價(jià)值最大？

0-1背包問(wèn)題，對(duì)于一個(gè)物品，0就是不拿它，1就是拿它。

在選擇裝入背包的物品時(shí)，對(duì)每種物品只有兩種選擇，要么裝入背包、要么不裝入背包。不能將一個(gè)物品裝入背包多次，也不能只裝入某物品的一部分。

• 背包問(wèn)題

??與0-1背包問(wèn)題類(lèi)似，所不同的是，在選擇物品i裝入背包時(shí)，可以選擇物品i的一部分，而不一定要全部裝入背包，1≤i≤n。

背包問(wèn)題，也叫“分?jǐn)?shù)背包問(wèn)題”，對(duì)于一個(gè)物品，物品太大了，背包剩余空間不夠了，此時(shí)我可以把物品拆下來(lái)、把一部分放進(jìn)去。

0/1背包問(wèn)題

• 已知
  • 背包容量C>0
  • n個(gè)物品，體積$w_i>0$，價(jià)值$p_i>0fori=1,...,n$
• 確定 { 1 , 2 , . . . , n } \{1,2,...,n\} {1,2,...,n}的子集，滿(mǎn)足：

$$max\sum _{i\in A}{p}_i,subjectto\sum _{i\in A}{w}_i\le C$$

0/1背包問(wèn)題——貪心法

• 有以下幾種貪心選擇準(zhǔn)則：

  • 最大價(jià)值優(yōu)先——先選擇最值錢(qián)的物品。

  緊著最值錢(qián)的先往上放。

  • 最小體積優(yōu)先

  緊著最小體積的先放，想裝的多。

  • 最大體積優(yōu)先

  想著一般大的東西都比較值錢(qián)？所以先緊著大件先放？

  • 最大單位價(jià)值優(yōu)先

這四個(gè)規(guī)則都有一定道理，那我們?cè)撨x哪種呢？選最大價(jià)值優(yōu)先？選最大單位價(jià)值優(yōu)先？

• 沒(méi)有一種方法能保證得到最優(yōu)解

最大價(jià)值優(yōu)先

（lb是重量單位，上面是價(jià)錢(qián)）

可見(jiàn)，最大價(jià)值優(yōu)先，放進(jìn)來(lái)的不一定是最優(yōu)解。

最小體積優(yōu)先

可見(jiàn)，最小體積優(yōu)先，放進(jìn)來(lái)的也不一定是最優(yōu)解。

最大體積優(yōu)先

可見(jiàn)，最大體積優(yōu)先得到的也不一定是最優(yōu)解。

最大單位價(jià)值優(yōu)先

可見(jiàn)，這個(gè)也不一定能得到最優(yōu)解。

---

分?jǐn)?shù)背包問(wèn)題

• 對(duì)于0/1背包問(wèn)題，沒(méi)有最優(yōu)的貪心算法。
• 分?jǐn)?shù)背包問(wèn)題：可以將第i個(gè)物品的一部分放入背包。
• 對(duì)于分?jǐn)?shù)背包問(wèn)題，貪心算法是其不二選擇，該算法基于最大單位價(jià)值的選擇準(zhǔn)則。（感覺(jué)有點(diǎn)類(lèi)似于微積分里的微元思想）

這個(gè)就沒(méi)啥好猶豫的了，我先緊著最大單位價(jià)值的往里面放，放不下整個(gè)物品的時(shí)候，我把當(dāng)前最大單位價(jià)值的物品切出來(lái)一塊往里面放。

這樣最后包里放的肯定是價(jià)值最大的情況。

• 貪心算法過(guò)程：
  • 降序排序$v_i/w_i$。
  • 根據(jù)排序次序增加物品，直到這個(gè)物品裝完，或是超出背包容量。
  • 如果背包沒(méi)有滿(mǎn)，選擇下一個(gè)物品開(kāi)始裝。

最優(yōu)解證明

• 證明：

??我們首先假設(shè)我們有一個(gè)最優(yōu)解$A_1$，那么我們首先找到$A_1$里面平均價(jià)值最高的物品$a_m$，然后我們將用商品里面平均價(jià)值最高的物品$a_1$將$a_m$進(jìn)行全部替換或者部分替換得到解$A_2$，又因?yàn)?span id="vxwlu0yf4" class="katex--inline">$\frac{v_1}{w_1}\ge \frac{v_m}{w_m}$，所以$A_2$的總價(jià)值高于$A_1$的總價(jià)值，這與$A_1$是最優(yōu)解矛盾，于是得到$A_1$里面包含平均價(jià)值最高的物品。

---

• 小數(shù)背包問(wèn)題還具有貪心選擇性質(zhì)，用貪心法求解更簡(jiǎn)單、更快速。
• 0-1背包問(wèn)題用貪心法求解不一定能得到最優(yōu)解。

任務(wù)調(diào)度問(wèn)題

• 9個(gè)任務(wù)需要調(diào)度，每個(gè)任務(wù)運(yùn)行時(shí)間為3,5,6,10,11,14,15,18,20

如果只有一個(gè)處理器，那就沒(méi)啥說(shuō)的，每個(gè)任務(wù)看看按照什么規(guī)則往里放就行了，反正最后總時(shí)間是一樣的。

但是如果有多個(gè)處理器呢？

• 有三個(gè)處理器執(zhí)行這些任務(wù)。

當(dāng)然，對(duì)于貪心而言，我們對(duì)這一問(wèn)題也可以有很多種貪心策略。

• 貪心準(zhǔn)則：先運(yùn)行時(shí)間最長(zhǎng)的任務(wù)。

每次把當(dāng)前需要運(yùn)行最長(zhǎng)時(shí)間的任務(wù)，分配給當(dāng)前任務(wù)時(shí)間最短的處理器。

因此，三個(gè)處理器執(zhí)行這些任務(wù)，花費(fèi)35分鐘時(shí)間。

這個(gè)解決方法不錯(cuò)，但是我們可能還可以有更好的策略。

• 另一種貪心準(zhǔn)則：優(yōu)先運(yùn)行最短任務(wù)

這個(gè)方式還不如剛才那個(gè)，這個(gè)需要花費(fèi)40分鐘。

最優(yōu)解

折騰半天都不是最好的，那我們看看最優(yōu)解到底是什么樣的，如上圖所示。

• 這個(gè)解為什么是最優(yōu)的？

很明顯么。因?yàn)槿齻€(gè)處理器剛好平均分了所有任務(wù)的總時(shí)長(zhǎng)，沒(méi)有任何的浪費(fèi)。

??但是，可見(jiàn)，若想得到這樣的一種解。你要付出的代價(jià)就會(huì)很高了。

??有必要么，實(shí)際解決一個(gè)問(wèn)題來(lái)說(shuō)，這樣去搞，可能沒(méi)這個(gè)必要。你找到最優(yōu)解了之后，最優(yōu)解固然能夠幫你節(jié)約時(shí)間；但是不要忽視了，你尋找這個(gè)最優(yōu)解也要花時(shí)間。你為了找一個(gè)最優(yōu)解去節(jié)約那一點(diǎn)點(diǎn)時(shí)間，然后你花了大量的時(shí)間在尋找到最優(yōu)解上，得不償失。

類(lèi)似上圖中這個(gè)最優(yōu)解，是咋找到的？可能是暴力窮舉吧，或者是什么方法。總之很耗時(shí)間才能找出來(lái)的。

??實(shí)際上我就用一種貪心策略，去做，就拉倒了。雖然可能不是最優(yōu)，但是接近最優(yōu)差不多就行了。

??對(duì)于一些特殊的問(wèn)題，貪心算法能直接找出其最優(yōu)解，能直接獲取最優(yōu)解那當(dāng)然更好了。

??總之貪心算法可能找到的不是最優(yōu)解，而只是局部最優(yōu)解；但是它的實(shí)現(xiàn)是很簡(jiǎn)單的，不會(huì)耗費(fèi)太多時(shí)間。

---

??同時(shí)，我們?cè)谪澬?#xff0c;貪的過(guò)程中，也可以利用回溯法的思想，對(duì)一些沒(méi)必要繼續(xù)探討下去的情況進(jìn)行剪枝，而沒(méi)必要全部貪到底、再去排除。也就是貪心法配合回溯法進(jìn)行使用。

活動(dòng)選擇問(wèn)題

• 這個(gè)就是活動(dòng)選擇問(wèn)題。

我選擇哪些活動(dòng)，能夠讓活動(dòng)數(shù)量最多？

活動(dòng)選擇——貪心法

• 貪心法選擇準(zhǔn)則：
  • 最早開(kāi)始時(shí)間優(yōu)先
  • 最小持續(xù)時(shí)間優(yōu)先
  • 最早完成時(shí)間優(yōu)先
• 哪個(gè)準(zhǔn)則更有效？

最早開(kāi)始時(shí)間優(yōu)先。

假設(shè)有一個(gè)從0開(kāi)始的活動(dòng)，但是它持續(xù)時(shí)間巨長(zhǎng)。

那這顯然不是最優(yōu)解。

如上圖。

這個(gè)持續(xù)時(shí)間最小，但是可能因?yàn)樽隽怂?#xff0c;它剛好介于兩個(gè)活動(dòng)鄰接點(diǎn)，導(dǎo)致兩個(gè)活動(dòng)都沒(méi)法做。

顯然也不是最優(yōu)解。

最早結(jié)束時(shí)間是不是能達(dá)到這個(gè)問(wèn)題的最優(yōu)解？

實(shí)際上，按最早結(jié)束時(shí)間優(yōu)先，基本上都能取到最優(yōu)解。

怎么證明這種策略的正確性？怎么知道上面的例子不是它的特例？

• 需要證明貪心法的正確性。

最早結(jié)束時(shí)間優(yōu)先——最優(yōu)性證明

**定理：**如果活動(dòng)$a_1$在所有活動(dòng)中具有最早結(jié)束時(shí)間，則最優(yōu)解中一定包含$a_1$。

證明：

• 令$A$是最優(yōu)解，$a_1$是貪心法選擇的最早結(jié)束時(shí)間的活動(dòng)。如果$a_1\in A$，則定理得證。
• 如果$a_1\notin A$，我們證明 A ? = A ? { a } + { a 1 } A^*=A-\{a\}+\{a_1\} A?=A?{a}+{a1?}是另一個(gè)包含$a_1$的最優(yōu)解，而$a$是$A$中具有最早結(jié)束時(shí)間的活動(dòng)。
• 因?yàn)榛顒?dòng)的結(jié)束時(shí)間已排序好，$f(a_1)\le f(a)$。假設(shè)$f(a_1)\le s(a)$，如果我們把$a_1$加到$A$，意味著$A$不是最優(yōu)的。所以$s(a)<f(a_1)$，并且$a_1$和$a$重疊。因?yàn)?span id="vxwlu0yf4" class="katex--inline">$f(a_1)\le f(a)$，如果我們移除$a$添加$a_1$，可以得到另一個(gè)最優(yōu)解$A^{?}$包含了$a_1$。$A^{?}$是最優(yōu)的，因?yàn)?span id="vxwlu0yf4" class="katex--inline">$|A^{?}|=|A|$。

沒(méi)太看懂。

**定理：**貪心子選擇一定產(chǎn)生最優(yōu)解。

即，證明去掉一個(gè)$a_1$之后，對(duì)剩下的活動(dòng)做最早結(jié)束時(shí)間優(yōu)先策略，得到的也是子集的最優(yōu)解。

證明：

• 令$a_1$是貪心算法選擇的活動(dòng)。
• 令$S^{?}$是不與$a_1$重疊的活動(dòng)子集

S ? = { a i ∣ i = 2 , . . . , n a n d s i ≥ f ( a 1 ) } S^*=\{a_i | i=2,...,n\ and\ s_i≥f(a_1)\} S?={ai?∣i=2,...,n?and?si?≥f(a1?)}

• 令$B$是$S^{?}$的最優(yōu)解。

• 從$S^{?}$的定義可知， A ? = { a 1 } ∪ B A^*=\{a_1\}∪B A?={a1?}∪B是可行的，并且是原問(wèn)題的解。

• 利用反證法證明$A^{?}$是最優(yōu)解。

• 假設(shè)$A^{?}$不是最優(yōu)解，令$A$是包含$a_1$的最優(yōu)解，則$|A^{?}|<|A|$，且 ∣ A ? { a 1 } ∣ > ∣ A ? ? { a 1 } ∣ = ∣ B ∣ |A-\{a_1\}|>|A^*-\{a_1\}|=|B| ∣A?{a1?}∣>∣A??{a1?}∣=∣B∣。

• 但是 A ? { a 1 } A-\{a_1\} A?{a1?}也是$S^{?}$的解，與$B$是$S^{?}$的最優(yōu)解矛盾。

• 所以$A^{?}$一定是原問(wèn)題的最優(yōu)解。

---

Prim算法

• 連通圖的一棵生成樹(shù)是包含圖的所有定點(diǎn)的連通無(wú)環(huán)子圖（一棵樹(shù)）。
• 加權(quán)連通圖的一棵最小生成樹(shù)是圖的一棵權(quán)重最小的生成樹(shù)。

??從某個(gè)點(diǎn)出發(fā)，首先找和它相鄰連接的結(jié)點(diǎn)中，權(quán)值最小的是誰(shuí)。是b結(jié)點(diǎn)、權(quán)值為4，那就把b結(jié)點(diǎn)并入進(jìn)來(lái)。接著，再找下一條邊，就找和a、b相鄰的結(jié)點(diǎn)中，權(quán)值最小的是哪個(gè)邊，并且把那個(gè)結(jié)點(diǎn)并入進(jìn)來(lái)。

??總之，可以視作兩個(gè)集合：一個(gè)是已并入最小生成樹(shù)的結(jié)點(diǎn)集合，另一個(gè)是還未并入的結(jié)點(diǎn)集合。每次找這兩個(gè)集合之間權(quán)值最小的連接（不能形成環(huán)）。

---

問(wèn)題：

??一個(gè)圖，按照這種方式，找出來(lái)的所有的最小生成樹(shù)是不是都是一樣的？

??它是一棵樹(shù)，樹(shù)的結(jié)構(gòu)是由什么決定的？——我每次的起始點(diǎn)選取不同，它的樹(shù)根結(jié)點(diǎn)不一樣，肯定就不一樣了。

---

總結(jié)

??貪心策略的選擇很重要。

??貪心在某些情況下是可以拿到最優(yōu)的，但是很容易得到一個(gè)局部最優(yōu)而非全局最優(yōu)的解。