貪心算法,AI算法中不常見的算法
貪心算法(又稱貪婪算法)是指,在對問題求解時,總是做出在當(dāng)前看來是最好的選擇。也就是說,不從整體最優(yōu)上加以考慮,算法得到的是在某種意義上的局部最優(yōu)解。
貪心算法不是對所有問題都能得到整體最優(yōu)解,關(guān)鍵是貪心策略的選擇。
算法思路
貪心算法一般按如下步驟進(jìn)行:
①建立數(shù)學(xué)模型來描述問題 。
②把求解的問題分成若干個子問題。
③對每個子問題求解,得到子問題的局部最優(yōu)解 。
④把子問題的解局部最優(yōu)解合成原來解問題的一個解 。
貪心算法是一種對某些求最優(yōu)解問題的更簡單、更迅速的設(shè)計(jì)技術(shù)。貪心算法的特點(diǎn)是一步一步地進(jìn)行,常以當(dāng)前情況為基礎(chǔ)根據(jù)某個優(yōu)化測度作最優(yōu)選擇,而不考慮各種可能的整體情況,省去了為找最優(yōu)解要窮盡所有可能而必須耗費(fèi)的大量時間。貪心算法采用自頂向下,以迭代的方法做出相繼的貪心選擇,每做一次貪心選擇,就將所求問題簡化為一個規(guī)模更小的子問題,通過每一步貪心選擇,可得到問題的一個最優(yōu)解。雖然每一步上都要保證能獲得局部最優(yōu)解,但由此產(chǎn)生的全局解有時不一定是最優(yōu)的,所以貪心算法不要回溯。
算法特性
貪心算法可解決的問題通常大部分都有如下的特性:
1、有一個以最優(yōu)方式來解決的問題。為了構(gòu)造問題的解決方案,有一個候選的對象的集合:比如不同面值的硬幣 。
2、隨著算法的進(jìn)行,將積累起其他兩個集合:一個包含已經(jīng)被考慮過并被選出的候選對象,另一個包含已經(jīng)被考慮過但被丟棄的候選對象 。
3、有一個函數(shù)來檢查一個候選對象的集合是否提供了問題的解答。該函數(shù)不考慮此時的解決方法是否最優(yōu) 。
4、還有一個函數(shù)檢查是否一個候選對象的集合是可行的,即是否可能往該集合上添加更多的候選對象以獲得一個解。和上一個函數(shù)一樣,此時不考慮解決方法的最優(yōu)性 。
5、選擇函數(shù)可以指出哪一個剩余的候選對象最有希望構(gòu)成問題的解 。
6、最后,目標(biāo)函數(shù)給出解的值。
使用條件
利用貪心法求解的問題應(yīng)具備如下2個特征 。
1、貪心選擇性質(zhì)
一個問題的整體最優(yōu)解可通過一系列局部的最優(yōu)解的選擇達(dá)到,并且每次的選擇可以依賴以前作出的選擇,但不依賴于后面要作出的選擇。這就是貪心選擇性質(zhì)。對于一個具體問題,要確定它是否具有貪心選擇性質(zhì),必須證明每一步所作的貪心選擇最終導(dǎo)致問題的整體最優(yōu)解 。
2、最優(yōu)子結(jié)構(gòu)性質(zhì)
當(dāng)一個問題的最優(yōu)解包含其子問題的最優(yōu)解時,稱此問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。問題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問題可用貪心法求解的關(guān)鍵所在。在實(shí)際應(yīng)用中,至于什么問題具有什么樣的貪心選擇性質(zhì)是不確定的,需要具體問題具體分析。
解題策略
貪心算法不從整體最優(yōu)上加以考慮,所做出的僅是在某種意義上的局部最優(yōu)選擇。使用貪心策略要注意局部最優(yōu)與全局最優(yōu)的關(guān)系,選擇當(dāng)前的局部最優(yōu)并不一定能推導(dǎo)出問題的全局最優(yōu)。貪心策略解題需要解決以下兩個問題:
1、該問題是否適合使用貪心策略求解,也就是該問題是否具有貪心選擇性質(zhì);
2、制定貪心策略,以達(dá)到問題的最優(yōu)解或較優(yōu)解 。
要確定一個問題是否適合用貪心算法求解,必須證明每一步所作的貪心選擇最終導(dǎo)致問題的整體最優(yōu)解。證明的大致過程為:首先考察問題的一個整體最優(yōu)解,并證明可修改這個最優(yōu)解,使其以貪心選擇開始,做了貪心選擇后,原問題簡化為規(guī)模更小的類似子問題。然后用數(shù)學(xué)歸納法證明通過每一步做貪心選擇,最終可得到問題的整體最優(yōu)解。
存在問題
貪心算法也存在如下問題:
1、不能保證解是最佳的。因?yàn)樨澬乃惴ǹ偸菑木植砍霭l(fā),并沒從整體考慮 ;
2、貪心算法一般用來解決求最大或最小解 ;
3、貪心算法只能確定某些問題的可行性范圍 。

發(fā)表評論
請輸入評論內(nèi)容...
請輸入評論/評論長度6~500個字
最新活動更多
-
10月23日火熱報(bào)名中>> 2025是德科技創(chuàng)新技術(shù)峰會
-
10月23日立即報(bào)名>> Works With 開發(fā)者大會深圳站
-
10月24日立即參評>> 【評選】維科杯·OFweek 2025(第十屆)物聯(lián)網(wǎng)行業(yè)年度評選
-
即日-11.25立即下載>>> 費(fèi)斯托白皮書《柔性:汽車生產(chǎn)未來的關(guān)鍵》
-
11月27日立即報(bào)名>> 【工程師系列】汽車電子技術(shù)在線大會
-
12月18日立即報(bào)名>> 【線下會議】OFweek 2025(第十屆)物聯(lián)網(wǎng)產(chǎn)業(yè)大會
推薦專題
- 1 特斯拉工人被故障機(jī)器人打成重傷,索賠3.6億
- 2 【行業(yè)深度研究】退居幕后四年后,張一鳴終于把算法公司變成AI公司?
- 3 AI 時代,阿里云想當(dāng)“安卓” ,那誰是“蘋果”?
- 4 硬剛英偉達(dá)!華為發(fā)布全球最強(qiáng)算力超節(jié)點(diǎn)和集群
- 5 機(jī)器人9月大事件|3家國產(chǎn)機(jī)器人沖刺IPO,行業(yè)交付與融資再創(chuàng)新高!
- 6 谷歌“香蕉”爆火啟示:國產(chǎn)垂類AI的危機(jī)還是轉(zhuǎn)機(jī)?
- 7 00后華裔女生靠兩部AI電影狂賺7.8億人民幣,AI正式進(jìn)軍好萊塢
- 8 美光:AI Capex瘋投不止,終于要拉起存儲超級周期了?
- 9 華為已殺入!AI領(lǐng)域最熱黃金賽道,大廠的數(shù)字人美女讓我一夜沒睡著覺
- 10 隱退4年后,張一鳴久違現(xiàn)身!互聯(lián)網(wǎng)大佬正集體殺回