貪婪算法ppt課件-在線瀏覽
2025-06-20 18:24本頁面
【正文】 欲分配任務(wù)的開始時(shí)間，若此時(shí)有舊的機(jī)器可用，則將任務(wù)分配給舊機(jī)器。 ?例如：機(jī)器調(diào)度算法 ?啟發(fā)式算法具有直覺傾向 ?近似算法：具有限定功能的啟發(fā)式算法 LOGO 2022/5/31 29 應(yīng)用 1：貨箱裝船 LOGO 2022/5/31 30 ?假設(shè) n=8, c=400 ?[w1 , ... w8 ]=[100, 200, 50, 90, 150, 50, 20, 80] ?利用貪婪算法時(shí)，所考察貨箱的順序?yàn)?, 3 , 6 , 8 , 4 , 1 , 5 , 2。 ?在這種貪婪解決算法中得到[x1 , ..., x8 ] = [ 1 , 0 , 1 , 1 , 0 , 1 , 1 , 1 ]且 6?? ix可以證明：利用貪婪算法能產(chǎn)生最佳裝載 LOGO 2022/5/31 31 貨箱裝載的C++算法實(shí)現(xiàn) void IndirectSort(int w[], int t[], int n) { //假設(shè) w已經(jīng)按照重 量升序排列 for (int i=1。 i++) t[i] = i。 // no swaps so far for (int i = 0。 i++) if (*table[i] *table[i+1]) { Swap(table[i], table[i + 1])。 } return swapped。 IndirectListT::BubbleSort() { for (int i = length。amp。 i)。 } LOGO 2022/5/31 33 應(yīng)用 2： 0/1背包問題 LOGO 2022/5/31 34 幾種貪婪策略 ?價(jià)值貪婪準(zhǔn)則 ：從剩余的物品中，挑選可以裝入背包的價(jià)值最大的物品 ?例如 : n=3, w=[100,10,10], p=[20,15,15], c=105 ?可行解： x=[1,0,0]， p=20 ?最優(yōu)解： x=[0,1,1]， p=30 ?并不能保證得到最優(yōu)解！ LOGO 2022/5/31 35 幾種貪婪策略（續(xù) 1） ?重量貪婪準(zhǔn)則 ：從剩余的物品中，挑選可以裝入背包的重量最小的物品 ?可以解決價(jià)值貪婪準(zhǔn)則的問題，也不能保證得到最優(yōu)解 ?例如： n=2, w=[10,20], p=[5,100], c=25 ?可行解： x=[1,0], p=5 ?最優(yōu)解： x=[0,1], p=100 LOGO 2022/5/31 36 幾種貪婪策略（續(xù) 2） ?價(jià)值密度準(zhǔn)則 ：定義 pi/wi，從剩余的物品中，挑選可以裝入背包的價(jià)值密度最大的物品 ?例如： n=2, w=[10,20], p=[5,100], c=25 ?直覺上接近最優(yōu)解，作為一個(gè)啟發(fā)算法 ?啟發(fā)式貪婪算法，不能保證得到最優(yōu)解 LOGO 2022/5/31 37 改進(jìn)算法 ?首先，最多將 k件物品放入背包； ?如這 k件物品重量大于 c, 則放棄 ?否則考慮用剩下的容量，將
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1