【正文】 儲(chǔ)存數(shù)據(jù)，其中 N為網(wǎng)絡(luò)節(jié)點(diǎn)，網(wǎng)絡(luò)節(jié)點(diǎn)太多時(shí)，將占用大量的計(jì)算 機(jī)內(nèi)存。 適應(yīng)已經(jīng)達(dá)到飽和，繼續(xù)進(jìn)化不會(huì)有適應(yīng)度更好 的個(gè)體 。這個(gè)過(guò)程不斷重復(fù)：每個(gè)個(gè)體都被評(píng)估，計(jì)算每一個(gè)個(gè)體的適應(yīng)度，兩個(gè)個(gè)體交配和突變，產(chǎn)生第三代。下一步是突變基因突變產(chǎn)生新的“孩子”個(gè)體。通過(guò)交配，每?jī)蓚€(gè)人產(chǎn)生兩個(gè)新個(gè)體，而原來(lái)的“老”的個(gè)體將會(huì)被替代。通過(guò)對(duì)初始數(shù)據(jù)的選擇，可組成一個(gè)相對(duì)最優(yōu)的群體。 下一步是產(chǎn)生下一代的個(gè)體組成種群。首先，算法隨機(jī)生成一定數(shù)量的個(gè)體，有時(shí)操作者可以在隨機(jī)生成的過(guò)程中進(jìn)行干預(yù)，以提高初始種群的質(zhì)量。進(jìn)化從完全隨機(jī)個(gè)體的種群開(kāi)始，代代發(fā)生。自然進(jìn)化的生物學(xué)現(xiàn)象，包括基因突變，自然選擇和雜交都被進(jìn)化算法用來(lái)參考。 A *算法可以找到任何一個(gè)因素的因素與其他各點(diǎn)之間的最短路徑。估計(jì) 值和實(shí)際值接近，就能獲得更好的評(píng)估函數(shù)。計(jì)算公式為： F（ N） = G（ N） +H（ N） F（ N）是節(jié)點(diǎn) n從初始點(diǎn)到目標(biāo)點(diǎn)的估價(jià)函數(shù)， G（ n）是實(shí)際成本從最初的節(jié)點(diǎn)到 n個(gè)節(jié)點(diǎn)，在狀態(tài)空間里， H（ N）是從 n到目標(biāo)節(jié)點(diǎn)的路徑的估計(jì)成本。該算法是基于這樣一種想法，一種解釋的幾十種不同的優(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ǔ)存的問(wèn)題是非常重要的，犧牲適當(dāng)?shù)臅r(shí)間效率，來(lái)節(jié)省空間，排序優(yōu)化算法放在了一個(gè)重要的位置上，可以更好地提高時(shí)間效率。 在提高時(shí)間效率方面有較好的應(yīng)用性。二 是限制網(wǎng)絡(luò)的特征，如要求網(wǎng)絡(luò)邊緣具有證書(shū)權(quán)值，這樣的方便使用基數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)算法的運(yùn)行結(jié)構(gòu) 。經(jīng)典圖論和計(jì)算機(jī)數(shù)據(jù)結(jié)構(gòu)和算法的不斷發(fā)展，有效地結(jié)合起來(lái)，使新的最短路徑算法不斷涌現(xiàn)。請(qǐng)注意，該算法要求，負(fù)權(quán)邊不準(zhǔn)許存在圖中。 Dijkstra算法（迪杰斯特拉）算法是一個(gè)典型的單源最短路徑算法， 用于計(jì)算節(jié)點(diǎn)到所有其他節(jié)點(diǎn)的最短路徑。以最初始的點(diǎn)為中心，向外層拓展，直到拓展到終點(diǎn)為止，是其最重要的特點(diǎn)。求單源點(diǎn)最短路徑的一個(gè)著名算法是 Dijkstra算法。 關(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)要展開(kāi) ..................................... 6 設(shè)計(jì)方案的可行性分析和預(yù)期目標(biāo) ................................. 9 本文主要研究?jī)?nèi)容 .............................................. 10 第二章 Dijkstra 經(jīng)典算法的研究 ..................................... 11 Dijkstra 算法原理 .............................................. 11 Dijkstra 算法的仿真實(shí)現(xiàn) ........................................ 12 第三章 軟件開(kāi)發(fā)、設(shè)計(jì)工具簡(jiǎn)介 ..................................... 16 C語(yǔ)言開(kāi)發(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èn)題是圖論、網(wǎng)絡(luò)分析研究的重要課題，它被廣泛用于網(wǎng)絡(luò)優(yōu)化，交通運(yùn)輸，物流配送，電子導(dǎo)航等領(lǐng)域。最短路徑問(wèn)題中最經(jīng)典的算法便是 Dijkstra算法，該理論是 很大一部分工程項(xiàng)目解決最短路徑問(wèn)題的基礎(chǔ)。傳統(tǒng)的 Dijkstra算法在求解節(jié)點(diǎn)之間的最短路徑時(shí)，對(duì)已經(jīng)標(biāo)識(shí)的節(jié)點(diǎn)以外的很多節(jié)點(diǎn)進(jìn)行了計(jì)算，因此算法的速度受到了影響。最短路徑問(wèn)題不單單是“純距離”的 最短路徑，也可以被擴(kuò)展來(lái)衡量其他的意義，如經(jīng)濟(jì)成本，時(shí)間和吞吐量。 最短路徑要解決的問(wèn)題是一個(gè)加權(quán)圖 G =V,E,w到兩個(gè)給出的定點(diǎn)之間的最短路徑。 Dijkstra算法是很有代表性的最短路徑算法，在很多專業(yè)課程中都作為基本內(nèi)容有詳細(xì)的介紹，如數(shù)據(jù)結(jié)構(gòu)，圖論，運(yùn)籌學(xué)等等。其主要特點(diǎn)是起點(diǎn)為中心向外擴(kuò)張，直到終點(diǎn)到為止的擴(kuò)展。 引言 5 Dijkstra算法的資料調(diào)研分析 最短路徑問(wèn)題一直是計(jì)算機(jī)科學(xué)、 運(yùn)籌學(xué)、地理信息科學(xué)等學(xué)科的一個(gè)研究四是采用拓?fù)鋵哟尉幋a路徑視圖，對(duì)最短路徑進(jìn)行部分實(shí)例化編碼存儲(chǔ)；五是采用并行算法，為并行計(jì)算服務(wù)。在空間的復(fù)雜性，時(shí)間復(fù)雜度和易于實(shí)施和應(yīng)用領(lǐng)域，各有獨(dú)特的地方。三是使用有損的算法，如限制搜索范圍，以限制搜索的方向和限制的幾何圖層次第歸序搜索 。其中圖增長(zhǎng)論是 T算法的根本，用兩個(gè) FIFO隊(duì)列直線了一個(gè)雙端隊(duì)列結(jié)構(gòu)來(lái)支持搜索過(guò)程，較適合于計(jì)算單源的點(diǎn)到另外的所有點(diǎn)的之間的最短距離。其中 T算法依靠的是圖增長(zhǎng)理論，直線了兩個(gè) FIFO隊(duì)列與一個(gè)雙 引言 6 端隊(duì)列結(jié)構(gòu)來(lái)支持搜索過(guò)程，更適合于計(jì)算單源點(diǎn)到所有其他點(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 *算法是一個(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ǔ)上。它不遍歷整個(gè)搜索空間，但根據(jù)選定的啟發(fā)式函數(shù)對(duì)最有前途的方向前進(jìn)。 遺傳算法通常作為計(jì)算機(jī)模擬實(shí)施。在每一代，種群的適應(yīng)度被評(píng) 估，通過(guò)自然選擇和突變產(chǎn)生新的生命種群，隨機(jī)從目前的種群選擇多個(gè)個(gè)體（根據(jù)其自身的適應(yīng)度），這個(gè)種群在第一次迭代算法中，生成為當(dāng)前的種群。每一個(gè)體在每一代，都被評(píng)估并通過(guò) 適應(yīng)度函數(shù) 的計(jì)算來(lái)得到一個(gè) 適應(yīng)度 的數(shù)值。這個(gè)過(guò)程是通過(guò)選擇和繁殖，包括復(fù)制，包括交配（ crossover，算法在該領(lǐng)域的研究，就是我們所說(shuō)的交叉操作）和突變（ mutation）。然后，被選擇后的個(gè)體進(jìn)入交配過(guò)程。交配父母的染色體交換，導(dǎo)致了兩個(gè)新的染色體產(chǎn)生，第一個(gè)個(gè)體前一半是父親的染 引言 8 色體，母親的則是后半段，第二個(gè)人則剛好相反。一般遺傳算法有一個(gè)固定的突變常數(shù)（又稱突變率）一般為 ，這代表了基因突變的概率。一遍又一遍，直到滿足終止條件。 人為干預(yù) 。 （ 2）原始的 Dijkstra算法的運(yùn)行時(shí)一般把網(wǎng)絡(luò)節(jié)點(diǎn)分為沒(méi)有被標(biāo)記節(jié)點(diǎn)，臨時(shí)標(biāo)記節(jié)點(diǎn)，永久標(biāo)記節(jié)點(diǎn)。由于所需要的硬件配置要求不高，對(duì)于代碼編制，和算法的實(shí)現(xiàn)都是非常合適的。原始 Dijkstra算法的網(wǎng)絡(luò)節(jié)點(diǎn)分為三個(gè)部分： 未標(biāo)記節(jié)點(diǎn)，臨時(shí)標(biāo)記的節(jié)點(diǎn)和永久標(biāo)記的節(jié)點(diǎn)。求解從起源點(diǎn)到 j點(diǎn)的小號(hào)的基本過(guò)程，最短路徑算法如 下： 1）初始化。從標(biāo)記點(diǎn)中，找到點(diǎn) I直接連接的點(diǎn) j*，作為前點(diǎn)，設(shè)：I= J *。以下是用到的一 段 Dijkstra算法的關(guān)鍵的代碼： private void ShortestDist(int s) { for (int i = 0。 //已求出最短路徑的頂點(diǎn)集合初始化 Dijkstra 經(jīng)典算法的研究 13 if (i != s amp。 //路徑存放數(shù)組初始 化 } S[s]=1。 i++) { //從頂點(diǎn) s確定 n1條路徑 double min = 。 j++) { //選擇當(dāng)前不在集合 S中具有最短路徑的頂點(diǎn) u /* 如果有路徑比目前的最小值還小，則替換這個(gè)最小值 */ if (S[j] == 0 amp。 } } S[u] = 1。amp。 path[w] = u。 D[k] != s。 } Dijkstra 經(jīng)典算法的研究 14