貪心算法ppt課件(2)-wenkub
2023-05-27 13:28:58 本頁(yè)面
【正文】 節(jié)省時(shí)間，主要的運(yùn)算時(shí)間是用來(lái)對(duì) n個(gè)元素進(jìn)行排序，故其復(fù)雜性是 O（ nlogn）。 貪婪算法雖不能保證得到最優(yōu)結(jié)果，但對(duì)于一些除了“窮舉”方法外沒(méi)有有效算法的問(wèn)題，用貪婪算法往往能很快地得出較好的結(jié)果，如果此較好結(jié)果與最優(yōu)結(jié)果相差不是很多的話，此方法還是很實(shí)用的?？偣灿昧鶄€(gè)砝碼，事實(shí)說(shuō)明這是最好的結(jié)果。在一些情況下，即使貪婪 算法不能得到整體最優(yōu)解，但其最終結(jié)果卻是最優(yōu)解的很好的近似解。當(dāng)然，我們希望貪婪算法得到的最終結(jié)果也是整體最優(yōu)的。 這里 ， 我們下意識(shí)地使用了這樣的找硬幣算法：首先選出一個(gè)面值不超過(guò)六角三分的最大硬幣 ， 即二角五分；然后從六角三分中減去二角五分 ， 剩下三角八分；再選出一個(gè)面值不超過(guò)三角八分的最大硬幣 ， 即又一個(gè)二角五分 ， 如此一直做下去 。 假設(shè)有四種硬幣 ，它們的面值分別為二角五分 、 一角 、 五分和一分 。 現(xiàn)在要找給某顧客六角三分錢 。 這個(gè)找硬幣的方法實(shí)際上就是貪婪算法 。上面所說(shuō)的找硬幣算法得到的結(jié)果就是一個(gè)整體最優(yōu)解。 2022/5/31 4 設(shè)天平有一些 25克的砝碼，一些 10克的砝碼，一些 5克的砝碼和一些 1克的砝碼。 例 1．選取砝碼 2022/5/31 5 如果問(wèn)題改成：砝碼的種類分別為 11克、 5克和 1克，待稱的物體是 15克。 2022/5/31 6 設(shè)有 n=8個(gè)體積分別為 54， 45， 43， 29， 23， 21，14， 1的物體和一個(gè)容積為 C=110的背包，問(wèn)選擇哪幾個(gè)物體裝入背包可以使其裝的最滿。 例 2. 背包問(wèn)題 2022/5/31 7 如果對(duì)上述算法作一些改進(jìn)，可得到更好的結(jié)果。因?yàn)閺?n個(gè)物體中取出 j個(gè)共有 種方案，此值隨著 j的增加而增加較快，但可以證明此改進(jìn)算法的復(fù)雜性為 O（ knk+1） ,因 k是常數(shù)，故仍為多項(xiàng)式界的算法。當(dāng) n增大時(shí)， k不能隨著 n不斷的加大，如 k隨 n增大而同時(shí)加大，其復(fù)雜性就是指數(shù)型而不是多項(xiàng)式型的了，而如 k取值較小，又不能保證得出最優(yōu)解。 得到一條回路： v1→v 3→v 4→v 2→v 5→v 1 同由分枝限解方法得到的路徑相同，因此是最佳的回路。 距離按從小到大的次序排列 : Dde(3), Dab(5), Dbc(5), Def(5), Dac(), Ddf(), Dbe(), Dbd(), Dcd(14), Dbf(), Dce(), Dae(), Dad(), Daf(18), Def() 2022/5/31 16 按貪婪算法原則 ， 其選擇過(guò)程如下： Dde； Dde+Dab； Dde+Dab+Dbc； Dde+Dab+Dbc+Def； Dde+Dab+Dbc+Def+[Dac]； (形成小回路 ，舍棄 ) Dde+Dab+Dbc+Def+[Ddf]； (形成小回路，舍棄 ) Dde+Dab+Dbc+Def+[Dbe]； (b頂點(diǎn)度數(shù)超過(guò) 2，舍棄 ) Dde+Dab+Dbc+Def+[Dbd]； (b頂點(diǎn)度數(shù)超過(guò) 2，舍棄 ) Dde+Dab+Dbc+Def+Dcd； Dde+Dab+Dbc+Def+Dcd+[Dbf]； (b頂點(diǎn)度數(shù)超過(guò) 2，舍棄 ) Dde+Dab+Dbc+Def+Dcd+[Dce]； (c、 e頂點(diǎn)度數(shù)超過(guò) 2，舍棄 ) Dde+Dab+Dbc+Def+Dcd+[Dae]； (e頂點(diǎn)度數(shù)超過(guò) 2，舍棄 ) Dde+Dab+Dbc+Def+Dcd+[Dae]； (e頂點(diǎn)度數(shù)
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1