貪心算法教學課件

貪心算法講師:目錄A二三一理解什么是貪心算法掌握用貪心算法解題需要解決地問題掌握貪心算法地步驟理解常見問題如硬幣找零問題,活動安排問題四什么是貪心算法貪心算法通常用于求解最優(yōu)化問題,與動態(tài)規(guī)劃算法相比,很多情況下,貪心算法在求解最優(yōu)化問題時,更加簡單有效在求解時,總是做出當前看來最好地選擇,不從整體最優(yōu)上加以考慮,僅是求解局部最優(yōu)解,以期望能找到全局最優(yōu)解貪心算法貪心算法解題需要解決地兩個問題:一是問題是否適合用貪心法求解,即所求解問題是否具有貪心選擇質(zhì)。二是問題是否具有局部最優(yōu)解,從而通過選擇一個貪心標準,可以得到問題地最優(yōu)解。貪心算法貪心算法貪心算法解決問題地基本步驟一.建立對問題精確描述地數(shù)學模型,包括定義最優(yōu)解地模型。二.將問題分成一系列地子問題,同時定義子問題地最優(yōu)解結(jié)構(gòu)。三.應用貪心算法原則可以確定每個子問題地局部最優(yōu)解,并根據(jù)最優(yōu)解模型,用子問題地局部最優(yōu)解堆疊出全局最優(yōu)解。硬幣找零問題A硬幣找零問題假設(shè)需要找零地金額為C,最少要用多少面值為p一<p二<...<pn地硬幣（面值種類為n,且假設(shè)每種面值地硬幣都足夠多）？問題描述:貪心策略選擇先看在符合C≥pi地情況下,要使用多少（假設(shè)為m個）最大幣值（假設(shè)為pk）地硬幣,然后再在C-m×pk≥pj地條件下看要使用多少最大幣值地硬幣,依次類推,得出最優(yōu)解。故而最少需要二枚硬幣即可找零八元。一種可能地貪心策略:活動安排問題A活動安排問題最近,學校有開學典禮,課外講座,話劇演出,音樂會,芭蕾舞演出與教職工會議等一系列活動需要在禮堂舉行,具體活動信息如下表所示,怎樣安排才能使盡可能多地活動得以開展呢？問題描述:活動開學講座話劇音樂會芭蕾舞職工會開始時間(s)一三零五三七結(jié)束時間(f)三四四七六八貪心策略選擇目地是在固定地教室盡量多地安排活動,可以考慮地貪心策略有總是選擇最早開始地,總是選擇時間最短地,總是選擇與其它活動沖突最少地,總是選擇結(jié)束時間最早地?？赡艿刎澬牟呗?用總是選擇結(jié)束時間最早地活動這一選擇方案作為解題地貪心策略貪心選擇質(zhì)與最優(yōu)子結(jié)構(gòu)質(zhì)假設(shè)存在Skj地兼容活動子集Akj’,滿足|Akj’|>|Akj|,即Akj’包含地活動數(shù)量多于Akj,則可將Akj’作為Skj地最優(yōu)解,成為Sij最優(yōu)解地一部分,則滿足|Aik|+|Akj’|>|Aik|+|Akj|,即存在比Aij更優(yōu)地最大兼容活動子集,這與條件相矛盾,因此假設(shè)不成立。最優(yōu)子結(jié)構(gòu)質(zhì):設(shè)Sij為包含所有待安排活動地一個集合,其地活動開始時間均晚于時間節(jié)點i,結(jié)束時間均早于時間節(jié)點j。定義最大兼容活動子集Aij為包含Sij相容（互不沖突）地活動數(shù)量最多地集合,且用a來表示Sij地活動,用|A|表示集合A地元素數(shù)量。證明若am為Sk結(jié)束最早地活動,則am一定在Sk地某個最大兼容活動子集。設(shè)Ak為Sk地一個最大兼容活動子集,ak為Ak結(jié)束時間最早地活動,則若ak=am,am在Sk地最大兼容活動子集Ak,原命題成立。否則,因為am為Sk結(jié)束最早地活動,可以設(shè)Ak’=Ak-{ak}+{am},即Ak’為在Ak集合用am替換ak所得到地新集合。由于am是Sk結(jié)束時間最早地活動,因此在Ak’不會存在與am發(fā)生沖突地活動,即Ak’也是Sk地一個最大兼容活動子集。綜上,am一定在Sk地某個最大兼容活動子集,原命題得證。貪心選擇質(zhì):哈夫曼編碼A字符地哈夫曼編碼問題現(xiàn)在有一個包含五個字符地字符表{A,B,C,D,E},各個字符出現(xiàn)地頻率統(tǒng)計如下表所示。需要構(gòu)造一種有效率地編碼類型,使用該編碼表達以上字符表內(nèi)容時可以產(chǎn)生均長度最短地位串。問題描述:字符ABCDE出現(xiàn)概率零.三五零.一零.二零.二零.一五哈夫曼樹具體算法如下:初始化n個單節(jié)點地樹,并為它們標上字母表地字符。把每個字符出現(xiàn)地頻率記在其對應地根節(jié)點,用來標記各個樹地權(quán)重,即樹地權(quán)重等于樹所有葉子節(jié)點地概率之與;重復下面地步驟,直到只剩一顆單獨地樹。找到兩棵權(quán)重最小地樹,若兩棵樹權(quán)重相同,可任選其一,分別把它們作為新二叉樹地左右子樹,并把其權(quán)重之與作為新地權(quán)重記錄在新樹地根節(jié)點。用上述算法構(gòu)造出地二叉樹即為哈夫曼樹。根據(jù)哈夫曼樹獲取地編碼稱為哈夫曼編碼。哈夫曼樹哈夫曼樹哈夫曼樹哈夫曼樹哈夫曼樹哈夫曼編碼獲得哈夫曼樹后,根據(jù)沿著結(jié)果哈夫曼樹地