圖與網(wǎng)路分析報(bào)告探討-資料下載頁(yè)
2025-01-16 08:00本頁(yè)面
【正文】 2) 次比較，最多 2(n ? 2) 次賦值 – i=k k(n ? k) 次比較，最多 k(n ? k) 次賦值 )1(31)12()1(622 )1(2)(2 211???????????nnnnnnnnknkn? Dijkstra算法 – i=1 n ? 1 次臨時(shí)標(biāo)記，永久標(biāo)記 n ? 1 次比較和賦值 – i=2 n ? 2 次臨時(shí)標(biāo)記，永久標(biāo)記 n ? 2 次比較和賦值 – i=k n ? k 次臨時(shí)標(biāo)記，永久標(biāo)記 n ? k 次比較和賦值 )1(2)(411??????nnknnk38 Prim算法的改進(jìn) 增加一個(gè)輔助記錄型數(shù)組，用以記錄當(dāng)前 V 中各節(jié)點(diǎn)到 V 的最小邊， minedge[i].cost 記錄該邊的權(quán)值， minedge[i].vex 記錄該邊 V 中的頂點(diǎn)。若 minedge[i].cost0 則表明 i 點(diǎn)進(jìn)入集合 V for i:=2 to n do begin minedge[i].vex:=1。 minedge[i].cost:=w[1,i] end。 for i:=1 to n ? 1 do begin mi:=maxint。 for j:=2 to n do if (minedge[j].cost0) and (minedge[j].costmi) then begin k:=j。 mi:=minedge[j].cost end。 minedge[k].cost:= ? minedge[k].cost。 {找到 k，將 k 加入集合 V} for j:=2 to n do if (w[k,j]minedge[j].cost) then begin minedge[j].cost:=w[k,j]。 minedge[j].vex:=k。 end。 end。 { 該算法復(fù)雜度 約為 5n(n1) } 39 匹配問(wèn)題 (Matching Problem) 定義 ：圖中一組邊的集合，當(dāng)圖中的每個(gè)節(jié)點(diǎn)最多只與該集合中的一條邊相關(guān)聯(lián)，則該邊集就成為 匹配 。 兩部圖 的匹配問(wèn)題 ? 圖中的節(jié)點(diǎn)可分為兩個(gè)集合， X, Y， X 與 Y 之間有邊相連，但 X 內(nèi)部和 Y 內(nèi)部無(wú)關(guān)聯(lián)邊，稱為兩部圖 – 運(yùn)輸問(wèn)題實(shí)際上是兩部圖的最小費(fèi)用最大流問(wèn)題 – 任務(wù)分配問(wèn)題實(shí)際上是兩部圖的最小完全匹配問(wèn)題 非 兩部圖 的匹配問(wèn)題 (1) 最大基數(shù)匹配 (maximum cardinality matching) (2) 最大權(quán)匹配 (maximum weight matching) (3) 最小完全匹配 (minimum weight perfect matching) (4) 最優(yōu)分?jǐn)?shù)匹配 (optimal fractional matching) 40 任務(wù)分配問(wèn)題、匹配問(wèn)題和 TSP的關(guān)系 ? 三個(gè)問(wèn)題都有一個(gè) n?n 正權(quán)值的邊權(quán)矩陣 ? 三個(gè)問(wèn)題的解都可以用代數(shù)置換 (permutation)表示 ????????????????1542354321 5432154321 iiiii? i1, i2, i3, i4, i5 是 1, 2, 3, 4, 5 的任一排列，表示元素位置的交換 ? 輪換，全輪換，對(duì)換 ? TSP的解必須是一個(gè)全輪換 ? 任務(wù)分配問(wèn)題的解可以是任一個(gè)置換 ? 匹配的解必須是 n/2 個(gè)對(duì)換 ? 任務(wù)分配問(wèn)題是匹配問(wèn)題的松弛問(wèn)題 41 選址問(wèn)題 ? 使所選地址到最遠(yuǎn)的服務(wù)對(duì)象距離盡可能小 ——中心點(diǎn) ? 使所選地址到各服務(wù)對(duì)象的總距離最小 ——中位點(diǎn) ? 有時(shí)間限制的多用中心點(diǎn)，如鄉(xiāng)郵局 ? 總資源約束的多用中位點(diǎn)，如電話交換局 各點(diǎn)之間的距離 ? 節(jié)點(diǎn)到節(jié)點(diǎn)間的最短距離，稱為節(jié)點(diǎn) —節(jié)點(diǎn)距離 ? 邊上某點(diǎn)到節(jié)點(diǎn)的最短距離，稱為點(diǎn) —節(jié)點(diǎn)距離 ? 節(jié)點(diǎn)到某邊上最遠(yuǎn)一點(diǎn)的距離，稱為節(jié)點(diǎn) —邊距離 ? 邊上一點(diǎn)到另一邊上最遠(yuǎn)點(diǎn)的距離，稱為點(diǎn) —邊距離 1 62 57 3 4211113242 邊上某點(diǎn)到節(jié)點(diǎn)的最短距離 – dij 代表 vi 與 vj 間的最短距離， ars 代表邊 (r, s)的邊長(zhǎng)，令 h 為邊 (r, s)上一點(diǎn)的 百分位 ， 0? h? 1 – 邊上對(duì)應(yīng) h 的一點(diǎn)到 vj 的最短距離為 d[h(r, s), j]=min[h?ars+drj, (1?h)?ars+dsj] 節(jié)點(diǎn)到某邊上最遠(yuǎn)一點(diǎn)的距離 – 指定節(jié)點(diǎn) j，它到邊 (r, s)上對(duì)應(yīng) h百分位點(diǎn)有兩條路，最遠(yuǎn)點(diǎn)必使兩條路一樣長(zhǎng)，故有 d[j, (r, s)]=[djr+ djs+ ars] 邊上指定一點(diǎn)到其他邊上最遠(yuǎn)點(diǎn)的距離 – h 是邊 (r, s)上指定的百分位點(diǎn)，另一邊為 (u, t) d[h(r, s), (u, t)]=min[h?ars+d[r, (u, t)], (1?h)?ars+d [s, (u, t)] ] 43 中心的選擇 ? 中心：以節(jié)點(diǎn) —節(jié)點(diǎn)距離為基礎(chǔ)，大中取小 (max min) ? 一般中心：以節(jié)點(diǎn) —邊距離為基礎(chǔ)，大中取小 ? 絕對(duì)中心：以點(diǎn) —節(jié)點(diǎn)距離為基礎(chǔ)，大中取小 ? 一般絕對(duì)中心：以點(diǎn) —邊距離為基礎(chǔ)，大中取小 ? 左圖的中心是 v1；而三個(gè)節(jié)點(diǎn)都是一般中心 ? 類似也有四種中位點(diǎn)： – 中位點(diǎn) – 一般中位點(diǎn) – 絕對(duì)中位點(diǎn) – 一般絕對(duì)中位點(diǎn) 332 125 4214332152744 例 ~ m a x m i n ? m i n0 2 3 4 4 4 ? 132 0 1 5 2 5 10 ?3 1 0 6 3 6 134 5 6 0 3 6 184 2 3 3 0 4 ? 12編號(hào) 1 23 4 5 6 7邊 ( i , j ) ( 1 , 2 ) ( 1 , 4 ) ( 2 , 3 ) ( 2 , 5 ) ( 3 , 5 ) ( 4 , 5 )邊長(zhǎng) 2 4 1 2 5 3m a x m i n ? m i n2 4 3 4 6 5 . 5 6 2 4 . 52 5 . 5 1 2 4 5 5 . 5 ? 1 9 . 5 ?3 6 . 5 1 3 4 6 6 . 5 2 3 . 55 . 5 4 6 5 7 3 7 3 0 . 54 5 . 5 3 2 4 3 5 . 5 ? 2 1 . 5中心 一般中心 中位點(diǎn) 一般中位點(diǎn) 45 演講完畢，謝謝觀看！
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1