【正文】 )是連通帶權(quán)圖， V={1,2,… ,n}。 構(gòu)造 G的最小生成樹的 Prim算法的 基本思想 是：首先置 S={1}，然后，只要 S是 V的真子集，就作如下的 貪心選擇： 選取滿足條件 i?S， j?VS，且 c[i][j]最小的邊，將頂點(diǎn) j添加到 S中。這個(gè)過程一直進(jìn)行到 S=V時(shí)為止。 在這個(gè)過程中選取到的所有邊恰好構(gòu)成 G的一棵 最小生成樹 2021年 11月 12日 90 實(shí)例： 2021年 11月 12日 91 在上述 Prim算法中，還應(yīng)當(dāng)考慮 如何有效地找出滿足條件 i?S,j?VS，且權(quán) c[i][j]最小的邊(i,j)。實(shí)現(xiàn)這個(gè)目的的較簡單的辦法是設(shè)置 2個(gè)數(shù)組 closest和 lowcost。 closest[j]表示 j在 S中的鄰接頂點(diǎn)； lowcost[j]表示 j與 S中的鄰接頂點(diǎn)最小的權(quán)值。 在 Prim算法執(zhí)行過程中，先找出 VS中使lowcost值最小的頂點(diǎn) j，然后根據(jù)數(shù)組 closest選取邊 (j,closest[j］ )，最后將 j添加到 S中，并對(duì)closest和 lowcost作必要的修改。 2021年 11月 12日 92 設(shè)圖 G中頂點(diǎn)的編號(hào)為 0～ n1， Prim算法如下： 1. 初始化兩個(gè)輔助數(shù)組 lowcost和 closest； 2. S={v}。 輸出頂點(diǎn) v。 //將頂點(diǎn) v加入生成樹中 3. 重復(fù)執(zhí)行下列操作 n1次 在 lowcost中選取最短邊 ， 取 closest中對(duì)應(yīng)的頂點(diǎn)序號(hào) j； 輸出頂點(diǎn) j和對(duì)應(yīng)的權(quán)值； S=S+{j}； 調(diào)整數(shù)組 lowcost和 closest ； Prim算法 2021年 11月 12日 93 算法描述： ? Templateclass Type void prim(int n,Type ** c) {Type lowcost[maxint]。 int closest[maxint]； bool s[maxint]。 s[1]=true。 for(int i=2。i=n。i++) {lowcost[i]=c[1][i]。 closest[i]=1。 s[i]=false。} 初始化兩個(gè)輔助數(shù)組 lowcost和closest 2021年 11月 12日 94 ? for (int i=1。in。i++) {Type min=inf。 int j=1。 for (int k=2。k=n。k++) if ((lowcost[k]min)amp。amp。(!s[k])) {min= lowcost[k]。 j=k。} coutj‘’closest [j]lowcost[j]end1。 s[j]=true。 // S=S+{j} for(int k=2。k=n。k++) if((c[j][k] lowcost[k]amp。amp。(!s[k])) {lowcost[k]= c[j][k]。 closest[k]=j。} //在 lowcost中選取最短邊，取 closest中對(duì)應(yīng)的頂點(diǎn)序號(hào) j； //輸出頂點(diǎn) j和對(duì)應(yīng)的權(quán)值 調(diào)整數(shù)組 lowcost和 closest 2021年 11月 12日 95 算法分析 設(shè)連通網(wǎng)中有 n個(gè)頂點(diǎn)，則第一個(gè)進(jìn)行初始化的循環(huán)語句需要執(zhí)行 n1次，第二個(gè)循環(huán)共執(zhí)行 n1次，內(nèi)嵌兩個(gè)循環(huán)，其一是在長度為 n的數(shù)組中求最小值，需要執(zhí)行 n1次，其二是調(diào)整輔助數(shù)組，需要執(zhí)行 n1次，所以， Prim算法的時(shí)間復(fù)雜度為 O(n2)。 2021年 11月 12日 96 Kruskal算法 ?克魯斯卡爾算法的基本思想為：為使生成樹上總的權(quán)值之和達(dá)到最小，則應(yīng)使每一條邊上的權(quán)值盡可能地小，自然應(yīng)從權(quán)值最小的邊選起，直至選出 n1 條互不構(gòu)成回路的權(quán)值最小邊為止。具體作法如下：首先構(gòu)造一個(gè)只含 n 個(gè)頂點(diǎn)的森林，然后依權(quán)值從小到大從連通網(wǎng)中選擇不使森林中產(chǎn)生回路的邊加入到森林中去，直至該森林變成一棵樹為止，這棵樹便是連通網(wǎng)的最小生成樹。 2021年 11月 12日 97 ?由于生成樹上不允許有回路，因此并非每一條居當(dāng)前權(quán)值最小的邊都可選，那么在算法中如何判別當(dāng)前權(quán)值最小邊的兩個(gè)頂點(diǎn)之間是否已經(jīng)連通？從生成樹的構(gòu)造過程可見，初始態(tài)為 n 個(gè)頂點(diǎn)分屬 n 棵樹，互不連通，每加入一條邊，就將兩棵樹合并為一棵樹，在同一棵樹上的兩個(gè)頂點(diǎn)之間自然相連通。由此判別當(dāng)前權(quán)值最小邊是否可取只要判別它的兩個(gè)頂點(diǎn)是否在同一棵樹上即可。 2021年 11月 12日 98 Kruskal算法 2021年 11月 12日 99 Kruskal算法 1. 初始化： U=V； TE={ }； 2. 循環(huán)直到 T中的連通分量個(gè)數(shù)為 1 在 E中尋找最短邊 (u， v)。 如果頂點(diǎn) u、 v位于 T的兩個(gè)不同連通分量，則 將邊 (u， v)并入 TE； 將這兩個(gè)連通分量合為一個(gè)； E=E{(u， v)}； Kruskal算法為了提高每次貪心選擇時(shí)查找最短邊的效率，可以先將圖 G中的邊按代價(jià)從小到大排序，則這個(gè)操作的時(shí)間復(fù)雜度為 O(eloge)，其中 e為無向連通網(wǎng)中邊的個(gè)數(shù)。對(duì)于兩個(gè)頂點(diǎn)是否屬于同一個(gè)連通分量，可以用并查集的操作將其時(shí)間性能提高到O(n)，所以， Kruskal算法的時(shí)間性能是 O(eloge)。 2021年 11月 12日 100 算法復(fù)雜性 ?當(dāng)圖的邊數(shù)為 e時(shí)， Kruskal算法所需的計(jì)算時(shí)間是 O(eloge)。當(dāng) e=?(n2)時(shí)， Kruskal算法比 Prim算法差，但當(dāng) e=o(n2)時(shí)， Kruskal算法卻比 Prim算法好得多。 2021年 11月 12日 101 ?有關(guān)說明： ?關(guān)于集合的一些基本運(yùn)算可用于實(shí)現(xiàn) Kruskal算法。 ?按權(quán)的遞增順序查看等價(jià)于對(duì)優(yōu)先隊(duì)列執(zhí)行deleteMin運(yùn)算?？梢杂枚褜?shí)現(xiàn)這個(gè)優(yōu)先隊(duì)列。 ?對(duì)一個(gè)由連通分支組成的集合不斷進(jìn)行修改，需要用到抽象數(shù)據(jù)類型并查集 UnionFind所支持的基本運(yùn)算。 2021年 11月 12日 102 提綱 一、貪心算法的基本思想 二、活動(dòng)安排問題 三、最優(yōu)裝載 四、哈夫曼編碼 五、單源最短路徑 六、最小生成樹 七、多機(jī)調(diào)度問題 2021年 11月 12日 103 問題定義 ?設(shè)有 n個(gè)獨(dú)立的作業(yè) {1, 2, …, n} ，由 m臺(tái)相同的機(jī)器{M1, M2, …, M m}進(jìn)行加工處理，作業(yè) i所需的處理時(shí)間為 ti（ 1≤i≤n）， 每個(gè)作業(yè)均可在任何一臺(tái)機(jī)器上加工處理，但不可間斷、拆分。 ?多機(jī)調(diào)度問題要求給出一種作業(yè)調(diào)度方案，使所給的 n個(gè)作業(yè)在盡可能短的時(shí)間內(nèi)由 m臺(tái)機(jī)器加工處理完成。 這個(gè)問題是 NP完全問題 ，到目前為止還沒有有效的解法。對(duì)于這一類問題 ,用 貪心選擇策略 有時(shí)可以設(shè)計(jì)出較好的近似算法。 2021年 11月 12日 104 貪心選擇 ?貪心法求解多機(jī)調(diào)度問題的貪心策略是 最長處理時(shí)間 作業(yè)優(yōu)先，即把處理時(shí)間最長的作業(yè)分配給最先空閑的機(jī)器，這樣可以保證處理時(shí)間長的作業(yè)優(yōu)先處理，從而在整體上獲得盡可能短的處理時(shí)間。 ?按照最長處理時(shí)間作業(yè)優(yōu)先的貪心策略，當(dāng) m≥n時(shí)，只要將機(jī)器 i的 [0, ti)時(shí)間區(qū)間分配給作業(yè) i即可；當(dāng) m＜ n時(shí)，首先將 n個(gè)作業(yè)依其所需的處理時(shí)間從大到小排序，然后依此順序?qū)⒆鳂I(yè)分配給最先空閑的處理機(jī)。 2021年 11月 12日 105 貪心算法 例：設(shè) 7個(gè)獨(dú)立作業(yè) {1, 2, 3, 4, 5, 6, 7}由 3臺(tái)機(jī)器 {M1, M2, M3}加工處理，各作業(yè)所需的處理時(shí)間分別為 {2, 14, 4, 16, 6, 5, 3}。貪心法產(chǎn)生的作業(yè)調(diào)度如下： M1 M2 M3 時(shí)間 分配 作業(yè) 5 作業(yè) 6 作業(yè) 3 作業(yè) 1 作業(yè) 2 作業(yè) 7 作業(yè) 4 17 16 圖：三臺(tái)機(jī)器的調(diào)度問題示例 6 5 4 2021年 11月 12日 106 貪心算法 1．將數(shù)組 t[n]由大到小排序，對(duì)應(yīng)的作業(yè)序號(hào)存儲(chǔ)在數(shù)組 p[n]中； 2．將數(shù)組 d[m]初始化為 0； //m個(gè)機(jī)器初始時(shí)都空閑 3． for (i=1。 i=m。 i++) M[i]={p[i]}。 //將 m個(gè)作業(yè)分配給 m個(gè)機(jī)器 d[i]=t[i]。 4. for (i=m+1。 i=n。 i++) j=數(shù)組 d[m]中最小值對(duì)應(yīng)的下標(biāo)； //j為最先空閑的機(jī)器序號(hào) M[j]=M[j]+{p[i]}。 //將作業(yè) i分配給最先空閑的機(jī)器 j d[j]=d[j]+t[i]。 //機(jī)器 j將在 d[j]后空閑 2021年 11月 12日 107 算法復(fù)雜性分析 當(dāng) 時(shí)，只要將機(jī)器 i的 [0, ti]時(shí)間區(qū)間分配給作業(yè) i即可，算法只需要 O(m)時(shí)間。 mn ?當(dāng) 時(shí)，排序需要時(shí)間 O(nlogn)。 操作“數(shù)組 d[m]中最小值對(duì)應(yīng)的下標(biāo)” 采用堆操作，第二個(gè) for循環(huán)需要時(shí)間 O(nlogm)。算法總的需要時(shí)間為：O(nlogn)+O(nlogm)。 mn ?通常情況下 mn。因此 算法需要時(shí)間為： ??????mnnnOmnOnT)l og()1()(