貪婪算法ppt課件-閱讀頁(yè)
2025-05-18 18:24本頁(yè)面
【正文】 剩余物品按照pi/wi的遞減順序裝入 LOGO 2022/5/31 38 示例 ?n=4, w=[2,4,6,7], p=[6,10,12,13], c=11 ?k=0, x=[1,1,0,0], p=16, 剩余 5個(gè)單元 ?k=1, 初始子集 {1}, {2}, {3}, {4} ?{1}{2}: x=[1,1,0,0], p=16 ?{3}: x={1,0,1,0}, p=18 ?{4}: x={1,0,0,1}, p=19， 最優(yōu)解 LOGO 2022/5/31 39 示例 續(xù) ?n=4, w=[2,4,6,7], p=[6,10,12,13], c=11, k=2, ?{1,2}, x=[1,1,0,0], p=16 ?{1,3}, x=[1,0,1,0], p=18 ?{1,4}, x=[1,0,0,1], p=19 ?{2,3}, x=[0,1,1,0], p=22 ?{2,4}, x=[0,1,0,1], p=23, 最優(yōu)解 ?{3,4}, 不可能！ LOGO 2022/5/31 40 應(yīng)用 3：拓?fù)渑判? 拓?fù)渑判颍河赡硞€(gè)集合上一個(gè)偏序關(guān)系得到一個(gè)全序關(guān)系 LOGO 2022/5/31 41 1 2 3 4 5 6 算法思想 1. 在有序圖上選取 一個(gè)沒(méi)有前驅(qū)的頂點(diǎn) 并輸出 2. 從該圖中刪除該頂 點(diǎn)以及所有以它為弧 尾的弧 序列 1： 213456 序列 2： 251346 LOGO 2022/5/31 42 拓?fù)渑判虻奶攸c(diǎn) ?拓?fù)渑判蜉敵龅男蛄锌赡苡卸喾N ! ?利用拓?fù)渑判?，可以判斷一個(gè)有向圖是否為有向無(wú)環(huán)圖 ?算法失?。罕硎居邢驁D中有環(huán)路 LOGO 2022/5/31 43 拓?fù)渑判蛴秘澙匪惴▽?shí)現(xiàn) 設(shè) n是有向圖中的頂點(diǎn)數(shù) 設(shè) V是一個(gè)空序列 While(true){ 設(shè) w不存在入邊（ v,w） ,其中頂點(diǎn) v不在 V中 如果沒(méi)有這樣的 w， break。 ? NetWork: 修改有向圖的基類函數(shù) LOGO 2022/5/31 45 bool Network::Topological(int v[]) { int n = Vertices()。 InitializePos()。 i = n。 for (i = 1。 i++) { int u = Begin(i)。 u = NextVertex(i)。 for (i = 1。 i++) if (!InDegree[i]) (i)。 while (!()) { int w。 v[i++] = w。 while (u) { InDegree[u]。 u = NextVertex(w)。 delete [] InDegree。 } 鄰接矩陣： Θ (n2) 鄰接鏈表： Θ (n+e)
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1