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