貪心算法ppt課件(2)(編輯修改稿)
2025-06-08 13:28 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 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ù)超過(guò) 2，舍棄 ) Dde+Dab+Dbc+Def+Dcd+[Dad]； (d頂點(diǎn)度數(shù)超過(guò) 2，舍棄 ) Dde+Dab+Dbc+Def+Dcd+Daf；得到 1條回路 2022/5/31 17 最后得到的回路如圖（ a） 的結(jié)果，總長(zhǎng)度為 50。 2022/5/31 18 不過(guò) ， 這不是此問(wèn)題的最優(yōu)解 ， 此問(wèn)題的最優(yōu)解為下圖所示的路徑 (可以用分枝限界等方法求得 )， 總長(zhǎng)度為。 用貪婪方法得到的結(jié)果同最優(yōu)解相比只多了 %。 2022/5/31 19 設(shè)有 n個(gè)獨(dú)立的作業(yè) {1,2,…,n}， 由 m臺(tái)相同的機(jī)器進(jìn)行加工處理 。 作業(yè) i所需的處理時(shí)間為 ti。 現(xiàn)約定 ， 任何作業(yè)可以在任何一臺(tái)機(jī)器上加工處理 ，但未完工前不允許中斷處理 。 任何作業(yè)不能拆分成更小的子作業(yè) 。 多機(jī)調(diào)度問(wèn)題要求給出一種作業(yè)調(diào)度方案 ， 使所給的 n個(gè)作業(yè)在盡可能短的時(shí)間內(nèi)由 m臺(tái)機(jī)器加工處理完成 。 例 5: 多機(jī)調(diào)度問(wèn)題 2022/5/31 20 ? 這個(gè)問(wèn)題是一個(gè) NP完全問(wèn)題，到目前為止還沒(méi)有一個(gè)有效的解法。對(duì)于這一類問(wèn)題，用貪婪選擇策略有時(shí)可以設(shè)計(jì)出較好的近似算法。采用最長(zhǎng)處理時(shí)間作業(yè)優(yōu)先的貪婪選擇策略可以設(shè)計(jì)出解多機(jī)調(diào)度問(wèn)題的較好的近似算法。按此策略，當(dāng) n≤m時(shí)，我們只要將機(jī)器 i的 [0,ti]時(shí)間區(qū)間分配給作業(yè) i即可。 ? 當(dāng) n＞ m時(shí)，我們首先將 n個(gè)作業(yè)依其所需的處理時(shí)間從大到小排序。然后依此順序?qū)⒆鳂I(yè)分配給空閑的處理機(jī)。 2022/5/31 21 例如 ， 設(shè) 7個(gè)獨(dú)立作業(yè) {1,2,3,4,5,6,7}由 3臺(tái)機(jī)器M1,M2,和 M3來(lái)加工處理 。 各作業(yè)所需的處理時(shí)間分別為{2,14,4,16,6,5,3}。 按貪婪算法產(chǎn)生的作業(yè)調(diào)度如圖 413所示 ， 所需的加工時(shí)間為 17。 當(dāng) n＞ m時(shí) ， 因此算法所需的計(jì)算時(shí)間復(fù)雜度為 O(nlogn)。 2022/5/31 22 一般情況下，用貪婪算法得到的是近似解，而不能保證得到最優(yōu)解。但用貪婪方法計(jì)算最小生成樹(shù)，卻可以設(shè)計(jì)出保證得到最優(yōu)解的算法。 設(shè) G=(V,E)是一個(gè)無(wú)向連通帶權(quán)圖 ， 即一個(gè)網(wǎng)絡(luò) 。 E中每條邊 (v,w)的權(quán)為 c[v][w]。 如果 G的一個(gè)子圖 G’是一棵包含 G的所有頂點(diǎn)的樹(shù) ， 則稱 G’為 G的生成樹(shù) 。 生成樹(shù)上各邊權(quán)的總和稱為該生成樹(shù)的費(fèi)用 。 在 G的所有生成樹(shù)中 ， 費(fèi)用最小的生成樹(shù)稱為 G的最小生成樹(shù) 。 網(wǎng)絡(luò)的最小生成樹(shù)在實(shí)際中有廣泛應(yīng)用 。 例如 ， 在設(shè)計(jì)通信網(wǎng)絡(luò)時(shí) ， 用圖的頂點(diǎn)表示城市 ， 用邊 (v,w)的權(quán) c[v][w]表示建立城市 v和城市 w之間的通信線路所需的費(fèi)用 ， 則最小生成樹(shù)就給出了建立通信網(wǎng)絡(luò)的最經(jīng)濟(jì)的方案 。 例 6: 最小生成樹(shù) 2
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1