【正文】 息開始回溯，一直回溯到起始的源節(jié)點(diǎn)，最后報(bào)告結(jié)果路徑 。另外，該算法只是路徑搜索，對于交通網(wǎng)絡(luò)中的路徑權(quán)值問題沒有任何解決辦法，因此該算法可以作為最優(yōu)路徑選擇的主要路徑搜索算法，而對于權(quán)值的提取和計(jì)算，需要額外 增加輔助算法來完成，能夠反映交通網(wǎng)絡(luò)系統(tǒng)在實(shí)時(shí)狀態(tài)下權(quán)值的變化情況 。 最初 Dijkstra 算法開發(fā)的目的是計(jì)算網(wǎng)絡(luò)圖中兩節(jié)點(diǎn)之間的最短路徑問題，當(dāng)該算法應(yīng)用到交通網(wǎng)絡(luò)的最短路徑搜索時(shí)，由于起始 點(diǎn)和終止點(diǎn)都是已知的，因此只需要從起始點(diǎn)開始搜索，按照其搜索原則尋找最短路徑，一直搜索的終止點(diǎn)為止，需要對該算法進(jìn)行優(yōu)化和改進(jìn)，才能使用到交通網(wǎng)絡(luò)的最優(yōu)路徑選擇系統(tǒng)當(dāng)中。 假 設(shè)帶權(quán)值的有向圖武漢紡織大學(xué) 20xx 屆畢業(yè)設(shè)計(jì)論文 12 為 G=(V， E)，其中 V 是數(shù)量為 n 的結(jié)點(diǎn)集， E是數(shù)量為 m的邊集， w為權(quán)值 向量。道路的權(quán)值是計(jì)算現(xiàn)實(shí)問題中最短路徑的基礎(chǔ)，最優(yōu)路徑選擇的準(zhǔn)確與否在很大程度上取決于道路權(quán)值的設(shè)計(jì)和計(jì)算。求解過程包括以下四個(gè)步驟酬： (1)交通網(wǎng)絡(luò)模型建立； (2)交通道路權(quán)重的計(jì)算； (3)利用最短路徑計(jì)算方法求解交通網(wǎng)絡(luò)中的最短路徑問題； (4)將交通網(wǎng)絡(luò)圖中的最短路徑問題轉(zhuǎn)化為現(xiàn)實(shí)交通網(wǎng)絡(luò)中的路段集合。使用鄰接矩陣來表示圖的存儲淺顯易懂，也可以通過鄰接矩陣來存儲邊的權(quán)值信息和節(jié)點(diǎn)信息以及他們之間的連同情況等等，因此在本文中也利用鄰接表和鄰接矩陣方法 。順序表 V0， V1， ?Vm1。如果某條道路出現(xiàn)禁止 通行的限制信息，用節(jié)點(diǎn)的交通限制信息來表示 。 交通路徑的限制信息是交通導(dǎo)航中需要終點(diǎn)考慮的因素，比如由于施工、交通事故、速度限制、惡劣天氣造成的交通限制等，實(shí)際的道路中交通限制信息十分復(fù)雜，而且隨時(shí)發(fā)生變化。節(jié)點(diǎn)圖層表示交通交叉口或者道路的起始點(diǎn)或終止點(diǎn)，用點(diǎn)對象來表示，路段圖層存儲這連接各個(gè)節(jié)點(diǎn)的交通路徑以及他們的屬性信息，用線對象表示。使用圖中的節(jié)點(diǎn)表示交通系統(tǒng)的的較差路徑，道路交叉即是圖中的節(jié)點(diǎn)，兩個(gè)節(jié)點(diǎn)之間的道路在圖中用弧表示，就是圖的邊，路段的長度以及消耗時(shí)問等信息則為邊帶有的權(quán)值。 3． 2． 2 交通路徑模型建立與數(shù)據(jù)存儲 （ 1）交通路徑模型的建立 最短路徑選擇的前提是對交通系統(tǒng)創(chuàng)建合適的模型。 3． 2 交通模型數(shù)據(jù)存儲 3． 2． 1 數(shù)據(jù)預(yù)處理 在實(shí)際應(yīng)用中，一般將交通網(wǎng)絡(luò)模型用矢量化的數(shù)據(jù)地圖表示，為了建立交通網(wǎng)絡(luò)可使用的數(shù)據(jù)模型，需要對原始道路構(gòu)成的交通網(wǎng)絡(luò)矢量圖進(jìn)行優(yōu)化武漢紡織大學(xué) 20xx 屆畢業(yè)設(shè)計(jì)論文 10 和預(yù)處理，建立相應(yīng)的拓 撲關(guān)系圖譜。實(shí)際生活中的道路不能簡單的抽象為一條直線，因?yàn)橛行┑缆反嬖诤芏嘬嚨?，每個(gè)車道的屬性信息不盡相同，多車道的交通道路屬性信息較為復(fù)雜。交通地址的交叉口所抽象的節(jié)點(diǎn)和將具體地址被抽象成圖中的節(jié)點(diǎn)是不相等價(jià)的，需要考慮實(shí)際情況，因此交通節(jié)點(diǎn)的阻抗值應(yīng)該視具體情況而定，而表示地名的節(jié)點(diǎn)的阻抗值可以視為零。 3． 1． 1 道路節(jié)點(diǎn)模型 可以將交通網(wǎng)絡(luò)抽象成一個(gè)有向圖，圖中的邊帶有一定的權(quán)值，但這個(gè)抽象的有向圖如何建立起來需要視具體的應(yīng)用環(huán)境而定。武漢紡織大學(xué) 20xx 屆畢業(yè)設(shè)計(jì)論文 9 由于在節(jié)點(diǎn)圖層和路段圖層中分別存儲的點(diǎn)、線圖元是分別獨(dú)立的，兩個(gè)圖層問不想關(guān)聯(lián)。例如：在早晚的上下班的高峰區(qū)段，進(jìn)出同一區(qū)域的同一條道路在不同方向表現(xiàn)的車流量是明顯不同的，交通擁堵現(xiàn)象大多數(shù)情況下是發(fā)生在某條車道的單向車道上。以完整的交通道路網(wǎng)絡(luò)作為模型建立對象，只需要對道路中的相關(guān)數(shù)據(jù)和參數(shù)進(jìn)行顯示和計(jì)算，但在實(shí)際的交通道路當(dāng)中，交通特征是實(shí)時(shí)變化的，這與交通道路模型密不可分。在同一一條道路上不同方向的車道具有不同的交通特性，如交通規(guī)則變化、交通量變化等。 以圖的理論為研究基礎(chǔ)研究交通道路模型，采用改進(jìn)的方法使得道路的車道信息加入到節(jié)點(diǎn)和邊的信息中。因此，應(yīng)當(dāng)首先考慮交通流的特征。圖論在近幾十年來得到了飛速的發(fā)展，尤其是與物理學(xué)、化學(xué)理論、信息理論、運(yùn)籌學(xué)、計(jì)算機(jī)理論、控制論、社會(huì)科學(xué)等 不同領(lǐng)域和學(xué)科的結(jié)合方面。 2． 3 本章小結(jié) 本章對最優(yōu)路徑算法和圖論的相關(guān)理論知識進(jìn)行了簡單概述?？梢钥闯墒且环N新的鏈表，該鏈表將有向圖的鄰接表和逆鄰接表結(jié)合在一起。這些表頭結(jié)點(diǎn)存儲數(shù)據(jù)的形式通常是順序存儲的，這樣存儲方式便于隨即訪問任何一個(gè)節(jié)點(diǎn)的 鏈表信息。三個(gè)域構(gòu)成了每個(gè)節(jié)點(diǎn)，其中結(jié)點(diǎn)的鄰接點(diǎn)域的數(shù)值表示與結(jié)點(diǎn) 相鄰節(jié)點(diǎn)在圖中的具體位置，結(jié)點(diǎn)的鏈域?qū)⒅甘鞠乱粭l邊的結(jié)點(diǎn)，結(jié)點(diǎn)數(shù)據(jù)域存儲的是圖中邊的信息，如權(quán)值、方向等。 圖 21 圖的結(jié)構(gòu) 武漢紡織大學(xué) 20xx 屆畢業(yè)設(shè)計(jì)論文 7 2． 2． 3 圖的存儲 (1)鄰接表 鄰接表結(jié)構(gòu)： 圖 22 鄰接表結(jié)構(gòu)表節(jié)點(diǎn)和頭結(jié)點(diǎn) 鄰接表以一種以鏈?zhǔn)酱鎯Y(jié)構(gòu)所構(gòu)成的圖。 V中的元素為結(jié)點(diǎn)， E中的元素為邊。圖 G(V， E)由其結(jié)點(diǎn)與邊之間的關(guān)系確定，且是唯一的。圖的結(jié)點(diǎn)的個(gè)數(shù)稱為圖的階。每條邊與邊兩端的節(jié)點(diǎn)是相互關(guān)聯(lián)的因此稱為相互關(guān)聯(lián)，與同一條邊相關(guān)聯(lián)的節(jié)點(diǎn)或者與同一個(gè)節(jié)點(diǎn)相互關(guān)聯(lián)的邊稱為相鄰的節(jié)點(diǎn)或者相鄰的邊，具有相同兩個(gè)節(jié)點(diǎn)的邊稱為重合邊或者是平行邊，兩個(gè)節(jié)點(diǎn)相同的邊組成環(huán)，簡單圖就是沒有環(huán)和重邊的圖。如果 P是一條邊“， 39。因此圖論中的圖能夠代表多種含義，因此圖論在諸多領(lǐng)域都有著非常廣泛的應(yīng)用。最優(yōu)化圖論既可以算作圖論中的一個(gè)研究方向，也可以看作運(yùn)籌學(xué)中最優(yōu)化理論的組成部分。目前在圖論領(lǐng)域中形成了兩個(gè)不同的方向：抽象圖論和最優(yōu)化圖論。圖論是數(shù)學(xué)學(xué)科當(dāng)中比較年輕的一個(gè)分支。在電子地圖中，每個(gè)路口都有坐標(biāo)位置和列表信息，那么在算法程序中我們首先要做的是讓每個(gè)結(jié)點(diǎn)都包含一條鄰居結(jié)點(diǎn)鏈表，并將結(jié)點(diǎn)號與位置信息關(guān)聯(lián)起來。 GPSR 中貪婪轉(zhuǎn)發(fā)算法能夠正常轉(zhuǎn)發(fā)數(shù)據(jù)的前提是：目的結(jié)點(diǎn)的位置都包含于每個(gè)數(shù)據(jù)分組中，每個(gè)結(jié)點(diǎn)都有鄰居結(jié)點(diǎn)列表信息以及鄰居結(jié)點(diǎn)和本結(jié)點(diǎn)的位置信息。該方法的優(yōu)點(diǎn)在于米面了在節(jié)點(diǎn)信息中存儲建立和維護(hù)路由表信息，只需要利用相鄰節(jié)點(diǎn)進(jìn)行路徑選取即可進(jìn)行，幾乎是不需要任何協(xié)議輔助；并且利用歐氏距離最小的方法進(jìn)行路由，數(shù)據(jù)傳輸?shù)难訒r(shí)最??；并能夠保證只要網(wǎng)絡(luò)路徑不被破壞，數(shù)據(jù)一定能到傳送到目標(biāo)節(jié)點(diǎn)中去。利用歐氏距離武漢紡織大學(xué) 20xx 屆畢業(yè)設(shè)計(jì)論文 5 計(jì)算距離方法計(jì)算距離該節(jié)點(diǎn)最近的相鄰節(jié)點(diǎn)，但如果數(shù)據(jù)傳輸?shù)哪骋还?jié)點(diǎn)是發(fā)現(xiàn)沒有找到下一個(gè)距離最小的節(jié)點(diǎn)使得數(shù)據(jù)傳送的目標(biāo)節(jié)點(diǎn)時(shí)，導(dǎo)致了數(shù)據(jù)傳輸?shù)氖　? 2． 1． 3 GPSR 算法 GPSR 路 由算法的思路是利用地理位置信息進(jìn)行最優(yōu)路徑選擇，該算法需要通過貪婪轉(zhuǎn)發(fā)算法來建立與其他信息之間的關(guān)聯(lián)和路由。算法需要維護(hù)兩個(gè)結(jié)點(diǎn)集 Q 和 P，集合 P 保留了我們通過迭代運(yùn)算所得的所有 dM的最短路徑的值結(jié)點(diǎn)，而集合 Q 則保留其他剩下的所有結(jié)點(diǎn)。如果這條路徑的長度比已知的路徑長度 d[v]的值小，我們可以用新的路徑來代替原有路徑。如果存在從 S 到 v 的路徑，那么當(dāng)蘇算法結(jié)束時(shí)儲存的信息是 S到 v 的距離最短路徑；如果從 S 到 v的路徑不存在，則 d[V]中儲存信息是無窮大。該算法通過圖中的每個(gè)節(jié)點(diǎn) v 建立額外的信息數(shù)組，存儲從其他任意節(jié)點(diǎn) S 到 v 的最短路徑。在一個(gè)圖 G 中， Dijkstra 算法不但可以給出兩指定結(jié)點(diǎn)之間的一條具有權(quán)值最下送的路徑，且還可找出從指定點(diǎn)到圖 G 中所有結(jié)點(diǎn)的最短路徑。但缺點(diǎn)是時(shí)間復(fù)雜度較高，不適合大規(guī)模數(shù)據(jù)的計(jì)算，耗時(shí)較長。 Floyd算法是一種動(dòng)態(tài)規(guī)劃算法，由于是窮舉法進(jìn)行計(jì)算，因此對于稠密圖效果較好。將圖的節(jié)點(diǎn)和邊的信息計(jì)算利用矩陣計(jì)算來完成，通過一個(gè)圖的權(quán)值矩陣中求出交通網(wǎng)絡(luò)中任意兩點(diǎn)之 間 的最短路徑。從 A 地到 B 地想要找一條最優(yōu)路徑，應(yīng)是一條的所用時(shí)間最短、駕駛者最舒適、道路上的車輛數(shù)量較少，或?qū)煌ㄜ囕v的損耗最少。最優(yōu)路徑問題并不是普通意義上的距離最短路徑選擇問題。目 前，國內(nèi)外學(xué)者己經(jīng)有許多傳統(tǒng)的經(jīng)典算法用來解決路徑優(yōu)化問題，但這些算法具有共同的點(diǎn)就是并沒考慮實(shí)際出行的具體特點(diǎn) 特點(diǎn)，如路況信息、道路質(zhì)量、道路上的車流量等。實(shí)際的交通網(wǎng)絡(luò)是一個(gè)復(fù)雜的動(dòng)態(tài)網(wǎng)絡(luò)系統(tǒng)結(jié)構(gòu)，它包括各種道路的限制信息以及交通流量的實(shí)時(shí)信息，然而現(xiàn)有的所有路徑優(yōu)化算法均是對某種抽象的具體網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行優(yōu)化計(jì)算各種，這就需要對實(shí)際的交通網(wǎng)絡(luò)建立模型。其中單源最優(yōu)路徑選擇問題更具有實(shí)際應(yīng)用的意義，而且良好的單源路勁問題的算法可為全源最優(yōu)路徑問題提供良好的研究基礎(chǔ)，因此本文在研究最優(yōu)路徑選擇問題的過程 中 只考慮單源最優(yōu)路徑選擇問題。各種不同類別的最優(yōu)路徑選擇算法相互組合可以成為解決不同問題的各種各樣算法。 最優(yōu)路徑選擇算法在不同的應(yīng)用條件下可以按照不同的方法進(jìn)行分類。數(shù)學(xué)家 E． W． Dijkstra 在 1959 年就提出了標(biāo)號設(shè)定法用于解決路徑問題，形成了目前仍被視為經(jīng)典的 Dijkstra 算法。經(jīng)典學(xué)科中的圖論、數(shù)論與計(jì)算機(jī)科學(xué)以及數(shù)據(jù)結(jié)構(gòu)與算法的有效結(jié)合使得對最優(yōu)路徑算法的研究有了很大進(jìn)展。 目前 我國 對有許多與最優(yōu)路徑求解相關(guān)的學(xué)科在側(cè)面對這個(gè)問題做過研究，如運(yùn)籌學(xué)、計(jì)算機(jī)科學(xué)、圖論、數(shù)論、交通工程學(xué)理論、地理信息科學(xué)研究等。最佳路勁的算法研究不僅可以應(yīng)用在交通網(wǎng)絡(luò)系統(tǒng)中，而且對出行決策、校車路徑查詢、快遞物流、資源分配等方面也有很好的應(yīng)用價(jià)值。最佳路徑選擇問題是智能交通系統(tǒng)中的重要組成部分，也是交通地理信息系統(tǒng)研究中的一個(gè)熱點(diǎn)問題之一，是出行路徑設(shè)計(jì)與優(yōu)化、現(xiàn)有有限資源重新利用和分配等問題的基礎(chǔ)。 在我國，隨著交通運(yùn)輸業(yè)的不斷發(fā)展，交通環(huán)境日益惡化的今天，研究出一套能夠適應(yīng)我國國情的現(xiàn)代智能交通系統(tǒng)和車輛導(dǎo)航系統(tǒng)，使之能夠?yàn)槿藗兂鲂刑峁┲匾慕煌ㄐ畔?，避免交通擁堵，減少交通事故，為駕駛者提供最佳的駕駛路徑，達(dá)到交通的路網(wǎng)暢通已經(jīng)迫在眉睫。智能交通系統(tǒng)的目標(biāo)是利用現(xiàn)金的計(jì)算機(jī)技術(shù)和先進(jìn)的網(wǎng)絡(luò)管理來減少交通擁堵、交通事故和環(huán)境污染，與此同時(shí)，交通系統(tǒng)能夠有效的正常的運(yùn)行 。通過中西交通道路系統(tǒng)的比較，我國城市交通系統(tǒng)的主要問題包括交通管理技術(shù)落后， 為 從根本上解決問題上述交通擁堵問題 ，并保持大中城市交通可持續(xù)發(fā)展帶動(dòng)城市的可持續(xù)反戰(zhàn)，除了合理地進(jìn)行交通道路等基礎(chǔ)設(shè)施建設(shè)外，另一個(gè)切實(shí)可行的辦法就是進(jìn)西方先進(jìn)的高科技管理技術(shù)改進(jìn)我們的交通系統(tǒng)，并使其符合我國國情，建立高性能高效率的智能城市交通系統(tǒng) (ITS)。不論是上海北京等特大城市還是其他省會(huì)城市或地級市，普遍存在交通問題，城市車輛不斷增多，人口越發(fā)密集，道路環(huán)境不斷惡化等原因都是導(dǎo)致城市交通問題的主要方面。 System design。 Optimal path。 系統(tǒng)設(shè)計(jì) 。 最優(yōu) 路徑 。本文將經(jīng)典的 Dijkstra 算法和改 進(jìn)的 Dijkstra 算法進(jìn)行編碼實(shí)現(xiàn)，使之在最優(yōu)路徑選擇系統(tǒng)中正確運(yùn)行。本文使用了 GIS 數(shù)據(jù)模型與數(shù)據(jù)庫的管理設(shè)計(jì)，主要包括 GIS 數(shù)據(jù)的簡介、選擇 Oracle 的理由、 GIS 數(shù)據(jù)向 Oracle 中的導(dǎo)入和存儲、 Oracle中 GIS 數(shù)據(jù)的訪問和維護(hù)?？紤] 到 實(shí)際道路中存在一定的交通