【正文】 ...... 5 一、原理及應(yīng)用 ................................................................................................................ 5 （一）原理 ................................................................................................................. 5 （二）應(yīng)用 ................................................................................................................. 6 （三）優(yōu)缺點(diǎn) ............................................................................................................. 9 二、 Dijkstra 算法與其他主流算法的比較 .................................................................... 11 （一）搜索速 度比較 ............................................................................................... 11 （二）搜索成功率比較 ........................................................................................... 12 第三章 基于 Dijkstra 算法的優(yōu)化算法的研究 .................................................................... 14 一、幾種優(yōu)化算法 .......................................................................................................... 14 （一）減小算法中成功搜索的搜索范圍 ............................................................... 14 （二）改進(jìn)算法的存儲(chǔ)結(jié)構(gòu) ................................................................................... 14 二、 本文對(duì) Dijlstra 優(yōu)化算法研究 ................................................................................ 14 （一）目標(biāo) ............................................................................................................... 15 （二）思路 ............................................................................................................... 15 （三）描述 ............................................................................................................... 16 （四）特點(diǎn) ............................................................................................................... 19 三、本文優(yōu)化算法與傳統(tǒng)算法的比較 .......................................................................... 20 第四章 此優(yōu)化算法在消防中的相關(guān)應(yīng)用 ........................................................................... 21 一、消防力量調(diào)集路徑最優(yōu)指標(biāo)的選取 ...................................................................... 21 二、 Dijkstra 最短路徑經(jīng)典算法及分析 ........................................................................ 22 （一）問題定義 .............................................................................................................. 22 （二） Dijkstra 算法 ........................................................................................................ 22 （三） Dijkstra 算法優(yōu)化及分析 .................................................................................... 22 1．優(yōu)化 Dijkstra 算法的思路 ................................................................................. 22 2．優(yōu)化 Dijkstra 算法的描述 ................................................................................. 23 結(jié)論 ......................................................................................................................................... 24 參考文獻(xiàn) ................................................................................................................................. 25 附錄一 ..................................................................................................................................... 26 致謝 ........................................................................................................... 錯(cuò)誤 !未定義書簽。其中，第二方面問題的研究得出的結(jié)論是“ 當(dāng)目標(biāo)是期望最短路徑時(shí)問題轉(zhuǎn)化為將邊的權(quán)重用期望值表示的最短路徑問題 ”。 最短路徑算法是計(jì)算機(jī)科學(xué)與地理信息科學(xué)等領(lǐng)域研究的熱點(diǎn)，其算法有很多種，其中傳統(tǒng)的 Dijkstra 算法一般用于計(jì)算一個(gè)源節(jié)點(diǎn)到所有其他節(jié)點(diǎn)的最小代價(jià)路徑，并且能夠適應(yīng)網(wǎng)絡(luò)拓?fù)涞淖兓?，性能穩(wěn)定，因而可以在運(yùn)輸路線規(guī)劃等領(lǐng)域都應(yīng)用廣泛。注意該算法要求圖中不存在負(fù)權(quán)邊。 3)選取下一個(gè)點(diǎn)?，F(xiàn)在 ,在北京市內(nèi)有若干家收治非典病人的醫(yī)院。 4)轉(zhuǎn) 2。后面的各步也都出現(xiàn)類似的情況 (后略 )，尤其是當(dāng)圖的邊數(shù)相對(duì)較少時(shí)更為明顯。 14 第三章 基于 Dijkstra 算法的優(yōu)化算法的研究 一、 幾種優(yōu)化算法 （一） 減小算法中成功搜索的搜索范圍 減小算法中成功搜索的搜索范圍以盡快到達(dá)目標(biāo)節(jié)點(diǎn)。但鄰接表卻難以判斷兩節(jié)點(diǎn)之間的關(guān)系，因此本文提出利用。針對(duì)此問題，提出了 Dijkstra 算法的改進(jìn)，本文在對(duì)傳統(tǒng) Dijkstra 算法分析的基礎(chǔ)上，對(duì)其進(jìn)行了優(yōu)化，優(yōu)化算法只對(duì)最短路徑上節(jié)點(diǎn)的鄰居做處理，而不涉及到其他節(jié)點(diǎn) [7]。 16 （三） 描述 基于上述兩點(diǎn)不足，對(duì)傳統(tǒng) Dijkstra算法進(jìn)行優(yōu)化，算法優(yōu)化思路為：首先從源點(diǎn) s的鄰居集合 NBS(與 s直接相連的節(jié)點(diǎn)集合 )中選擇距離最小的鄰居節(jié)點(diǎn) k作為轉(zhuǎn)接點(diǎn)，同時(shí)將劃歸到標(biāo)識(shí)集合 S(初始時(shí)， S為 {s})。 圖 31 非負(fù)權(quán)值圖 17 經(jīng)典 Dijkstra算法求解過程： Step0：初始化 S = (v1)， w1 = 0， T = (v2,v4, v3,v5, v6,v7)； Step1： w4 = d14 = mind1j = 2（ d12 = d14，任選其一，本文選 v4）， S = (v1,v4)， j∈ T T=(v2,v3,v5,v6,v7)； Step2： T= (v2,v3,v5,v6,v7) w2 = min{w2,w4 + d42}= min{2,4}= 2， w3 = min{w3,w4 + d43}= min{5,5} = 5 2 = w2， w5 = min{w5,w4 + d45} = {∞,3} = 3 2 = w2， w6 = min{w6,w4 + d46} = ∞， (31) w7 = min{w7,w4 + d47} = ∞， (32) ∵ minwj =w2 = 2， ∴ S = (v1,v2,v4)， T = (v3,v5,v6,v7)； Step3： T = (v3,v5,v6,v7) w3 = min{w3,w2 + d23} = min{5,5} = 5， w5 = min{w5,w2 + d25} = min{3, ∞} = 3 5 = w3， w6 = min{w6,w4 + d46} = ∞， (33) w7 = min{w7,w4 + d47} = ∞， (34) ∵ minwj = w5 = 3， ∴ S = (v1,v2,v4,v5)， T = (v3,v6,v7)； Step4： T = (v3,v6,v7) w3 = min{w3,w5 + d53} = min{5,4} = 4， w6 = min{w6,w5 + d56} = {∞,4} = 4 = w3， w7 = min{w7,w5 + d57} = {∞,5} = 5 4 = w3 = w6， ∵ minwj = w3 = w6 = 4，任選其一，若為 w3， ∴ S = (v1,v2,v3,v4,v5)， T = (v6,v7)； Step5： T = (v6,v7) w6 = min{w6,w3+d36}= min{4,∞} = 4， w7 = min{w7,w3 + d37} = {5,∞} = 5 4 = w3 = w6， ∵ minwj = w6 = 4， 18 ∴ S = (v1,v2,v3,v4,v5,v6)， T = (v7)； Step6： T = (v7) w7 = min{w7,w6 + d67} = {5,6} = 5。 本文提出的優(yōu)化算法在更新最短路徑值與選擇最短路徑值最小的節(jié)點(diǎn)時(shí)，僅僅涉及到節(jié)點(diǎn)的鄰居集合及已標(biāo)識(shí)集合中所有節(jié)點(diǎn)的鄰居集合與已標(biāo)識(shí)集合的差集，其運(yùn)行時(shí)間取決于轉(zhuǎn)接點(diǎn)的鄰居集合的元素?cái)?shù)量多少 (而該數(shù)量值往往小于未標(biāo) 識(shí)集合中的元素個(gè)數(shù) )。 21 第四章 此優(yōu)化算法 在消防中的 相關(guān)應(yīng)用 火災(zāi)是城市中較為頻繁的災(zāi)害，其損失經(jīng)常是巨大的。 一、消防力量調(diào)集路徑最優(yōu)指標(biāo)的選取 Dijkstra 算法在通用路徑選擇算法中，對(duì)最短路 徑的衡量標(biāo)準(zhǔn)是通過計(jì)算路徑的邊權(quán)來(lái)決定的。該方案較好地反映了現(xiàn)實(shí)情況，且技術(shù)上切實(shí)可行，綜合考慮了實(shí)用性與可行性 [12]。下一條次短路徑的長(zhǎng)度一定是： D[j] = min{D[i]|Vi∈ V S }，其中 S為已求得最短路徑的終點(diǎn)的集合。否則，本優(yōu)化算法效果不明顯。根據(jù)計(jì)算結(jié)果，取這兩段中權(quán)值最小的一段，作為最佳路徑中的一段 [15]。 namespace