多階段決策過程multistepdecisionpr

1、多階段決策過程mu Itistepdec i s i onpRevised as of 23 November 2020第七部分最短路徑(Shortest-paths)7. 1問題描述在一個(gè)帶權(quán)的無向或者有向圖中，如果從圖中某頂點(diǎn)(稱源點(diǎn))到達(dá)另頂 點(diǎn)(稱為終點(diǎn))的路徑可能不止一條，如何找到一條路徑使得沿此路徑上各邊 上的權(quán)值總和達(dá)到最小。實(shí)際應(yīng)用中，有把交通運(yùn)輸網(wǎng)絡(luò)作為一個(gè)圖，圖中頂 點(diǎn)表示城市，圖中各邊表示城市之間的交通運(yùn)輸線。邊上的權(quán)值就根據(jù)具體需 要，可以用各種代價(jià)表示，比如路程，運(yùn)費(fèi)，時(shí)間。同時(shí)，可以用有向圖表示 往返代價(jià)的不一致。計(jì)算機(jī)網(wǎng)絡(luò)中，把網(wǎng)絡(luò)結(jié)構(gòu)看成帶權(quán)圖，路由選擇的時(shí)候

2、釆用的固定路山算法其中有使用最短路徑算法。此外，最短路徑算法還應(yīng)用于 電子導(dǎo)航中，根據(jù)已知地理網(wǎng)絡(luò)，得岀合適的航線；應(yīng)用于電力、通訊等各種 管網(wǎng)、管線的布局設(shè)訃，城市規(guī)劃等等。由于應(yīng)用的需要，最短路徑算法問題 成為訃算機(jī)科學(xué)、運(yùn)籌學(xué)、地理信息系統(tǒng)和交通誘導(dǎo)、導(dǎo)航系統(tǒng)等領(lǐng)域研究的 個(gè)熱點(diǎn)。在最短路徑問題中，給出的是一個(gè)帶權(quán)有向圖G=(K E),加權(quán)函數(shù)w:ER 為從邊到實(shí)型權(quán)值的映射。路徑P=(vO,vl, v2,vk)的權(quán)是指組成邊的所有權(quán) 值之和：w(p) = Ew(vi-l, vi) i=lk;定義從U到V間的最短路徑的權(quán)為：5(“ I，)_ minMp):u 若從至lj存在一條通路sot

3、herelse從頂點(diǎn)U到V的最短路徑定義為權(quán)w(p)=&(u,v)的任何路徑.不帶權(quán)圖的最短路徑問題是一個(gè)特例，可將圖視為沒條邊的權(quán)值均為1的 帶權(quán)圖。兩種最常見的最短路徑問題：從某個(gè)源點(diǎn)到其余各頂點(diǎn)的最短路徑每對(duì)頂點(diǎn)間的最短路徑7. 2 松弛技術(shù) Relaxation在后面介紹的兒個(gè)算法中都用到了松弛技術(shù)，現(xiàn)在就來看看松弛技術(shù)。對(duì)于每個(gè)頂點(diǎn)vGV,都設(shè)置一個(gè)屬性dv,用來描述從源點(diǎn)s到v的最短 路徑上權(quán)值的上界，稱為最短路徑估計(jì)(shortest-path estimate)。我們用 下面的0 (V)時(shí)間的過程來對(duì)最短路徑估訃和前趨進(jìn)行初始化。INITIALIZE-SINGLE-SOURCE

4、 G, s)1 for each vertex vWVG2 do dv83 n v -NIL4 ds0經(jīng)過初始化以后，對(duì)所有vWV, Ji v二NIL,對(duì)vev-s,有ds二0以及 dv=8。在松弛一條邊(u,v)的過程中，要測(cè)試是否可以通過u,對(duì)迄今找到的v的 最短路徑進(jìn)行改進(jìn)；如果可以改進(jìn)的話，則更新dv和31 vlo 一次松弛操作 可以減小最短路徑估計(jì)的值dv,并更新V的前趨域JI vlo下面的偽代碼對(duì) 邊(u,v)進(jìn)行了一步松弛操作。RELAX (u, v, w)1 if (dvdu+w(u, v)2 then dv du+w(u, v)3 n v u在 Bellman-Ford al

5、gorithm 和 Dijkstra s algorithm 都會(huì)調(diào)用到 INITIALIZE-SINGLE-SOURCE(G, s),然后重復(fù)對(duì)邊進(jìn)行松弛的過程。另外松弛是 改變最短路徑和前趨的唯一方式，在兩個(gè)算法之間的區(qū)別在于對(duì)每條邊進(jìn)行的 松弛操作的次數(shù)，以及對(duì)邊執(zhí)行松弛操作的次序不同。在Dijkstra * s algorithm以及關(guān)于有向無回路圖的最短路徑算法中，對(duì)每條邊執(zhí)行情況一次 松弛操作。而在Bellman-Ford算法中，對(duì)每條邊要執(zhí)行多次松弛操作。7. 3 Bellman-Ford algorithm思想：運(yùn)用松弛技術(shù)，對(duì)每一個(gè)結(jié)點(diǎn)vWV,逐步減少從源s到v的最短路徑的權(quán)

6、的估計(jì)值dv,直至其達(dá)到實(shí)際最短路徑的權(quán)8 (s, v) o算法返回布爾值TURE當(dāng)且僅當(dāng)圖中沒有源結(jié)點(diǎn)可達(dá)的負(fù)權(quán)回路。優(yōu)點(diǎn)：解決更一般情況的單源最短路徑問題。且邊的權(quán)值可以為負(fù)，可檢 測(cè)出圖中是否存在一個(gè)從源結(jié)點(diǎn)可達(dá)的負(fù)權(quán)回路，如果存在負(fù)權(quán)回路則無解； 否則將產(chǎn)生最短路徑及其權(quán)。BELLMAN-FORD (G,w, s)1 INITIALIZE-SINGLE-SOURCE G, s2 for il to iVG|-13 do for each edge (u, v) WEG4 do RELAX (u, v, w)5 for each edge (u, v) WEG6 do if dvdu+w

7、(u, v)7 then return false;8 return true引理7.3.1設(shè)為帶權(quán)有向圖，其源點(diǎn)為s,權(quán)函數(shù)為w : ER,并且假定G中 不包含從s點(diǎn)可達(dá)的負(fù)權(quán)回路。那么BELLMAN-FORD第24行循環(huán)的|V卜1次迭代 后，對(duì)任何s可達(dá)的頂點(diǎn)v,有dv= (s, v)e推論：設(shè)G二(V, E)為帶權(quán)有向圖，源頂點(diǎn)為s,加權(quán)函數(shù)為w:ER,對(duì)每個(gè) 頂點(diǎn)v(vWV),從s到v存在一條通路，當(dāng)且僅當(dāng)對(duì)G運(yùn)行BELLW-FORD (G,w,s) 算法，算法終止時(shí),有dvoo0定理：設(shè)G二(V, E)為帶權(quán)有向圖，源頂點(diǎn)為s,加權(quán)函數(shù)為w:ER,對(duì)該圖 運(yùn)行BELLMAN-FORD

8、 (G,w,s)算法，若G不包含s可達(dá)的負(fù)權(quán)回路，則算法返回 TRUE.對(duì)所有頂點(diǎn)v(vGV).有dv=(s, v)成立。前趨子圖G是以s為根的最短 路徑樹。如果G包含從s可達(dá)的負(fù)權(quán)回路，則算法返回FALSE。7. 4 Dijkstra s algorithm目的:解決有向加權(quán)圖的最短路徑問題。條件：該圖的所有邊的權(quán)值非負(fù)。算法思想：設(shè)置一個(gè)結(jié)點(diǎn)集合S,從源點(diǎn)S到集合中結(jié)點(diǎn)的最終最短路徑的 權(quán)均已確定。算法反復(fù)挑選出其最短路徑估計(jì)為最小的結(jié)點(diǎn)uEV-S.把u插入到 集合S中，并對(duì)離開u的所有邊進(jìn)行松弛。Dijkstra算法總是在集合V-S中選擇 “最近”的結(jié)點(diǎn)插入集合S中，它使用了貪心策略。D

9、ijkstra(G, w, s) Init-Singlesource (G, s) s = emptyQ = VGZwhile ( Q != empty) do u = extract-min (Q) s = s and u for 每個(gè)頂點(diǎn) v 屬于 Adju do Relax (u, v, w)Dijkstra執(zhí)行過程:S： A103 oo co1038 OCAfCQ：1077ooII1100539Relax all edges leaving Bx10Q：D711937 90A7 as2 J)35I 4 C, E, B 103oo7115711S:AC,E,B,D9定理：Dijkstra

10、算法的正確性證明證明：將證明對(duì)每一結(jié)點(diǎn)u屬于V,當(dāng)U被插入集合S時(shí)有du =Q(s, u)成 立，且此后該等式一直保持成立。設(shè)U為插入集合S中的第一個(gè)滿足du!=Q(s, u)的結(jié)點(diǎn)?？芍猽!二s,可知u被插入集合S前S!二空。從s到u必存在某條通路，否則du二Q (s, u) =inf,與du !=Q(s, u)矛盾。因?yàn)榇嬖谝粭l通路，所以存在一條最短路P。路徑P聯(lián)結(jié)集合S中的結(jié)點(diǎn)S 到V-S的結(jié)點(diǎn)Uo考察沿路徑P的第一個(gè)屬于V-S的結(jié)點(diǎn)y。設(shè)x屬于V是y的 先輩。路徑P可以分解為sVx和yp2-u。(若第一個(gè)點(diǎn)為U,則 du=Q(s, u),已得證)因?yàn)镾到U的最短路徑上y出現(xiàn)在y之前且所

11、有邊的權(quán)均為非負(fù)，我們有 Q(s, y) =Q(s, u),因而 dy = Q(s, y) = Q(s,u) =du,但因?yàn)樵诘?5 行選擇 u時(shí)結(jié)點(diǎn)u和y都屬于V-S,所以有du=dy 因此du二dy。最后得出結(jié)論du二Q(s, u),這與我們對(duì)u的假設(shè)矛盾。Dijkstra算法效率：若用線性數(shù)組實(shí)現(xiàn)優(yōu)先隊(duì)列：每次Extract_Min為 0(v),存在V次，則為0(廠2)。for中有E次迭代。所以整個(gè)算法運(yùn)行時(shí)間0(曠2)。稀疏圖用二義堆比較合適。Extract.Min需要0(lgv),建立需要0(V)。更 改權(quán)值用Decrease_key?？倳r(shí)間為0 (V+E) lgV)。如果用斐波那契堆可以進(jìn)一 步提高效率至0(VlgV+E)o7. 5總結(jié)根據(jù)各種教材介紹，還有兒種經(jīng)典的算法，所有頂點(diǎn)之間的最短路徑(Floyed算法)、特定兩個(gè)頂點(diǎn)之間的最短路徑(A*算法)等。在上述介紹的 算法，當(dāng)減低問