【正文】 變的概率。交叉點(diǎn)可以是任何染色體上的位置。交配父母的染色體交換，導(dǎo)致了兩個(gè)新的染色體產(chǎn)生，第一個(gè)個(gè)體前一半是父親的染 引言 8 色體，母親的則是后半段，第二個(gè)人則剛好相反。例如，交配概率為 ， 80％“夫婦”可以生育后代。然后，被選擇后的個(gè)體進(jìn)入交配過程。作為一種妥協(xié)，根據(jù)遺傳算法的原則基礎(chǔ)上：適應(yīng)度越高，被選中的機(jī)會(huì)越高，適應(yīng)低被選中的機(jī)會(huì)越低。這個(gè)過程是通過選擇和繁殖，包括復(fù)制，包括交配（ crossover，算法在該領(lǐng)域的研究，就是我們所說的交叉操作）和突變（ mutation）。 “高”是指對(duì)初始群的低適應(yīng)度來講的。每一個(gè)體在每一代，都被評(píng)估并通過 適應(yīng)度函數(shù) 的計(jì)算來得到一個(gè) 適應(yīng)度 的數(shù)值。染色體一般被表達(dá)為一個(gè)簡(jiǎn)單的字符串或數(shù)字字符串，但也適用于于特殊問題的表達(dá)方法，這個(gè)過程稱為編碼。在每一代，種群的適應(yīng)度被評(píng) 估，通過自然選擇和突變產(chǎn)生新的生命種群，隨機(jī)從目前的種群選擇多個(gè)個(gè)體（根據(jù)其自身的適應(yīng)度），這個(gè)種群在第一次迭代算法中，生成為當(dāng)前的種群。傳統(tǒng)的二進(jìn)制表示（即 0和 1的字符串），但也可以使用其他方法來陳述。 遺傳算法通常作為計(jì)算機(jī)模擬實(shí)施。 引言 7 遺傳算法 是用來解決優(yōu)化問題的搜索算法，是一種進(jìn)化算法。它不遍歷整個(gè)搜索空間，但根據(jù)選定的啟發(fā)式函數(shù)對(duì)最有前途的方向前進(jìn)。城鎮(zhèn)土地定級(jí)和評(píng)價(jià)，而不考慮道路網(wǎng)絡(luò)，可以是一個(gè)網(wǎng)格八個(gè)方向法國(guó)。 A *算法是一個(gè)典型的人工智能啟發(fā)式搜索算法，該算法的創(chuàng)新，是選擇下一個(gè)節(jié)點(diǎn)，探索引進(jìn)一個(gè)已知的道路網(wǎng)絡(luò)和目標(biāo)點(diǎn)和當(dāng)前點(diǎn)的距離年底評(píng)估選擇下一個(gè)路徑節(jié)點(diǎn)的基礎(chǔ)上。如果估計(jì)值大于實(shí)際值，搜索點(diǎn)少，搜索范圍小，效率高，但不能保證最佳的解決方案。保證找到最短路徑（最優(yōu)解）的條件下，關(guān)鍵是要選擇的評(píng)估函數(shù) H（ N）： h的估計(jì)值（ N） = n到目標(biāo)節(jié)點(diǎn)的距離實(shí)際價(jià)值，在這種情況下，搜索點(diǎn)多，搜索范圍變大，就會(huì)得到更低得效率。 *算法 A*（ AStar)算法 是最短路最有效的方式來解決一個(gè)靜態(tài)的路網(wǎng)。其中 T算法依靠的是圖增長(zhǎng)理論，直線了兩個(gè) FIFO隊(duì)列與一個(gè)雙 引言 6 端隊(duì)列結(jié)構(gòu)來支持搜索過程，更適合于計(jì)算單源點(diǎn)到所有其他點(diǎn)的最短距離。 現(xiàn)在公認(rèn)的最好的方法解決最短路徑問題，是由 ， 1959年提出的，也就是俗稱的 Dijkstra算法，他的名字命名的標(biāo)記方法。其中圖增長(zhǎng)論是 T算法的根本，用兩個(gè) FIFO隊(duì)列直線了一個(gè)雙端隊(duì)列結(jié)構(gòu)來支持搜索過程，較適合于計(jì)算單源的點(diǎn)到另外的所有點(diǎn)的之間的最短距離。五是利用并行算法，并行計(jì)算服務(wù)。三是使用有損的算法，如限制搜索范圍，以限制搜索的方向和限制的幾何圖層次第歸序搜索 。盡可能以統(tǒng)一的時(shí)間復(fù)雜度的基礎(chǔ)上的提高算法的工作效率 。在空間的復(fù)雜性，時(shí)間復(fù)雜度和易于實(shí)施和應(yīng)用領(lǐng)域，各有獨(dú)特的地方。大量的國(guó)內(nèi)外專家和學(xué)者對(duì)這一問題進(jìn)行深入研究。 引言 5 Dijkstra算法的資料調(diào)研分析 最短路徑問題一直是計(jì)算機(jī)科學(xué)、 運(yùn)籌學(xué)、地理信息科學(xué)等學(xué)科的一個(gè)研究四是采用拓?fù)鋵哟尉幋a路徑視圖，對(duì)最短路徑進(jìn)行部分實(shí)例化編碼存儲(chǔ)；五是采用并行算法，為并行計(jì)算服務(wù)。 Dijkstra算法的表達(dá)方式一般有兩種方式，一個(gè)為永久的和臨時(shí)的標(biāo)號(hào)方法，另一個(gè)用 OPEN， CLOSE表方法，這里是永久和臨時(shí)標(biāo)號(hào)的方式。其主要特點(diǎn)是起點(diǎn)為中心向外擴(kuò)張，直到終點(diǎn)到為止的擴(kuò)展。注意該算法要求圖中不存在負(fù)權(quán)邊。 Dijkstra算法是很有代表性的最短路徑算法，在很多專業(yè)課程中都作為基本內(nèi)容有詳細(xì)的介紹，如數(shù)據(jù)結(jié)構(gòu)，圖論，運(yùn)籌學(xué)等等。 Dijkstra(迪杰斯 特拉 )算法是典型的單源最短路徑算法，用于計(jì)算任意節(jié)點(diǎn)到其它所有節(jié)點(diǎn)的最短路徑。 最短路徑要解決的問題是一個(gè)加權(quán)圖 G =V,E,w到兩個(gè)給出的定點(diǎn)之間的最短路徑。 最短路徑問題要解決的就是加權(quán)圖 G=V， E， w兩給定定點(diǎn)之間的最短路徑。最短路徑問題不單單是“純距離”的 最短路徑，也可以被擴(kuò)展來衡量其他的意義，如經(jīng)濟(jì)成本，時(shí)間和吞吐量。因此，在優(yōu)化算法中計(jì)算的節(jié)點(diǎn)數(shù)量大幅減少，使算法的運(yùn)算在速度上得到了大量的提升。傳統(tǒng)的 Dijkstra算法在求解節(jié)點(diǎn)之間的最短路徑時(shí)，對(duì)已經(jīng)標(biāo)識(shí)的節(jié)點(diǎn)以外的很多節(jié)點(diǎn)進(jìn)行了計(jì)算，因此算法的速度受到了影響。 畢業(yè)設(shè)計(jì)說明書 基于 Dijkstra 算法的最短路徑搜索仿真 學(xué) 院： 專 業(yè)： 學(xué)生姓名 ： 學(xué) 號(hào)： 指導(dǎo)教師 ： 2021 年 6 月 摘要 I 摘 要 GIS地理網(wǎng)絡(luò)分析功能中的一個(gè)最重要問題就是最短路徑分析。最短路徑問題中最經(jīng)典的算法便是 Dijkstra算法，該理論是 很大一部分工程項(xiàng)目解決最短路徑問題的基礎(chǔ)。在傳統(tǒng) Dijkstra算法分析的基礎(chǔ)上，進(jìn)行改進(jìn)和優(yōu)化，最短路徑上節(jié)點(diǎn)的鄰接點(diǎn)被進(jìn)行了處理，從而得到了算法優(yōu)化，但其余的節(jié)點(diǎn)不受到波及。 關(guān)鍵詞： 最短路徑， Dijkstra算法，仿真 英文摘要 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． Keywords: the shortest path， Dijkstra algorithm， Simulation 目錄 III 目 錄 摘 要 ............................................................ I Abstract .......................................................... II 目 錄 .......................................................... III 第一章 引言 ........................................................ 4 課題的目的意義 ................................................. 4 Dijkstra 算法的資料調(diào)研分析 ..................................... 5 國(guó)內(nèi)外主流算法及其簡(jiǎn)要展開 ..................................... 6 設(shè)計(jì)方案的可行性分析和預(yù)期目標(biāo) ................................. 9 本文主要研究?jī)?nèi)容 .............................................. 10 第二章 Dijkstra 經(jīng)典算法的研究 ..................................... 11 Dijkstra 算法原理 .............................................. 11 Dijkstra 算法的仿真實(shí)現(xiàn) ........................................ 12 第三章 軟件開發(fā)、設(shè)計(jì)工具簡(jiǎn)介 ..................................... 16 C語(yǔ)言開發(fā)工具 ............................................... 226 ACCESS 數(shù)據(jù)庫(kù)設(shè)計(jì)工具 .......................................... 22 第 四 章 系統(tǒng)設(shè)計(jì) .................................................. 152 圖形界面 ...................................................... 22 功能實(shí)現(xiàn) ...................................................... 24 數(shù)據(jù)庫(kù)設(shè)計(jì) ................................................... 235 系統(tǒng)測(cè)試 ...................................................... 28 總結(jié) .............................................................. 30 參考文獻(xiàn) .......................................................... 31 致 謝 ........................................................... 32 引言 4 第一章 引言 課題的目的意義 最短路徑問題是圖論、網(wǎng)絡(luò)分析研究的重要課題，它被廣泛用于網(wǎng)絡(luò)優(yōu)化，交通運(yùn)輸，物流配送，電子導(dǎo)航等領(lǐng)域。例如，城市交通，旅客選擇旅游的最佳路徑，最可靠的路徑運(yùn)輸網(wǎng)絡(luò)，的最大容量，最少的成本問題，和統(tǒng)籌方法關(guān)的鍵路徑問題，全部可以轉(zhuǎn)化為最短路徑問題。求單源點(diǎn)最短路徑的一個(gè)著名算法是 Dijkstra算法。尋求一個(gè)單源最短路徑算法就是眾所周知的 Dijkstra算法。以最初始的點(diǎn)為中心，向外層拓展，直到拓展到終點(diǎn)為止，是其最重要的特點(diǎn)。Dijkstra一般的表述通常有兩種方式，一種用永久和臨時(shí)標(biāo)號(hào)方式，一種是用 OPEN, CLOSE表的方式，這里均采用永久和臨時(shí)標(biāo)號(hào)的方式。 Dijkstra算法（迪杰斯特拉）算法是一個(gè)典型的單源最短路徑算法， 用于計(jì)算節(jié)點(diǎn)到所有其他節(jié)點(diǎn)的最短路徑。 Dijkstra算法的是非常典型的最短路徑算法，在很多專業(yè)中都是被作為基礎(chǔ)的內(nèi)容來進(jìn)行詳細(xì)的介紹，如數(shù)據(jù)結(jié)構(gòu)，圖論，運(yùn)籌學(xué)等許多專業(yè)課程，是非常代表。請(qǐng)注意，該算法要求，負(fù)權(quán)邊不準(zhǔn)許存在圖中。 最短路徑問題一直是計(jì)算機(jī)科學(xué)，運(yùn)籌學(xué)，地理信息科學(xué)與其他學(xué)科的研究熱點(diǎn)。經(jīng)典圖論和計(jì)算機(jī)數(shù)據(jù)結(jié)構(gòu)和算法的不斷發(fā)展，有效地結(jié)合起來，使新的最短路徑算法不斷涌現(xiàn)。目前的研究重點(diǎn)，一為實(shí)際應(yīng)用網(wǎng)絡(luò)的特征優(yōu)化運(yùn)行結(jié)構(gòu)。二 是限制網(wǎng)絡(luò)的特征，如要求網(wǎng)絡(luò)邊緣具有證書權(quán)值，這樣的方便使用基數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)算法的運(yùn)行結(jié)構(gòu) 。四為使用拓?fù)鋵哟尉幋a路徑視圖，一些實(shí)例化編碼存儲(chǔ)用來對(duì)最短路徑進(jìn)行實(shí)施 。 在提高時(shí)間效率方面有較好的應(yīng)用性。后兩種算法則是基于 Dijkstra算法，采用桶結(jié)構(gòu)明顯提高了 永久標(biāo)記點(diǎn)的搜索速度。該算法是基于這樣一種想法，一種解釋的幾十種不同的優(yōu)化算法更好的算法 T(graph growth with two queues),DKA(the Dijkstra`algorithm implemented with approximate buckets),DKD(the Dijkstra`s algorithm implemented with double buckets)，排序的優(yōu)化算法，前面的三種算法中，空間儲(chǔ)存的問題是非常重要的，犧牲適當(dāng)?shù)臅r(shí)間效率，來節(jié)省空間，排序優(yōu)化算法放在了一