人工智能算法（Python語言版）PPT第4章-貪心法

提綱應(yīng)用背景和動機貪心算法的基本思想哈夫曼編碼總結(jié)應(yīng)用背景和動機(1)背景：主播帶貨已成為了一種新的產(chǎn)品推銷手段。為響應(yīng)國家脫貧攻堅和鄉(xiāng)村振興戰(zhàn)略，邊遠山區(qū)的地方政府也采取主播帶貨的方式推廣農(nóng)產(chǎn)品。例如：假設(shè)一批農(nóng)產(chǎn)品要被想被大眾熟知，則其影響因子需要達到1.3，現(xiàn)有3類主播，其中A類主播可幫助農(nóng)產(chǎn)品提高0.4的影響因子，B類主播可幫助農(nóng)產(chǎn)品提高0.3的影響因子，C類主播可幫助農(nóng)產(chǎn)品提高0.1的影響因子。問題：應(yīng)該如何安排主播帶貨，能夠在最少的主播數(shù)量下幫助政府使得該農(nóng)產(chǎn)品被大眾熟知？直觀的方案：盡量選擇影響因子高的主播，即選擇3名A類主播和1名C類主播，就可在最少的主播數(shù)量下讓這批農(nóng)產(chǎn)品的影響因子達到期望值。應(yīng)用背景和動機(2)優(yōu)化問題（Optimizationproblem）

不僅要找到答案，且要找到最佳答案貪心算法（Greedyalgorithm）

有時對優(yōu)化問題能有較好的解決方案貪心算法分階段執(zhí)行，每一個階段：當考慮做何種選擇時，只考慮對當前問題最佳的選擇，而不考慮其子問題的結(jié)果希望通過每一個步驟的局部最優(yōu)（Localoptimum）而得到全局最優(yōu)（Globaloptimum）未必能得到最優(yōu)解應(yīng)用背景和動機(3)運行9個作業(yè)，其時間分別為3,5,6,10,11,14,15,18,20

共有3個處理器，可執(zhí)行這些作業(yè)按照最長時間作業(yè)優(yōu)先的原則，將作業(yè)安排到空閑處理器201815141110653P1P2P3完成作業(yè)所需時間為18+11+6=35這一方案并不差，但是可能有更好的方案引例：多機調(diào)度應(yīng)用背景和動機(4)若按照最短時間作業(yè)優(yōu)先的原則，結(jié)果如何？201815141110653P1P2P3以上方案并不是一個好的方案，完成作業(yè)所需時間為6+14+20=40注意到：貪心算法本身能高效地執(zhí)行每個階段所需：選擇當前最小或最大者應(yīng)用背景和動機(5)顯然，該方案是最優(yōu)的，仍可能有其他最優(yōu)方案如何得到以上最優(yōu)方案？-嘗試所有作業(yè)安排給處理器的可能方案，選擇最短完成時間-需指數(shù)計算時間

更好的方案：201815141110653P1P2P3結(jié)論：貪心算法具有較高效率，其答案從實際應(yīng)用的角度看已足夠好提綱應(yīng)用背景和動機貪心算法的基本思想哈夫曼編碼總結(jié)貪心算法的基本思想1、貪心選擇性質(zhì)所求問題的整體最優(yōu)解，希望通過一系列局部最優(yōu)的選擇

（貪心選擇）——貪心算法可行的第一個基本要素通常以自頂向下的方式進行，以迭代的方式作出相繼的貪心選擇，每作一次貪心選擇就將所求問題簡化為規(guī)模更小的子問題每一步對目前構(gòu)造的部分解做一個擴展，滿足：可行（滿足約束）、局部最優(yōu)、不可取消（貪心算法與動態(tài)規(guī)劃算法的主要區(qū)別）

2、最優(yōu)子結(jié)構(gòu)性質(zhì)問題的最優(yōu)解包含其子問題的最優(yōu)解證明貪心算法的正確性（針對最優(yōu)化問題的求解）：-證明每一步所作的貪心選擇最終導致問題的整體最優(yōu)解-數(shù)學歸納法提綱應(yīng)用背景和動機貪心算法的基本思想哈夫曼編碼總結(jié)哈夫曼編碼(1)背景-哈夫曼編碼廣泛地用于數(shù)據(jù)文件壓縮-壓縮率通常在20%～90%之間（變長碼）-哈夫曼編碼算法用字符在文件中出現(xiàn)的頻率表來建立一個用0，1串表示各字符的最優(yōu)表示方式-給出現(xiàn)頻率高的字符較短的編碼，出現(xiàn)頻率較低的字符以較長的編碼，可以大大縮短總碼長前綴碼-盡可能多地壓縮文件、源文件很容易被重建-任一字符的代碼(0,1序列)都不是其他字符代碼的前綴——完全二叉樹T-滿足前綴約束，則編碼無二義性-平均碼長：字符c出現(xiàn)的頻率為f(c),在T中的深度為dT(c)哈夫曼編碼(2)哈夫曼編碼（Huffmanencoding）算法為貪心法選擇并合并最小出現(xiàn)頻度的兩個數(shù)字平均編碼長度0.22*2+0.12*3+0.24*2+0.06*4+0.27*2+0.09*4

=2.42哈夫曼編碼能得到最優(yōu)編碼

2212246279

ABCDEF152746100A=00

B=100

C=01

D=1010

E=11

F=101154編碼結(jié)果哈夫曼編碼(3)

哈夫曼編碼(4)哈夫曼編碼算法正確性證明的思路對最優(yōu)前綴碼二叉樹T作修改得T，T

表示對C做出貪心選擇得到的最優(yōu)前綴碼，x和y是T

中最深葉子且為兄弟（樹T

與T具有相等的平均碼長）。xybcTbcxyT

T中：

f(b)f(c)

f(x)f(y)

x和y是具有最小頻率的兩個字符

f(x)f(b)

f(y)f(c)T

是對C做出貪心選擇的前綴編碼樹提綱應(yīng)用背景和動機