標籤: 暫無標籤

貪心演算法(又稱貪婪演算法)是指,在對問題求解時,總是做出在當前看來是最好的選擇。也就是說,不從整體最優上加以考慮,他所做出的僅是在某種意義上的局部最優解。貪心演算法不是對所有問題都能得到整體最優解,但對範圍相當廣泛的許多問題他能產生整體最優解或者是整體最優解的近似解。

1概念

貪婪演算法(Greedy algorithm)是一種對某些求最優解問題的更簡單、更迅速的設計技術。用貪婪法設計演算法的特點是一步一步地進行,常以當前情況為基礎根據某個優化測度作最優選擇,而不考慮各種可能的整體情況,它省去了為找最優解要窮盡所有可能而必須耗費的大量時間,它採用自頂向下,以迭代的方法做出相繼的貪心選擇,每做一次貪心選擇就將所求問題簡化為一個規模更小的子問題,通過每一步貪心選擇,可得到問題的一個最優解,雖然每一步上都要保證能獲得局部最優解,但由此產生的全局解有時不一定是最優的,所以貪婪法不要回溯。
貪婪演算法是一種改進了的分級處理方法。其核心是根據題意選取一種量度標準。然後將這多個輸入排成這種量度標準所要求的順序,按這種順序一次輸入一個量。如果這個輸入和當前已構成在這種量度意義下的部分最佳解加在一起不能產生一個可行解,則不把此輸入加到這部分解中。這種能夠得到某種量度意義下最優解的分級處理方法稱為貪婪演算法。
對於一個給定的問題,往往可能有好幾種量度標準。初看起來,這些量度標準似乎都是可取的,但實際上,用其中的大多數量度標準作貪婪處理所得到該量度意義下的最優解並不是問題的最優解,而是次優解。因此,選擇能產生問題最優解的最優量度標準是使用貪婪演算法的核心。
一般情況下,要選出最優量度標準並不是一件容易的事,但對某問題能選擇出最優量度標準后,用貪婪演算法求解則特別有效。最優解可以通過一系列局部最優的選擇即貪婪選擇來達到,根據當前狀態做出在當前看來是最好的選擇,即局部最優解選擇,然後再去解做出這個選擇后產生的相應的子問題。每做一次貪婪選擇就將所求問題簡化為一個規模更小的子問題,最終可得到問題的一個整體最優解。

2特性

貪婪演算法可解決的問題通常大部分都有如下的特性:
⑴ 有一個以最優方式來解決的問題。為了構造問題的解決方案,有一個候選的對象的集合:比如不同面值的硬幣。
⑵ 隨著演算法的進行,將積累起其它兩個集合:一個包含已經被考慮過並被選出的候選對象,另一個包含已經被考慮過但被丟棄的候選對象。
⑶ 有一個函數來檢查一個候選對象的集合是否提供了問題的解答。該函數不考慮此時的解決方法是否最優。
⑷ 還有一個函數檢查是否一個候選對象的集合是可行的,也即是否可能往該集合上添加更多的候選對象以獲得一個解。和上一個函數一樣,此時不考慮解決方法的最優性。
⑸ 選擇函數可以指出哪一個剩餘的候選對象最有希望構成問題的解。
⑹ 最後,目標函數給出解的值。
為了解決問題,需要尋找一個構成解的候選對象集合,它可以優化目標函數,貪婪演算法一步一步的進行。起初,演算法選出的候選對象的集合為空。接下來的每一步中,根據選擇函數,演算法從剩餘候選對象中選出最有希望構成解的對象。如果集合中加上該對象后不可行,那麼該對象就被丟棄並不再考慮;否則就加到集合里。每一次都擴充集合,並檢查該集合是否構成解。如果貪婪演算法正確工作,那麼找到的第一個解通常是最優的。

3基本思路

⒈建立數學模型來描述問題。
⒉把求解的問題分成若干個子問題。
⒊對每一子問題求解,得到子問題的局部最優解。
⒋把子問題的解局部最優解合成原來解問題的一個解。
實現該演算法的過程:
從問題的某一初始解出發;
while 能朝給定總目標前進一步 do
求出可行解的一個解元素;
由所有解元素組合成問題的一個可行解。
下面是一個可以試用貪心演算法解的題目,貪心解的確不錯,可惜不是最優解。

4例題分析

[0-1背包問題]有一個背包,背包容量是M=150。有7個物品,物品不可以分割成任意大小。
要求儘可能讓裝入背包中的物品總價值最大,但不能超過總容量。
物品 A B C D E F G
重量 35 30 60 50 40 10 25
價值 10 40 30 50 35 40 30
分析:
目標函數:∑pi最大
約束條件是裝入的物品總重量不超過背包容量:∑wi<=M(M=150)
⑴根據貪心的策略,每次挑選價值最大的物品裝入背包,得到的結果是否最優?
⑵每次挑選所佔重量最小的物品裝入是否能得到最優解?
⑶每次選取單位重量價值最大的物品,成為解本題的策略。
值得注意的是,貪心演算法並不是完全不可以使用,貪心策略一旦經過證明成立后,它就是一種高效的演算法。
貪心演算法還是很常見的演算法之一,這是由於它簡單易行,構造貪心策略不是很困難。
可惜的是,它需要證明后才能真正運用到題目的演算法中。
一般來說,貪心演算法的證明圍繞著:整個問題的最優解一定由在貪心策略中存在的子問題的最優解得來的。
對於例題中的3種貪心策略,都是無法成立(無法被證明)的,解釋如下:
⑴貪心策略:選取價值最大者。
反例:
W=30
物品:A B C
重量:28 12 12
價值:30 20 20
根據策略,首先選取物品A,接下來就無法再選取了,可是,選取B、C則更好。
⑵貪心策略:選取重量最小。它的反例與第一種策略的反例差不多。
⑶貪心策略:選取單位重量價值最大的物品。
反例:
W=30
物品:A B C
重量:28 20 10
價值:28 20 10
根據策略,三種物品單位重量價值一樣,程序無法依據現有策略作出判斷,如果選擇A,則答案錯誤。
【注意:如果物品可以分割為任意大小,那麼策略3可得最優解】
對於選取單位重量價值最大的物品這個策略,可以再加一條優化的規則:對於單位重量價值一樣的,則優先選擇重量小的!這樣,上面的反例就解決了。
但是,如果題目是如下所示,這個策略就也不行了。
W=40
物品:A B C
重量:25 20 15
價值:25 20 15
附:本題是個DP問題,用貪心法並不一定可以求得最優解,以後了解了動態規劃演算法后本題就有了新的解法。

5備註

貪心演算法當然也有正確的時候。求最小生成樹的Prim演算法和Kruskal演算法都是漂亮的貪心演算法。
貪心法的應用演算法有Dijkstra的單源最短路徑和Chvatal的貪心集合覆蓋啟髮式
所以需要說明的是,貪心演算法可以與隨機化演算法一起使用,具體的例子就不再多舉了。(因為這一類演算法普及性不高,而且技術含量是非常高的,需要通過一些反例確定隨機的對象是什麼,隨機程度如何,但也是不能保證完全正確,只能是極大的幾率正確)

6例題

馬踏棋盤的貪心演算法
123041-23 XX
【問題描述】
馬的遍歷問題。在8×8方格的棋盤上,從任意指定方格出發,為馬尋找一條走遍棋盤每一格並且只經過一次的一條最短路徑。
【初步設計】
首先這是一個搜索問題,運用深度優先搜索進行求解。演算法如下:
⒈ 輸入初始位置坐標x,y;
⒉ 步驟 c:
如果c> 64輸出一個解,返回上一步驟c--
(x,y) ← c
計算(x,y)的八個方位的子結點,選出那此可行的子結點
循環遍歷所有可行子結點,步驟c++重複2
顯然⑵是一個遞歸調用的過程,大致如下:
#define N 8
……
……
void dfs(int x,int y,int count)
{
int i,tx,ty;
if(count> N*N)
{
output_solution();//輸出一個解
return;
}
for(I=0;i <8;++i)
{
tx=hn[i].x;//hn[]保存八個方位子結點
ty=hn[i].y;
s[tx][ty]=count;
dfs(tx,ty,count+1);//遞歸調用
s[tx][ty]=0;
}
}
Pascal程序:
Program YS;
Const FXx:array[1..8]of -2..2=(1,2,2,1,-1,-2,-2,-1);
FXy:array[1..8]of -2..2=(2,1,-1,-2,-2,-1,1,2);
Var
Road:array[1..10,1..10]of integer;
x,y,x1,y1,total:integer;
Procedure Find(x,y:integer);
var Nx,Ny,i:integer;
Begin
For i:=1 to 8 do begin {8個方向}
If (x+FXx[i] in [1..8]) and (y+FXy[i] in [1..8]) Then{確定新坐標是否越界}
If Road[x+Fxx[i],y+Fxy[i]]=0 Then begin{判斷是否走過}
Nx:=x+FXx[i]; Ny:=y+FXy[i]; Road[Nx,Ny]:=1;{建立新坐標}
If (Nx=x1) and (Ny=y1) Then inc(total)
else Find(Nx,Ny); {遞歸}
Road[Nx,Ny]:=0 {回朔}
end
end
End;
BEGIN{Main}
Total:=0;
FillChar(Road,sizeof(road),0);
Readln(x,y); {讀入開始坐標}
Readln(x1,y1); {讀入結束坐標}
If (x>10) or (y>10) or (x1>10) or (y1>10) Then writeln('Eorror') {判斷是否越界}
Else Find(x,y);
Writeln('Total:',total) {打出總數}
END.
這樣做是完全可行的,它輸入的是全部解,但是馬遍歷當8×8時解是非常之多的,用天文數字形容也不為過,這樣一來求解的過程就非常慢,並且出一個解也非常慢。
怎麼才能快速地得到部分解呢?
【貪心演算法】
其實馬踏棋盤的問題很早就有人提出,且早在1823年,J.C.Warnsdorff就提出了一個有名的演算法。在每個結點對其子結點進行選取時,優先選擇『出口』最小的進行搜索,『出口』的意思是在這些子結點中它們的可行子結點的個數,也就是『孫子』結點越少的越優先跳,為什麼要這樣選取,這是一種局部調整最優的做法,如果優先選擇出口多的子結點,那出口少的子結點就會越來越多,很可能出現『死』結點(顧名思義就是沒有出口又沒有跳過的結點),這樣對下面的搜索純粹是徒勞,這樣會浪費很多無用的時間,反過來如果每次都優先選擇出口少的結點跳,那出口少的結點就會越來越少,這樣跳成功的機會就更大一些。這種演算法稱為為貪心演算法,也叫貪婪演算法或啟髮式演算法,它對整個求解過程的局部做最優調整,它只適用於求較優解或者部分解,而不能求最優解。這樣的調整方法叫貪心策略,至於什麼問題需要什麼樣的貪心策略是不確定的,具體問題具體分析。實驗可以證明馬遍歷問題在運用到了上面的貪心策略之後求解速率有非常明顯的提高,如果只要求出一個解甚至不用回溯就可以完成,因為在這個演算法提出的時候世界上還沒有計算機,這種方法完全可以用手工求出解來,其效率可想而知。

7數學應用

如把3/7和13/23分別化為三個單位分數的和
【貪心演算法】
設a、b為互質正整數,a<b 分數a/b 可用以下的步驟分解成若干個單位分數之和:
步驟一: 用b 除以a,得商數q1 及餘數r1。(r1=b - a*q1)
步驟二:把a/b 記作:a/b=1/(q1+1)+(a-r)/b(q1+1)
步驟三:重複步驟2,直到分解完畢
3/7=1/3+2/21=1/3+1/11+1/231
13/23=1/2+3/46=1/2+1/16+1/368
以上其實是數學家斐波那契提出的一種求解埃及分數的貪心演算法,準確的演算法表述應該是這樣的:
設某個真分數的分子為a,分母為b;
把b除以a的商部分加1后的值作為埃及分數的某一個分母c;
將a乘以c再減去b,作為新的a;
將b乘以c,得到新的b;
如果a大於1且能整除b,則最後一個分母為b/a;演算法結束;
或者,如果a等於1,則,最後一個分母為b;演算法結束;
否則重複上面的步驟。
備註:事實上,後面判斷a是否大於1和a是否等於1的兩個判斷可以合在一起,及判斷b%a是否等於0,最後一個分母為b/a,顯然是正確的。
上一篇[孕早期]    下一篇 [帕斯卡語言]

相關評論

同義詞:暫無同義詞