算法之旅(十二) 核心算法思想之一貪心算法

貪心算法(Greedy Algorithm)是一種在每一步選擇中都采取在當(dāng)前狀態(tài)下最好或最優(yōu)(即最有利)的選擇,從而希望能夠得到全局最優(yōu)解的算法虎韵。它不從整體最優(yōu)上考慮,只是在每個(gè)子步驟上作出局部最優(yōu)的選擇胳搞。


貪心算法的思想:

  1. 局部最優(yōu)選擇: 在問(wèn)題求解的每個(gè)階段拨黔,都作出當(dāng)前看來(lái)最好的選擇,不考慮未來(lái)可能產(chǎn)生的影響匾竿。

  2. 全局最優(yōu)目標(biāo): 希望通過(guò)一系列的局部最優(yōu)選擇奔脐,最終得到問(wèn)題的全局最優(yōu)解辫诅。

  3. 一次決策悬而,不可回退: 一旦作出選擇零截,便不再更改,不會(huì)回溯或調(diào)整之前的決策昵慌。


貪心算法的應(yīng)用:

其實(shí)有很多假夺,我舉例比較日常的兩個(gè)

一、最短路徑

Dijkstra算法

應(yīng)用背景:

在帶非負(fù)權(quán)值的有向圖中斋攀,尋找從源點(diǎn)到其他所有節(jié)點(diǎn)的最短路徑已卷。Dijkstra算法通過(guò)貪心策略,每次選擇距離最近的未訪(fǎng)問(wèn)節(jié)點(diǎn)蜻韭,更新其鄰居的最短路徑。

貪心策略:

  • 每次選擇當(dāng)前已知的最近節(jié)點(diǎn)柿扣,更新其鄰接節(jié)點(diǎn)的最短路徑肖方。
  • 不回溯,因?yàn)橐坏┐_定了節(jié)點(diǎn)的最短路徑未状,就不會(huì)再更新俯画。

實(shí)際應(yīng)用:

  • 導(dǎo)航系統(tǒng):如GPS導(dǎo)航,計(jì)算從當(dāng)前位置到目的地的最短路線(xiàn)司草。
  • 網(wǎng)絡(luò)路由:在數(shù)據(jù)通信中艰垂,尋找數(shù)據(jù)包傳輸?shù)淖疃搪窂健?/li>

二泡仗、工序調(diào)度問(wèn)題

應(yīng)用背景:

有多個(gè)需要在同一臺(tái)機(jī)器上處理的任務(wù),每個(gè)任務(wù)有不同的處理時(shí)間和截止時(shí)間猜憎,目標(biāo)是最小化延遲任務(wù)的數(shù)量或總延遲時(shí)間娩怎。

貪心策略:

  • 按照截止時(shí)間排序,優(yōu)先處理截止時(shí)間早的任務(wù)胰柑。
  • 或者按照處理時(shí)間排序截亦,優(yōu)先處理處理時(shí)間短的任務(wù)(SJF調(diào)度)。

實(shí)際應(yīng)用:

  • 生產(chǎn)線(xiàn)調(diào)度:提高生產(chǎn)效率柬讨,減少延遲崩瓤。
  • CPU調(diào)度:優(yōu)化任務(wù)執(zhí)行順序,提升系統(tǒng)性能踩官。

簡(jiǎn)單來(lái)說(shuō)-却桶。- 短進(jìn)程優(yōu)先


貪心算法的特性:

  1. 貪心選擇性質(zhì)(Greedy Choice Property): 可以通過(guò)局部最優(yōu)選擇構(gòu)建全局最優(yōu)解。

  2. 最優(yōu)子結(jié)構(gòu)性質(zhì)(Optimal Substructure): 問(wèn)題的最優(yōu)解包含其子問(wèn)題的最優(yōu)解蔗牡。


貪心算法的優(yōu)點(diǎn):

  • 高效性: 通常具有較低的時(shí)間復(fù)雜度颖系,計(jì)算速度快。

  • 實(shí)現(xiàn)簡(jiǎn)單: 算法邏輯直觀明了蛋逾,編程實(shí)現(xiàn)較為容易集晚。


貪心算法的缺點(diǎn):

  • 局限性: 并非所有問(wèn)題都適合貪心算法,只有滿(mǎn)足特定性質(zhì)的問(wèn)題才能保證最優(yōu)解区匣。

  • 可能非最優(yōu): 由于只關(guān)注局部最優(yōu)偷拔,可能導(dǎo)致無(wú)法獲得全局最優(yōu)解。


貪心算法與回溯算法的區(qū)別:

1. 思想不同:

  • 貪心算法:

    • 局部視角: 每一步都作出當(dāng)前最優(yōu)選擇亏钩,不考慮整體情況和未來(lái)可能的后果莲绰。

    • 不可回退: 一旦作出選擇,不會(huì)回溯調(diào)整之前的決策姑丑。

  • 回溯算法:

    • 全局視角: 通過(guò)遍歷所有可能的解空間蛤签,找到所有滿(mǎn)足條件的解或最優(yōu)解。

    • 回退機(jī)制: 當(dāng)某條路徑無(wú)法達(dá)成目標(biāo)時(shí)栅哀,回溯到上一步震肮,嘗試其他可能性。

2. 解決問(wèn)題方式不同:

  • 貪心算法: 一次性決策留拾,逐步構(gòu)建解答戳晌,不考慮之前或之后的選擇對(duì)當(dāng)前的影響。

  • 回溯算法: 試探性地搜索痴柔,通過(guò)遞歸和回溯機(jī)制沦偎,系統(tǒng)地嘗試所有可能的方案。

3. 時(shí)間復(fù)雜度不同:

  • 貪心算法: 通常為多項(xiàng)式時(shí)間復(fù)雜度,如O(n log n)豪嚎、O(n)搔驼,效率高。

  • 回溯算法: 時(shí)間復(fù)雜度通常為指數(shù)級(jí)別侈询,隨著問(wèn)題規(guī)模增大舌涨,計(jì)算量迅速增長(zhǎng)。

4. 適用問(wèn)題類(lèi)型不同:

  • 貪心算法: 適用于滿(mǎn)足貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)的問(wèn)題妄荔。

  • 回溯算法: 適用于需要搜索全部解空間的問(wèn)題泼菌,如組合、排列啦租、路徑搜索等哗伯。

5. 解的最優(yōu)性保證不同:

  • 貪心算法: 不能保證對(duì)所有問(wèn)題都得到全局最優(yōu)解。

  • 回溯算法: 通過(guò)全面搜索篷角,可以找到全局最優(yōu)解或所有可行解焊刹。


舉例對(duì)比:

背包問(wèn)題:

  • 貪心算法(部分背包問(wèn)題):

    • 場(chǎng)景: 物品可以分割成任意大小。

    • 方法: 按照物品的單位價(jià)值從高到低排序恳蹲,依次裝入背包虐块,直到容量用完。

    • 結(jié)果: 能夠獲得最大總價(jià)值嘉蕾,貪心算法在此適用且最優(yōu)贺奠。

  • 回溯算法(0-1背包問(wèn)題):

    • 場(chǎng)景: 物品不可分割,每個(gè)物品只能選擇“拿”或“不拿”错忱。

    • 方法: 通過(guò)回溯算法嘗試所有可能的物品組合儡率,計(jì)算總價(jià)值和總重量,選擇符合條件的最大價(jià)值組合以清。

    • 結(jié)果: 能夠找到全局最優(yōu)解儿普,但計(jì)算量大。


總結(jié):

  • 貪心算法:

    • 優(yōu)勢(shì): 高效掷倔、實(shí)現(xiàn)簡(jiǎn)單眉孩,在某些問(wèn)題上可以快速得到最優(yōu)解。

    • 劣勢(shì): 由于只考慮局部最優(yōu)勒葱,可能無(wú)法得到全局最優(yōu)解浪汪,適用范圍有限。

  • 回溯算法:

    • 優(yōu)勢(shì): 能夠找到所有可能的解凛虽,確保全局最優(yōu)死遭。

    • 劣勢(shì): 計(jì)算復(fù)雜度高,可能導(dǎo)致性能問(wèn)題涩维。


總體來(lái)說(shuō)殃姓,貪心算法和回溯算法在思想和應(yīng)用上有顯著區(qū)別:

  • 貪心算法適用于希望快速找到一個(gè)可能是最優(yōu)的解,但不要求遍歷所有可能性的情況瓦阐。

  • 回溯算法則用于需要窮舉所有可能的方案蜗侈,以確保找到所有解或最優(yōu)解的情況。

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
禁止轉(zhuǎn)載睡蟋,如需轉(zhuǎn)載請(qǐng)通過(guò)簡(jiǎn)信或評(píng)論聯(lián)系作者踏幻。
  • 序言:七十年代末,一起剝皮案震驚了整個(gè)濱河市戳杀,隨后出現(xiàn)的幾起案子该面,更是在濱河造成了極大的恐慌,老刑警劉巖信卡,帶你破解...
    沈念sama閱讀 212,718評(píng)論 6 492
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件隔缀,死亡現(xiàn)場(chǎng)離奇詭異,居然都是意外死亡傍菇,警方通過(guò)查閱死者的電腦和手機(jī)猾瘸,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 90,683評(píng)論 3 385
  • 文/潘曉璐 我一進(jìn)店門(mén),熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)丢习,“玉大人牵触,你說(shuō)我怎么就攤上這事「赖停” “怎么了揽思?”我有些...
    開(kāi)封第一講書(shū)人閱讀 158,207評(píng)論 0 348
  • 文/不壞的土叔 我叫張陵,是天一觀的道長(zhǎng)见擦。 經(jīng)常有香客問(wèn)我钉汗,道長(zhǎng),這世上最難降的妖魔是什么锡宋? 我笑而不...
    開(kāi)封第一講書(shū)人閱讀 56,755評(píng)論 1 284
  • 正文 為了忘掉前任儡湾,我火速辦了婚禮,結(jié)果婚禮上执俩,老公的妹妹穿的比我還像新娘徐钠。我一直安慰自己,他們只是感情好役首,可當(dāng)我...
    茶點(diǎn)故事閱讀 65,862評(píng)論 6 386
  • 文/花漫 我一把揭開(kāi)白布尝丐。 她就那樣靜靜地躺著,像睡著了一般衡奥。 火紅的嫁衣襯著肌膚如雪爹袁。 梳的紋絲不亂的頭發(fā)上,一...
    開(kāi)封第一講書(shū)人閱讀 50,050評(píng)論 1 291
  • 那天矮固,我揣著相機(jī)與錄音失息,去河邊找鬼譬淳。 笑死,一個(gè)胖子當(dāng)著我的面吹牛盹兢,可吹牛的內(nèi)容都是我干的邻梆。 我是一名探鬼主播,決...
    沈念sama閱讀 39,136評(píng)論 3 410
  • 文/蒼蘭香墨 我猛地睜開(kāi)眼绎秒,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼浦妄!你這毒婦竟也來(lái)了?” 一聲冷哼從身側(cè)響起见芹,我...
    開(kāi)封第一講書(shū)人閱讀 37,882評(píng)論 0 268
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤剂娄,失蹤者是張志新(化名)和其女友劉穎,沒(méi)想到半個(gè)月后玄呛,有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體阅懦,經(jīng)...
    沈念sama閱讀 44,330評(píng)論 1 303
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 36,651評(píng)論 2 327
  • 正文 我和宋清朗相戀三年徘铝,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了故黑。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 38,789評(píng)論 1 341
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡庭砍,死狀恐怖场晶,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情怠缸,我是刑警寧澤诗轻,帶...
    沈念sama閱讀 34,477評(píng)論 4 333
  • 正文 年R本政府宣布,位于F島的核電站揭北,受9級(jí)特大地震影響扳炬,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜搔体,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 40,135評(píng)論 3 317
  • 文/蒙蒙 一恨樟、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧疚俱,春花似錦劝术、人聲如沸。這莊子的主人今日做“春日...
    開(kāi)封第一講書(shū)人閱讀 30,864評(píng)論 0 21
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)。三九已至梁钾,卻和暖如春绳泉,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背姆泻。 一陣腳步聲響...
    開(kāi)封第一講書(shū)人閱讀 32,099評(píng)論 1 267
  • 我被黑心中介騙來(lái)泰國(guó)打工零酪, 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留冒嫡,地道東北人。 一個(gè)月前我還...
    沈念sama閱讀 46,598評(píng)論 2 362
  • 正文 我出身青樓四苇,卻偏偏與公主長(zhǎng)得像灯谣,于是被迫代替她去往敵國(guó)和親。 傳聞我的和親對(duì)象是個(gè)殘疾皇子蛔琅,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 43,697評(píng)論 2 351

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