【文章內(nèi)容簡介】 Prim 算法的基本思想是： 設(shè)圖 G 頂點(diǎn)集合為 U，首先任意選擇圖 G 中的一點(diǎn)作為起始點(diǎn) a，將該點(diǎn)加入集合 V，再從集 合 UV中找到另一點(diǎn) b 使得點(diǎn) b 到 V 中任意一點(diǎn)的權(quán)值最小，此時(shí)將 b 點(diǎn)也加入集合 V；以此類推，現(xiàn)在的集合 V={a， b}，再從集合 UV 中找到另一點(diǎn) c 使得點(diǎn) c 到 V 中任意一點(diǎn)的權(quán)值最小，此時(shí)將 c 點(diǎn)加入集合 V，直至所有頂點(diǎn)全部被加入 V，此時(shí)就構(gòu)建出了一顆 MST。 普里姆算法： procedure PRIM(E,COST,n,T,mincost) //E 是 G 的邊集。 COST(n,n)是 n 結(jié)點(diǎn)圖 G 的成本鄰接矩陣 ， 矩陣元素 COST(i,j)是一個(gè)正實(shí)數(shù) ， 如果不存在邊 (i,j)， 則為 ＋∞ 。計(jì)算一棵最小生成樹并把它作為一個(gè)集合存放到數(shù)組 T(1:n1,2)中 (T(i,1),T(i,2))是最小成本生成樹的一條邊。最小成本生成樹的總成本最后賦給mincost。 NEAR(j)是樹中使得 COST(j,NEAR(j))是對(duì) NEAR(j)所有選擇中的最小值 // real COST(n,n), mincost integer NEAR(n), n, i, j,k, l, T(1:n1,2) (k,l)←具有最小成本的邊 mincost← COST(k,l) (T(l,1),T(l,2)) ← (k,l) for i← 1 to n do //將 NEAR 置初值 // if COST(i,l) ＜ COST(i,k) then NEAR(i)← l else NEAR(i) ← k endif repeat NEAR(k)← NEAR(l)← 0 for i← 2 to n1 do //找 T 的其余 n2 條邊 // 設(shè) j 是 NEAR(j)≠ 0 且 COST(j,NEAR(j))最小的下標(biāo) (T(i,1),T(i,2))← (j,NEAR(j)) mincost← mincost+COST(j,NEAR(j)) NEAR(j)← 0 for k← 1 to n do //修改 NEAR// if NEAR(k)≠ 0 and COST(k,NEAR(k))＞ COST(k,j) then NEAR(k)← j endif repeat iiwx? iipx? 計(jì)算機(jī)算法設(shè)計(jì)與分析 11 / 24 repeat if mincost≥∞ then print(‘ no spanning tree’ ) endif end PRIM 計(jì)算復(fù)雜性： O(n2) 四、 單源點(diǎn)最短路徑 即一直的一個(gè) n 結(jié)點(diǎn)有向圖 G=（ V,E）和邊的權(quán)函數(shù) C(e)，求由 G 中某指定結(jié)點(diǎn) V0到其他各個(gè)點(diǎn)的最短路徑。 生成最短路徑的貪心算法： Procedure SHORTEST (V,COST,DIST,n) //G 是一個(gè)有 n 個(gè)結(jié)點(diǎn)的有向圖，它由其鄰接矩陣 COST（ n， n）表示， DIST（ n， n）表示，DIST（ j）被置以結(jié)點(diǎn) V 到結(jié)點(diǎn) j 的最短路徑的長度，這里 1j≤n。DIST(v)被置為 0// Boolean S(1:n)。 real COST(1:n,1:n),DIST(1:n) Integer u,v,n,num,i,w For i←1 to n do S(i) ←0。 DIST(i) ←COST(v,i) Repeat S(v) ←1。 DIST(v) ←0 For sum←2 to n1 do S(u) ←1 For 所有 S(w)=0 的結(jié)點(diǎn) w do DIST(w) ←min(DIST(w), DIST(w)+ COST(u,w)) Repeat Repeat End 生成最短路徑的貪心算法 的計(jì)算時(shí)間是 O（ n2）。 計(jì)算機(jī)算法設(shè)計(jì)與分析 12 / 24 第四章 動(dòng)態(tài)規(guī)劃 一、 優(yōu)化問題 分類 (1) 線性優(yōu)化與非線性優(yōu)化 (2) 約束優(yōu)化和無約束優(yōu)化 (3) 確定性優(yōu)化和隨意性優(yōu)化 (4) 動(dòng)態(tài)優(yōu)化和靜態(tài)優(yōu)化 (5) 單目標(biāo)優(yōu)化與多目標(biāo)優(yōu)化（最值與平衡解） 優(yōu)化問題求解難度上 可分為 (1) 函數(shù)優(yōu)化：目標(biāo)函數(shù) (2) 參數(shù)優(yōu)化 (3) 模型優(yōu)化：模型是什么樣的，建立模型 二、 一般 原理 用來求解優(yōu)化問題。特點(diǎn)： (1) 多階段決策 (2) 滿足最優(yōu)解原理：不論初始決策是什么樣的，后面的決策相對(duì)初始決策產(chǎn)生一個(gè)最優(yōu)的決策。 三、 多段圖 最優(yōu)性原理對(duì)多段圖問題成立 ， 在多段圖中求從 s 到 t 的一條最小成本的路徑，可以看作是在 k2 個(gè)段作出某種決策的結(jié)果 ，其中 第 i（ 1≤ i≤ k2） 次決策決定 Vi+1中的哪個(gè)結(jié)點(diǎn)在這條路徑上 。 令源點(diǎn) s 編號(hào)為 1，然后依次對(duì) V V3… Vk1 中的結(jié)點(diǎn)編號(hào)，匯點(diǎn) t 編號(hào)為n。 如下圖所示： 圖 41 一個(gè) 5 段圖 由前向后推 設(shè) BP(i, j)是一條從源點(diǎn) s 到 Vi 中的結(jié)點(diǎn) j 的最小成本路徑， BCOST(I ,j)是這條路徑的成本則 向后遞推式 為 對(duì)圖 中 所示的多段圖采用向后策略遞推： 1( , )( , ) m in { ( 1 , ) ( , ) }ilvl j EB C O S T i j B C O S T i l c l j?? ?? ? ? 計(jì)算機(jī)算法設(shè)計(jì)與分析 13 / 24 第 2 段 BCOST(2,2) = 9 BCOST(2,3) = 7 BCOST(2,4) = 3 BCOST(2,5) = 2 第 3 段 BCOST(3,6) = min{BCOST(2,2)+4,BCOST(2,3)+2} = 9 BCOST(3,7) = min{BCOST(2,2)+2,BCOST(2,3)+7, BCOST(2,5)+11} = 11 BCOST(3,8) = min{BCOST(2,4)+11, BCOST(2,5)+8} = 10 第 4 段 BCOST(4,9) = min{BCOST(3,6)+6,BCOST(3,7)+4} = 15 BCOST(4,10) = min{BCOST(3,6)+5,BCOST(3,7)+3, BCOST(3,8)+5} = 14 BCOST(4,11) = min{BCOST(3,8)+6} = 16 第 5 段 BCOST(5,12) = min{BCOST(4,9)+4,BCOST(4,10)+2, BCOST(4,11)+5}= 16 S 到 t 的最小成本路徑的成本 ＝ 16 最小路徑的求取 ： 記 BD(i, j)＝每一 COST(i, j)的決策 ， 即使 COST(i1, l)+c(l, j)取得最小值的 l 值。 例： BD(3,6) = 3， BD(3,7)= 2， BD(3,8) = 5， BD(4,9) = 6， BD(4,10) = 7， BD(4,11) = 8， BD(5,12) = 10 根據(jù) D(5,12)的決策值向前遞推求取最小成本路徑： v4 = BD(5,12)=10， v3 = BD(4,BD(5,12)) = 7， v2 = BD(3,BD(4,BD(5,12))) = BD(3,7) = 2， 故由 s 到 t 的最小成本路徑是： 1→ 2→ 7→ 10→12 由后向前推 設(shè) P(i,j)是一條從 Vi 中的結(jié)點(diǎn) j 到匯點(diǎn) t 的最小成本路徑， COST(i,j)是這條路徑的成本。設(shè) i 表示 Vi， j 表示 Vi 中的結(jié)點(diǎn)號(hào)向前遞推式 為 對(duì)圖中所示的多段圖采用向前策略遞推： 第 4 段 COST(4,9) = c(9,12) = 4 COST(4,10) = c(10,12) = 2 COST(4,11) = c(11,12) = 5 第 3 段 COST(3,6) = min{6+COST(4,9),5+COST(4,10)} = 7 COST(3,7) = min{4+COST(4,9),3+COST(4,10)} = 5 COST(3,8) = min{5+COST(4,10),6+COST(4,11)} = 7 第 2 段 COST(2,2) = min{4+COST(3,6) , 2+COST(3,7), 1+COST(3,8)} = 7 COST(2,3) = 9 COST(2,4) = 18 COST(2,5) = 15 第 1 段 COST(1,1) = min{9+COST(2,2),7+COST(2,3), 3+COST(2,4),2+COST(2,5)} = 16 S 到 t 的最小成本路徑的成本 ＝ 16 最小路徑的求取 ： 記 D(i,j)＝每一 COST(i,j)的決策即，使 c(j,l)+COST(i+1,l)取得最小值的 l 值。 例： D(3,6) = 10, D(3,7)= 10 ， D(3,8) = 10， D(2,2) = 7， D(2,3) = 6， D(2,4) = 8， D(2,5) = 8，D(1,1) = 2， 根據(jù) D(1,1)的決策值向后遞推求取最小成本路徑： v2=D(1,1)=2， v3 = D(2,D