貪心算法（又稱貪婪算法）是指，在對(duì)問(wèn)題求解時(shí)，總是做出在當(dāng)前看來(lái)是最好的選擇。也就是說(shuō)，不從整體最優(yōu)上加以考慮，算法得到的是在某種意義上的局部最優(yōu)解。

貪心算法不是對(duì)所有問(wèn)題都能得到整體最優(yōu)解，關(guān)鍵是貪心策略的選擇。

算法思路

貪心算法一般按如下步驟進(jìn)行：

①建立數(shù)學(xué)模型來(lái)描述問(wèn)題 。

②把求解的問(wèn)題分成若干個(gè)子問(wèn)題。

③對(duì)每個(gè)子問(wèn)題求解，得到子問(wèn)題的局部最優(yōu)解 。

④把子問(wèn)題的解局部最優(yōu)解合成原來(lái)解問(wèn)題的一個(gè)解 。

貪心算法是一種對(duì)某些求最優(yōu)解問(wèn)題的更簡(jiǎn)單、更迅速的設(shè)計(jì)技術(shù)。貪心算法的特點(diǎn)是一步一步地進(jìn)行，常以當(dāng)前情況為基礎(chǔ)根據(jù)某個(gè)優(yōu)化測(cè)度作最優(yōu)選擇，而不考慮各種可能的整體情況，省去了為找最優(yōu)解要窮盡所有可能而必須耗費(fèi)的大量時(shí)間。貪心算法采用自頂向下，以迭代的方法做出相繼的貪心選擇，每做一次貪心選擇，就將所求問(wèn)題簡(jiǎn)化為一個(gè)規(guī)模更小的子問(wèn)題，通過(guò)每一步貪心選擇，可得到問(wèn)題的一個(gè)最優(yōu)解。雖然每一步上都要保證能獲得局部最優(yōu)解，但由此產(chǎn)生的全局解有時(shí)不一定是最優(yōu)的，所以貪心算法不要回溯。

算法特性

貪心算法可解決的問(wèn)題通常大部分都有如下的特性：

1、有一個(gè)以最優(yōu)方式來(lái)解決的問(wèn)題。為了構(gòu)造問(wèn)題的解決方案，有一個(gè)候選的對(duì)象的集合：比如不同面值的硬幣 。

2、隨著算法的進(jìn)行，將積累起其他兩個(gè)集合：一個(gè)包含已經(jīng)被考慮過(guò)并被選出的候選對(duì)象，另一個(gè)包含已經(jīng)被考慮過(guò)但被丟棄的候選對(duì)象 。

3、有一個(gè)函數(shù)來(lái)檢查一個(gè)候選對(duì)象的集合是否提供了問(wèn)題的解答。該函數(shù)不考慮此時(shí)的解決方法是否最優(yōu)  。

4、還有一個(gè)函數(shù)檢查是否一個(gè)候選對(duì)象的集合是可行的，即是否可能往該集合上添加更多的候選對(duì)象以獲得一個(gè)解。和上一個(gè)函數(shù)一樣，此時(shí)不考慮解決方法的最優(yōu)性 。

5、選擇函數(shù)可以指出哪一個(gè)剩余的候選對(duì)象最有希望構(gòu)成問(wèn)題的解 。

6、最后，目標(biāo)函數(shù)給出解的值。

使用條件

利用貪心法求解的問(wèn)題應(yīng)具備如下2個(gè)特征  。

1、貪心選擇性質(zhì)

一個(gè)問(wèn)題的整體最優(yōu)解可通過(guò)一系列局部的最優(yōu)解的選擇達(dá)到，并且每次的選擇可以依賴以前作出的選擇，但不依賴于后面要作出的選擇。這就是貪心選擇性質(zhì)。對(duì)于一個(gè)具體問(wèn)題，要確定它是否具有貪心選擇性質(zhì)，必須證明每一步所作的貪心選擇最終導(dǎo)致問(wèn)題的整體最優(yōu)解 。

2、最優(yōu)子結(jié)構(gòu)性質(zhì)

當(dāng)一個(gè)問(wèn)題的最優(yōu)解包含其子問(wèn)題的最優(yōu)解時(shí)，稱此問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問(wèn)題可用貪心法求解的關(guān)鍵所在。在實(shí)際應(yīng)用中，至于什么問(wèn)題具有什么樣的貪心選擇性質(zhì)是不確定的，需要具體問(wèn)題具體分析。

解題策略

貪心算法不從整體最優(yōu)上加以考慮，所做出的僅是在某種意義上的局部最優(yōu)選擇。使用貪心策略要注意局部最優(yōu)與全局最優(yōu)的關(guān)系，選擇當(dāng)前的局部最優(yōu)并不一定能推導(dǎo)出問(wèn)題的全局最優(yōu)。貪心策略解題需要解決以下兩個(gè)問(wèn)題：

1、該問(wèn)題是否適合使用貪心策略求解，也就是該問(wèn)題是否具有貪心選擇性質(zhì)；

2、制定貪心策略，以達(dá)到問(wèn)題的最優(yōu)解或較優(yōu)解 。

要確定一個(gè)問(wèn)題是否適合用貪心算法求解，必須證明每一步所作的貪心選擇最終導(dǎo)致問(wèn)題的整體最優(yōu)解。證明的大致過(guò)程為：首先考察問(wèn)題的一個(gè)整體最優(yōu)解，并證明可修改這個(gè)最優(yōu)解，使其以貪心選擇開始，做了貪心選擇后，原問(wèn)題簡(jiǎn)化為規(guī)模更小的類似子問(wèn)題。然后用數(shù)學(xué)歸納法證明通過(guò)每一步做貪心選擇，最終可得到問(wèn)題的整體最優(yōu)解。

存在問(wèn)題

貪心算法也存在如下問(wèn)題：

1、不能保證解是最佳的。因?yàn)樨澬乃惴�總是從局部出發(fā)，并沒從整體考慮 ；

2、貪心算法一般用來(lái)解決求最大或最小解 ；

3、貪心算法只能確定某些問(wèn)題的可行性范圍 。