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