【正文】 種群滿足預(yù)定指標(biāo) 編碼為染色體（向量） 種群 P（ t） 計(jì)算各染色體適應(yīng)度 通過遺傳運(yùn)算存優(yōu)去劣 種群 P（ t+1） 復(fù)制 交換 變異 種群 P（ t） ?種群 P（ t+1） 解碼染色體 問題解答空間 N 4 經(jīng)典 Dijkstra算法 存在的問題 （ 1）原始 Dijkstra 算法在存儲(chǔ)圖形數(shù)據(jù)和運(yùn)算時(shí)，基于網(wǎng)絡(luò)的權(quán)矩陣，需要根據(jù)其節(jié)點(diǎn)與距離之間的關(guān)系，形成關(guān)聯(lián)矩陣、鄰接矩陣與距離矩陣，需要定義 NN的數(shù)組來(lái)存儲(chǔ) 數(shù)據(jù)，其中 N 為網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)，當(dāng)網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)較大時(shí)，將占用大量的計(jì)算機(jī)內(nèi)存。 圖 遺傳算法工作原理示意圖 Dijkstra算法 Dijkstra算法的基本思想是，設(shè)置一個(gè)頂點(diǎn)的集合 S，從源點(diǎn) S到集合中的各頂點(diǎn)的最終最短路徑的權(quán)值均已經(jīng)確定。 GA 就這樣反復(fù)迭代，直至滿足某種預(yù)定的優(yōu)化指標(biāo)。算法開始時(shí)先隨機(jī)地產(chǎn)生一些染色體，計(jì)算其適應(yīng)度，根據(jù)適應(yīng)度對(duì)諸染色體進(jìn)行選擇、交換、變異等遺傳操作，剔除適應(yīng)度 3 低的染色體，留下適應(yīng)度高的染色體。所有染色體組成群體。它的思想源于生物遺傳學(xué)和適者生存的自然規(guī)律，是具有 ―生存 +檢測(cè) ‖的迭代過程的搜索算法。它的搜索速度雖然較快，理論上也能找到最優(yōu)解，但在實(shí)際應(yīng)用過程中往往由于啟發(fā)式函數(shù)選取不當(dāng)而經(jīng)常找不到最短路徑，搜索的成功率并不是很高。通過 A*算法可以尋找任何一個(gè)因素因子與其它各點(diǎn)之間的最短路徑。通用的 A*算法可采用四方向，八方向，對(duì)于矢量路網(wǎng)則可采用遍歷相連路徑法進(jìn)行路徑探索。估價(jià)值與實(shí)際值越接近，估價(jià)函數(shù)取得就越好。但能得到最優(yōu)解。公式表示為： f(n)=g(n)+h(n) 其中 f(n) 是節(jié)點(diǎn) n 從初始點(diǎn)到目標(biāo)點(diǎn)的估價(jià)函數(shù)， g(n) 是在狀態(tài)空間中從初始節(jié)點(diǎn)到 n 節(jié)點(diǎn)的實(shí)際代價(jià)， h(n)是從 n 到目標(biāo)節(jié)點(diǎn)最佳路徑的估計(jì)代價(jià)。在不確定的情況下最短路徑問題的研究包含以下幾個(gè)方面：Frank（ 1969）和 Mirchandani（ 1976）研究了路段長(zhǎng)度隨機(jī)變化的且非時(shí)間獨(dú)立的情況下的最短路徑問題； Loui（ 1983）、 Muethy 和 Sarkar（ 1996）考慮不同的費(fèi)用函數(shù)研究最短路徑問題，他們的結(jié)論是當(dāng)目標(biāo)是期望最短路徑時(shí)問題轉(zhuǎn)化為將邊的權(quán)重用期望值表示的最短路徑問題； Hall（ 1986）、 LiPing Fu 和 （ 1998）、Elise 和 Hani（ 2020）研究了路段長(zhǎng)度 隨機(jī)變化且時(shí)間獨(dú)立情況下的最短路徑問題；Tomas 和 Rajeev 研究了路段長(zhǎng)度為區(qū)間范圍的最短路徑問題。在這種確定情況下最短路徑問題的研究中， Bellman（ 1958）、Dijkstra（ 1959）和 Dreyfus（ 1969）已發(fā)展出許多高效 算法。 當(dāng)前對(duì)于最短路徑的相關(guān)研究主要包含兩方面。 [1] 現(xiàn)今比較流行的最短路徑規(guī)劃算法主要有以下三類：第一類是基于圖論理論的算法；如 Dijkstra及其改進(jìn)算法， Floyd算法等 ；第二類則是基于傳統(tǒng)人工智能理論的算法，如 A*機(jī)器改進(jìn)算法，深度有限、寬度有限算法等；第三類則是基于智能控制技術(shù)的算法，如人工神經(jīng)網(wǎng)絡(luò)算法、遺傳算法等。當(dāng)時(shí)的 Dijkstra提出的這一算法主要解決的問題是從固定的一個(gè)點(diǎn)到其他各點(diǎn)的最短路徑問題。 關(guān)鍵詞： 最短路徑； Dijkstra 算法；優(yōu)化 II Abstract Shortest path analysis is the key problem of work analyses， Dijkstra algorithm is a classic arithmetic for the shortest path. It is the academic foundation that many engineerings were solved in the shortest path issue. When a shortest path between nodes is searched with Dijkstra algorithm， a lot of nodes away from lagged nodes are involved， so that the efficiency of Dijkstra algorithm is low． An optimization algorithm is presented in this paper based on analysis of Dijkstra algorithm． Only these nodes that the neighbor of nodes in the shortest path are processed， and other nodes are not processed. Therefore， the number of processed nodes is largely reduced in the optimization algorithm， and efficiency of the optimization algorithm is improved． The improved algorithm is proved to be correct and efficient by experiments and practical application. Keywords: the shortest path； Dijkstra algorithm； optimization III 目 錄 摘 要 .......................................................................................................................... I Abstract ........................................................................................................................ II 第 1 章 概述 .............................................................................................................. 1 國(guó)內(nèi)外最短路徑算法概況 .......................................................................... 1 國(guó)內(nèi)外最短路徑研究的主流與方向 ................................................... 1 國(guó)內(nèi)外主流算法及其簡(jiǎn)要展開 ........................................................... 2 A*算法 [3].................................................................................... 2 遺傳算法 [4] ................................................................................ 2 Dijkstra 算法 .............................................................................. 3 經(jīng)典 Dijkstra 算法存在的問題 ............................................................ 4 研究的意義 .................................................................................................. 4 本文研究目標(biāo)和內(nèi)容 .................................................................................. 4 第 2 章 Dijkstra 經(jīng)典算法研究 ................................................................................ 6 Dijkstra 算法的原理及應(yīng)用 ........................................................................ 6 Dijkstra 算法原理 ................................................................................. 6 Dijkstra 算法應(yīng)用 ................................................................................. 7 Dijkstra 算法的優(yōu)缺點(diǎn) ....................................................................... 10 以 Dijkstra 算法為基礎(chǔ)算法進(jìn)行優(yōu)化的原因 ......................................... 12 Dijkstra 算法與其他主流算法的比較 [5]............................................ 12 搜索速度比較 .......................................................................... 12 搜索成功率比較 ...................................................................... 13 第 3 章 Dijkstra 優(yōu)化算法研究 .............................................................................. 14 多種 Dijkstra 優(yōu)化算法的研究 [6].............................................................. 14 第一類優(yōu)化算法 ——減小算法中成功搜索的搜索范圍 ................. 14 第二類優(yōu)化算法 ——改進(jìn)算法的存儲(chǔ)結(jié)構(gòu) ..................................... 14 本文對(duì) Dijkstra 優(yōu)化算法的研究 ............................................................. 15 優(yōu)化算法的目標(biāo) ................................................................................. 15 優(yōu) 化算法思路 ..................................................................................... 15 優(yōu)化算法描述 ..................................................................................... 16 優(yōu)化算法的特點(diǎn) ................................................................................. 19 優(yōu)化 Dijkstra 算法與原 Dijkstra 經(jīng)典算法比較 ...................................... 20 第 4 章 優(yōu)化 Dijkstra 算法的應(yīng)用 ......................................................................... 21 優(yōu)化算法在上海市物流中的實(shí)現(xiàn) ............................................................ 21 地圖說明 ............................................................................................. 21 屬性數(shù)據(jù)庫(kù)設(shè)計(jì) ................................................................................. 22 算法實(shí)現(xiàn) ..........................