五大常用算法之三:貪心算法

一正什、基本概念:

?所謂貪心算法是指,在對問題求解時(shí)裹唆,總是做出在當(dāng)前看來是最好的選擇誓斥。也就是說,不從整體最優(yōu)上加以考慮许帐,他所做出的僅是在某種意義上的局部最優(yōu)解岖食。

?貪心算法沒有固定的算法框架,算法設(shè)計(jì)的關(guān)鍵是貪心策略的選擇舞吭。必須注意的是泡垃,貪心算法不是對所有問題都能得到整體最優(yōu)解,選擇的貪心策略必須具備無后效性羡鸥,即某個(gè)狀態(tài)以后的過程不會影響以前的狀態(tài)蔑穴,只與當(dāng)前狀態(tài)有關(guān)。

?所以對所采用的貪心策略一定要仔細(xì)分析其是否滿足無后效性惧浴。

二存和、貪心算法的基本思路:

??? 1.建立數(shù)學(xué)模型來描述問題。

??? 2.把求解的問題分成若干個(gè)子問題。

??? 3.對每一子問題求解捐腿,得到子問題的局部最優(yōu)解纵朋。

??? 4.把子問題的解局部最優(yōu)解合成原來解問題的一個(gè)解。

三茄袖、貪心算法適用的問題

????? 貪心策略適用的前提是:局部最優(yōu)策略能導(dǎo)致產(chǎn)生全局最優(yōu)解操软。

實(shí)際上,貪心算法適用的情況很少宪祥。一般聂薪,對一個(gè)問題分析是否適用于貪心算法,可以先選擇該問題下的幾個(gè)實(shí)際數(shù)據(jù)進(jìn)行分析蝗羊,就可做出判斷藏澳。


四、貪心算法的實(shí)現(xiàn)框架

??? 從問題的某一初始解出發(fā)耀找;

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

??? {?

????????? 利用可行的決策翔悠,求出可行解的一個(gè)解元素;

??? }

??? 由所有解元素組合成問題的一個(gè)可行解野芒;


五蓄愁、貪心策略的選擇

???? 因?yàn)橛秘澬乃惴ㄖ荒芡ㄟ^解局部最優(yōu)解的策略來達(dá)到全局最優(yōu)解,因此复罐,一定要注意判斷問題是否適合采用貪心算法策略涝登,找到的解是否一定是問題的最優(yōu)解。

六效诅、例題分析

??? 下面是一個(gè)可以試用貪心算法解的題目胀滚,貪心解的確不錯(cuò),可惜不是最優(yōu)解乱投。

??? [背包問題]有一個(gè)背包咽笼,背包容量是M=150。有7個(gè)物品戚炫,物品可以分割成任意大小剑刑。

??? 要求盡可能讓裝入背包中的物品總價(jià)值最大,但不能超過總?cè)萘俊?/p>

??? 物品 A B C D E F G

??? 重量 35 30 60 50 40 10 25

??? 價(jià)值 10 40 30 50 35 40 30

??? 分析:

??? 目標(biāo)函數(shù): ∑pi最大

??? 約束條件是裝入的物品總重量不超過背包容量:∑wi<=M( M=150)

??? (1)根據(jù)貪心的策略双肤,每次挑選價(jià)值最大的物品裝入背包施掏,得到的結(jié)果是否最優(yōu)?

??? (2)每次挑選所占重量最小的物品裝入是否能得到最優(yōu)解茅糜?

??? (3)每次選取單位重量價(jià)值最大的物品七芭,成為解本題的策略。

??? 值得注意的是蔑赘,貪心算法并不是完全不可以使用狸驳,貪心策略一旦經(jīng)過證明成立后预明,它就是一種高效的算法。

??? 貪心算法還是很常見的算法之一耙箍,這是由于它簡單易行撰糠,構(gòu)造貪心策略不是很困難。

??? 可惜的是辩昆,它需要證明后才能真正運(yùn)用到題目的算法中阅酪。

??? 一般來說,貪心算法的證明圍繞著:整個(gè)問題的最優(yōu)解一定由在貪心策略中存在的子問題的最優(yōu)解得來的卤材。

??? 對于例題中的3種貪心策略遮斥,都是無法成立(無法被證明)的峦失,解釋如下:

??? (1)貪心策略:選取價(jià)值最大者扇丛。反例:

??? W=30

??? 物品:A B C

??? 重量:28 12 12

??? 價(jià)值:30 20 20

??? 根據(jù)策略,首先選取物品A尉辑,接下來就無法再選取了帆精,可是,選取B隧魄、C則更好卓练。

??? (2)貪心策略:選取重量最小。它的反例與第一種策略的反例差不多购啄。

??? (3)貪心策略:選取單位重量價(jià)值最大的物品襟企。反例:

??? W=30

??? 物品:A B C

??? 重量:28 20 10

??? 價(jià)值:28 20 10

??? 根據(jù)策略,三種物品單位重量價(jià)值一樣狮含,程序無法依據(jù)現(xiàn)有策略作出判斷顽悼,如果選擇A,則答案錯(cuò)誤几迄。

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末蔚龙,一起剝皮案震驚了整個(gè)濱河市,隨后出現(xiàn)的幾起案子映胁,更是在濱河造成了極大的恐慌木羹,老刑警劉巖,帶你破解...
    沈念sama閱讀 218,607評論 6 507
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件解孙,死亡現(xiàn)場離奇詭異坑填,居然都是意外死亡,警方通過查閱死者的電腦和手機(jī)弛姜,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 93,239評論 3 395
  • 文/潘曉璐 我一進(jìn)店門脐瑰,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人娱据,你說我怎么就攤上這事蚪黑≈严В” “怎么了?”我有些...
    開封第一講書人閱讀 164,960評論 0 355
  • 文/不壞的土叔 我叫張陵忌穿,是天一觀的道長抒寂。 經(jīng)常有香客問我,道長掠剑,這世上最難降的妖魔是什么屈芜? 我笑而不...
    開封第一講書人閱讀 58,750評論 1 294
  • 正文 為了忘掉前任,我火速辦了婚禮朴译,結(jié)果婚禮上井佑,老公的妹妹穿的比我還像新娘。我一直安慰自己眠寿,他們只是感情好躬翁,可當(dāng)我...
    茶點(diǎn)故事閱讀 67,764評論 6 392
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著盯拱,像睡著了一般盒发。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上狡逢,一...
    開封第一講書人閱讀 51,604評論 1 305
  • 那天宁舰,我揣著相機(jī)與錄音,去河邊找鬼奢浑。 笑死蛮艰,一個(gè)胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的雀彼。 我是一名探鬼主播壤蚜,決...
    沈念sama閱讀 40,347評論 3 418
  • 文/蒼蘭香墨 我猛地睜開眼,長吁一口氣:“原來是場噩夢啊……” “哼详羡!你這毒婦竟也來了仍律?” 一聲冷哼從身側(cè)響起,我...
    開封第一講書人閱讀 39,253評論 0 276
  • 序言:老撾萬榮一對情侶失蹤实柠,失蹤者是張志新(化名)和其女友劉穎水泉,沒想到半個(gè)月后,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體窒盐,經(jīng)...
    沈念sama閱讀 45,702評論 1 315
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡草则,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 37,893評論 3 336
  • 正文 我和宋清朗相戀三年,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了蟹漓。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片炕横。...
    茶點(diǎn)故事閱讀 40,015評論 1 348
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡,死狀恐怖葡粒,靈堂內(nèi)的尸體忽然破棺而出份殿,到底是詐尸還是另有隱情膜钓,我是刑警寧澤,帶...
    沈念sama閱讀 35,734評論 5 346
  • 正文 年R本政府宣布卿嘲,位于F島的核電站颂斜,受9級特大地震影響,放射性物質(zhì)發(fā)生泄漏拾枣。R本人自食惡果不足惜沃疮,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 41,352評論 3 330
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望梅肤。 院中可真熱鬧司蔬,春花似錦蔓搞、人聲如沸手报。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,934評論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至蒲凶,卻和暖如春鹏倘,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背炒辉。 一陣腳步聲響...
    開封第一講書人閱讀 33,052評論 1 270
  • 我被黑心中介騙來泰國打工, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留泉手,地道東北人黔寇。 一個(gè)月前我還...
    沈念sama閱讀 48,216評論 3 371
  • 正文 我出身青樓,卻偏偏與公主長得像斩萌,于是被迫代替她去往敵國和親缝裤。 傳聞我的和親對象是個(gè)殘疾皇子,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 44,969評論 2 355

推薦閱讀更多精彩內(nèi)容

  • 分治算法 一颊郎、基本概念 在計(jì)算機(jī)科學(xué)中憋飞,分治法是一種很重要的算法。字面上的解釋是“分而治之”姆吭,就是把一個(gè)復(fù)雜的問題...
    木葉秋聲閱讀 5,296評論 0 3
  • 分治算法 一榛做、基本概念 在計(jì)算機(jī)科學(xué)中,分治法是一種很重要的算法内狸。字面上的解釋是“分而治之”检眯,就是把一個(gè)復(fù)雜的問題...
    Java資訊庫閱讀 9,770評論 0 14
  • 貪心算法的基本思想 貪心算法,是尋找最優(yōu)解問題的常用方法昆淡,這種方法模式一般將求解過程分成若干個(gè)步驟锰瘸,但每個(gè)步驟都應(yīng)...
    結(jié)構(gòu)學(xué)AI閱讀 7,707評論 0 0
  • 1.簡介、思路和特性 1.1 簡介 貪心算法(又稱貪婪算法)是指昂灵,在對問題求解時(shí)避凝,總是做出在當(dāng)前看來是最好的選擇舞萄。...
    王偵閱讀 454評論 0 0
  • 今天談?wù)摰闹鹘鞘顷惞谙:蜆銟洹? 談及陳冠希鹏氧,小伙伴們肯定立馬想到“艷照門”事件,我只能說大家都...
    益達(dá)居士閱讀 260評論 1 5