精品文檔多階段決策過程multistepdecisionprocess是指這樣一類特殊的

1、第七部分 最短路徑（Shortest-paths）71 問題描述在一個帶權(quán)的無向或者有向圖中，如果從圖中某頂點(diǎn)（稱源點(diǎn)）到達(dá)另頂點(diǎn)（稱為終點(diǎn)）的路徑可能不止一條，如何找到一條路徑使得沿此路徑上各邊上的權(quán)值總和達(dá)到最小。實(shí)際應(yīng)用中，有把交通運(yùn)輸網(wǎng)絡(luò)作為一個圖，圖中頂點(diǎn)表示城市，圖中各邊表示城市之間的交通運(yùn)輸線。邊上的權(quán)值就根據(jù)具體需要，可以用各種代價表示，比如路程，運(yùn)費(fèi)，時間。同時，可以用有向圖表示往返代價的不一致。計(jì)算機(jī)網(wǎng)絡(luò)中，把網(wǎng)絡(luò)結(jié)構(gòu)看成帶權(quán)圖，路由選擇的時候采用的固定路由算法其中有使用最短路徑算法。此外，最短路徑算法還應(yīng)用于電子導(dǎo)航中，根據(jù)已知地理網(wǎng)絡(luò)，得出合適的航線；應(yīng)用于電力、通訊等

2、各種管網(wǎng)、管線的布局設(shè)計(jì)，城市規(guī)劃等等。由于應(yīng)用的需要，最短路徑算法問題成為計(jì)算機(jī)科學(xué)、運(yùn)籌學(xué)、地理信息系統(tǒng)和交通誘導(dǎo)、導(dǎo)航系統(tǒng)等領(lǐng)域研究的一個熱點(diǎn)。在最短路徑問題中，給出的是一個帶權(quán)有向圖G(V, E)，加權(quán)函數(shù)w:EàR為從邊到實(shí)型權(quán)值的映射。路徑p=(v0,v1,v2,vk)的權(quán)是指組成邊的所有權(quán)值之和：w(p)=w(vi-1,vi) i=1k;定義從u到v間的最短路徑的權(quán)為：從頂點(diǎn)u到v的最短路徑定義為權(quán)w(p)=&(u,v)的任何路徑.不帶權(quán)圖的最短路徑問題是一個特例，可將圖視為沒條邊的權(quán)值均為1的帶權(quán)圖。兩種最常見的最短路徑問題：l 從某個源點(diǎn)到其余各頂點(diǎn)的最短路

3、徑l 每對頂點(diǎn)間的最短路徑72松弛技術(shù)Relaxation在后面介紹的幾個算法中都用到了松弛技術(shù)，現(xiàn)在就來看看松弛技術(shù)。對于每個頂點(diǎn)vV，都設(shè)置一個屬性dv，用來描述從源點(diǎn)s到v的最短路徑上權(quán)值的上界，稱為最短路徑估計(jì)（shortest-path estimate）。我們用下面的(V)時間的過程來對最短路徑估計(jì)和前趨進(jìn)行初始化。INITIALIZE-SINGLE-SOURCE(G,s)1 for each vertex vVG2 do dv3 vNIL4 ds0經(jīng)過初始化以后，對所有vV，v=NIL，對vV-s，有ds=0以及dv=。在松弛一條邊(u,v)的過程中，要測試是否可以通過u，對迄今

4、找到的v的最短路徑進(jìn)行改進(jìn)；如果可以改進(jìn)的話，則更新dv和v。一次松弛操作可以減小最短路徑估計(jì)的值dv，并更新v的前趨域v。下面的偽代碼對邊(u,v)進(jìn)行了一步松弛操作。RELAX(u, v, w)1 if(dv>du+w(u,v)2 then dvdu+w(u,v)3 vu在Bellman-Ford algorithm和Dijkstras algorithm都會調(diào)用到INITIALIZE-SINGLE-SOURCE(G,s)，然后重復(fù)對邊進(jìn)行松弛的過程。另外松弛是改變最短路徑和前趨的唯一方式，在兩個算法之間的區(qū)別在于對每條邊進(jìn)行的松弛操作的次數(shù)，以及對邊執(zhí)行松弛操作的次序不同。在Dij

5、kstras algorithm以及關(guān)于有向無回路圖的最短路徑算法中，對每條邊執(zhí)行情況一次松弛操作。而在Bellman-Ford算法中，對每條邊要執(zhí)行多次松弛操作。73Bellman-Ford algorithm思想：運(yùn)用松弛技術(shù)，對每一個結(jié)點(diǎn)vV，逐步減少從源s到v的最短路徑的權(quán)的估計(jì)值dv，直至其達(dá)到實(shí)際最短路徑的權(quán)(s,v)。算法返回布爾值TURE當(dāng)且僅當(dāng)圖中沒有源結(jié)點(diǎn)可達(dá)的負(fù)權(quán)回路。優(yōu)點(diǎn)：解決更一般情況的單源最短路徑問題。且邊的權(quán)值可以為負(fù)，可檢測出圖中是否存在一個從源結(jié)點(diǎn)可達(dá)的負(fù)權(quán)回路，如果存在負(fù)權(quán)回路則無解；否則將產(chǎn)生最短路徑及其權(quán)。BELLMAN-FORD（G,w,s）1 INI

6、TIALIZE-SINGLE-SOURCE(G,s)2 for iß1 to |VG|-13 do for each edge(u,v)EG4 do RELAX(u,v,w)5 for each edge(u,v) EG6 do if dv>du+w(u,v)7 then return false;8 return true引理 設(shè)為帶權(quán)有向圖，其源點(diǎn)為s，權(quán)函數(shù)為w：EàR，并且假定G中不包含從s點(diǎn)可達(dá)的負(fù)權(quán)回路。那么BELLMAN-FORD第24行循環(huán)的|V|-1次迭代后，對任何s可達(dá)的頂點(diǎn)v，有dv=(s,v)。推論：設(shè)G=（V，E）為帶權(quán)有向圖，源頂點(diǎn)為s，加

7、權(quán)函數(shù)為w:EàR，對每個頂點(diǎn)v(vV)，從s到v存在一條通路，當(dāng)且僅當(dāng)對G運(yùn)行BELLMAN-FORD（G,w,s）算法，算法終止時，有dv<。定理：設(shè)G=（V，E）為帶權(quán)有向圖，源頂點(diǎn)為s，加權(quán)函數(shù)為w:EàR，對該圖運(yùn)行BELLMAN-FORD（G,w,s）算法，若G不包含s可達(dá)的負(fù)權(quán)回路，則算法返回TRUE，對所有頂點(diǎn)v(vV)，有dv=(s,v)成立。前趨子圖G是以s為根的最短路徑樹。如果G包含從s可達(dá)的負(fù)權(quán)回路，則算法返回FALSE。74 Dijkstras algorithm目的：解決有向加權(quán)圖的最短路徑問題。條件：該圖的所有邊的權(quán)值非負(fù)。算法思想：設(shè)置

8、一個結(jié)點(diǎn)集合S，從源點(diǎn)s到集合中結(jié)點(diǎn)的最終最短路徑的權(quán)均已確定。算法反復(fù)挑選出其最短路徑估計(jì)為最小的結(jié)點(diǎn)uV-S，把u插入到集合S中，并對離開u的所有邊進(jìn)行松弛。Dijkstra算法總是在集合V-S中選擇“最近”的結(jié)點(diǎn)插入集合S中，它使用了貪心策略。Dijkstra(G,w,s)Init-Singlesource(G,s)s = emptyQ = VGwhile ( Q != empty)    do u = extract-min(Q)        s = s and u 

9、0;      for 每個頂點(diǎn)v屬于Adju            do Relax(u,v,w)Dijkstra執(zhí)行過程：定理7.1：Dijkstra算法的正確性證明證明：將證明對每一結(jié)點(diǎn)u屬于V，當(dāng)u被插入集合S時有duQ(s,u)成立，且此后該等式一直保持成立。設(shè)u為插入集合S中的第一個滿足du!=Q(s,u)的結(jié)點(diǎn)?？芍猽!=s，可知u被插入集合S前S!=空。從s到u必存在某條通路，否則du=Q(s,u)inf，與du!=Q(

10、s,u)矛盾。因?yàn)榇嬖谝粭l通路，所以存在一條最短路p。路徑p聯(lián)結(jié)集合S中的結(jié)點(diǎn)S到V-S的結(jié)點(diǎn)u?？疾煅芈窂絧的第一個屬于V-S的結(jié)點(diǎn)y。設(shè)x屬于V是y的先輩。路徑p可以分解為sp->x和yp2->u。（若第一個點(diǎn)為u，則du=Q(s,u)，已得證）因?yàn)閟到u的最短路徑上y出現(xiàn)在y之前且所有邊的權(quán)均為非負(fù)，我們有Q(s,y)<=Q(s,u),因而dy = Q(s,y) <= Q(s,u) <=du,但因?yàn)樵诘?行選擇u時結(jié)點(diǎn)u和y都屬于V-S，所以有du<=dy。因此du=dy。最后得出結(jié)論du=Q(s,u)，這與我們對u的假設(shè)矛盾。Dijkstra算法效率：若用線性數(shù)組實(shí)現(xiàn)優(yōu)先隊(duì)列：每次Extract_Min為O(v)，存在V次，則為O(v2)。for中有E次迭代。所以整個算法運(yùn)行時間O(V2)。稀疏圖用二叉堆比較合適。Extract_Min需要O(lgv)，建立需要O(V)。更改權(quán)值用Decrease_key?？倳r間為O(V+E)lgV)。如果用斐波那契堆可以進(jìn)一步提高效率至O(VlgV+E)。75 總結(jié) 根據(jù)各種教材介紹，還有幾種經(jīng)典的算法，所有頂點(diǎn)之間的最短路徑（Floyed算法）、特定兩個頂點(diǎn)之間的最短路徑（A*算法）等。在上述介紹的算法，當(dāng)減低問題