【文章內(nèi)容簡(jiǎn)介】 探測(cè)到周圍的空洞，并利用右手法則沿著空洞周圍的節(jié)點(diǎn)傳輸數(shù)據(jù)來解決這類問題。該方法的優(yōu)點(diǎn)在于米面了在節(jié)點(diǎn)信息中存儲(chǔ)建立和維護(hù)路由表信息，只需要利用相鄰節(jié)點(diǎn)進(jìn)行路徑選取即可進(jìn)行，幾乎是不需要任何協(xié)議輔助；并且利用歐氏距離最小的方法進(jìn)行路由，數(shù)據(jù)傳輸?shù)难訒r(shí)最?。徊⒛軌虮ＷC只要網(wǎng)絡(luò)路徑不被破壞，數(shù)據(jù)一定能到傳送到目標(biāo)節(jié)點(diǎn)中去。但該算法存在這一定的缺點(diǎn)，當(dāng)網(wǎng)絡(luò)中的某節(jié)點(diǎn)與源點(diǎn)集中在兩個(gè)區(qū)域時(shí)，由于通信的不平衡能夠?qū)е虏糠止?jié)點(diǎn)無效，從而是網(wǎng)絡(luò)的連通性遭到破壞；另一方面是該方法需要 GPS 定位系統(tǒng)的輔助來計(jì)算幾點(diǎ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)的位置信息。在實(shí)際的路線選取過程中，我們將路口與上述的結(jié)點(diǎn)對(duì)用。在電子地圖中，每個(gè)路口都有坐標(biāo)位置和列表信息，那么在算法程序中我們首先要做的是讓每個(gè)結(jié)點(diǎn)都包含一條鄰居結(jié)點(diǎn)鏈表，并將結(jié)點(diǎn)號(hào)與位置信息關(guān)聯(lián)起來。 2． 2 圖論簡(jiǎn)介 圖論 (Graph Theory)是組合數(shù)學(xué)的一個(gè)分支，它源于瑞士數(shù)學(xué)家歐(Euler)1736 年對(duì)于著名的哥尼斯堡七橋問題的解決，從而使歐拉成為了圖論 的創(chuàng)始人。圖論是數(shù)學(xué)學(xué)科當(dāng)中比較年輕的一個(gè)分支。在圖論被提出后的兩百年中，圖論的發(fā)展相對(duì)緩慢，但自從圖論與大量的實(shí)際問題相結(jié)合，在物理學(xué)、化學(xué)、信息論、運(yùn)籌學(xué)、計(jì)算機(jī)科學(xué)、控制論、社會(huì)科學(xué)，經(jīng)濟(jì)管理等各種學(xué)科中找到了更廣泛的應(yīng)用，使圖論在近幾十年來得到了快速的的發(fā)展。目前在圖論領(lǐng)域中形成了兩個(gè)不同的方向：抽象圖論和最優(yōu)化圖論。前者主要研究圖的性質(zhì)，后者主要討論與圖有關(guān)的優(yōu)化問題。最優(yōu)化圖論既可以算作圖論中的一個(gè)研究方向，也可以看作運(yùn)籌學(xué)中最優(yōu)化理論的組成部分。圖論中的圖是由若干節(jié)點(diǎn)以及兩節(jié)點(diǎn)之間的連線所構(gòu)成 的圖形，圖論的研究對(duì)象是圖，這種圖形不考慮點(diǎn)的大小、形狀和邊的形狀、長度、大小以及邊與邊的角度等幾何問武漢紡織大學(xué) 20xx 屆畢業(yè)設(shè)計(jì)論文 6 題，而主要表達(dá)的是點(diǎn)點(diǎn)之間通過線的連通關(guān)系，通?？梢杂脕砻枋瞿承┦挛镏g的相互關(guān)系，即用點(diǎn)來代表事件發(fā)生，用連接兩點(diǎn)的邊表示兩個(gè)事件之間的關(guān)系。因此圖論中的圖能夠代表多種含義，因此圖論在諸多領(lǐng)域都有著非常廣泛的應(yīng)用。 2. 2. 1 圖的概念 無向圖是指有序三元組 (V， E,F)中邊沒有方向，其中集合 y 被稱為結(jié)點(diǎn)集，y中的元素稱為結(jié)點(diǎn)：集合 E被稱為邊集， E中的元素被稱為邊；而函數(shù)是邊集E到無序結(jié)點(diǎn)對(duì)兒所構(gòu)成的 集合的一個(gè)映射關(guān)系，稱之為關(guān)聯(lián)函數(shù)。如果 P是一條邊“， 39。，兩個(gè)結(jié)點(diǎn)，且滿足 F(E)=uv，那么就可稱為 e連接：并且稱Ⅳ， y為 E 的端點(diǎn)。每條邊與邊兩端的節(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)，簡(jiǎn)單圖就是沒有環(huán)和重邊的圖。每個(gè)結(jié)點(diǎn)度數(shù)相同的簡(jiǎn)單圖稱為正則圖，最大度與最小度恰好相差 1 的簡(jiǎn)單圖被稱為幾乎正則圖。圖的結(jié)點(diǎn)的個(gè)數(shù)稱為圖的階。 2． 2． 2 圖的表示 由點(diǎn)集合 V 和點(diǎn)與 點(diǎn)之間的連線的集合 E 所組成的集合對(duì) (V， E)可以構(gòu)成圖，用 G(V,E)來表示。圖 G(V， E)由其結(jié)點(diǎn)與邊之間的關(guān)系確定，且是唯一的。也由它的結(jié)點(diǎn)對(duì)兒之間的鄰接關(guān)系唯一確定。 V中的元素為結(jié)點(diǎn)， E中的元素為邊。節(jié)點(diǎn)集合 V 與邊集合 E 均為有限的圖稱為有限圖。 圖 21 圖的結(jié)構(gòu) 武漢紡織大學(xué) 20xx 屆畢業(yè)設(shè)計(jì)論文 7 2． 2． 3 圖的存儲(chǔ) (1)鄰接表 鄰接表結(jié)構(gòu)： 圖 22 鄰接表結(jié)構(gòu)表節(jié)點(diǎn)和頭結(jié)點(diǎn) 鄰接表以一種以鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)所構(gòu)成的圖。在鄰接表中，圖中的每個(gè)節(jié)點(diǎn)都會(huì)有一個(gè)單鏈表與之對(duì)應(yīng)，第 i 個(gè)單鏈表中的結(jié)點(diǎn)數(shù)據(jù)表示依附于結(jié)點(diǎn) v。三個(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ù)域存儲(chǔ)的是圖中邊的信息，如權(quán)值、方向等。每個(gè)鏈表都會(huì)有一個(gè)表頭結(jié)點(diǎn)與之對(duì)應(yīng)，在表頭結(jié)點(diǎn)中，設(shè)有存儲(chǔ)結(jié)點(diǎn) q 的各個(gè)域及與該信息有關(guān)的相關(guān)數(shù)據(jù)域。這些表頭結(jié)點(diǎn)存儲(chǔ)數(shù)據(jù)的形式通常是順序存儲(chǔ)的，這樣存儲(chǔ)方式便于隨即訪問任何一個(gè)節(jié)點(diǎn)的 鏈表信息。 (2)十字鏈表 十字鏈表針對(duì)有向圖的另一種存儲(chǔ)結(jié)構(gòu)?？梢钥闯墒且环N新的鏈表，該鏈表將有向圖的鄰接表和逆鄰接表結(jié)合在一起。在十字鏈表中，每一條邊都有一個(gè)節(jié)點(diǎn)與之對(duì)應(yīng)，每一個(gè)節(jié)點(diǎn)也有一個(gè)節(jié)點(diǎn)與之對(duì)應(yīng)。 2． 3 本章小結(jié) 本章對(duì)最優(yōu)路徑算法和圖論的相關(guān)理論知識(shí)進(jìn)行了簡(jiǎn)單概述。對(duì)幾個(gè)經(jīng)典的最優(yōu)路徑選擇算法進(jìn)行了介紹，如 Floyd 算法、 Dijkstra 算法、 GPSR 算法，并分析了他們的優(yōu)點(diǎn)和不足。圖論在近幾十年來得到了飛速的發(fā)展，尤其是與物理學(xué)、化學(xué)理論、信息理論、運(yùn)籌學(xué)、計(jì)算機(jī)理論、控制論、社會(huì)科學(xué)等 不同領(lǐng)域和學(xué)科的結(jié)合方面。 adfvex nextarc info data firstarc 武漢紡織大學(xué) 20xx 屆畢業(yè)設(shè)計(jì)論文 8 3 最優(yōu)路徑 最優(yōu)路徑選擇和交通系統(tǒng)優(yōu)化的目的就是是交通流均衡化，合理的在交通系統(tǒng)中分配，提高交通運(yùn)輸效率。因此，應(yīng)當(dāng)首先考慮交通流的特征。一般地，交通網(wǎng)絡(luò)有如下特點(diǎn)： (1)線性分布，交通網(wǎng)絡(luò)結(jié)構(gòu)在空問分布中一般呈現(xiàn)線性特征，因此交通網(wǎng)絡(luò)建?？梢砸揽繄D論的相關(guān)理論和知識(shí)； (2)網(wǎng)絡(luò)分布，交通網(wǎng)絡(luò)是一個(gè)負(fù)載的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，連通性好，結(jié)構(gòu)復(fù)雜： (3)分段分布，交通系統(tǒng)中不同路段的特征一般不同，表現(xiàn)為空間的差異性，且同一路段的不同時(shí)間的交通網(wǎng)絡(luò)特征也可能不同，表現(xiàn)為時(shí)間差異性； (4)動(dòng)態(tài)性特點(diǎn)，交通網(wǎng)絡(luò)上交通狀況不是一層不變的，隨時(shí)間的變化而變化，失意 是 時(shí)變系統(tǒng)： (5)車輛行駛的主觀性，交通網(wǎng)絡(luò)不同于其它網(wǎng)絡(luò)，交通網(wǎng)絡(luò)的主體可以自主的選擇交通路徑，行駛時(shí)間和行駛路線等是他的一個(gè)最顯著特征。 以圖的理論為研究基礎(chǔ)研究交通道路模型，采用改進(jìn)的方法使得道路的車道信息加入到節(jié)點(diǎn)和邊的信息中。以完整的交通道路作為建模的基本單元，但在交通應(yīng)用當(dāng)中，交通特征的變化在交通系統(tǒng)的具體應(yīng)用當(dāng)中經(jīng)常和車道關(guān)聯(lián)密切。在同一一條道路上不同方向的車道具有不同的交通特性，如交通規(guī)則變化、交通量變化等。 3． 1 建立城市交通模型 利用圖論 的相關(guān)理論和知識(shí)，對(duì)圖中的節(jié)點(diǎn)和邊設(shè)法加入車道信息用于模擬就哀痛系統(tǒng)。以完整的交通道路網(wǎng)絡(luò)作為模型建立對(duì)象，只需要對(duì)道路中的相關(guān)數(shù)據(jù)和參數(shù)進(jìn)行顯示和計(jì)算，但在實(shí)際的交通道路當(dāng)中，交通特征是實(shí)時(shí)變化的，這與交通道路模型密不可分。首先，在同一條道路上不同的車道在不同的行駛方向的交通特征可能不同，如交通量變化和交通規(guī)則等。例如：在早晚的上下班的高峰區(qū)段，進(jìn)出同一區(qū)域的同一條道路在不同方向表現(xiàn)的車流量是明顯不同的，交通擁堵現(xiàn)象大多數(shù)情況下是發(fā)生在某條車道的單向車道上。其次， 不同方向的 車道由于具有不同的拓?fù)潢P(guān)系，因此交通規(guī)則有可能不同。武漢紡織大學(xué) 20xx 屆畢業(yè)設(shè)計(jì)論文 9 由于在節(jié)點(diǎn)圖層和路段圖層中分別存儲(chǔ)的點(diǎn)、線圖元是分別獨(dú)立的，兩個(gè)圖層問不想關(guān)聯(lián)。為建立點(diǎn)線各個(gè)元素之間的空間拓?fù)潢P(guān)系，使他們構(gòu)成有機(jī)整體，需要分別在存儲(chǔ)點(diǎn)線信息的兩張表文件中擴(kuò)展一定長度的字段，用對(duì)象的屬性字段之問的相互聯(lián)系來建立交通網(wǎng)絡(luò)圖的拓?fù)潢P(guān)系，這樣就建立了交通網(wǎng)絡(luò)系統(tǒng)的有機(jī)整體即他們的拓?fù)潢P(guān)系結(jié)構(gòu)圖。 3． 1． 1 道路節(jié)點(diǎn)模型 可以將交通網(wǎng)絡(luò)抽象成一個(gè)有向圖，圖中的邊帶有一定的權(quán)值，但這個(gè)抽象的有向圖如何建立起來需要視具體的應(yīng)用環(huán)境而定。在實(shí)際情 況中人民出行是從一個(gè)地方到另一個(gè)地方，這種不能簡(jiǎn)單的歸結(jié)在圖中從一個(gè)節(jié)點(diǎn)到另一個(gè)節(jié)點(diǎn)的轉(zhuǎn)移，實(shí)際情況的交通網(wǎng)絡(luò)運(yùn)行是非常復(fù)雜的，所以不能簡(jiǎn)單的把某一個(gè)具體的地方當(dāng)成是圖中的某個(gè)節(jié)點(diǎn)，把道路信息抽象成圖中帶有權(quán)值的邊，而是要將具體的地址信息抽象為節(jié)點(diǎn)以及其附屬信息并加入到交通網(wǎng)絡(luò)系統(tǒng)中。交通地址的交叉口所抽象的節(jié)點(diǎn)和將具體地址被抽象成圖中的節(jié)點(diǎn)是不相等價(jià)的，需要考慮實(shí)際情況，因此交通節(jié)點(diǎn)的阻抗值應(yīng)該視具體情況而定，而表示地名的節(jié)點(diǎn)的阻抗值可以視為零。 3． 1． 2 交叉口和道路模型 將道路的數(shù)據(jù)模型抽象為一條 線，因此選擇道路中問的中心線表示道路數(shù)據(jù)模型，這種建模方法不能很好的描述交通道路的屬性信息，丟失很多信息量。實(shí)際生活中的道路不能簡(jiǎn)單的抽象為一條直線，因?yàn)橛行┑缆反嬖诤芏嘬嚨?，每個(gè)車道的屬性信息不盡相同，多車道的交通道路屬性信息較為復(fù)雜。在 GPS進(jìn)行導(dǎo)航式，需要考慮到的交通網(wǎng)絡(luò)信息往往與車道信息密切相關(guān) 。 3． 2 交通模型數(shù)據(jù)存儲(chǔ) 3． 2． 1 數(shù)據(jù)預(yù)處理 在實(shí)際應(yīng)用中，一般將交通網(wǎng)絡(luò)模型用矢量化的數(shù)據(jù)地圖表示，為了建立交通網(wǎng)絡(luò)可使用的數(shù)據(jù)模型，需要對(duì)原始道路構(gòu)成的交通網(wǎng)絡(luò)矢量圖進(jìn)行優(yōu)化武漢紡織大學(xué) 20xx 屆畢業(yè)設(shè)計(jì)論文 10 和預(yù)處理，建立相應(yīng)的拓 撲關(guān)系圖譜。矢量圖形的預(yù)處理的一般包括： (1)對(duì)原始道路圖像進(jìn)行拓?fù)潢P(guān)系檢查并進(jìn)行剪斷處理，保證地圖中不存在兩條道路相交的情況，將原來的道路拆分成多條道路的集合： (2)為每一條剪斷后的道路建立拓?fù)潢P(guān)系，并定義其屬性特征，如道路名稱、道路長度、交通流等特征； (3)將地圖經(jīng)過上述處理之后生成拓?fù)湮募? 3． 2． 2 交通路徑模型建立與數(shù)據(jù)存儲(chǔ) （ 1）交通路徑模型的建立 最短路徑選擇的前提是對(duì)交通系統(tǒng)創(chuàng)建合適的模型。按照上述方法對(duì)原始的交通道路進(jìn)行預(yù)處理之后就可以確定道路之間的拓?fù)潢P(guān)系，進(jìn)而可以建立以道路拓?fù)?關(guān)系為基準(zhǔn)的交通系統(tǒng)模型，拓?fù)潢P(guān)系中包括線性實(shí)體之間的模型，線性實(shí)體與節(jié)點(diǎn)之問的模型，節(jié)點(diǎn)與節(jié)點(diǎn)之間的模型，以及他們的連通性等。使用圖中的節(jié)點(diǎn)表示交通系統(tǒng)的的較差路徑，道路交叉即是圖中的節(jié)點(diǎn)，兩個(gè)節(jié)點(diǎn)之間的道路在圖中用弧表示，就是圖的邊，路段的長度以及消耗時(shí)問等信息則為邊帶有的權(quán)值。在本文中，交通路徑系統(tǒng)的模型由兩部分圖層所構(gòu)成，一部分是節(jié)點(diǎn)圖層，一部分是交通道路圖層。節(jié)點(diǎn)圖層表示交通交叉口或者道路的起始點(diǎn)或終止點(diǎn)，用點(diǎn)對(duì)象來表示，路段圖層存儲(chǔ)這連接各個(gè)節(jié)點(diǎn)的交通路徑以及他們的屬性信息，用線對(duì)象表示。在兩圖 層中分別存儲(chǔ)的節(jié)點(diǎn)信息和路段信息分別是獨(dú)立的，下一步就是建立兩個(gè)圖層之問的拓?fù)渎?lián)系，使得兩個(gè)圖層構(gòu)成有機(jī)整體，形成交通路徑系統(tǒng)的完整性，需要用兩個(gè)圖層所對(duì)應(yīng)的兩張表中的文件擴(kuò)展出一定的字段，用對(duì)象的屬性信息來代表兩個(gè)圖層之間的拓?fù)潢P(guān)系，這樣就構(gòu)成了交通路徑模型的整體拓?fù)潢P(guān)系結(jié)構(gòu)圖。 交通路徑的限制信息是交通導(dǎo)航中需要終點(diǎn)考慮的因素，比如由于施工、交通事故、速度限制、惡劣天氣造成的交通限制等，實(shí)際的道路中交通限制信息十分復(fù)雜，而且隨時(shí)發(fā)生變化。本文考慮的交通限制信息只考慮了禁止通行的信息。如果某條道路出現(xiàn)禁止 通行的限制信息，用節(jié)點(diǎn)的交通限制信息來表示 。 武漢紡織大學(xué) 20xx 屆畢業(yè)設(shè)計(jì)論文 11 （ 2）數(shù)據(jù)存儲(chǔ) 一般地，在計(jì)算機(jī)中大多采用利