簡單的貪心算法ppt

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

2、 假設(shè)一個小孩買了3333美分的糖果（需要找給小孩6767美分）。引例引例找零錢找零錢2022-1-224?算法思想算法思想 在現(xiàn)實生活中，我們經(jīng)常為下意在現(xiàn)實生活中，我們經(jīng)常為下意識的做貪心的選擇，例如在購買商品識的做貪心的選擇，例如在購買商品時候總是尋求物美價廉的物品，在質(zhì)時候總是尋求物美價廉的物品，在質(zhì)量相同情況下，價格低的首選。量相同情況下，價格低的首選。貪心貪心抱歉我找不到更好的詞去形抱歉我找不到更好的詞去形容容是個好東西。貪心是對的，貪是個好東西。貪心是對的，貪心是奏效的。心是奏效的。 電影電影華爾街華爾街2022-1-225?算法思想算法思想 將問題的求解過程看作是一系列選擇，每

3、次選擇一個輸入，每次選擇都是當前狀態(tài)下的最好選擇(局部最優(yōu)解)。每作一次選擇后，所求問題會簡化為一個規(guī)模更小的子問題。從而通過每一步的最優(yōu)解逐步達到整體的最優(yōu)解。2022-1-226?算法過程算法過程 顧名思義，貪心算法總是作出在當前看來最好的選擇。也就是說貪心算法并不從整體最優(yōu)考慮，它所作出的選擇只是在某種意義上的局部最優(yōu)選擇。找的硬幣總數(shù)最少找的硬幣總數(shù)最少使剩余金額最少使剩余金額最少找硬幣的時候：找硬幣的時候：【標準轉(zhuǎn)化】貪心猜想（貪心策略）貪心猜想（貪心策略）原現(xiàn)2022-1-227?算法過程算法過程 貪心算法步驟 從問題的某一初始解出發(fā)；從問題的某一初始解出發(fā)；whilewhile

4、能朝給定總目標前進一步能朝給定總目標前進一步dodo 求出可行解的一個解元素；求出可行解的一個解元素；由所有解元素組合成問題的一個由所有解元素組合成問題的一個可行解；可行解；真正意義要求解原問題真正意義要求解原問題將原問題變成更小將原問題變成更小子問題的步驟子問題的步驟理解理解2022-1-228?算法過程算法過程【貪心算法一般步驟】1 1、設(shè)計數(shù)據(jù)找規(guī)律、設(shè)計數(shù)據(jù)找規(guī)律2 2、進行貪心猜想、進行貪心猜想3 3、正確性證明（嚴格證明和一般證明）、正確性證明（嚴格證明和一般證明） 嚴格證明：數(shù)學歸納和反證法嚴格證明：數(shù)學歸納和反證法 一般證明：列舉反例一般證明：列舉反例4 4、程序?qū)崿F(xiàn)、程序?qū)崿F(xiàn)

5、2022-1-229?算法分析算法分析【適用問題】 具備貪心選擇貪心選擇和最優(yōu)子結(jié)構(gòu)最優(yōu)子結(jié)構(gòu)性質(zhì)的最優(yōu)化問題【常見應(yīng)用】會議安排問題,哈夫曼編碼問題, 等等【算法優(yōu)點】求解速度快,時間復雜性有較低的階.【算法缺點】需證明是最優(yōu)解.整體的最優(yōu)解可通過一系列整體的最優(yōu)解可通過一系列局部最優(yōu)解達到局部最優(yōu)解達到. 每次的選擇每次的選擇可以依賴以前作出的選擇可以依賴以前作出的選擇, 但但不能依賴于后面的選擇不能依賴于后面的選擇問題的整體最優(yōu)解問題的整體最優(yōu)解中包含著它子問題中包含著它子問題的最優(yōu)解的最優(yōu)解2022-1-2210?常見應(yīng)用常見應(yīng)用1、會議安排問題、會議安排問題【問題陳述】設(shè)有【問題陳述

6、】設(shè)有n個會議個會議E=1,2,n要使用同一資源要使用同一資源,同一時間內(nèi)同一時間內(nèi)只允許一個會議使用該資源只允許一個會議使用該資源. 設(shè)會議設(shè)會議i的起止時間區(qū)間的起止時間區(qū)間si, fi) ,如果選如果選擇了會議擇了會議i,則它在時間區(qū)間則它在時間區(qū)間si, fi)內(nèi)占用該資源內(nèi)占用該資源;若若si, fi)與與sj, fj)不不相交相交 , 則稱會議則稱會議 i 與與 j 是是 相容相容 的的 . 求解目標是在所給的會議集合中求解目標是在所給的會議集合中選出最大相容會議子集選出最大相容會議子集.【算法思路】將【算法思路】將n個會議按結(jié)束時間非減序排列個會議按結(jié)束時間非減序排列,依次考慮會

7、議依次考慮會議i, 若若i與已選擇的會議相容與已選擇的會議相容,則添加此會議到相容會議子集則添加此會議到相容會議子集.【例】設(shè)待安排的【例】設(shè)待安排的11個會議起止時間按結(jié)束時間的非減序排列個會議起止時間按結(jié)束時間的非減序排列事件編號12 3 4567891011發(fā)生時刻13 0 535688212結(jié)束時刻45 6 78910111213142022-1-2211?常見應(yīng)用常見應(yīng)用會議安排問題貪心算法：會議安排問題貪心算法：void GreedySelector(int n, Type s, Type f, bool A) A1=true; int j=1; for (int i=2;i=fj

8、) Ai=true; j=i; else Ai=false; 2022-1-22122022-1-2212?常見應(yīng)用常見應(yīng)用2、哈夫曼編碼、哈夫曼編碼【問題陳述】【問題陳述】哈夫曼編碼是廣泛地用于數(shù)據(jù)文件壓縮的十分有效的哈夫曼編碼是廣泛地用于數(shù)據(jù)文件壓縮的十分有效的編碼方法。其壓縮率通常在編碼方法。其壓縮率通常在20%90%之間。哈夫曼編碼算法用字之間。哈夫曼編碼算法用字符在文件中出現(xiàn)的頻率表來建立一個用符在文件中出現(xiàn)的頻率表來建立一個用0，1串表示各字符的最優(yōu)表串表示各字符的最優(yōu)表示方式。示方式?！舅惴ㄋ悸贰俊舅惴ㄋ悸贰浚?）以）以n個字母為結(jié)點構(gòu)成個字母為結(jié)點構(gòu)成n棵僅含一個點的二叉樹集合

9、，字母的棵僅含一個點的二叉樹集合，字母的頻率即為結(jié)點的權(quán)。頻率即為結(jié)點的權(quán)。（2）每次從二叉樹集合中找出兩個權(quán)最小者合并為一棵二叉樹：）每次從二叉樹集合中找出兩個權(quán)最小者合并為一棵二叉樹：增加一個根結(jié)點將這兩棵樹作為左右子樹。新樹的權(quán)為兩棵子樹的增加一個根結(jié)點將這兩棵樹作為左右子樹。新樹的權(quán)為兩棵子樹的權(quán)之和。權(quán)之和。（3）反復進行步驟）反復進行步驟（2）直到只剩一棵樹為止。直到只剩一棵樹為止。a: 0000 b :11c: 1000 d: 1001e: 101 f :01g: 0001 h:001有八種字符：有八種字符：a b c d e f g h ，其在通信聯(lián)絡(luò)中出現(xiàn)的概率分別為：，其在

10、通信聯(lián)絡(luò)中出現(xiàn)的概率分別為：0.05 0.29 0.07 0.08 0.14 0.23 0.03 0.11 ,試設(shè)計哈夫曼編碼。試設(shè)計哈夫曼編碼。 設(shè)權(quán)設(shè)權(quán) w = ( 5 , 29 , 7 ,8 , 14 , 23 ,3 , 11) n = 8 構(gòu)造過程：構(gòu)造過程：529781423311538297814231178152923111411191429234229581000000000111111129232914232022-1-2214談?wù)勛约旱恼務(wù)勛约旱南敕ㄏ敕?022-1-2215 選擇需慎重 貪心算法在對問題求解時，總是作出在當前看來是最好的選擇。也就是說，不從整體上加以考慮，

11、它所作出的僅僅是在某種意義上的局部最優(yōu)解。eg：數(shù)字三角形問題：有一個數(shù)字三角形（如右圖）?，F(xiàn)有一只螞蟻從頂層開始向下走，每走下一級時，可向左下方向或右下方向走。求走到底層后它所經(jīng) 過的數(shù)的最大值。 解：如果用貪心法，每次向最大的方向 走，得到結(jié)果為1+6+8+2+3=20。可是明明還有另一條路，1+3+6+6+7=23。問題出在哪？每次的選擇對后面的步驟會有影響！第三級選了8，就選不到第四、五級較大的數(shù)了。 1 6 3 8 2 6 2 1 6 53 2 4 7 62022-1-2216綜述 貪心算法是一種分級處理方法，它得到某種度量意義下一個問題的最優(yōu)解，所做的每一次選擇都是當前狀態(tài)下的貪心選擇，通過一系列的選擇來得到最終解。這種策略是一種很簡潔的方法，適用于許多問題