貪婪算法ppt課件(更新版)
【正文】 ?在每個階段，都作出一個看上去最優(yōu)的決策（在一定的標準下）。 ?貨箱 7, 3 , 6 , 8 , 4 , 1的總重量為 390個單位且已被裝載，剩下的裝載能力為 10個單位，小于剩下的任何一個貨箱。 swapped = true。 return *this。 i++) InDegree[i] = 0。 i = n。 if (!InDegree[u]) (u)。 } } DeactivatePos()。 i = 0。 i = n。 把 w添加到 V的尾部 } If(V中的頂點個數(shù)少于 n)算法失敗 else V是一個拓撲序列 LOGO 2022/5/31 44 拓撲排序的實現(xiàn) ?（ 1）數(shù)據(jù)結(jié)構(gòu)的選擇 ? 實現(xiàn)方法：將序列 V用一維數(shù)組 v來描述，用一個棧來保存加入 V的候選頂點；另有一個一維數(shù)組InDegree， InDegree[j]表示與頂點 j相連的節(jié)點 i的數(shù)目，其中頂點 i不是 V中的成員，它們之間的有向圖的邊表示為（ i， j）。 } templateclass T IndirectListTamp。 i = n。 ?作出貪婪決策的依據(jù)成為 貪婪準則 貪婪算法思想 LOGO 2022/5/31 20 ?貪心算法的基本思路如下： 1. 建立數(shù)學模型來描述問題 2. 把求解的問題分成若干個子問題 3. 對每一子問題求解，得到子問題的局部最優(yōu)解 4. 把子問題的解局部最優(yōu)解合成原來解問題的一個解 貪婪算法思想（續(xù) 1） LOGO 2022/5/31 21 ?實現(xiàn)該算法的過程： 從問題的某一初始解出發(fā)； while 能朝給定總目標前進一步 do 求出可行解的一個解元素； 由所有解元素組合成問題的一個可行解； 貪婪算法思想（續(xù) 2） LOGO 2022/5/31 22 例 134 找零錢問題 LOGO 2022/5/31 23 ?貪婪算法有一種 直覺 的傾向， ?例如：在找零錢時，直覺告訴我們應使找出的硬幣數(shù)目最少（至少是接近最少的數(shù)目） LOGO 2022/5/31 24 例 135 機器調(diào)度問題 使用 7臺機器 使用 5臺機器 LOGO 2022/5/31 25 ?一種獲取最有分配的貪婪方法是逐步分配任務(wù)。 。也就是說，不從整體最優(yōu)上加以考慮，他所做出的僅是在某種意義上的局部最優(yōu)解。 ?存在問題： ?； ?； ?。 ?在選擇機器時，遵循的 貪婪法則 為：根據(jù)欲分配任務(wù)的開始時間，若此時有舊的機器可用，則將任務(wù)分配給舊機器。 // no swaps so far for (int i = 0。amp。 InitializePos()。 u = NextVertex(i)。 v[i++] = w。 } 鄰接矩陣： Θ (n2) 鄰接鏈表： Θ (n+e)
教學課件相關(guān)推薦
鄂ICP備17016276號-1