一、誕生原因

有如下場景：針對一組數(shù)據(jù)，我們定義了限制值和期望值，希望從中選出幾個數(shù)據(jù)，在滿足限制值的情況下，期望值最大。

為了達到上述目的，貪心算法是其中的一個解決方案。

例如，路徑選擇問題，從 S 城市至 E 城市，在只能路過 2 個城市的情況下，如何走的最短，如下圖所示：

二、基本信息

英文全稱：greedy algorithm

三、原理說明

每次選擇當前情況下，在對限制值同等貢獻量的情況下，對期望值貢獻最大的數(shù)據(jù)。

轉(zhuǎn)為解決上圖的問題的語言：保證每次從當前城市走到下一個城市的路徑最短，即：路徑為 S ? A2 ? B1 ? E ，總長度為 1 + 1 + 2 = 4 。

四、缺陷說明

貪心算法每次計算時其結(jié)果都會受到之前 n 次結(jié)果的影響，有可能之前某一次的結(jié)果導致之后的結(jié)果都是較次的，從而得不到全局最優(yōu)解。栗子：

按照貪心算法，路徑為 S ? A2 ? B1 ? E ，總長度為 1 + 5?+ 7?= 13，

但是實際上最佳路徑為 S ? A3?? B2?? E，總長度為 5?+ 2?+ 1?= 8 。

五、實際應用

1、霍夫曼編碼（Huffman Coding）

2、Prim 和 Kruskal 最小生成樹算法

3、Dijkstra 單源最短路徑算法

?

參考：極客時間《數(shù)據(jù)結(jié)構與算法之美》王爭

這門課真心推薦，內(nèi)容很經(jīng)典、栗子很形象，里面還包含了很多面試題目。真是居家旅行必備良藥。

?

（SAW：Game Over！）

?

總結(jié)

以上是生活随笔為你收集整理的数据结构与算法 / 贪心算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。