貪心算法簡介

1、貪心算法 一、算法思想貪心法的基本思路：從問題的某一個初始解出發(fā)逐步逼近給定的目標(biāo)，以盡可能快的地求得更好的解。當(dāng)達(dá)到某算法中的某一步不能再繼續(xù)前進(jìn)時，算法停止。該算法存在問題：1. 不能保證求得的最后解是最佳的；2. 不能用來求最大或最小解問題；3. 只能求滿足某些約束條件的可行解的范圍。實現(xiàn)該算法的過程：從問題的某一初始解出發(fā)；while 能朝給定總目標(biāo)前進(jìn)一步 do求出可行解的一個解元素；由所有解元素組合成問題的一個可行解；二、例題分析1、背包問題有一個背包，背包容量是M=150。有7個物品，物品可以分割成任意大小。要求盡可能讓裝入背包中的物品總價值最大，但不能超過總?cè)萘?。物品A B C

2、 D E F G 重量 35 30 60 50 40 10 25 價值 10 40 30 50 35 40 30  分析：目標(biāo)函數(shù)： pi最大約束條件是裝入的物品總重量不超過背包容量：wi<=M( M=150)（1）根據(jù)貪心的策略，每次挑選價值最大的物品裝入背包，得到的結(jié)果是否最優(yōu)？（2）每次挑選所占空間最小的物品裝入是否能得到最優(yōu)解？（3）每次選取單位容量價值最大的物品，成為解本題的策略。 源程序2、單源最短路徑一個有向圖G，它的每條邊都有一個非負(fù)的權(quán)值ci,j，“路徑長度”就是所經(jīng)過的所有邊的權(quán)值之和。對于源點需要找出從源點出發(fā)到達(dá)其他所有結(jié)點的最短路徑。E.Dijkstr

3、a發(fā)明的貪婪算法可以解決最短路徑問題。算法的主要思想是：分步求出最短路徑，每一步產(chǎn)生一個到達(dá)新目的頂點的最短路徑。下一步所能達(dá)到的目的頂點通過如下貪婪準(zhǔn)則選?。涸谖串a(chǎn)生最短路徑的頂點中，選擇路徑最短的目的頂點。設(shè)置頂點集合S并不斷作貪心選擇來擴(kuò)充這個集合。當(dāng)且僅當(dāng)頂點到該頂點的最短路徑已知時該頂點屬于集合S。初始時S中只含源。 設(shè)u為G中一頂點，我們把從源點到u且中間僅經(jīng)過集合S中的頂點的路稱為從源到u特殊路徑，并把這個特殊路徑記錄下來（例如程序中的disti，j）。每次從V-S選出具有最短特殊路徑長度的頂點u，將u添加到S中，同時對特殊路徑長度進(jìn)行必要的修改。一旦V=S，就得到從源到其他所有

4、頂點的最短路徑，也就得到問題的解 。 Dijkstra.pas 3、機器調(diào)度現(xiàn)有N項任務(wù)和無限多臺機器。任務(wù)可以在機器上處理。每件任務(wù)開始時間和完成時間有下表：任務(wù)abcdefg開始(si)0349716完成(fi)277111058在可行分配中每臺機器在任何時刻最多處理一個任務(wù)。最優(yōu)分配是指使用的機器最少的可行分配方案。請就本題給出的條件，求出最優(yōu)分配。 三、練習(xí)題：已知5個城市之間有班機傳遞郵件，目的是為了尋找一條耗油量較少的飛行路線。5個城市的聯(lián)系網(wǎng)絡(luò)如圖所示。圖中編號的結(jié)點表示城市，兩個城市之間的連線上的值表示班機沿該航線已行的耗油量，并假定從城市i到j(luò)和城市j到i

5、之間的耗油量是相同的。分析：1. 運用貪心思想：在每一步前進(jìn)的選擇上，選取相對當(dāng)前城市耗油量最小的航線；2. 圖解：若從1出發(fā)，有圖：總耗油量=14 1-2-5-3-4-1但若路線改為：1-5-3-4-2-1，則總耗油量=13所以，這樣的貪心法并不能得出最佳解。3. 改善方案：從所有城市出發(fā)的信心過程，求最優(yōu)的。編程：1. 數(shù)據(jù)結(jié)構(gòu)：城市聯(lián)系網(wǎng)絡(luò)圖的描述(圖的鄰接矩陣的描述)：constc=array1.5,1.5 of integer=(0,1,2,7,5),(1,0,4,4,3),(2,4,0,1,2),(7,4,1,0,3);2. 貪心過程：begin初始化所有城市的算途徑標(biāo)志；設(shè)置出發(fā)城市V；for i:=1 to n-1 do n-1個城市begins:=從V至所有未曾到過的城市的邊集中耗油量最少的那個城市；累加耗油量；V:=s；設(shè)V城市的訪問標(biāo)志；end;最后一個城市返回第一個城市，累加耗油量；end;3. 主過程：實現(xiàn)改善方案beginfor i:=1 t