本文在寫作過程中參考了大量資料，不能一一列舉，還請見諒。
貪心算法的定義：
貪心算法是指在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優(yōu)上加以考慮，只做出在某種意義上的局部最優(yōu)解。貪心算法不是對所有問題都能得到整體最優(yōu)解，關鍵是貪心策略的選擇，選擇的貪心策略必須具備無后效性，即某個狀態(tài)以前的過程不會影響以后的狀態(tài)，只與當前狀態(tài)有關。
解題的一般步驟是：
1.建立數學模型來描述問題；
2.把求解的問題分成若干個子問題；
3.對每一子問題求解，得到子問題的局部最優(yōu)解；
4.把子問題的局部最優(yōu)解合成原來問題的一個解。
如果大家比較了解動態(tài)規(guī)劃，就會發(fā)現它們之間的相似之處。最優(yōu)解問題大部分都可以拆分成一個個的子問題，把解空間的遍歷視作對子問題樹的遍歷，則以某種形式對樹整個的遍歷一遍就可以求出最優(yōu)解，大部分情況下這是不可行的。貪心算法和動態(tài)規(guī)劃本質上是對子問題樹的一種修剪，兩種算法要求問題都具有的一個性質就是子問題最優(yōu)性(組成最優(yōu)解的每一個子問題的解，對于這個子問題本身肯定也是最優(yōu)的)。動態(tài)規(guī)劃方法代表了這一類問題的一般解法，我們自底向上構造子問題的解，對每一個子樹的根，求出下面每一個葉子的值，并且以其中的最優(yōu)值作為自身的值，其它的值舍棄。而貪心算法是動態(tài)規(guī)劃方法的一個特例，可以證明每一個子樹的根的值不取決于下面葉子的值，而只取決于當前問題的狀況。換句話說，不需要知道一個節(jié)點所有子樹的情況，就可以求出這個節(jié)點的值。由于貪心算法的這個特性，它對解空間樹的遍歷不需要自底向上，而只需要自根開始，選擇最優(yōu)的路，一直走到底就可以了。
話不多說，我們來看幾個具體的例子慢慢理解它：
1.活動選擇問題
這是《算法導論》上的例子，也是一個非常經典的問題。有n個需要在同一天使用同一個教室的活動a1,a2,…,an，教室同一時刻只能由一個活動使用。每個活動ai都有一個開始時間si和結束時間fi 。一旦被選擇后，活動ai就占據半開時間區(qū)間[si,fi)。如果[si,fi]和[sj,fj]互不重疊，ai和aj兩個活動就可以被安排在這一天。該問題就是要安排這些活動使得盡量多的活動能不沖突的舉行。例如下圖所示的活動集合S，其中各項活動按照結束時間單調遞增排序。
考慮使用貪心算法的解法。為了方便，我們用不同顏色的線條代表每個活動，線條的長度就是活動所占據的時間段，藍色的線條表示我們已經選擇的活動；紅色的線條表示我們沒有選擇的活動。
如果我們每次都選擇開始時間最早的活動，不能得到最優(yōu)解：
延伸閱讀
- ssh框架 2016-09-30
- 阿里移動安全 [無線安全]玩轉無線電——不安全的藍牙鎖 2017-07-26
- 消息隊列NetMQ 原理分析4-Socket、Session、Option和Pipe 2024-03-26
- Selective Search for Object Recognition 論文筆記【圖片目標分割】 2017-07-26
- 詞向量-LRWE模型-更好地識別反義詞同義詞 2017-07-26
- 從棧不平衡問題 理解 calling convention 2017-07-26
- php imagemagick 處理 圖片剪切、壓縮、合并、插入文本、背景色透明 2017-07-26
- Swift實現JSON轉Model - HandyJSON使用講解 2017-07-26
- 阿里移動安全 Android端惡意鎖屏勒索應用分析 2017-07-26
- 集合結合數據結構來看看(二) 2017-07-26
學習是年輕人改變自己的最好方式