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