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

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

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

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

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

5、kstras algorithm以及關于有向無回路圖的最短路徑算法中，對每條邊執(zhí)行情況一次松弛操作。而在Bellman-Ford算法中，對每條邊要執(zhí)行多次松弛操作。73Bellman-Ford algorithm思想：運用松弛技術，對每一個結點vV，逐步減少從源s到v的最短路徑的權的估計值dv，直至其達到實際最短路徑的權(s,v)。算法返回布爾值TURE當且僅當圖中沒有源結點可達的負權回路。優(yōu)點：解決更一般情況的單源最短路徑問題。且邊的權值可以為負，可檢測出圖中是否存在一個從源結點可達的負權回路，如果存在負權回路則無解；否則將產生最短路徑及其權。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引理 設為帶權有向圖，其源點為s，權函數(shù)為w：EàR，并且假定G中不包含從s點可達的負權回路。那么BELLMAN-FORD第24行循環(huán)的|V|-1次迭代后，對任何s可達的頂點v，有dv=(s,v)。推論：設G=（V，E）為帶權有向圖，源頂點為s，加

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

8、一個結點集合S，從源點s到集合中結點的最終最短路徑的權均已確定。算法反復挑選出其最短路徑估計為最小的結點uV-S，把u插入到集合S中，并對離開u的所有邊進行松弛。Dijkstra算法總是在集合V-S中選擇“最近”的結點插入集合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 每個頂點v屬于Adju            do Relax(u,v,w)Dijkstra執(zhí)行過程：定理7.1：Dijkstra算法的正確性證明證明：將證明對每一結點u屬于V，當u被插入集合S時有duQ(s,u)成立，且此后該等式一直保持成立。設u為插入集合S中的第一個滿足du!=Q(s,u)的結點?？芍猽!=s，可知u被插入集合S前S!=空。從s到u必存在某條通路，否則du=Q(s,u)inf，與du!=Q(

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