【文章內(nèi)容簡(jiǎn)介】 幾何問(wèn)題，而主要表達(dá)的是點(diǎn)點(diǎn)之間通過(guò)線的連通關(guān)系，通?？梢杂脕?lái)描述某些事物之間的相互關(guān)系，即用點(diǎn)來(lái)代表事件發(fā)生，用連接兩點(diǎn)的邊表示兩個(gè)事件之間的關(guān)系。因此圖論中的圖能夠代表多種含義，因此圖論在諸多領(lǐng)域都有著非常廣泛的應(yīng)用。2. 2. 1 圖的概念無(wú)向圖是指有序三元組(V，E,F)中邊沒(méi)有方向，其中集合y被稱為結(jié)點(diǎn)集，y中的元素稱為結(jié)點(diǎn)：集合E被稱為邊集，E中的元素被稱為邊；而函數(shù)是邊集E到無(wú)序結(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)單圖就是沒(méi)有環(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)來(lái)表示。圖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) 2．2．3 圖的存儲(chǔ)(1) 鄰接表鄰接表結(jié)構(gòu)： adfvexnextarc info datafirstarc 圖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ǔ)方式便于隨即訪問(wèn)任何一個(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)和不足。圖論在近幾十年來(lái)得到了飛速的發(fā)展，尤其是與物理學(xué)、化學(xué)理論、信息理論、運(yùn)籌學(xué)、計(jì)算機(jī)理論、控制論、社會(huì)科學(xué)等不同領(lǐng)域和學(xué)科的結(jié)合方面。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)在空問(wèn)分布中一般呈現(xiàn)線性特征，因此交通網(wǎng)絡(luò)建模可以依靠圖論的相關(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ī)則有可能不同。由于在節(jié)點(diǎn)圖層和路段圖層中分別存儲(chǔ)的點(diǎn)、線圖元是分別獨(dú)立的，兩個(gè)圖層問(wèn)不想關(guān)聯(lián)。為建立點(diǎn)線各個(gè)元素之間的空間拓?fù)潢P(guān)系，使他們構(gòu)成有機(jī)整體，需要分別在存儲(chǔ)點(diǎn)線信息的兩張表文件中擴(kuò)展一定長(zhǎng)度的字段，用對(duì)象的屬性字段之問(wèn)的相互聯(lián)系來(lái)建立交通網(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è)抽象的有向圖如何建立起來(lái)需要視具體的應(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ù)模型抽象為一條線，因此選擇道路中問(wèn)的中心線表示道路數(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)化和預(yù)處理，建立相應(yīng)的拓?fù)潢P(guān)系圖譜。矢量圖形的預(yù)處理的一般包括：(1)對(duì)原始道路圖像進(jìn)行拓?fù)潢P(guān)系檢查并進(jìn)行剪斷處理，保證地圖中不存在兩條道路相交的情況，將原來(lái)的道路拆分成多條道路的集合：(2)為每一條剪斷后的道路建立拓?fù)潢P(guān)系，并定義其屬性特征，如道路名稱、道路長(zhǎng)度、交通流等特征；(3)將地圖經(jīng)過(guò)上述處理之后生成拓?fù)湮募?．2．2 交通路徑模型建立與數(shù)據(jù)存儲(chǔ)（1）交通路徑模型的建立最短路徑選擇的前提是對(duì)交通系統(tǒng)創(chuàng)建合適的模型。按照上述方法對(duì)原始的交通道路進(jìn)行預(yù)處理之后就可以確定道路之間的拓?fù)潢P(guān)系，進(jìn)而可以建立以道路拓?fù)潢P(guān)系為基準(zhǔn)的交通系統(tǒng)模型，拓?fù)潢P(guān)系中包括線性實(shí)體之間的模型，線性實(shí)體與節(jié)點(diǎn)之問(wèn)的模型，節(jié)點(diǎn)與節(jié)點(diǎn)之間的模型，以及他們的連通性等。使用圖中的節(jié)點(diǎn)表示交通系統(tǒng)的的較差路徑，道路交叉即是圖中的節(jié)點(diǎn)，兩個(gè)節(jié)點(diǎn)之間的道路在圖中用弧表示，就是圖的邊，路段的長(zhǎng)度以及消耗時(shí)問(wèn)等信息則為邊帶有的權(quán)值。在本文中，交通路徑系統(tǒng)的模型由兩部分圖層所構(gòu)成，一部分是節(jié)點(diǎn)圖層，一部分是交通道路圖層。節(jié)點(diǎn)圖層表示交通交叉口或者道路的起始點(diǎn)或終止點(diǎn)，用點(diǎn)對(duì)象來(lái)表示，路段圖層存儲(chǔ)這連接各個(gè)節(jié)點(diǎn)的交通路徑以及他們的屬性信息，用線對(duì)象表示。在兩圖層中分別存儲(chǔ)的節(jié)點(diǎn)信息和路段信息分別是獨(dú)立的，下一步就是建立兩個(gè)圖層之問(wèn)的拓?fù)渎?lián)系，使得兩個(gè)圖層構(gòu)成有機(jī)整體，形成交通路徑系統(tǒng)的完整性，需要用兩個(gè)圖層所對(duì)應(yīng)的兩張表中的文件擴(kuò)展出一定的字段，用對(duì)象的屬性信息來(lái)代表兩個(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)的交通限制信息來(lái)表示。（2）數(shù)據(jù)存儲(chǔ)一般地，在計(jì)算機(jī)中大多采用利用鄰接表和鄰接矩陣的方法存儲(chǔ)有向圖。順序表V0，V1，?Vm1。的形式在鄰接局長(zhǎng)呢中存儲(chǔ)圖中所有的結(jié)點(diǎn)，以mm大小的矩陣存儲(chǔ)圖的邊。使用鄰接矩陣來(lái)表示圖的存儲(chǔ)淺顯易懂，也可以通過(guò)鄰接矩陣來(lái)存儲(chǔ)邊的權(quán)值信息和節(jié)點(diǎn)信息以及他們之間的連同情況等等，因此在本文中也利用鄰接表和鄰接矩陣方法。3．3 最優(yōu)路徑選擇3．3．1 最優(yōu)路徑的求解過(guò)程在交通網(wǎng)絡(luò)中，求解最優(yōu)路徑的一般思路是：把最優(yōu)路徑選擇問(wèn)題轉(zhuǎn)化成優(yōu)化問(wèn)題來(lái)解決，應(yīng)用優(yōu)化理論的相關(guān)思想和思路解決最優(yōu)路徑優(yōu)化問(wèn)題。求解過(guò)程包括以下四個(gè)步驟酬：(1)交通網(wǎng)絡(luò)模型建立；(2)交通道路權(quán)重的計(jì)算；(3)利用最短路徑計(jì)算方法求解交通網(wǎng)絡(luò)中的最短路徑問(wèn)題；(4)將交通網(wǎng)絡(luò)圖中的最短路徑問(wèn)題轉(zhuǎn)化為現(xiàn)實(shí)交通網(wǎng)絡(luò)中的路段集合。其中，建立交通網(wǎng)絡(luò)模型是最優(yōu)路徑選擇的基礎(chǔ)，交通網(wǎng)絡(luò)模型中道路權(quán)值的計(jì)算以及利用權(quán)值信息求解最短路徑是關(guān)鍵。道路的權(quán)值是計(jì)算現(xiàn)實(shí)問(wèn)題中最短路徑的基礎(chǔ)，最優(yōu)路徑選擇的準(zhǔn)確與