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

1、2021-7-181 貪心算法簡(jiǎn)談與應(yīng)用舉例貪心算法簡(jiǎn)談與應(yīng)用舉例 組員：組員： 學(xué)院：通信與信息工程學(xué)院：通信與信息工程 2021-7-182 簡(jiǎn)談：簡(jiǎn)談： 算法思想算法思想 算法過(guò)程算法過(guò)程 算法分析算法分析 應(yīng)用舉例：應(yīng)用舉例： 常見(jiàn)應(yīng)用常見(jiàn)應(yīng)用 2021-7-183 ?算法思想算法思想 找錢(qián)的方法找錢(qián)的方法： 25+25+10+5+1+1 我們有種直覺(jué)的傾向我們有種直覺(jué)的傾向： 在找零錢(qián)時(shí)，直覺(jué) 告訴我們使用面值大的硬 幣，剩余的金額就越少， 這樣找的硬幣數(shù)目最少。 假設(shè)提供了數(shù)假設(shè)提供了數(shù) 目不限的面值為目不限的面值為2 2 5 5美分、美分、1 01 0美分、美分、 5 5美分、及

2、美分、及1 1美分美分 的硬幣。的硬幣。 假設(shè)一個(gè)小 孩買(mǎi)了3333美分的 糖果（需要找給 小孩6767美分）。 引例引例找零錢(qián)找零錢(qián) 2021-7-184 ?算法思想算法思想 在現(xiàn)實(shí)生活中，我們經(jīng)常為下意在現(xiàn)實(shí)生活中，我們經(jīng)常為下意 識(shí)的做貪心的選擇，例如在購(gòu)買(mǎi)商品識(shí)的做貪心的選擇，例如在購(gòu)買(mǎi)商品 時(shí)候總是尋求物美價(jià)廉的物品，在質(zhì)時(shí)候總是尋求物美價(jià)廉的物品，在質(zhì) 量相同情況下，價(jià)格低的首選。量相同情況下，價(jià)格低的首選。 貪心貪心抱歉我找不到更好的詞去形抱歉我找不到更好的詞去形 容容是個(gè)好東西。貪心是對(duì)的，貪是個(gè)好東西。貪心是對(duì)的，貪 心是奏效的。心是奏效的。 電影電影華爾街華爾街 2021-

3、7-185 ?算法思想算法思想 將問(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)解。 2021-7-186 ?算法過(guò)程算法過(guò)程 顧名思義，貪心算法總是作出在當(dāng)前看來(lái)最 好的選擇。也就是說(shuō)貪心算法并不從整體最優(yōu)考 慮，它所作出的選擇只是在某種意義上的局部最 優(yōu)選擇。 找的硬幣總數(shù)最少找的硬幣總數(shù)最少使剩余金額最少使剩余金額最少 找硬幣的時(shí)候：找硬幣的時(shí)候： 【標(biāo)準(zhǔn)轉(zhuǎn)化】 貪心猜想（貪心策略）貪心猜想（貪心策略） 原 現(xiàn) 2021-7-187 ?

4、算法過(guò)程算法過(guò)程 貪心算法步驟 從問(wèn)題的某一初始解出發(fā)；從問(wèn)題的某一初始解出發(fā)； whilewhile 能朝給定總目標(biāo)前進(jìn)一步能朝給定總目標(biāo)前進(jìn)一步 dodo 求出可行解的一個(gè)解元素；求出可行解的一個(gè)解元素； 由所有解元素組合成問(wèn)題的一個(gè)由所有解元素組合成問(wèn)題的一個(gè) 可行解；可行解； 真正意義要求解原問(wèn)題真正意義要求解原問(wèn)題 將原問(wèn)題變成更小將原問(wèn)題變成更小 子問(wèn)題的步驟子問(wèn)題的步驟 理解理解 2021-7-188 ?算法過(guò)程算法過(guò)程 【貪心算法一般步驟】 1 1、設(shè)計(jì)數(shù)據(jù)找規(guī)律、設(shè)計(jì)數(shù)據(jù)找規(guī)律 2 2、進(jìn)行貪心猜想、進(jìn)行貪心猜想 3 3、正確性證明（嚴(yán)格證明和一般證明）、正確性證明（嚴(yán)格證明

5、和一般證明） 嚴(yán)格證明：數(shù)學(xué)歸納和反證法嚴(yán)格證明：數(shù)學(xué)歸納和反證法 一般證明：列舉反例一般證明：列舉反例 4 4、程序?qū)崿F(xiàn)、程序?qū)崿F(xiàn) 2021-7-189 ?算法分析算法分析 【適用問(wèn)題】 具備貪心選擇貪心選擇和最優(yōu)子結(jié)構(gòu)最優(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)解可通過(guò)一系列 局部最優(yōu)解達(dá)到局部最優(yōu)解達(dá)到. 每次的選擇每次的選擇 可以依賴(lài)以前作出的選擇可以依賴(lài)以前作出的選擇, 但但 不能依賴(lài)于后面的選擇不能依賴(lài)于后面的選擇 問(wèn)題的整體最優(yōu)解問(wèn)題

6、的整體最優(yōu)解 中包含著它子問(wèn)題中包含著它子問(wèn)題 的最優(yōu)解的最優(yōu)解 2021-7-1810 ?常見(jiàn)應(yīng)用常見(jiàn)應(yīng)用 1、會(huì)議安排問(wèn)題、會(huì)議安排問(wèn)題 【問(wèn)題陳述】設(shè)有【問(wèn)題陳述】設(shè)有n個(gè)會(huì)議個(gè)會(huì)議E=1,2,n要使用同一資源要使用同一資源,同一時(shí)間內(nèi)同一時(shí)間內(nèi) 只允許一個(gè)會(huì)議使用該資源只允許一個(gè)會(huì)議使用該資源. 設(shè)會(huì)議設(shè)會(huì)議i的起止時(shí)間區(qū)間的起止時(shí)間區(qū)間si, fi) ,如果選如果選 擇了會(huì)議擇了會(huì)議i,則它在時(shí)間區(qū)間則它在時(shí)間區(qū)間si, fi)內(nèi)占用該資源內(nèi)占用該資源;若若si, fi)與與sj, fj)不不 相交相交 , 則稱(chēng)會(huì)議則稱(chēng)會(huì)議 i 與與 j 是是 相容相容 的的 . 求解目標(biāo)是在所給的

7、會(huì)議集合中求解目標(biāo)是在所給的會(huì)議集合中 選出最大相容會(huì)議子集選出最大相容會(huì)議子集. 【算法思路】將【算法思路】將n個(gè)會(huì)議按結(jié)束時(shí)間非減序排列個(gè)會(huì)議按結(jié)束時(shí)間非減序排列,依次考慮會(huì)議依次考慮會(huì)議i, 若若i 與已選擇的會(huì)議相容與已選擇的會(huì)議相容,則添加此會(huì)議到相容會(huì)議子集則添加此會(huì)議到相容會(huì)議子集. 【例】設(shè)待安排的【例】設(shè)待安排的11個(gè)會(huì)議起止時(shí)間按結(jié)束時(shí)間的非減序排列個(gè)會(huì)議起止時(shí)間按結(jié)束時(shí)間的非減序排列 事件編號(hào)12 3 4567891011 發(fā)生時(shí)刻13 0 535688212 結(jié)束時(shí)刻45 6 7891011121314 2021-7-1811 ?常見(jiàn)應(yīng)用常見(jiàn)應(yīng)用 會(huì)議安排問(wèn)題貪心算法：

8、會(huì)議安排問(wèn)題貪心算法： void GreedySelector(int n, Type s, Type f, bool A) A1=true; int j=1; for (int i=2;i=fj) Ai=true; j=i; else Ai=false; 2021-7-18122021-7-1812 ?常見(jiàn)應(yīng)用常見(jiàn)應(yīng)用 2、哈夫曼編碼、哈夫曼編碼 【問(wèn)題陳述】【問(wèn)題陳述】哈夫曼編碼是廣泛地用于數(shù)據(jù)文件壓縮的十分有效的哈夫曼編碼是廣泛地用于數(shù)據(jù)文件壓縮的十分有效的 編碼方法。其壓縮率通常在編碼方法。其壓縮率通常在20%90%之間。哈夫曼編碼算法用字之間。哈夫曼編碼算法用字 符在文件中出現(xiàn)的頻率

9、表來(lái)建立一個(gè)用符在文件中出現(xiàn)的頻率表來(lái)建立一個(gè)用0，1串表示各字符的最優(yōu)表串表示各字符的最優(yōu)表 示方式。示方式。 【算法思路】【算法思路】 （1）以）以n個(gè)字母為結(jié)點(diǎn)構(gòu)成個(gè)字母為結(jié)點(diǎn)構(gòu)成n棵僅含一個(gè)點(diǎn)的二叉樹(shù)集合，字母的棵僅含一個(gè)點(diǎn)的二叉樹(shù)集合，字母的 頻率即為結(jié)點(diǎn)的權(quán)。頻率即為結(jié)點(diǎn)的權(quán)。 （2）每次從二叉樹(shù)集合中找出兩個(gè)權(quán)最小者合并為一棵二叉樹(shù)：）每次從二叉樹(shù)集合中找出兩個(gè)權(quán)最小者合并為一棵二叉樹(shù)： 增加一個(gè)根結(jié)點(diǎn)將這兩棵樹(shù)作為左右子樹(shù)。新樹(shù)的權(quán)為兩棵子樹(shù)的增加一個(gè)根結(jié)點(diǎn)將這兩棵樹(shù)作為左右子樹(shù)。新樹(shù)的權(quán)為兩棵子樹(shù)的 權(quán)之和。權(quán)之和。 （3）反復(fù)進(jìn)行步驟）反復(fù)進(jìn)行步驟（2）直到只剩一棵樹(shù)為止。

10、直到只剩一棵樹(shù)為止。 a: 0000 b :11 c: 1000 d: 1001 e: 101 f :01 g: 0001 h:001 有八種字符：有八種字符：a b c d e f g h ，其在通信聯(lián)絡(luò)中出現(xiàn)的概率分別為：，其在通信聯(lián)絡(luò)中出現(xiàn)的概率分別為： 0.05 0.29 0.07 0.08 0.14 0.23 0.03 0.11 ,試設(shè)計(jì)哈夫曼編碼。試設(shè)計(jì)哈夫曼編碼。 設(shè)權(quán)設(shè)權(quán) w = ( 5 , 29 , 7 ,8 , 14 , 23 ,3 , 11) n = 8 構(gòu)造過(guò)程：構(gòu)造過(guò)程： 529781423311 53 8 2978 142311 7 8 15 292311 14 1

11、1 19 14 29 23 42 29 58 100 0 0 0 0 0 0 01 1 1 1 1 1 1 2923 29 14 23 2021-7-1814 談?wù)勛约旱恼務(wù)勛约旱?想法想法 2021-7-1815 選擇需慎重 貪心算法在對(duì)問(wèn)題求解時(shí)，總是作出在當(dāng)前看 來(lái)是最好的選擇。也就是說(shuō)，不從整體上加以考慮， 它所作出的僅僅是在某種意義上的局部最優(yōu)解。 eg：數(shù)字三角形問(wèn)題：有一個(gè)數(shù)字三角形 （如右圖）?，F(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ù)了。 1 6 3 8 2 6 2 1 6 5 3 2 4 7 6 2021-7-1816 綜述 貪心算法是一種分級(jí)處理方法，它得到某種度量意義下 一個(gè)問(wèn)題的最優(yōu)解，所做的每一次選擇都是當(dāng)前狀態(tài)下的貪 心選擇，通過(guò)一系列的選擇來(lái)得到最終解。這種策略是一種 很簡(jiǎn)潔的方法，適用于許多問(wèn)題，但并