貪婪算法ppt課件(編輯修改稿)
2025-05-30 18:24 本頁面
【文章內(nèi)容簡介】 使用 5臺機器 LOGO 2022/5/31 25 ?一種獲取最有分配的貪婪方法是逐步分配任務。每步分配一件任務，且按照任務的 非遞減 順序進行分配。 ?若已經(jīng)至少有一件任務分配給某臺機器，則稱這臺機器是舊的；若機器非舊則它就是新的。 ?在選擇機器時，遵循的 貪婪法則 為：根據(jù)欲分配任務的開始時間，若此時有舊的機器可用，則將任務分配給舊機器。否則，任務分配給新機器 貪婪算法求解：機器調(diào)度 LOGO 2022/5/31 26 機器調(diào)度 （續(xù)） 首先，按照任務時間區(qū)間遞增排列（可以使用堆） 然后，按照貪婪準則“先舊后新”將任務分配給機器 LOGO 2022/5/31 27 例 136 最短路徑 貪婪算法 不一定能獲取 最優(yōu)解！ 1 3 4 2 5： 10 145： 6 LOGO 2022/5/31 28 總結(jié) ?貪婪算法并不總能保證得到最優(yōu)解 ?啟發(fā)式算法：算法并不保證得到最優(yōu)解，但是通常所得結(jié)果與最優(yōu)解相差無幾或很接近。 ?例如：機器調(diào)度算法 ?啟發(fā)式算法具有直覺傾向 ?近似算法：具有限定功能的啟發(fā)式算法 LOGO 2022/5/31 29 應用 1：貨箱裝船 LOGO 2022/5/31 30 ?假設 n=8, c=400 ?[w1 , ... w8 ]=[100, 200, 50, 90, 150, 50, 20, 80] ?利用貪婪算法時，所考察貨箱的順序為7, 3 , 6 , 8 , 4 , 1 , 5 , 2。 ?貨箱 7, 3 , 6 , 8 , 4 , 1的總重量為 390個單位且已被裝載，剩下的裝載能力為 10個單位，小于剩下的任何一個貨箱。 ?在這種貪婪解決算法中得到[x1 , ..., x8 ] = [ 1 , 0 , 1 , 1 , 0 , 1 , 1 , 1 ]且 6?? ix可以證明：利用貪婪算法能產(chǎn)生最佳裝載 LOGO 2022/5/31 31 貨箱裝載的C++算法實現(xiàn) void IndirectSort(int w[], int t[], int n) { //假設 w已經(jīng)按照重 量升序排列 for (int i=1。 i = n。 i++) t[i] = i。 } LOGO 2022/5/31 32 templateclass T bool IndirectListT::Bubble(int n) { bool swapped = false。 // no swaps so far for (int i = 0。 i n 1。 i++) if (*table[i] *table[i+1]) { Swap(table[i], table[i + 1])。 swapped = true。 } return swapped。 } templateclass T IndirectListTa
教學課件相關(guān)推薦
鄂ICP備17016276號-1