【文章內(nèi)容簡介】 幾何問題，而主要表達(dá)的是點點之間通過線的連通關(guān)系，通?？梢杂脕砻枋瞿承┦挛镏g的相互關(guān)系，即用點來代表事件發(fā)生，用連接兩點的邊表示兩個事件之間的關(guān)系。因此圖論中的圖能夠代表多種含義，因此圖論在諸多領(lǐng)域都有著非常廣泛的應(yīng)用。2. 2. 1 圖的概念無向圖是指有序三元組(V，E,F)中邊沒有方向，其中集合y被稱為結(jié)點集，y中的元素稱為結(jié)點：集合E被稱為邊集，E中的元素被稱為邊；而函數(shù)是邊集E到無序結(jié)點對兒所構(gòu)成的集合的一個映射關(guān)系，稱之為關(guān)聯(lián)函數(shù)。如果P是一條邊“，39。，兩個結(jié)點，且滿足F(E)=uv，那么就可稱為e連接：并且稱Ⅳ，y為E的端點。每條邊與邊兩端的節(jié)點是相互關(guān)聯(lián)的因此稱為相互關(guān)聯(lián)，與同一條邊相關(guān)聯(lián)的節(jié)點或者與同一個節(jié)點相互關(guān)聯(lián)的邊稱為相鄰的節(jié)點或者相鄰的邊，具有相同兩個節(jié)點的邊稱為重合邊或者是平行邊，兩個節(jié)點相同的邊組成環(huán)，簡單圖就是沒有環(huán)和重邊的圖。每個結(jié)點度數(shù)相同的簡單圖稱為正則圖，最大度與最小度恰好相差1的簡單圖被稱為幾乎正則圖。圖的結(jié)點的個數(shù)稱為圖的階。2．2．2 圖的表示由點集合V和點與點之間的連線的集合E所組成的集合對(V，E)可以構(gòu)成圖，用G(V,E)來表示。圖G(V，E)由其結(jié)點與邊之間的關(guān)系確定，且是唯一的。也由它的結(jié)點對兒之間的鄰接關(guān)系唯一確定。V中的元素為結(jié)點，E中的元素為邊。節(jié)點集合V與邊集合E均為有限的圖稱為有限圖。 圖21 圖的結(jié)構(gòu) 2．2．3 圖的存儲(1) 鄰接表鄰接表結(jié)構(gòu)： adfvexnextarc info datafirstarc 圖22 鄰接表結(jié)構(gòu)表節(jié)點和頭結(jié)點鄰接表以一種以鏈?zhǔn)酱鎯Y(jié)構(gòu)所構(gòu)成的圖。在鄰接表中，圖中的每個節(jié)點都會有一個單鏈表與之對應(yīng)，第i個單鏈表中的結(jié)點數(shù)據(jù)表示依附于結(jié)點v。三個域構(gòu)成了每個節(jié)點，其中結(jié)點的鄰接點域的數(shù)值表示與結(jié)點相鄰節(jié)點在圖中的具體位置，結(jié)點的鏈域?qū)⒅甘鞠乱粭l邊的結(jié)點，結(jié)點數(shù)據(jù)域存儲的是圖中邊的信息，如權(quán)值、方向等。每個鏈表都會有一個表頭結(jié)點與之對應(yīng)，在表頭結(jié)點中，設(shè)有存儲結(jié)點q的各個域及與該信息有關(guān)的相關(guān)數(shù)據(jù)域。這些表頭結(jié)點存儲數(shù)據(jù)的形式通常是順序存儲的，這樣存儲方式便于隨即訪問任何一個節(jié)點的鏈表信息。(2)十字鏈表十字鏈表針對有向圖的另一種存儲結(jié)構(gòu)?？梢钥闯墒且环N新的鏈表，該鏈表將有向圖的鄰接表和逆鄰接表結(jié)合在一起。在十字鏈表中，每一條邊都有一個節(jié)點與之對應(yīng)，每一個節(jié)點也有一個節(jié)點與之對應(yīng)。2．3 本章小結(jié)本章對最優(yōu)路徑算法和圖論的相關(guān)理論知識進(jìn)行了簡單概述。對幾個經(jīng)典的最優(yōu)路徑選擇算法進(jìn)行了介紹，如Floyd算法、Dijkstra算法、GPSR算法，并分析了他們的優(yōu)點和不足。圖論在近幾十年來得到了飛速的發(fā)展，尤其是與物理學(xué)、化學(xué)理論、信息理論、運籌學(xué)、計算機理論、控制論、社會科學(xué)等不同領(lǐng)域和學(xué)科的結(jié)合方面。3 最優(yōu)路徑最優(yōu)路徑選擇和交通系統(tǒng)優(yōu)化的目的就是是交通流均衡化，合理的在交通系統(tǒng)中分配，提高交通運輸效率。因此，應(yīng)當(dāng)首先考慮交通流的特征。一般地，交通網(wǎng)絡(luò)有如下特點：(1)線性分布，交通網(wǎng)絡(luò)結(jié)構(gòu)在空問分布中一般呈現(xiàn)線性特征，因此交通網(wǎng)絡(luò)建模可以依靠圖論的相關(guān)理論和知識；(2)網(wǎng)絡(luò)分布，交通網(wǎng)絡(luò)是一個負(fù)載的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，連通性好，結(jié)構(gòu)復(fù)雜：(3)分段分布，交通系統(tǒng)中不同路段的特征一般不同，表現(xiàn)為空間的差異性，且同一路段的不同時間的交通網(wǎng)絡(luò)特征也可能不同，表現(xiàn)為時間差異性；(4)動態(tài)性特點，交通網(wǎng)絡(luò)上交通狀況不是一層不變的，隨時間的變化而變化，失意是時變系統(tǒng)：(5)車輛行駛的主觀性，交通網(wǎng)絡(luò)不同于其它網(wǎng)絡(luò)，交通網(wǎng)絡(luò)的主體可以自主的選擇交通路徑，行駛時間和行駛路線等是他的一個最顯著特征。以圖的理論為研究基礎(chǔ)研究交通道路模型，采用改進(jìn)的方法使得道路的車道信息加入到節(jié)點和邊的信息中。以完整的交通道路作為建模的基本單元，但在交通應(yīng)用當(dāng)中，交通特征的變化在交通系統(tǒng)的具體應(yīng)用當(dāng)中經(jīng)常和車道關(guān)聯(lián)密切。在同一一條道路上不同方向的車道具有不同的交通特性，如交通規(guī)則變化、交通量變化等。3．1 建立城市交通模型利用圖論的相關(guān)理論和知識，對圖中的節(jié)點和邊設(shè)法加入車道信息用于模擬就哀痛系統(tǒng)。以完整的交通道路網(wǎng)絡(luò)作為模型建立對象，只需要對道路中的相關(guān)數(shù)據(jù)和參數(shù)進(jìn)行顯示和計算，但在實際的交通道路當(dāng)中，交通特征是實時變化的，這與交通道路模型密不可分。首先，在同一條道路上不同的車道在不同的行駛方向的交通特征可能不同，如交通量變化和交通規(guī)則等。例如：在早晚的上下班的高峰區(qū)段，進(jìn)出同一區(qū)域的同一條道路在不同方向表現(xiàn)的車流量是明顯不同的，交通擁堵現(xiàn)象大多數(shù)情況下是發(fā)生在某條車道的單向車道上。其次，不同方向的車道由于具有不同的拓?fù)潢P(guān)系，因此交通規(guī)則有可能不同。由于在節(jié)點圖層和路段圖層中分別存儲的點、線圖元是分別獨立的，兩個圖層問不想關(guān)聯(lián)。為建立點線各個元素之間的空間拓?fù)潢P(guān)系，使他們構(gòu)成有機整體，需要分別在存儲點線信息的兩張表文件中擴展一定長度的字段，用對象的屬性字段之問的相互聯(lián)系來建立交通網(wǎng)絡(luò)圖的拓?fù)潢P(guān)系，這樣就建立了交通網(wǎng)絡(luò)系統(tǒng)的有機整體即他們的拓?fù)潢P(guān)系結(jié)構(gòu)圖。3．1．1 道路節(jié)點模型可以將交通網(wǎng)絡(luò)抽象成一個有向圖，圖中的邊帶有一定的權(quán)值，但這個抽象的有向圖如何建立起來需要視具體的應(yīng)用環(huán)境而定。在實際情況中人民出行是從一個地方到另一個地方，這種不能簡單的歸結(jié)在圖中從一個節(jié)點到另一個節(jié)點的轉(zhuǎn)移，實際情況的交通網(wǎng)絡(luò)運行是非常復(fù)雜的，所以不能簡單的把某一個具體的地方當(dāng)成是圖中的某個節(jié)點，把道路信息抽象成圖中帶有權(quán)值的邊，而是要將具體的地址信息抽象為節(jié)點以及其附屬信息并加入到交通網(wǎng)絡(luò)系統(tǒng)中。交通地址的交叉口所抽象的節(jié)點和將具體地址被抽象成圖中的節(jié)點是不相等價的，需要考慮實際情況，因此交通節(jié)點的阻抗值應(yīng)該視具體情況而定，而表示地名的節(jié)點的阻抗值可以視為零。 3．1．2 交叉口和道路模型將道路的數(shù)據(jù)模型抽象為一條線，因此選擇道路中問的中心線表示道路數(shù)據(jù)模型，這種建模方法不能很好的描述交通道路的屬性信息，丟失很多信息量。實際生活中的道路不能簡單的抽象為一條直線，因為有些道路存在很多車道，每個車道的屬性信息不盡相同，多車道的交通道路屬性信息較為復(fù)雜。在GPS進(jìn)行導(dǎo)航式，需要考慮到的交通網(wǎng)絡(luò)信息往往與車道信息密切相關(guān)。3．2 交通模型數(shù)據(jù)存儲3．2．1 數(shù)據(jù)預(yù)處理在實際應(yīng)用中，一般將交通網(wǎng)絡(luò)模型用矢量化的數(shù)據(jù)地圖表示，為了建立交通網(wǎng)絡(luò)可使用的數(shù)據(jù)模型，需要對原始道路構(gòu)成的交通網(wǎng)絡(luò)矢量圖進(jìn)行優(yōu)化和預(yù)處理，建立相應(yīng)的拓?fù)潢P(guān)系圖譜。矢量圖形的預(yù)處理的一般包括：(1)對原始道路圖像進(jìn)行拓?fù)潢P(guān)系檢查并進(jìn)行剪斷處理，保證地圖中不存在兩條道路相交的情況，將原來的道路拆分成多條道路的集合：(2)為每一條剪斷后的道路建立拓?fù)潢P(guān)系，并定義其屬性特征，如道路名稱、道路長度、交通流等特征；(3)將地圖經(jīng)過上述處理之后生成拓?fù)湮募?．2．2 交通路徑模型建立與數(shù)據(jù)存儲（1）交通路徑模型的建立最短路徑選擇的前提是對交通系統(tǒng)創(chuàng)建合適的模型。按照上述方法對原始的交通道路進(jìn)行預(yù)處理之后就可以確定道路之間的拓?fù)潢P(guān)系，進(jìn)而可以建立以道路拓?fù)潢P(guān)系為基準(zhǔn)的交通系統(tǒng)模型，拓?fù)潢P(guān)系中包括線性實體之間的模型，線性實體與節(jié)點之問的模型，節(jié)點與節(jié)點之間的模型，以及他們的連通性等。使用圖中的節(jié)點表示交通系統(tǒng)的的較差路徑，道路交叉即是圖中的節(jié)點，兩個節(jié)點之間的道路在圖中用弧表示，就是圖的邊，路段的長度以及消耗時問等信息則為邊帶有的權(quán)值。在本文中，交通路徑系統(tǒng)的模型由兩部分圖層所構(gòu)成，一部分是節(jié)點圖層，一部分是交通道路圖層。節(jié)點圖層表示交通交叉口或者道路的起始點或終止點，用點對象來表示，路段圖層存儲這連接各個節(jié)點的交通路徑以及他們的屬性信息，用線對象表示。在兩圖層中分別存儲的節(jié)點信息和路段信息分別是獨立的，下一步就是建立兩個圖層之問的拓?fù)渎?lián)系，使得兩個圖層構(gòu)成有機整體，形成交通路徑系統(tǒng)的完整性，需要用兩個圖層所對應(yīng)的兩張表中的文件擴展出一定的字段，用對象的屬性信息來代表兩個圖層之間的拓?fù)潢P(guān)系，這樣就構(gòu)成了交通路徑模型的整體拓?fù)潢P(guān)系結(jié)構(gòu)圖。交通路徑的限制信息是交通導(dǎo)航中需要終點考慮的因素，比如由于施工、交通事故、速度限制、惡劣天氣造成的交通限制等，實際的道路中交通限制信息十分復(fù)雜，而且隨時發(fā)生變化。本文考慮的交通限制信息只考慮了禁止通行的信息。如果某條道路出現(xiàn)禁止通行的限制信息，用節(jié)點的交通限制信息來表示。（2）數(shù)據(jù)存儲一般地，在計算機中大多采用利用鄰接表和鄰接矩陣的方法存儲有向圖。順序表V0，V1，?Vm1。的形式在鄰接局長呢中存儲圖中所有的結(jié)點，以mm大小的矩陣存儲圖的邊。使用鄰接矩陣來表示圖的存儲淺顯易懂，也可以通過鄰接矩陣來存儲邊的權(quán)值信息和節(jié)點信息以及他們之間的連同情況等等，因此在本文中也利用鄰接表和鄰接矩陣方法。3．3 最優(yōu)路徑選擇3．3．1 最優(yōu)路徑的求解過程在交通網(wǎng)絡(luò)中，求解最優(yōu)路徑的一般思路是：把最優(yōu)路徑選擇問題轉(zhuǎn)化成優(yōu)化問題來解決，應(yīng)用優(yōu)化理論的相關(guān)思想和思路解決最優(yōu)路徑優(yōu)化問題。求解過程包括以下四個步驟酬：(1)交通網(wǎng)絡(luò)模型建立；(2)交通道路權(quán)重的計算；(3)利用最短路徑計算方法求解交通網(wǎng)絡(luò)中的最短路徑問題；(4)將交通網(wǎng)絡(luò)圖中的最短路徑問題轉(zhuǎn)化為現(xiàn)實交通網(wǎng)絡(luò)中的路段集合。其中，建立交通網(wǎng)絡(luò)模型是最優(yōu)路徑選擇的基礎(chǔ)，交通網(wǎng)絡(luò)模型中道路權(quán)值的計算以及利用權(quán)值信息求解最短路徑是關(guān)鍵。道路的權(quán)值是計算現(xiàn)實問題中最短路徑的基礎(chǔ)，最優(yōu)路徑選擇的準(zhǔn)確與