【文章內(nèi)容簡介】 O(N log N)。 （三）研究內(nèi)容 本文的研究范疇是智能交通系統(tǒng)中的最短路徑算法，研究領(lǐng)域是城市路網(wǎng)中的限制搜索區(qū)域最短路徑算法，研究內(nèi)容是典型城市路網(wǎng)中最短路徑算法的理論研究及實(shí)驗(yàn)驗(yàn)證，研究目的是保證查詢結(jié)果可靠的情況下，最大程度降低最短路徑查詢時(shí)間，研究方法是充分研究和利用城市路網(wǎng)的特 征參數(shù)，降低最短路徑算法冗余度和復(fù)雜度，性能驗(yàn)證是軟件仿真預(yù)測和實(shí)測數(shù)據(jù)統(tǒng)計(jì)雙重評估標(biāo)準(zhǔn) 。 （四） 論文結(jié)構(gòu) 論文共分為六個(gè)章節(jié)，各章內(nèi)容組織如下 : 第一章為緒論，首先敘述了本課題研究的背景意義，然后依次回顧了智能交通系統(tǒng)的發(fā)展歷程，介紹了最短路徑算法的研究現(xiàn)狀，最終引出論文的工作內(nèi)容 并給出了論文組織結(jié)構(gòu)。 第二章是本文的理論研究基礎(chǔ)，介紹城市路網(wǎng)中各種限制搜索區(qū)域最短路徑算法，著重討論了Dij kstra算法、 Floyd算法的運(yùn)行機(jī)理。 第三章是 介紹了系統(tǒng)的開發(fā)工具及系統(tǒng)的運(yùn)行環(huán)境 。 第四章 分析 交通咨詢系統(tǒng)的最短路徑 算法實(shí)現(xiàn)代碼的編寫 。 第五章 簡要介紹了系統(tǒng)的界面設(shè)計(jì) 。 第六章 總結(jié)，提出文章的缺點(diǎn)與不足之處，談?wù)勛约旱南敕?，并提出發(fā)展期望 。 二、 最短路徑算法 相關(guān)原理 本章介紹城市路網(wǎng)中各種限制搜索區(qū)域最短路徑算法，重點(diǎn)討論 Dijkstra 算法、 Floyd 算法的實(shí)現(xiàn)原理。 （一） Dijkstra 算法 Dijkstra 算法是一個(gè)按權(quán)值大小遞增的次序產(chǎn)生最優(yōu)路徑的算法，用于計(jì)算從有向圖中任意結(jié)點(diǎn)到其他結(jié)點(diǎn)的最優(yōu)路徑。 設(shè)一個(gè)有向圖 G=(V,E),已知各邊的權(quán)值，以某指定點(diǎn) 為源點(diǎn)，求到圖的其余各點(diǎn)的最短路徑。 5 1959 年狄克斯特拉（ Dijkstra）提出一個(gè)按路徑“長度”遞增的次序產(chǎn)生最短路徑的算法，即：把圖中所有的頂點(diǎn)分成兩組，第一組 S包括已經(jīng)確定最短路徑的頂點(diǎn)，初始時(shí)只含有源點(diǎn)；第二組 VS中包括尚未包括最短路徑的頂點(diǎn)，初始時(shí)含有圖中初源點(diǎn)之外的所有其他頂點(diǎn)。按路徑長度遞增的順序計(jì)算源點(diǎn)到各頂點(diǎn)的最短路徑，逐個(gè)把第二組中的頂點(diǎn)加到第一組中去，直至 V=S。 有向網(wǎng)用鄰接矩陣 cost[][]表示，其中規(guī)定：（ 1）如果兩個(gè)頂點(diǎn)之間無直接路徑，即 弧對應(yīng)權(quán) 值為無窮大；（ 2）兩個(gè)頂點(diǎn)之間有直接路徑 的，矩陣中的權(quán)值就是 弧對應(yīng)的公路長度；（ 3） 對應(yīng)的值為 0。 S 集合初始存放最短路徑的源點(diǎn)，計(jì)算過程中將已經(jīng)確定了最短路徑的頂點(diǎn)加到 S中去。 Dist 數(shù)組最終存放源點(diǎn)到各頂點(diǎn)的最短路徑結(jié)果。 Path 數(shù)組最終存放源點(diǎn)到個(gè)頂點(diǎn)的最短路徑經(jīng)過的頂點(diǎn)。 如下圖所示： 由 F到 A的路徑有三條： F A： 24； F B A： 5+18=23； F B C A： 5+7+9=21 第一條最短路徑為與源點(diǎn) V鄰接頂點(diǎn)的弧集合中， 權(quán)值最小的弧。 下一條長度次短的最短路徑是：假設(shè)該次短路徑的終點(diǎn)是 ，則這條路徑或者是 ， 或者是 ，它的長度或者是從V到 弧上的權(quán)值，或者是 V到 路徑長度與 到 的弧上權(quán)值之和。 引進(jìn)一個(gè)輔助向量 D，它的每個(gè)分量 D[i]表示當(dāng)前找到的從 源點(diǎn) V到每 個(gè)終點(diǎn) 的最短路徑的長度。設(shè)用帶權(quán)的鄰接矩陣 dist[i][j]來表示有向圖， dist[i][j]表示弧 上的權(quán)值，若不存在，則置 dist[i][j]為某一最大值。向量 S為已找到從 V出發(fā)的最短路徑的終點(diǎn)的集合，其初始值為空集。算法按下面的步驟進(jìn)行： 6 ① 從 V出發(fā)到圖 上其余各個(gè)頂點(diǎn)（終點(diǎn)） 可能達(dá)到的最短路徑長度的初始值為： D[i]=dist[ORDINAL(V)][i]， Vi∈ V 其中 ORDINAL(V)表示頂點(diǎn) V在有向圖中的序號 ② 選擇 Vj，使 D[j]=Min{D[i]|Vi S， Vi∈ V} Vj就是當(dāng)前求得的一條從 V出發(fā)的最短路徑的終點(diǎn)，且令 S=S∪ {j} 即將 j加入到 S集合中。 ③ 修改從 V出發(fā)到集合 VS上所有頂點(diǎn) Vk 可達(dá)到的最短路徑長度。如果 D[j]+dist[j][k]D[k] 則 修改 D[k]為 D[k]=D[j]+dist[j][k] ④ 重復(fù)操作 （ 2），（ 3） 共 n1 次。最后求得從 V 到圖上其余各定點(diǎn)的最短路徑是依路徑長度遞增的序列。 例：對上圖，鄰接矩陣為 最短路徑求解過程圖例， F為源點(diǎn)； ①
初始狀態(tài) ， A B C D E F S D 求得 min{D}={24,5, ∞ ,25, ∞ }=5，最短路徑 F B ② 以 D[j]修改（即 F B路徑長度修改 ） 向量 D， A B C D E F S 0 0 0 0 0 1 24 5 ∞ 25 ∞ 0 FA FB 無 FD 無 無 0 1 0 0 0 1 7 D 求得 min{D}={23,12, 25, ∞ }=12，最短路徑 F B C ③ 以 D[j]修改（即 F B C路徑長度修改）向量 D， A B C D E F S D 求得 min{D}={21, 25, ∞ }=21，最短路徑 F B C A ④ 以 D[j]修改（即 F B C A路徑長度修改）向量 D， A B C D E F S D 求得 min{D}={25, ∞ }=25，最短路徑 F D ⑤ 以 D[j]修改（即 F D路徑長度修改）向量 D， A B C D E F S D 求得 min{D}={∞ }=∞ ， 即 F E無路徑 （二） Floyd 算法 FloydWarshall算法 （ FloydWarshall algorithm）是解決任意兩點(diǎn)間的最短路徑的一種算法，可以正確處理有向圖或負(fù)權(quán)的最短路徑問題，同時(shí)也被用于計(jì)算有向圖的傳遞閉包。FloydWarshall算法的時(shí)間復(fù)雜度為 O(N3)，空間復(fù)雜度為 O(N2)。 23 5 12 25 ∞ 0 FBA FB FBC FD 無 無 0 1 1 0 0 1 21 5 12 25 ∞ 0 FBCA FB FBC FD 無 無 1 1 1 0 0 1 21 5 12 25 ∞ 0 FBCA FB FBC FD 無 無 1 1 1 1 0 1 21 5 12 25 ∞ 0 FBCA FB FBC FD 無 無 8 ： Floyd算法是一個(gè)經(jīng)典的動態(tài)規(guī)劃算法。用通俗的語言來描述的話，首先我們的目標(biāo)是尋找從點(diǎn) i到點(diǎn) j的最短路徑。從動態(tài)規(guī)劃的角度看問題，我們需要為這個(gè)目標(biāo)重新 做一個(gè)詮釋（這個(gè)詮釋正是動態(tài)規(guī)劃最富創(chuàng)造力的精華所在） 從任意節(jié)點(diǎn) i到任意節(jié)點(diǎn) j的最短路徑不外乎 2種可能， 1是直接從 i到 j， 2是從 i經(jīng)過若干個(gè)節(jié)點(diǎn) k到 j。所以，我們假設(shè) Dis(i,j)為節(jié)點(diǎn) u到節(jié)點(diǎn) v的最短路徑的距離，對于每一個(gè)節(jié)點(diǎn)k，我們檢查 Dis(i,k) + Dis(k,j) Dis(i,j)是否成立，如果成立，證明從 i到 k再到 j的路徑比 i直接到 j的路徑短，我們便設(shè)置 Dis(i,j) = Dis(i,k) + Dis(k,j)，這樣一來，當(dāng)我們遍歷完所有節(jié)點(diǎn) k， Dis(i,j)中記錄的便是 i到 j的 最短路徑的距離。 ： 。所有兩點(diǎn)之間的距離是邊的權(quán)，如果兩點(diǎn)之間沒有邊相連，則權(quán)為無窮大。 u 和 v，看看是否存在一個(gè)頂點(diǎn) w 使得從 u 到 w 再到 v 比己知的路徑更短。如果是更新它。 算法過程矩陣的計(jì)算 十字交叉法 方法：兩條線，從左上角開始計(jì)算一直到右下角 如下所示給出矩陣，其中矩陣 A是鄰接矩陣，而矩陣 Path記錄 u,v兩點(diǎn)之間最短路徑所必須經(jīng)過的點(diǎn) 相應(yīng)計(jì)算方法如下： 9 10 最后 A3即為所求結(jié)果 。 三、開發(fā)工具與環(huán)境 （一） Java 技術(shù) 1. Java 簡介 Java是由 SunMicrosystems公司于 1995年 5月推出的 Java程序設(shè)計(jì)語言（以下簡稱 Java語言）和 Java平臺的總稱。用 Java實(shí)現(xiàn)的 HotJava瀏覽器（支持 Javaapplet）顯示了 Java的魅力：跨平臺、動感的 Web、 Inter 計(jì)算。從此， Java 被廣泛接受并推動了 Web 的迅速發(fā)展，常用的瀏覽器現(xiàn)在均支持 Javaapplet。另一方面， Java技術(shù)也不斷更新。 Java 平臺由 Java 虛擬機(jī)（ Java Virtual Machine）和 Java 應(yīng)用編程接口（ Application ProgrammingInterface、簡稱 API）構(gòu)成。 Java應(yīng)用編程接口為 Java 應(yīng)用提供了一個(gè)獨(dú)立于操 作系統(tǒng)的標(biāo)準(zhǔn)接口，可分為基本部分和擴(kuò)展部分。在硬件或操作系統(tǒng)平臺上安裝一個(gè) Java平臺之后，Java 應(yīng)用程序就可運(yùn)行?，F(xiàn)在 Java 平臺已經(jīng)嵌入了幾乎所有的操作系統(tǒng)。這樣 Java 程序可以只編譯一次，就可以在各種系統(tǒng)中運(yùn)行。 Java應(yīng)用編程接口已經(jīng)從 。目前常用的 Java平臺基于 ，最近版本為 。 Java分為三個(gè)體系 JavaSE， JavaEE， JavaME。 Java的特點(diǎn)是 ： (1) Java 的簡單性：和 C++相比，語法簡單了，取消了指針的語法；內(nèi)存分配和 回收不需要我們來過渡關(guān)注， C++可以多繼承，但 java只能是單繼承，相對于類來說。（注：接口可以多繼承）使用 Asp可以組合 HTML頁、腳本命令和 ActiveX組件以創(chuàng)建交互的 Web 頁和基于 Web的功能強(qiáng)大的應(yīng)用程序。 (2) java面向?qū)ο螅?java算是純面向?qū)ο?，?jquery是更純的面向?qū)ο蟆? 在 java編程 思想這本書說過，“ Everything is object!” 這樣便于人類的構(gòu)思和設(shè)計(jì)，更符 合人們的思考問題方式。 (3) 分布式：主要還是用在 EJB上 。 (4) 安全性： java的語法限定了源程序的安全性，首先編譯器會進(jìn)行源代碼的第一步檢查 。 (5) 跨平臺： java 能夠跨越不同的操作系統(tǒng)平臺，平臺無關(guān)性 怎么跨平臺呢？ 主要是在不同的操作系統(tǒng)中， JVM規(guī)范都是一樣的，被 JVM加載成各個(gè)操作系統(tǒng)所支持的，屏蔽了底層操作系統(tǒng)的差異 。 (6) 高性能：開閉原則 對擴(kuò)展開放，對修改關(guān)閉 java是即時(shí)編譯的。 (7) 多線程。 11 的處理流程 (1) 首先編輯 .java源程序 。 (2) 編譯成 .class字節(jié)碼文件 byte code（一種二進(jìn)制文件） 。 (3) 最后被 java虛擬機(jī) （ JVM）加載解釋并執(zhí)行 。 四、 交通咨詢系統(tǒng)的實(shí)現(xiàn) （一）系統(tǒng)分析 為了保證系統(tǒng)能夠長期、安全、穩(wěn)定、可靠、高效的運(yùn)行，系統(tǒng)應(yīng)該滿足以下的性能需求： 統(tǒng)一處理的準(zhǔn)確性和及時(shí)性：系統(tǒng)處理的準(zhǔn)確性和及時(shí)性是系統(tǒng)的必要性能。在系統(tǒng)設(shè)計(jì)和開發(fā)過程中，要充分考慮系統(tǒng)當(dāng)前和將來可能承受的工作量，使系統(tǒng)的處 理能力和響應(yīng)時(shí)間能夠滿足企業(yè)對員工信息處理的需求。 系統(tǒng)的開放性和可擴(kuò)充性：系統(tǒng)在開發(fā)過程中，應(yīng)該充分考慮以后的可擴(kuò)充性。例如數(shù)據(jù)表中用戶選擇字段方式的改變，用戶查詢的需求也會不斷的更新和完善。所有這些，都要求系統(tǒng)提供足夠的手段進(jìn)行功能的調(diào)整和擴(kuò)充。而要實(shí)現(xiàn)這一點(diǎn)，應(yīng)通過系統(tǒng)的開放性來完成，既系統(tǒng)應(yīng)是一個(gè)開放系統(tǒng)，只要符合一定的規(guī)范，可以簡單的加入和減少系統(tǒng)的模塊，配置系統(tǒng)的硬件。通過軟件的修補(bǔ)、替換完成系統(tǒng)的升級和更新?lián)Q代。 系統(tǒng)的易用性和易維護(hù)性：要實(shí)現(xiàn)這一點(diǎn)，就要求系統(tǒng)應(yīng)該盡量使用用戶熟悉的術(shù)語和中文 信息的界面；針對用戶可能出現(xiàn)的使用問題，要提供足夠的在線幫助，縮短用戶對系統(tǒng)熟悉的過程。 系統(tǒng)的數(shù)據(jù)要求： (1) 數(shù)據(jù)錄入和處理的準(zhǔn)確性和實(shí)時(shí)性； (2) 數(shù)據(jù)的一致性與完整性； (3) 數(shù)據(jù)的共享與獨(dú)立性。 設(shè)計(jì)內(nèi)容 ： 設(shè)計(jì)一個(gè)交通咨詢系統(tǒng)，能讓旅客咨詢?nèi)我庖粋€(gè)城市到另一個(gè)城市之間的最短路徑問題。 該交通咨詢系統(tǒng)設(shè)計(jì)共三部分，一是建立交通網(wǎng)絡(luò)圖的存儲結(jié)構(gòu)；二是解決單源路徑問題；最后再實(shí)現(xiàn)兩個(gè)城市之間的最短路徑問題。 12 設(shè)計(jì)思想 用鄰接矩陣來存儲交通