貪心算法,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個字
最新活動更多
-
7月8日立即報(bào)名>> 【在線會議】英飛凌新一代智能照明方案賦能綠色建筑與工業(yè)互聯(lián)
-
7月22-29日立即報(bào)名>> 【線下論壇】第三屆安富利汽車生態(tài)圈峰會
-
7月31日免費(fèi)預(yù)約>> OFweek 2025具身機(jī)器人動力電池技術(shù)應(yīng)用大會
-
7.30-8.1火熱報(bào)名中>> 全數(shù)會2025(第六屆)機(jī)器人及智能工廠展
-
免費(fèi)參會立即報(bào)名>> 7月30日- 8月1日 2025全數(shù)會工業(yè)芯片與傳感儀表展
-
即日-2025.8.1立即下載>> 《2024智能制造產(chǎn)業(yè)高端化、智能化、綠色化發(fā)展藍(lán)皮書》
推薦專題
- 1 AI 眼鏡讓百萬 APP「集體失業(yè)」?
- 2 豆包前負(fù)責(zé)人喬木出軌BP后續(xù):均被辭退
- 3 一文看懂視覺語言動作模型(VLA)及其應(yīng)用
- 4 “支付+”時代,支付即生態(tài) | 2025中國跨境支付十大趨勢
- 5 中國最具實(shí)力AI公司TOP10
- 6 特斯拉Robotaxi上路,馬斯克端上畫了十年的餅
- 7 國家數(shù)據(jù)局局長劉烈宏調(diào)研格創(chuàng)東智
- 8 AI的夏天:第四范式VS云從科技VS地平線機(jī)器人
- 9 張勇等人退出阿里合伙人
- 10 深圳跑出40億超級隱形冠軍:賣機(jī)器人年入6.1億,港股上市