白山建設(shè)局網(wǎng)站游戲優(yōu)化軟件
文章目錄
- 貪心法
- 找零問題(change-making problem)
- 貪心算法要求
- 基本思想
- 適合求解問題的特征
- ==背包問題==
- 0/1背包問題
- 0/1背包問題——貪心法
- 分?jǐn)?shù)背包問題
- 任務(wù)調(diào)度問題
- 活動(dòng)選擇問題
- 活動(dòng)選擇——貪心法
- 最早結(jié)束時(shí)間優(yōu)先——最優(yōu)性證明
- ==Prim算法==
貪心法
??我在當(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í)水平,那起碼對(duì)于現(xiàn)在的這些選擇來說,我選擇“學(xué)編程”或者“讀書”就是最優(yōu)的。
只是說當(dāng)前這一步怎么走是最優(yōu)的,也并沒有去管后面的路怎么走。
比如你說選擇“打游戲”,后面可能也會(huì)更成功,但是不管這個(gè)。
找零問題(change-making problem)
- 給定無限多不同面額的硬幣 d 1 > . . . > d m d_1>...>d_m d1?>...>dm?,對(duì)于總額 n n n,如何找到最少的硬幣數(shù)目?
- 問題:目標(biāo)函數(shù)和約束條件是什么?
例如:
d 1 = 25 c , d 2 = 10 c , d 3 = 5 c , d 4 = 1 c ,而且 n = 48 c d_1=25c,d_2=10c,d_3=5c,d_4=1c,而且n=48c d1?=25c,d2?=10c,d3?=5c,d4?=1c,而且n=48c。
我們可能想,要使得硬幣數(shù)目最少,那簡單啊。
先緊著面額最大的來湊就行了。
先拿個(gè)25c的、再拿兩個(gè)10c的,5c的沒法拿,于是再拿3個(gè)1c的。
于是得到貪婪解:
<1,2,0,3>
。我們這個(gè)策略就是,很簡單,先緊著最大的拿。
但是我們雖然這樣做了,而且貌似可行。
但是實(shí)際上,它對(duì)于大多數(shù)情況而言,這樣可能是沒問題的;但是沒法保證所有情況啊,你沒法保證對(duì)于所有情況、任意某一種情況,這樣都沒問題。
有一些情況,你這樣做,可能就壓根不是最優(yōu)解了。
但是:
- 對(duì)大多數(shù)常用的硬幣面額都可以得到最優(yōu)解。
- 對(duì)任意硬幣面額,有可能不是最優(yōu)解。
例如:
d 1 = 25 c , d 2 = 10 c , d 3 = 1 c 而且 n = 30 c d_1=25c,d_2=10c,d_3=1c而且n=30c d1?=25c,d2?=10c,d3?=1c而且n=30c。
那么你還按照上面的規(guī)則,
先拿個(gè)25c的,然后拿五個(gè)1c的。——此時(shí)是6個(gè)硬幣。
但實(shí)際上我們可以看出,直接拿三個(gè)10c的就夠了,而且只用3個(gè)硬幣。
所以可見,我們剛才的那種簡單的想法:先緊著大面額的拿。
這種方法,可能在某些情況下沒毛病,但是在有些情況下就不對(duì)了、不是最優(yōu)解了。
**那咋辦呢。**是不是我的想法、我的策略設(shè)計(jì)的有問題呢?
那到底咋樣弄,才能對(duì)于所有情況都能得到最優(yōu)解呢?
我們可以用回溯法。(不是講貪心嗎,咋又說回溯了?——后面再說這個(gè)問題)
- **貪婪法:**建議通過一系列步驟來構(gòu)造問題的解,每一步對(duì)目前構(gòu)造的部分解做一個(gè)擴(kuò)展,直到獲得問題的完全解。(完全解,不是最優(yōu)解)
- 必須滿足:可行、局部最優(yōu)、不可取消。
貪心算法要求
- 可行的:即它必須滿足問題的約束。
- 局部最優(yōu):它是當(dāng)前步驟中所有可行選擇中最佳的局部選擇。
- 不可取消:即選擇一旦做出,在算法的后面步驟中就無法改變了。
就像人生中的一些選擇一樣,就是貪心算法么,每次選的是局部最優(yōu),而且選了之后就沒法取消了。
??在每一步中,它要求“貪婪”地選擇最佳操作,并希望通過一系列局部的最優(yōu)選擇,能夠產(chǎn)生一個(gè)整個(gè)問題的(全局的)最優(yōu)解。
基本思想
- 從問題的某一個(gè)初始解出發(fā),通過一系列的貪心選擇(當(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)稱為貪心準(zhǔn)則(greedy criterion)。
- 貪心算法的正確性,就是要證明按貪心準(zhǔn)則求得的解是全局最優(yōu)解。
- 貪心算法不能對(duì)所有問題都得到全局最優(yōu)解。
- 但是對(duì)于許多問題,它能夠產(chǎn)生全局最優(yōu)解。如單源最短路徑問題,最小生成樹問題等。
適合求解問題的特征
- **貪心選擇性質(zhì):**可通過局部最優(yōu)(貪心)選擇達(dá)到全局最優(yōu)解。
- 通常以自頂向下的方式進(jìn)行,每次選擇后將問題轉(zhuǎn)化為規(guī)模更小的子問題。
- 該性質(zhì)是貪心法使用成功的保障,否則得到的是近優(yōu)解。
- 最優(yōu)子結(jié)構(gòu)性質(zhì):問題的最優(yōu)解包含它的子問題的最優(yōu)解。
- 并不是所有具有最優(yōu)子結(jié)構(gòu)性質(zhì)的問題都可以采用貪心策略。
- 往往可以利用最優(yōu)子結(jié)構(gòu)性質(zhì)來證明貪心選擇性質(zhì)。
背包問題
- 0-1背包問題
??給定n種物品和一個(gè)背包。物品i
的重量是 W i W_i Wi?,其價(jià)值為 V i V_i Vi?,背包的容量為C
。應(yīng)如何選擇裝入背包的物品,使得裝入背包中物品的總價(jià)值最大?
0-1背包問題,對(duì)于一個(gè)物品,0就是不拿它,1就是拿它。
在選擇裝入背包的物品時(shí),對(duì)每種物品只有兩種選擇,要么裝入背包、要么不裝入背包。不能將一個(gè)物品裝入背包多次,也不能只裝入某物品的一部分。
- 背包問題
??與0-1背包問題類似,所不同的是,在選擇物品i
裝入背包時(shí),可以選擇物品i的一部分,而不一定要全部裝入背包,1≤i≤n
。
背包問題,也叫“分?jǐn)?shù)背包問題”,對(duì)于一個(gè)物品,物品太大了,背包剩余空間不夠了,此時(shí)我可以把物品拆下來、把一部分放進(jìn)去。
0/1背包問題
- 已知
- 背包容量C>0
- n個(gè)物品,體積 w i > 0 w_i>0 wi?>0,價(jià)值 p i > 0 f o r i = 1 , . . . , n p_i>0\ for\ i=1,...,n pi?>0?for?i=1,...,n
- 確定 { 1 , 2 , . . . , n } \{1,2,...,n\} {1,2,...,n}的子集,滿足:
m a x ∑ i ∈ A p i , s u b j e c t t o ∑ i ∈ A w i ≤ C max\sum_{i∈A}p_i,subject\ to\ \sum_{i∈A}w_i≤C maxi∈A∑?pi?,subject?to?i∈A∑?wi?≤C
0/1背包問題——貪心法
-
有以下幾種貪心選擇準(zhǔn)則:
- 最大價(jià)值優(yōu)先——先選擇最值錢的物品。
緊著最值錢的先往上放。
- 最小體積優(yōu)先
緊著最小體積的先放,想裝的多。
- 最大體積優(yōu)先
想著一般大的東西都比較值錢?所以先緊著大件先放?
- 最大單位價(jià)值優(yōu)先
這四個(gè)規(guī)則都有一定道理,那我們?cè)撨x哪種呢?選最大價(jià)值優(yōu)先?選最大單位價(jià)值優(yōu)先?
- 沒有一種方法能保證得到最優(yōu)解
最大價(jià)值優(yōu)先
(lb
是重量單位,上面是價(jià)錢)
可見,最大價(jià)值優(yōu)先,放進(jìn)來的不一定是最優(yōu)解。
最小體積優(yōu)先
可見,最小體積優(yōu)先,放進(jìn)來的也不一定是最優(yōu)解。
最大體積優(yōu)先
可見,最大體積優(yōu)先得到的也不一定是最優(yōu)解。
最大單位價(jià)值優(yōu)先
可見,這個(gè)也不一定能得到最優(yōu)解。
分?jǐn)?shù)背包問題
- 對(duì)于0/1背包問題,沒有最優(yōu)的貪心算法。
- 分?jǐn)?shù)背包問題:可以將第
i
個(gè)物品的一部分放入背包。 - 對(duì)于分?jǐn)?shù)背包問題,貪心算法是其不二選擇,該算法基于最大單位價(jià)值的選擇準(zhǔn)則。(感覺有點(diǎn)類似于微積分里的微元思想)
這個(gè)就沒啥好猶豫的了,我先緊著最大單位價(jià)值的往里面放,放不下整個(gè)物品的時(shí)候,我把當(dāng)前最大單位價(jià)值的物品切出來一塊往里面放。
這樣最后包里放的肯定是價(jià)值最大的情況。
- 貪心算法過程:
- 降序排序 v i / w i v_i/w_i vi?/wi?。
- 根據(jù)排序次序增加物品,直到這個(gè)物品裝完,或是超出背包容量。
- 如果背包沒有滿,選擇下一個(gè)物品開始裝。
最優(yōu)解證明
- 證明:
??我們首先假設(shè)我們有一個(gè)最優(yōu)解 A 1 A_1 A1?,那么我們首先找到 A 1 A_1 A1?里面平均價(jià)值最高的物品 a m a_m am?,然后我們將用商品里面平均價(jià)值最高的物品 a 1 a_1 a1?將 a m a_m am?進(jìn)行全部替換或者部分替換得到解 A 2 A_2 A2?,又因?yàn)?span id="vxwlu0yf4" class="katex--inline"> v 1 w 1 ≥ v m w m \frac{v_1}{w_1}≥\frac{v_m}{w_m} w1?v1??≥wm?vm??,所以 A 2 A_2 A2?的總價(jià)值高于 A 1 A_1 A1?的總價(jià)值,這與 A 1 A_1 A1?是最優(yōu)解矛盾,于是得到 A 1 A_1 A1?里面包含平均價(jià)值最高的物品。
- 小數(shù)背包問題還具有貪心選擇性質(zhì),用貪心法求解更簡單、更快速。
- 0-1背包問題用貪心法求解不一定能得到最優(yōu)解。
任務(wù)調(diào)度問題
- 9個(gè)任務(wù)需要調(diào)度,每個(gè)任務(wù)運(yùn)行時(shí)間為
3,5,6,10,11,14,15,18,20
如果只有一個(gè)處理器,那就沒啥說的,每個(gè)任務(wù)看看按照什么規(guī)則往里放就行了,反正最后總時(shí)間是一樣的。
但是如果有多個(gè)處理器呢?
- 有三個(gè)處理器執(zhí)行這些任務(wù)。
當(dāng)然,對(duì)于貪心而言,我們對(duì)這一問題也可以有很多種貪心策略。
- 貪心準(zhǔn)則:先運(yùn)行時(shí)間最長的任務(wù)。
每次把當(dāng)前需要運(yùn)行最長時(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í)長,沒有任何的浪費(fèi)。
??但是,可見,若想得到這樣的一種解。你要付出的代價(jià)就會(huì)很高了。
??有必要么,實(shí)際解決一個(gè)問題來說,這樣去搞,可能沒這個(gè)必要。你找到最優(yōu)解了之后,最優(yōu)解固然能夠幫你節(jié)約時(shí)間;但是不要忽視了,你尋找這個(gè)最優(yōu)解也要花時(shí)間。你為了找一個(gè)最優(yōu)解去節(jié)約那一點(diǎn)點(diǎn)時(shí)間,然后你花了大量的時(shí)間在尋找到最優(yōu)解上,得不償失。
類似上圖中這個(gè)最優(yōu)解,是咋找到的?可能是暴力窮舉吧,或者是什么方法??傊芎臅r(shí)間才能找出來的。
??實(shí)際上我就用一種貪心策略,去做,就拉倒了。雖然可能不是最優(yōu),但是接近最優(yōu)差不多就行了。
??對(duì)于一些特殊的問題,貪心算法能直接找出其最優(yōu)解,能直接獲取最優(yōu)解那當(dāng)然更好了。
??總之貪心算法可能找到的不是最優(yōu)解,而只是局部最優(yōu)解;但是它的實(shí)現(xiàn)是很簡單的,不會(huì)耗費(fèi)太多時(shí)間。
??同時(shí),我們?cè)谪澬?#xff0c;貪的過程中,也可以利用回溯法的思想,對(duì)一些沒必要繼續(xù)探討下去的情況進(jìn)行剪枝,而沒必要全部貪到底、再去排除。也就是貪心法配合回溯法進(jìn)行使用。
活動(dòng)選擇問題
- 這個(gè)就是活動(dòng)選擇問題。
我選擇哪些活動(dòng),能夠讓活動(dòng)數(shù)量最多?
活動(dòng)選擇——貪心法
- 貪心法選擇準(zhǔn)則:
- 最早開始時(shí)間優(yōu)先
- 最小持續(xù)時(shí)間優(yōu)先
- 最早完成時(shí)間優(yōu)先
- 哪個(gè)準(zhǔn)則更有效?
最早開始時(shí)間優(yōu)先。
假設(shè)有一個(gè)從0開始的活動(dòng),但是它持續(xù)時(shí)間巨長。
那這顯然不是最優(yōu)解。
如上圖。
這個(gè)持續(xù)時(shí)間最小,但是可能因?yàn)樽隽怂?#xff0c;它剛好介于兩個(gè)活動(dòng)鄰接點(diǎn),導(dǎo)致兩個(gè)活動(dòng)都沒法做。
顯然也不是最優(yōu)解。
最早結(jié)束時(shí)間是不是能達(dá)到這個(gè)問題的最優(yōu)解?
實(shí)際上,按最早結(jié)束時(shí)間優(yōu)先,基本上都能取到最優(yōu)解。
怎么證明這種策略的正確性?怎么知道上面的例子不是它的特例?
- 需要證明貪心法的正確性。
最早結(jié)束時(shí)間優(yōu)先——最優(yōu)性證明
**定理:**如果活動(dòng) a 1 a_1 a1?在所有活動(dòng)中具有最早結(jié)束時(shí)間,則最優(yōu)解中一定包含 a 1 a_1 a1?。
證明:
- 令 A A A是最優(yōu)解, a 1 a_1 a1?是貪心法選擇的最早結(jié)束時(shí)間的活動(dòng)。如果 a 1 ∈ A a_1∈A a1?∈A,則定理得證。
- 如果 a 1 ? A a_1?A a1?∈/A,我們證明 A ? = A ? { a } + { a 1 } A^*=A-\{a\}+\{a_1\} A?=A?{a}+{a1?}是另一個(gè)包含 a 1 a_1 a1?的最優(yōu)解,而 a a a是 A A A中具有最早結(jié)束時(shí)間的活動(dòng)。
- 因?yàn)榛顒?dòng)的結(jié)束時(shí)間已排序好, f ( a 1 ) ≤ f ( a ) f(a_1)≤f(a) f(a1?)≤f(a)。假設(shè) f ( a 1 ) ≤ s ( a ) f(a_1)≤s(a) f(a1?)≤s(a),如果我們把 a 1 a_1 a1?加到 A A A,意味著 A A A不是最優(yōu)的。所以 s ( a ) < f ( a 1 ) s(a)<f(a_1) s(a)<f(a1?),并且 a 1 a_1 a1?和 a a a重疊。因?yàn)?span id="vxwlu0yf4" class="katex--inline"> f ( a 1 ) ≤ f ( a ) f(a_1)≤f(a) f(a1?)≤f(a),如果我們移除 a a a添加 a 1 a_1 a1?,可以得到另一個(gè)最優(yōu)解 A ? A^* A?包含了 a 1 a_1 a1?。 A ? A^* A?是最優(yōu)的,因?yàn)?span id="vxwlu0yf4" class="katex--inline"> ∣ A ? ∣ = ∣ A ∣ |A^*|=|A| ∣A?∣=∣A∣。
沒太看懂。
**定理:**貪心子選擇一定產(chǎn)生最優(yōu)解。
即,證明去掉一個(gè) a 1 a_1 a1?之后,對(duì)剩下的活動(dòng)做最早結(jié)束時(shí)間優(yōu)先策略,得到的也是子集的最優(yōu)解。
證明:
- 令 a 1 a_1 a1?是貪心算法選擇的活動(dòng)。
- 令 S ? S^* S?是不與 a 1 a_1 a1?重疊的活動(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 B B是 S ? S^* S?的最優(yōu)解。
-
從 S ? S^* S?的定義可知, A ? = { a 1 } ∪ B A^*=\{a_1\}∪B A?={a1?}∪B是可行的,并且是原問題的解。
-
利用反證法證明 A ? A^* A?是最優(yōu)解。
-
假設(shè) A ? A^* A?不是最優(yōu)解,令 A A A是包含 a 1 a_1 a1?的最優(yōu)解,則 ∣ A ? ∣ < ∣ A ∣ |A^*|<|A| ∣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 ? S^* S?的解,與 B B B是 S ? S^* S?的最優(yōu)解矛盾。
-
所以 A ? A^* A?一定是原問題的最優(yōu)解。
Prim算法
- 連通圖的一棵生成樹是包含圖的所有定點(diǎn)的連通無環(huán)子圖(一棵樹)。
- 加權(quán)連通圖的一棵最小生成樹是圖的一棵權(quán)重最小的生成樹。
??從某個(gè)點(diǎn)出發(fā),首先找和它相鄰連接的結(jié)點(diǎn)中,權(quán)值最小的是誰。是b結(jié)點(diǎn)、權(quán)值為4,那就把b結(jié)點(diǎn)并入進(jìn)來。接著,再找下一條邊,就找和a、b相鄰的結(jié)點(diǎn)中,權(quán)值最小的是哪個(gè)邊,并且把那個(gè)結(jié)點(diǎn)并入進(jìn)來。
??總之,可以視作兩個(gè)集合:一個(gè)是已并入最小生成樹的結(jié)點(diǎn)集合,另一個(gè)是還未并入的結(jié)點(diǎn)集合。每次找這兩個(gè)集合之間權(quán)值最小的連接(不能形成環(huán))。
問題:
??一個(gè)圖,按照這種方式,找出來的所有的最小生成樹是不是都是一樣的?
??它是一棵樹,樹的結(jié)構(gòu)是由什么決定的?——我每次的起始點(diǎn)選取不同,它的樹根結(jié)點(diǎn)不一樣,肯定就不一樣了。
總結(jié)
??貪心策略的選擇很重要。
??貪心在某些情況下是可以拿到最優(yōu)的,但是很容易得到一個(gè)局部最優(yōu)而非全局最優(yōu)的解。