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