貪心算法簡(jiǎn)介

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

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

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

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

5、之間的耗油量是相同的。分析：1. 運(yùn)用貪心思想：在每一步前進(jìn)的選擇上，選取相對(duì)當(dāng)前城市耗油量最小的航線；2. 圖解：若從1出發(fā)，有圖：總耗油量=14 1-2-5-3-4-1但若路線改為：1-5-3-4-2-1，則總耗油量=13所以，這樣的貪心法并不能得出最佳解。3. 改善方案：從所有城市出發(fā)的信心過(guò)程，求最優(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. 貪心過(guò)程：begin初始化所有城市的算途徑標(biāo)志；設(shè)置出發(fā)城市V；for i:=1 to n-1 do n-1個(gè)城市begins:=從V至所有未曾到過(guò)的城市的邊集中耗油量最少的那個(gè)城市；累加耗油量；V:=s；設(shè)V城市的訪問(wèn)標(biāo)志；end;最后一個(gè)城市返回第一個(gè)城市，累加耗油量；end;3. 主過(guò)程：實(shí)現(xiàn)改善方案beginfor i:=1 t