【正文】 另外， 感謝我的家人，在我 上學 期間和整理論文期問，他們無私的關心和照顧著我的生活，是我能夠順利完成學業(yè)的必要條件。并詳細分析了經(jīng)典的最優(yōu)路徑選擇 Dijkstra 算法并對其進行改進，考慮到在實際情況中由道路質量、擁堵情況等導致交通道路存在一定的交通阻抗， 并將交通阻抗的計算加入到改進的 Dijkstra 算法當中，使之更具有應用價值。 5． 3 本章小結 本章的工作重點是首先依據(jù)電子地圖結合路徑優(yōu)化算法的實現(xiàn)改進的動態(tài)路徑優(yōu)化算法，證明其實時性、合理性。 武漢紡織大學 20xx 屆畢業(yè)設計論文 19 4． 8 本章小結 本章介紹的是關于 GIS 數(shù)據(jù)模型與 Oracle 數(shù)據(jù)庫管理設計的相關內容，主要包括以下幾個方面： GIS 數(shù)據(jù)模型的建立； GIS 數(shù)據(jù)的管理與組織；數(shù)據(jù)管理設計基礎知識； Oracle Spatial 簡介； GIS 數(shù)據(jù)向 Oracle 中的導入； GIS 數(shù)據(jù)在 Oracle 中的存儲； oracle 中 GIS 數(shù)據(jù)的訪問； Oracle 中 GIS 數(shù)據(jù)的維護。該控制為二進制文件，能夠記錄數(shù)據(jù)的物理結構，主要內容包括：數(shù)據(jù)庫的名稱和屬性、數(shù)據(jù)庫的創(chuàng)建時間點、當前日志的序號、檢驗點信息等等，． ctl表示控制文件的擴展名。4. 3 SpatiaI 簡介 隨著 Oracle 8i 的推出， Spatial Cartridge 將升級為 Oracle Spatial。例如，一條公路可以用實線或連續(xù)像素點或矢量表示的曲線實體，并可以用一定的顏色符號把 GIS 數(shù)據(jù)中要表達的內容完整的表達出來，這樣道路的類型就可以用相應的符號表達出來。本章的內容主要是介紹了 GIS 數(shù)據(jù)的一些相關內容和數(shù)據(jù)庫管理設計內容，主要內容包括 GIS 數(shù)據(jù)的相關概念和內容知識、 Oracle 數(shù)據(jù)庫選擇的原因、 GIS 數(shù)據(jù)導入、 GIS 數(shù)據(jù)在數(shù)據(jù)庫中的管理和維護等內容。因此交通阻抗的最小值 為以上各個元素最小值的總和，而最大值為以上各個元素最大值的總和。 (6)算法結束。 3． 3． 2 經(jīng)典 Dijkstra 算 法分析 在 1959 年荷蘭數(shù)學家 EW． Dijkstra 首先提出的 Dijkstra 算法，該算法是一種單源最短路徑的搜索算法，他適用于非負權值網(wǎng)絡的，是目前求解最短路問題的理論上最完備、應用范圍最廣的算法，可以計算出從圖中的某一節(jié)點到其他任意節(jié)點的最短路徑搜索結果 .Dijkstra 是一種迭代的貪心策略的路徑搜索算法，他根據(jù)路徑的長短逐漸增長來搜索點數(shù)，構造了一顆路徑樹，從而得到路徑樹中的根部節(jié)點到其他任意節(jié)點的最短路徑結果。 武漢紡織大學 20xx 屆畢業(yè)設計論文 11 （ 2）數(shù)據(jù)存儲 一般地，在計算機中大多采用利用鄰接表和鄰接矩陣的方法存儲有向圖。按照上述方法對原始的交通道路進行預處理之后就可以確定道路之間的拓撲關系，進而可以建立以道路拓撲 關系為基準的交通系統(tǒng)模型，拓撲關系中包括線性實體之間的模型，線性實體與節(jié)點之問的模型，節(jié)點與節(jié)點之間的模型，以及他們的連通性等。在實際情 況中人民出行是從一個地方到另一個地方，這種不能簡單的歸結在圖中從一個節(jié)點到另一個節(jié)點的轉移，實際情況的交通網(wǎng)絡運行是非常復雜的，所以不能簡單的把某一個具體的地方當成是圖中的某個節(jié)點，把道路信息抽象成圖中帶有權值的邊，而是要將具體的地址信息抽象為節(jié)點以及其附屬信息并加入到交通網(wǎng)絡系統(tǒng)中。 3． 1 建立城市交通模型 利用圖論 的相關理論和知識，對圖中的節(jié)點和邊設法加入車道信息用于模擬就哀痛系統(tǒng)。對幾個經(jīng)典的最優(yōu)路徑選擇算法進行了介紹，如 Floyd 算法、 Dijkstra 算法、 GPSR 算法，并分析了他們的優(yōu)點和不足。在鄰接表中，圖中的每個節(jié)點都會有一個單鏈表與之對應，第 i 個單鏈表中的結點數(shù)據(jù)表示依附于結點 v。每個結點度數(shù)相同的簡單圖稱為正則圖，最大度與最小度恰好相差 1 的簡單圖被稱為幾乎正則圖。前者主要研究圖的性質，后者主要討論與圖有關的優(yōu)化問題。但該算法存在這一定的缺點，當網(wǎng)絡中的某節(jié)點與源點集中在兩個區(qū)域時，由于通信的不平衡能夠導致部分節(jié)點無效，從而是網(wǎng)絡的連通性遭到破壞；另一方面是該方法需要 GPS 定位系統(tǒng)的輔助來計算幾點的位置信息 。這種拓展邊的迭代運算一直進行，一直運行到所有的 dM都代表從 S到 v 最短路徑為止。 武漢紡織大學 20xx 屆畢業(yè)設計論文 4 2． 1． 2 Dijkstra 算法 Dijkstra 算法由荷蘭數(shù)學家 Edsger Wybe Dijkstra 在 1959 年提出來的，是一種單源最短路算法適用于非負權值網(wǎng)絡的計算，是目前在求解最短路徑問題較為完備且應用廣泛的算法之一，可以計算出圖中從指定結點到圖中其他任意節(jié)點之問的最短路徑。實際情況下最優(yōu)路徑選擇問題包括兩層含義：首先最優(yōu)路徑是一條可以從 A 地到達 B 地的暢通的路徑；其次這條路徑在所有路徑當 中是最佳的。最優(yōu)路徑問題按照是否是單源問題還可以分為單源最優(yōu)路徑選擇問題及全源最優(yōu)路徑選擇問題。日前網(wǎng)絡發(fā)展十分迅速，而網(wǎng)絡的構成類似交通道路系統(tǒng)，可以利用最優(yōu)路徑算法來解決很多網(wǎng)絡方面的問題。在交通、計算機、電子通信、信息技術和系統(tǒng)科學與工程應用領域中，智能交通系統(tǒng)是日前許多國內外學者和研究機構集中、深入的 研究 領域之一，具有非常好的發(fā)展前景。 GIS data。對道路交通系統(tǒng)的建模、最優(yōu)路徑選擇算法的研究以及數(shù)據(jù)庫的開發(fā)設計目的是建立一套接近實際情況的最優(yōu)路徑選擇系統(tǒng)。 武漢紡織大學 畢 業(yè)設計 (論文 ) 交通線路選擇軟件的設計與實現(xiàn) 姓 名： 學 號： 1003741126 學 院： 電子與電氣工程學院 指 導 老 師： 肖 適 20xx 年 5 月 30 日 I 摘 要 隨著社會經(jīng)濟的飛速發(fā)展，出行方式的多樣選擇，設計和研究一套簡單交通線路選擇軟件，成為利民便民和增強 市場競爭力的重要舉措。本文將經(jīng)典的 Dijkstra 算法和改 進的 Dijkstra 算法進行編碼實現(xiàn)，使之在最優(yōu)路徑選擇系統(tǒng)中正確運行。 System design。 在我國，隨著交通運輸業(yè)的不斷發(fā)展，交通環(huán)境日益惡化的今天，研究出一套能夠適應我國國情的現(xiàn)代智能交通系統(tǒng)和車輛導航系統(tǒng)，使之能夠為人們出行提供重要的交通信息，避免交通擁堵，減少交通事故，為駕駛者提供最佳的駕駛路徑，達到交通的路網(wǎng)暢通已經(jīng)迫在眉睫。經(jīng)典學科中的圖論、數(shù)論與計算機科學以及數(shù)據(jù)結構與算法的有效結合使得對最優(yōu)路徑算法的研究有了很大進展。其中單源最優(yōu)路徑選擇問題更具有實際應用的意義，而且良好的單源路勁問題的算法可為全源最優(yōu)路徑問題提供良好的研究基礎，因此本文在研究最優(yōu)路徑選擇問題的過程 中 只考慮單源最優(yōu)路徑選擇問題。從 A 地到 B 地想要找一條最優(yōu)路徑，應是一條的所用時間最短、駕駛者最舒適、道路上的車輛數(shù)量較少，或對交通車輛的損耗最少。在一個圖 G 中， Dijkstra 算法不但可以給出兩指定結點之間的一條具有權值最下送的路徑，且還可找出從指定點到圖 G 中所有結點的最短路徑。算法需要維護兩個結點集 Q 和 P，集合 P 保留了我們通過迭代運算所得的所有 dM的最短路徑的值結點，而集合 Q 則保留其他剩下的所有結點。 GPSR 中貪婪轉發(fā)算法能夠正常轉發(fā)數(shù)據(jù)的前提是：目的結點的位置都包含于每個數(shù)據(jù)分組中，每個結點都有鄰居結點列表信息以及鄰居結點和本結點的位置信息。最優(yōu)化圖論既可以算作圖論中的一個研究方向，也可以看作運籌學中最優(yōu)化理論的組成部分。圖的結點的個數(shù)稱為圖的階。三個域構成了每個節(jié)點，其中結點的鄰接點域的數(shù)值表示與結點 相鄰節(jié)點在圖中的具體位置，結點的鏈域將指示下一條邊的結點，結點數(shù)據(jù)域存儲的是圖中邊的信息，如權值、方向等。圖論在近幾十年來得到了飛速的發(fā)展，尤其是與物理學、化學理論、信息理論、運籌學、計算機理論、控制論、社會科學等 不同領域和學科的結合方面。以完整的交通道路網(wǎng)絡作為模型建立對象，只需要對道路中的相關數(shù)據(jù)和參數(shù)進行顯示和計算，但在實際的交通道路當中，交通特征是實時變化的，這與交通道路模型密不可分。交通地址的交叉口所抽象的節(jié)點和將具體地址被抽象成圖中的節(jié)點是不相等價的，需要考慮實際情況，因此交通節(jié)點的阻抗值應該視具體情況而定，而表示地名的節(jié)點的阻抗值可以視為零。使用圖中的節(jié)點表示交通系統(tǒng)的的較差路徑，道路交叉即是圖中的節(jié)點，兩個節(jié)點之間的道路在圖中用弧表示，就是圖的邊，路段的長度以及消耗時問等信息則為邊帶有的權值。順序表 V0， V1， ?Vm1。 假 設帶權值的有向圖武漢紡織大學 20xx 屆畢業(yè)設計論文 12 為 G=(V， E)，其中 V 是數(shù)量為 n 的結點集， E是數(shù)量為 m的邊集， w為權值 向量。 當算法結束時，集合 S 中的每個節(jié)點，其 d值表示的就是原始節(jié)點到達該節(jié)點利用最短路徑所耗費的市靜安。在路徑選擇中，有出行時間長度、行駛距離長度、擁擠程度、道路質量和出行費用等評價指標，以提供不同的應用環(huán)境進行選擇使用。 4． 1 GIS 數(shù)據(jù)模型建立 數(shù)據(jù)模型是能夠描述數(shù)據(jù)內在特征的工具，也是一門描述語言，是現(xiàn)實世武漢紡織大學 20xx 屆畢業(yè)設計論文 15 界中對某種或某類特征的模擬、抽象、提取和組織。而道路的屬性數(shù)據(jù)就由于道路的寬度、路面結構、修繕日期、水管電纜走向和位置、特殊交通規(guī)則標記以及現(xiàn)實空間世界 外模式 外模式 外模式 概念數(shù)據(jù)模型 邏輯數(shù)據(jù)模型 物理數(shù)據(jù)模型 武漢紡織大學 20xx 屆畢業(yè)設計論文 16 某一時間的車流量等。在新的數(shù)據(jù)庫工具中，新的表示數(shù)據(jù)空間類型的抽系那個數(shù)據(jù)類型被提出，用(ADT)一 SDOGEOMETRY 來表示， (ADT)一 SDO GEOMETRY 可以將數(shù)據(jù)存儲在一列中，Oracle Spatial 發(fā)展了新型的數(shù)據(jù)庫管理方式，也對索引機制進行了一體化管理進 行了優(yōu)化，增加了緩沖區(qū)生成、二級過濾和疊加分析等新的數(shù)據(jù)處理過程。 4． 5 GIS 數(shù)據(jù)在 OracIe中的存儲 在數(shù)據(jù)庫中可以存儲多種 空問數(shù)據(jù)，根據(jù)實驗的需要，本文只介紹與我們實驗和研究內容相關的空間數(shù)據(jù)，包括道路數(shù)據(jù)，道路節(jié)點數(shù)據(jù)，分層路段數(shù)據(jù)，和多比例尺道路數(shù)據(jù)等。數(shù)據(jù)庫在整個程序系統(tǒng)設計與實現(xiàn)中起到非常重要的，可以說數(shù)據(jù)庫選擇和設計的好壞直接影響到系統(tǒng)的性能，和系統(tǒng)工作的效率，影響到路徑選擇的最優(yōu)效率。同時關鍵性的代碼和運行結果界面，將經(jīng)典的 Dijkstra 算法也進行了編碼實現(xiàn)，把 Dijkstra、分層 A*、速度模式概念的引入以及出行者容忍度等改進的分層 A*算法進行比較，證明改進的算法具有可行性。在系統(tǒng)開發(fā)方面，對 各項 數(shù)據(jù)模型進行了分析，使用 Oracle 數(shù)據(jù)庫 進行學習編譯 ，建立了最優(yōu)路徑選擇系統(tǒng)。 最后，感謝 曾幫助我的那些同學， 謝謝你們 對我論文寫作中的給予的意 見建議， 感謝你們