【正文】 H． Insert(x)； } for(inti： n； i=1； i){ H． DeleteMin(x)； cout”將機(jī)器” x． ID“從” x． avail到” (x． avail十 a[i]． time) ”的時(shí)間段分配給作業(yè)” a[i]. IDendl； x． avail+=a[i]． time； H． insert(x)； } } 。 } 多機(jī)調(diào)度問題的 貪心近似算法 多機(jī)調(diào)度問題的 貪心近似算法 templateclass Type void Greedy(Type a[]， int n， int m) {if (n=m){ cont”為每個(gè)作業(yè)分配一臺機(jī)器 .“endl return； } Sort(a， n)； MinHeapMachineNodeH(m)； MachineNode x； for(int： i=1； i=m。 public: operator int( ) const { return avail。 }。 public: operator int () const {return time。 算法設(shè)計(jì)與分析 貪心算法 class JobNode { friend void Greedy(JobNode * , int, int)。在機(jī)器 3上，作業(yè) 5在 0～ 6時(shí)刻內(nèi)完成，作業(yè) 6在 6～ 8時(shí)刻內(nèi)完成，作業(yè) 3在 11～ 1 5時(shí)刻內(nèi)完成，作業(yè) 1在 15～ 17時(shí)刻內(nèi)完成。 ? 作業(yè) 4在 0到 16 時(shí)刻被調(diào)度到機(jī)器 1（ M1）上運(yùn)行，在這 16個(gè)時(shí)間單位中，機(jī)器 1完成了對作業(yè) 4的處理。三臺機(jī)器分別被編號為 M M2 和 M3。 7個(gè)獨(dú)立作業(yè) {1, 2, 3, 4, 5, 6, 7} 由 M1,M2和 M3來加工處理 各作業(yè)所需時(shí)間間分別為 {2, 14, 4, 16, 6, 5, 3}。 貪心近似算法 : 采用最長處理時(shí)間作業(yè)優(yōu)先的貪心策略 : 當(dāng) n≤m時(shí) , 只要將機(jī)器 i的 [0, ti]時(shí)間區(qū)間分配給作業(yè) i即可。 ? NP完全問題是一類判斷問題，也就是說，這類問題的答案為是或否。 多機(jī)調(diào)度問題 該問題為 NP完全問題 . ? 調(diào)度問題是著名的 NP復(fù)雜問題（ NP表示nondeterministic polynornial) 中的一種。 // N為起點(diǎn)城市 , v為當(dāng)前出發(fā)城市 / 4. for k:=1 to N1 do 5. { tour:= tour+(v,w) //(v,w)為從 v到其余城市代價(jià)中值最小的邊 / 6. cost:= cost+c(v,w) 7 v:=w} 8 tour:= tour+(v,N) 9 cost:= cost+c(v,N) print tour, cost } 算法的最壞時(shí)間復(fù)雜性為 O(n2) *該算法不能求的最優(yōu)解 . 算法設(shè)計(jì)與分析 貪心算法 該問題為 NP難問題 . 算法設(shè)計(jì)與分析 貪心算法 問題 :設(shè)有 n個(gè)獨(dú)立的作業(yè) {1, 2, … , n}, 由 m臺相同的機(jī)器進(jìn)行加工處理 . 作業(yè) i所需時(shí)間為 t i. 約定 :任何作業(yè)可以在任何一臺機(jī)器上加工處理 , 但未完工前不允許中斷處理 ,任何作業(yè)不能拆分成更小的子作業(yè) 。 // tour 紀(jì)錄路線 / 2. cost:=0。滿足約束條件的輸入稱為 可行解 ,它 是輸入的一個(gè)子集 .使優(yōu)化函數(shù)取得極值的可行解稱為 最優(yōu)解 . 算法設(shè)計(jì)與分析 貪心算法 例 1 *旅行商問題 (貨郎擔(dān)問題 ) 問題 : 設(shè)一個(gè)由 N個(gè)城市 v1,v2,…vn組成的網(wǎng)絡(luò) , ci,j 為從 vi 到 vj的代價(jià)不妨設(shè) ci,j = cj,i ,且 ci,i=? .一推銷員要從某城市出發(fā)經(jīng)過每城市一次且僅一次后返回出發(fā)地問如何選擇路線使代價(jià)最小 。 ? 所以 Kruska的時(shí)間是 O(eloge),適合求邊數(shù)較少的最小生成樹。 ? while循環(huán)中 ,DeleteMin需要 O(loge)時(shí)間因此關(guān)于優(yōu)先隊(duì)列所作運(yùn)算需時(shí)間 O(eloge)。由此可知， T具有最小耗費(fèi)。而且 U的耗費(fèi)不會因?yàn)檗D(zhuǎn)化而改變。 通過把 U變換為 T來證明 U與 T具有相同的耗費(fèi)，這種轉(zhuǎn)化可在 k 步內(nèi)完成。如果 T=U, 則 T就具有最小耗費(fèi)，那么不必再證明下去。由于 G具有有限棵生成樹，所以它至少具有一棵最小生成樹。也就是若 G開始時(shí)是連通的，算法不會終止于 E= 和 | T | n 1。而且在 Kruskal 算法中被拒絕（丟棄）的邊是那些會產(chǎn)生環(huán)路的邊。 證明 1： 令 G為任意加權(quán)無向圖（即 G是一個(gè)無向網(wǎng)絡(luò)）。 U. Union(a, b)。 int b = ()。 e。 x. weight = 5。 = 2。amp。 iht k = 0。 H. Initialize(E, e, e)。 ) 并查集的數(shù)學(xué)模型 ? 并查集的數(shù)學(xué)模型是若干不相交的動態(tài)集合的集合 S＝{A,B,C,...}，它支持以下的運(yùn)算： ? (1)INITIAL(A,x)：構(gòu)造一個(gè)取名為 A的集合，它只包含一個(gè)元素 x； ? (2)MERGE(A,B)：將集合 A和 B合并，其結(jié)果取名為 A或B； ? (3)FIND(x)：找出元素 x的所在集合，并返回該集合的名字。適合于描述這類問題的抽象數(shù)據(jù)類型稱為并查集 (給出各個(gè)元素之間的聯(lián)系，要求將這些元素分成幾個(gè)集合，每個(gè)集合中的元素直接或間接有聯(lián)系。這種問題的一個(gè)解決辦法是，在開始時(shí)，讓每個(gè)元素自成一個(gè)單元素集合，然后按一定順序?qū)儆谕唤M的元素所在的集合合并。 ? I n i t i a l i z e函數(shù)：使用數(shù)組 a中的元素對最大堆進(jìn)行初始化。在最小優(yōu)先隊(duì)列（ min priority q u e u e）中，查找操作用來搜索優(yōu)先權(quán)最小的元素，刪除操作用來刪除該元素；對于最大優(yōu)先隊(duì)列（ max priority queue），查找操作用來搜索優(yōu)先權(quán)最大的元素，刪除操作用來刪除該元素。 ? 可以利用堆數(shù)據(jù)結(jié)構(gòu)來高效地實(shí)現(xiàn)優(yōu)先隊(duì)列。 例 題 算法設(shè)計(jì)與分析 貪心算法 最小生成樹 e1(1) e2(6) e8(9) e6 (2) e9(4) e5(5) e4(7) e10(8) e11(3) e7(10) e3(11) 1) 以 G 中全部點(diǎn)為點(diǎn)作圖 2) 按權(quán)的大小次序依次添加 各邊 ,若出 現(xiàn)回路則忽略此邊 . 3) 加入 n1條邊后就得到最小 生成樹 . 1 2 5 3 7 求最小生成樹 (Kruscal) 最優(yōu)解 : (e1, e6, e11, e5, e4) 例 題 算法設(shè)計(jì)與分析 貪心算法 最小生成樹 優(yōu)先隊(duì)列 ? 定義：優(yōu)先隊(duì)列中元素出隊(duì)列的順序由元素的優(yōu)先級決定。直到只剩下一個(gè)連通分支為止。 }}} Prim算法 算法分析 : O(n2). 算法設(shè)計(jì)與分析 貪心算法 最小生成樹 算法思路 :首先將 G的 n個(gè)頂點(diǎn)看成 n個(gè)孤立的連通分支 , 將所有的邊按權(quán)從小到大排序 , 然后從第一條邊開始 , 依邊權(quán)遞增的順序查看每一條邊，并按下述方法連接兩個(gè)通分支： 當(dāng)查看到第 k條邊 (v,w)時(shí) , 如果端點(diǎn) u和 w分別是當(dāng)前兩個(gè)不同的連通分支 T1, T2中的頂點(diǎn)時(shí) ,就用邊 (u,w)將 TI和 T2連接成一個(gè)連通分支，然后繼續(xù)查看第 k+1條邊 。(!s[k])) lowcost[i] = c[j][k]。 k++) if ((c[j][k] lowcost[k])amp。 for(intk= 2。 closest[j] end}。} cout j 39。(!s[k])) min = lowcost[ k]。 k++) if ((lowcost[k] min)amp。 for (int k = 2。 i++){ Type min = inf。 } for (int i = 1。 closest[ i] = 1。i= n。 s[1] = true。 int closest[ maxim]。對于每個(gè) j ?VS， closest[j]是 j在 S中的鄰接頂點(diǎn)，它與 j在 S中的其他鄰接頂點(diǎn) k相比較有 c[j][closet[j]] ≤c[j][k]。 例 題 算法設(shè)計(jì)與分析 貪心算法 最小生成樹 問題：如何選取滿足條件 i?S, j?VS,且 c[i][j]最小的邊 (i, j), 成了算法難點(diǎn)問題。 S= S U{j}。 while (S!= V) { (i, j) = i ? S且 j?V S的最小權(quán)邊 。 void Prim(int n, Type * * c) { T= 216。 在 G的所有生成樹中 ,耗費(fèi)最小的生成樹稱為 G的最小生成樹 . 抽象描述 : 輸入 :任一連通生成子圖 (該子圖的邊集合 ) 可行解 :圖的生成樹 , 優(yōu)化函數(shù) :生成樹的各邊權(quán)值之和 最優(yōu)解 :使優(yōu)化函數(shù)達(dá)到最小的生成樹 . 4. 6 最小生成樹 算法設(shè)計(jì)與分析 貪心算法 最小生成樹 應(yīng)用領(lǐng)域與圖模型 算法思路 : 首先置 S={1}, T= 216。 E中每條邊 (v, w)的權(quán)為 c[v][w],若 G的一個(gè)子圖 G’是一棵包含 G的所有頂點(diǎn)的樹，則稱 G’為 G的生成樹。 if (newdistdist[j]){ dist[]]=newdist； prev[j]=u。(dist[j]temp)){ u=j； temp=dist[j]； } s[u]=true； for (int j=1； j=n。in； i++){ int temp=maxint； int u= v； for (int j = 1； j=n； j++) if ((!s[j])amp。 i++){ dist[i]=c[v][i]； s[i]=false； if(dist[i]= =maxint) prev[i]=0； else prev[i]=v 。令 S=SU{j}//更新 S (3) 修改從 v到集合 VS上任一頂點(diǎn) vk的當(dāng)前最短路徑長度 : 如果 dist[j]+c[j][k] dist[k] 則修改 dist[K]= dist[j]+c[j][k] //更新 dist和 prev (4) 重復(fù)操作 (2),(3)共 n1次 . 算法設(shè)計(jì)與分析 貪心算法 單源最短路徑 例 題 迭代 S vi d[ 2] d[ 3] d[ 4] d[ 5]初始 {1} 10 ? 30 100 1 { 1,2} 2 10 60 30 100 2 { 1,2 , 4} 4 10 50 30 90