簡(jiǎn)單的貪心算法ppt

2023/2/21貪心算法簡(jiǎn)談與應(yīng)用舉例組員：學(xué)院：通信與信息工程2023/2/22

※簡(jiǎn)談：

算法思想

算法過(guò)程

算法分析

※應(yīng)用舉例：

常見(jiàn)應(yīng)用2023/2/23?算法思想找錢的方法：25+25+10+5+1+1我們有種直覺(jué)的傾向：在找零錢時(shí)，直覺(jué)告訴我們使用面值大的硬幣，剩余的金額就越少，這樣找的硬幣數(shù)目最少。

假設(shè)提供了數(shù)目不限的面值為25美分、10美分、5美分、及1美分的硬幣。假設(shè)一個(gè)小孩買了33美分的糖果（需要找給小孩67美分）。引例——找零錢2023/2/24?算法思想

在現(xiàn)實(shí)生活中，我們經(jīng)常為下意識(shí)的做貪心的選擇，例如在購(gòu)買商品時(shí)候總是尋求物美價(jià)廉的物品，在質(zhì)量相同情況下，價(jià)格低的首選。貪心——抱歉我找不到更好的詞去形容——是個(gè)好東西。貪心是對(duì)的，貪心是奏效的?！娪啊度A爾街》2023/2/25?算法思想將問(wèn)題的求解過(guò)程看作是一系列選擇，每次選擇一個(gè)輸入，每次選擇都是當(dāng)前狀態(tài)下的最好選擇(局部最優(yōu)解)。每作一次選擇后，所求問(wèn)題會(huì)簡(jiǎn)化為一個(gè)規(guī)模更小的子問(wèn)題。從而通過(guò)每一步的最優(yōu)解逐步達(dá)到整體的最優(yōu)解。2023/2/26?算法過(guò)程顧名思義，貪心算法總是作出在當(dāng)前看來(lái)最好的選擇。也就是說(shuō)貪心算法并不從整體最優(yōu)考慮，它所作出的選擇只是在某種意義上的局部最優(yōu)選擇。找的硬幣總數(shù)最少→使剩余金額最少找硬幣的時(shí)候：【標(biāo)準(zhǔn)轉(zhuǎn)化】貪心猜想（貪心策略）原現(xiàn)2023/2/27?算法過(guò)程[貪心算法步驟]從問(wèn)題的某一初始解出發(fā)；

while

能朝給定總目標(biāo)前進(jìn)一步

do

求出可行解的一個(gè)解元素；

由所有解元素組合成問(wèn)題的一個(gè)可行解；真正意義要求解原問(wèn)題將原問(wèn)題變成更小子問(wèn)題的步驟理解2023/2/28?算法過(guò)程

【貪心算法一般步驟】1、設(shè)計(jì)數(shù)據(jù)找規(guī)律2、進(jìn)行貪心猜想3、正確性證明（嚴(yán)格證明和一般證明）·嚴(yán)格證明：數(shù)學(xué)歸納和反證法·一般證明：列舉反例4、程序?qū)崿F(xiàn)2023/2/29?算法分析【適用問(wèn)題】具備貪心選擇和最優(yōu)子結(jié)構(gòu)性質(zhì)的最優(yōu)化問(wèn)題【常見(jiàn)應(yīng)用】會(huì)議安排問(wèn)題,哈夫曼編碼問(wèn)題,等等【算法優(yōu)點(diǎn)】求解速度快,時(shí)間復(fù)雜性有較低的階.【算法缺點(diǎn)】需證明是最優(yōu)解.整體的最優(yōu)解可通過(guò)一系列局部最優(yōu)解達(dá)到.每次的選擇可以依賴以前作出的選擇,但不能依賴于后面的選擇問(wèn)題的整體最優(yōu)解中包含著它子問(wèn)題的最優(yōu)解2023/2/210?常見(jiàn)應(yīng)用1、會(huì)議安排問(wèn)題【問(wèn)題陳述】設(shè)有n個(gè)會(huì)議E={1,2,…,n}要使用同一資源,同一時(shí)間內(nèi)只允許一個(gè)會(huì)議使用該資源.設(shè)會(huì)議i的起止時(shí)間區(qū)間[si,fi),如果選擇了會(huì)議i,則它在時(shí)間區(qū)間[si,fi)內(nèi)占用該資源;若[si,fi)與[sj,fj)不相交,則稱會(huì)議i與j是相容的.求解目標(biāo)是在所給的會(huì)議集合中選出最大相容會(huì)議子集.【算法思路】將n個(gè)會(huì)議按結(jié)束時(shí)間非減序排列,依次考慮會(huì)議i,若i與已選擇的會(huì)議相容,則添加此會(huì)議到相容會(huì)議子集.【例】設(shè)待安排的11個(gè)會(huì)議起止時(shí)間按結(jié)束時(shí)間的非減序排列事件編號(hào)1234567891011發(fā)生時(shí)刻130535688212結(jié)束時(shí)刻45678910111213142023/2/211?常見(jiàn)應(yīng)用

會(huì)議安排問(wèn)題貪心算法：voidGreedySelector(intn,Types[],Typef[],boolA[]){A[1]=true;intj=1;for(inti=2;i<=n;i++){if(s[i]>=f[j]){A[i]=true;j=i;}elseA[i]=false;}}2023/2/2122023/2/212?常見(jiàn)應(yīng)用2、哈夫曼編碼【問(wèn)題陳述】哈夫曼編碼是廣泛地用于數(shù)據(jù)文件壓縮的十分有效的編碼方法。其壓縮率通常在20%～90%之間。哈夫曼編碼算法用字符在文件中出現(xiàn)的頻率表來(lái)建立一個(gè)用0，1串表示各字符的最優(yōu)表示方式?！舅惴ㄋ悸贰浚?）以n個(gè)字母為結(jié)點(diǎn)構(gòu)成n棵僅含一個(gè)點(diǎn)的二叉樹(shù)集合，字母的頻率即為結(jié)點(diǎn)的權(quán)。（2）每次從二叉樹(shù)集合中找出兩個(gè)權(quán)最小者合并為一棵二叉樹(shù)：增加一個(gè)根結(jié)點(diǎn)將這兩棵樹(shù)作為左右子樹(shù)。新樹(shù)的權(quán)為兩棵子樹(shù)的權(quán)之和。（3）反復(fù)進(jìn)行步驟（2）直到只剩一棵樹(shù)為止。a:0000b:11c:1000d:1001e:101f:01g:0001h:001有八種字符：abcdefgh，其在通信聯(lián)絡(luò)中出現(xiàn)的概率分別為：0.050.290.070.080.140.230.030.11,試設(shè)計(jì)哈夫曼編碼。設(shè)權(quán)w=(5,29,7,8,14,23,3,11)n=8

構(gòu)造過(guò)程：529781423311538297814231178152923111411191429234229581000000000111111129232914232023/2/214談?wù)勛约旱南敕ā?023/2/215選擇需慎重

貪心算法在對(duì)問(wèn)題求解時(shí)，總是作出在當(dāng)前看來(lái)是最好的選擇。也就是說(shuō)，不從整體上加以考慮，它所作出的僅僅是在某種意義上的局部最優(yōu)解。eg：數(shù)字三角形問(wèn)題：有一個(gè)數(shù)字三角形（如右圖）。現(xiàn)有一只螞蟻從頂層開(kāi)始向下走，每走下一級(jí)時(shí)，可向左下方向或右下方向走。求走到底層后它所經(jīng)過(guò)的數(shù)的最大值。解：如果用貪心法，每次向最大的方向走，得到結(jié)果為1+6+8+2+3=20。可是明明還有另一條路，1+3+6+6+7=23。問(wèn)題出在哪？每次的選擇對(duì)后面的步驟會(huì)有影響！第三級(jí)選了8，就選不到第四、五級(jí)較大的數(shù)了。

1638262165324762023/2/216綜述

貪心算法是一種分級(jí)處理方法，它得到某種度量意義下一個(gè)問(wèn)題的最優(yōu)解，所做的每一次選擇都是當(dāng)前狀態(tài)下的貪心選擇，通過(guò)一系列的選擇來(lái)得到最終解。這種策略是一種很簡(jiǎn)潔的方法，適用于許多問(wèn)題，但并不能依賴于它，因?yàn)樗€有一下不足：（1）不能保證求得的最后解是最佳的，由于貪心策略總是從局部看來(lái)是最優(yōu)的選擇，因此從整體上考慮