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

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

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

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

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

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

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

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

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

中最深葉子且為兄弟（樹(shù)T

與T具有相等的平均碼長(zhǎng)）。xybcTbcxyT

T中：

f(b)f(c)

f(x)f(y)

x和y是具有最小頻率的兩個(gè)字符

f(x)f(b)

f(y)f(c)T

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