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

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

第8頁，課件共22頁，創(chuàng)作于2023年2月貪心法的設(shè)計模式

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

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

第20頁，課件共22頁，創(chuàng)作于2023年2月8.2.4背包問題物品ABCDF重量1234