貪心法與動(dòng)態(tài)規(guī)劃

貪心法與動(dòng)態(tài)規(guī)劃第1頁，共22頁，2023年，2月20日，星期日大綱◎貪心法的基本概念，以及使用貪心法解決問題：哈夫曼編碼、單源最短路徑、最小生成樹、背包問題◎動(dòng)態(tài)規(guī)劃的基本概念，以及使用動(dòng)態(tài)規(guī)劃解決問題：多源最短路徑、背包問題、圖像壓縮和最長(zhǎng)公共子序列問題。第2頁，共22頁，2023年，2月20日，星期日8.1貪心法貪心法是求解關(guān)于獨(dú)立系統(tǒng)組合優(yōu)化問題的一種簡(jiǎn)單方法。介紹貪心法的基本思想的前提下，重點(diǎn)介紹利用貪心法的思想如何解決一些實(shí)際問題如哈夫曼編碼、單源最短路徑、最小生成樹、背包問題。第3頁，共22頁，2023年，2月20日，星期日8.1.1問題提出假設(shè)有4種硬幣，它們的面值分別是二角五分、一角、五分和一分?，F(xiàn)在有一個(gè)小孩買了價(jià)值四角的東西，并給售貨員一元錢。當(dāng)售貨員找給小孩零錢時(shí)，希望她找給小孩的硬幣數(shù)目最少。為使找回的零錢的硬幣數(shù)目最少，一個(gè)很自然的方法是：首先選出1個(gè)面值不超過六角的最大硬幣，即二角五分，然后從六角減去二角五分，剩下三角五分。再選出一個(gè)面值不超過三角五分的最大硬幣，即二角五分，然后再?gòu)娜俏宸譁p去二角五分，剩下一角此時(shí)，再選一個(gè)一角的硬幣即可。這種簡(jiǎn)單地從具有最大面值的幣種開始，按遞減的順序考慮各種幣種的方法稱為貪心法(GreedyMethod)，或稱為啟發(fā)式搜索法。第4頁，共22頁，2023年，2月20日，星期日8.1.1問題提出對(duì)于諸如找零錢的類似問題可以描述為：它有n個(gè)輸入，而它的解由這n個(gè)輸入的某個(gè)子集組成，只有當(dāng)某個(gè)子集滿足某些事先給定的條件（稱為約束條件）時(shí)才稱此子集為該問題的一個(gè)可行解。顯然，滿足約束條件的子集可能有多個(gè)。因此，一般來講，可行解也存在多個(gè)。為了衡量不同可行解的優(yōu)劣，事先需要給出一定的判斷標(biāo)準(zhǔn)。這些標(biāo)準(zhǔn)一般以目標(biāo)函數(shù)的形式出現(xiàn)，只有保證目標(biāo)函數(shù)能獲取到極值的可行解才稱為最優(yōu)解。由于貪心法的精神是“今朝有酒今朝醉”。因此，每一步面臨選擇時(shí),貪心法都作對(duì)眼前來講是最有利的選擇,不考慮該選擇對(duì)將來是否有不良影響。換言之，貪心法并不從整體的角度來考慮它做出的選擇是否最優(yōu)，該選擇只是在某種意義上的局部最優(yōu)就行。即貪心法只希望得到較為滿意的解一種方法，而不是一種追求最優(yōu)解的方法。實(shí)踐表明，貪心法一般可以快速得到滿意的解，因?yàn)樗∪チ藶閷ふ易顑?yōu)解需要窮盡所有可能的操作。另外，貪心法對(duì)許多問題也能產(chǎn)生整體最優(yōu)解如對(duì)單源最短路經(jīng)、最小生成樹等問題的求解。在有些情況下，即使貪心法得不到整體最優(yōu)解，但其最終結(jié)果也可能是最優(yōu)解的近似解。第5頁，共22頁，2023年，2月20日，星期日8.1.2貪心法概述（1）貪心法的基本思想貪心法的基本思路是從問題的某一個(gè)初始解出發(fā)逐步逼近給定的目標(biāo)，以盡可能快地方法求得更好的解。即當(dāng)達(dá)到算法中的某一步不能再繼續(xù)前進(jìn)時(shí)，算法停止，得到問題的一個(gè)解。顯然，該算法有如下特點(diǎn)：①不能保證求得的最終解是最佳的；②不能用來求最大或最小等有極值要求的問題的解；③只能求得滿足某些約束條件的可行解。第6頁，共22頁，2023年，2月20日，星期日（2）貪心法的使用條件利用貪心法求解的問題應(yīng)具備如下2個(gè)特征：①貪心選擇性質(zhì)一個(gè)問題的整體最優(yōu)解可通過一系列局部的最優(yōu)解的選擇達(dá)到，并且每次的選擇可以依賴以前做出的選擇，但不依賴于后面要做出的選擇。這就是貪心選擇性質(zhì)。對(duì)于一個(gè)具體問題，要確定它是否具有貪心選擇性質(zhì)，必須證明每一步所作的貪心選擇最終導(dǎo)致問題的整體最優(yōu)解。②最優(yōu)子結(jié)構(gòu)性質(zhì)當(dāng)一個(gè)問題的最優(yōu)解包含其子問題的最優(yōu)解時(shí)，稱此問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。問題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問題可用貪心法求解的關(guān)鍵所在。在實(shí)際應(yīng)用中，至于什么問題具有什么樣的貪心選擇性質(zhì)是不確定的，需要具體問題具體分析。第7頁，共22頁，2023年，2月20日，星期日（3）解決問題的步驟利用貪心法求解問題的過程通常包含如下3個(gè)步驟：①分解將原問題分解為若干個(gè)相互獨(dú)立的階段。②解決對(duì)于每個(gè)階段求局部的最優(yōu)解，即進(jìn)行貪心選擇。在每個(gè)階段，選擇一旦做出就不可再更改。做出貪心選擇的依據(jù)稱為貪心準(zhǔn)則（GreedyCriterion）。貪心準(zhǔn)則的制定是用貪心法解決最優(yōu)化問題的關(guān)鍵，它關(guān)系到問題能否得到成功解決及解決質(zhì)量的高低。③合并將各個(gè)階段的解合并為原問題的一個(gè)可行解。

第8頁，共22頁，2023年，2月20日，星期日貪心法的設(shè)計(jì)模式

Greedy(A，n){A[0:n-1]包含n個(gè)輸入；將解向量solution初始化為空;for(i=0;i<n;i++){x=select(A)；//從問題的某一初始解出發(fā)；if(x可以包含在solutioin)solution=union(solution,x)；//部分解空間進(jìn)行合并}return(解向量solution)}第9頁，共22頁，2023年，2月20日，星期日8.2貪心法應(yīng)用舉例8.2.1哈夫曼編碼哈夫曼編碼是一種被廣泛地應(yīng)用于數(shù)據(jù)文件和圖像壓縮的編碼方式，其壓縮率通常在20%～90%之間。第10頁，共22頁，2023年，2月20日，星期日哈夫曼編碼1.問題描述在進(jìn)行遠(yuǎn)距離通信時(shí)，通常需要將要傳送的文字轉(zhuǎn)換為由二進(jìn)制字符組成的字符串，并使要傳送的電文的總長(zhǎng)度盡可能地短。顯然，只要將電文中出現(xiàn)次數(shù)較多的字符采用盡可能短的編碼，就可以減少要傳送的電文的總長(zhǎng)度。為實(shí)現(xiàn)此目標(biāo)，需要設(shè)計(jì)一種非等長(zhǎng)的編碼，且必須保證在所有字符的編碼中，任何一個(gè)字符都不是另一個(gè)字符的前綴，這種編碼稱為前綴編碼。第11頁，共22頁，2023年，2月20日，星期日回顧：哈夫曼編碼第12頁，共22頁，2023年，2月20日，星期日回顧：哈夫曼編碼第13頁，共22頁，2023年，2月20日，星期日回顧：哈夫曼樹第14頁，共22頁，2023年，2月20日，星期日哈夫曼編碼由于構(gòu)造上述編碼的方法是由哈夫曼提出的，所以，由此產(chǎn)生的編碼方案稱為哈夫曼編碼。其核心思想是：①每一個(gè)字符用一個(gè)0，1串作為其代碼，并要求任意一個(gè)字符的代碼都不是其它字符代碼的前綴；②用字符在文件中出現(xiàn)的頻率表來建立一個(gè)用0，1串表示各字符的最優(yōu)表示方式。即使出現(xiàn)頻率高的字符獲得較短的編碼，出現(xiàn)頻率較低的字符獲得較長(zhǎng)的編碼。③將字符在文件中出現(xiàn)的頻度值作為一棵二叉樹的葉子結(jié)點(diǎn)的權(quán)值。并通過構(gòu)造一棵哈夫曼樹得到最優(yōu)前綴碼。哈夫曼樹(HuffmanTree)又稱為最優(yōu)二叉樹。它是由n個(gè)帶權(quán)葉子結(jié)點(diǎn)構(gòu)成的所有二叉樹中，帶權(quán)路徑長(zhǎng)度（帶權(quán)路徑長(zhǎng)度指樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和）最小的二叉樹。構(gòu)造這種樹的方法是由哈夫曼提出的，因此稱這種樹為哈夫曼樹。顯然，尋找哈夫曼編碼的過程就是構(gòu)造哈夫曼樹的過程。第15頁，共22頁，2023年，2月20日，星期日哈夫曼編碼構(gòu)造哈夫曼樹的步驟如下：①用給定的n個(gè)權(quán)值{w1,w2,…,wn}對(duì)應(yīng)的n個(gè)結(jié)點(diǎn)構(gòu)成n棵二叉樹的森林F={T1,T2,…,Tn}，其中每一棵二叉樹Ti(1≤i≤n)都只有一個(gè)權(quán)值為wi的根結(jié)點(diǎn)，其左、右子樹為空。②在森林F中選擇兩棵根結(jié)點(diǎn)權(quán)值最小的二叉樹，作為一棵新二叉樹的左、右子樹，標(biāo)記新二叉樹的根結(jié)點(diǎn)權(quán)值為其左右子樹的根結(jié)點(diǎn)權(quán)值之和。③從F中刪除被選中的那兩棵二叉樹，同時(shí)把新構(gòu)成的二叉樹加入到森林F中。④重復(fù)②、③操作，直到森林中只含有一棵二叉樹為止，此時(shí)得到的這棵二叉樹就是哈夫曼樹。上述算法的核心思想是：每一步操作都是將兩棵二叉樹合并為一棵，直到所有的結(jié)點(diǎn)都加入到這棵樹中為止。算法中所使用的貪心準(zhǔn)則為：每次均從可用的二叉樹中選出權(quán)值最小的兩棵樹。第16頁，共22頁，2023年，2月20日，星期日哈夫曼編碼的編程第17頁，共22頁，2023年，2月20日，星期日哈夫曼編碼的編程由于哈夫曼樹中沒有度為1的結(jié)點(diǎn)，且具有n個(gè)字符的哈夫曼樹的結(jié)點(diǎn)總數(shù)為2n-1個(gè)，因此可以使用順序存儲(chǔ)結(jié)構(gòu)來實(shí)現(xiàn)哈夫曼算法。將結(jié)點(diǎn)信息存儲(chǔ)在一個(gè)2n-1的一維數(shù)組中。當(dāng)構(gòu)造完哈夫曼樹后，求每一個(gè)字符的編碼的過程就是走一條從葉子結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑。譯碼的過程需要走一條從根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的路徑。因此，哈夫曼樹中的結(jié)點(diǎn)結(jié)構(gòu)中應(yīng)該包含其孩子結(jié)點(diǎn)和父結(jié)點(diǎn)的信息。

第18頁，共22頁，2023年，2月20日，星期日8.2.4背包問題1.問題描述給定n種物品和一個(gè)背包。n物品的重量和價(jià)值分別為w1，w2，…，wn和v1，v2，…，vn；背包可以容納的總重量為c。如何選擇裝入背包的物品，使得裝入背包中的物品的總價(jià)值最大？第19頁，共22頁，2023年，2月20日，星期日2.算法實(shí)現(xiàn)按照貪心法的思想，解決部分背包問題的算法描述是：①計(jì)算每種物品單位重量的價(jià)值；②將盡可能多的單位重量?jī)r(jià)值最高的物品裝入背包；③如果單位重量?jī)r(jià)值最高的物品全部裝入背包后，背包內(nèi)的物品總重量小于c，則選擇單位重量?jī)r(jià)值次高的物品并盡可能多裝入背包。④依次進(jìn)行下去，直到背包裝滿為止。

第20頁，共22頁，2023年，2月20日，星期日8.2.4背包問題物品ABCDF重量12345