網(wǎng)絡分析的實現(xiàn)

網(wǎng)絡分析的實現(xiàn)目錄CONTENTS二、路徑分析算法設計一、數(shù)據(jù)準備一、數(shù)據(jù)準備在現(xiàn)實生活中，常將空間事物抽象成點、線、面等幾何要素。點、線建立拓撲關系，可以組成網(wǎng)絡。網(wǎng)絡在幾何上由邊連成，邊的端點、交點是網(wǎng)絡的節(jié)點。例如，道路網(wǎng)可以定義為幾何上的“網(wǎng)”，行車路線可以定義為網(wǎng)絡的“邊”，車站站點可以定義為網(wǎng)絡的“節(jié)點“。這樣就把現(xiàn)實世界中的客觀對象抽象成網(wǎng)絡、節(jié)點、邊之間的關系。對應幾何特征又有相應的屬性特征，例如道路網(wǎng)中的行車路線的距離等特征，轉向點的通行規(guī)則等特征。一般，網(wǎng)絡在數(shù)學和計算機領域中是被抽象為“圖”這個概念的，所以其基礎是圖的存儲表示。數(shù)據(jù)準備一、項目概況

1、數(shù)據(jù)準備網(wǎng)絡分析是建立在拓撲關系基礎上的,因此要進行網(wǎng)絡分析就要建立相應拓撲關系,這就決定了需要什么樣的數(shù)據(jù)，應該怎么組織。以交通道路網(wǎng)為例，要對其進行網(wǎng)絡分析，就必須構建交通道路拓撲網(wǎng)絡，如圖所示。數(shù)據(jù)準備a數(shù)據(jù)分類對于給定的城市交通道路網(wǎng)，要在其基礎上進行最短路徑分析，最佳乘車方案分析，就必須構建道路拓撲網(wǎng)絡，這才能進行最基本的分析。。以城市公交網(wǎng)絡為例，數(shù)據(jù)分類如下。（1）公交路線線段：是公交網(wǎng)絡中的最小線單元，以公交連接點為端點。（2）公交連接點：是公交路線線段端點。（3）公交路線：是一組公交路線線段的有序排列，為公交車輛行駛構建一個物理路徑。其定義了公交網(wǎng)絡中的一個有向路徑。數(shù)據(jù)準備（4）公交線路；是復雜要素，指一組具有共同名稱或編號的公交路線。大多數(shù)情況下，公交線路包含兩個公交路線，每個代表不同的方向。（5）公交車站：是乘客上下公交車輛的地點。（6）公交換乘區(qū)：由一個或多個鄰近的公交車站所構成。是乘客可在步行距離內換乘公交線路的公交車站的集合。（7）公交點：是公交網(wǎng)絡中可設定地址的位置。該點可以有明確的物理意義，如景觀點。數(shù)據(jù)準備b數(shù)據(jù)組織假設圖4.1為一個公交網(wǎng)絡。圖中的每個小方塊表示一個車站站點，邊表示各站點之間的距離。如何用一定的數(shù)據(jù)結構來存儲該網(wǎng)絡圖呢？可以采用“結點-弧段(可有多條弧段)-結點”的數(shù)據(jù)組織方式，按照公共汽車線路選擇所經(jīng)過的"站點-路線-站點"形成路徑分析中的有向線。一般網(wǎng)絡都是由節(jié)點、弧段兩大基本要素組成。為了便于分析我們把這些信息組織成最基本的三類文件，即節(jié)點文件、弧段文件、目標文件。數(shù)據(jù)準備節(jié)點文件主要記錄每個屬于節(jié)點集的點，其數(shù)據(jù)項包括：點的ID、點的地理坐標、點的名稱、類型標識碼等，見下表。點的ID號XY節(jié)點名稱類型標識碼……………Node_IDi462.58912431.6324火車站1……………Node_IDj510.63242276.9718汽車總站0……………數(shù)據(jù)準備

表1節(jié)點文件結構弧段文件主要記錄弧段的ID、起始節(jié)點、終止節(jié)點編號、中間點串以及弧段權值（可描述弧段各種屬性信息，一般主要用來描述距離信息），見表2。弧段的ID起始節(jié)點ID終止節(jié)點ID中間點串權值……………Arc一IDiNode_IDiNode_IDj…110……………數(shù)據(jù)準備

表2弧段文件結構目標文件主要記錄以點目標為端點，在兩個端點之間加入若干點目標和弧段目標形成一種有方向的線（如公交線路），如果考慮到現(xiàn)實生活中線路的有向性,還可以由已經(jīng)存在的有向線目標反向形成。對于每條有向線，記錄其ID、幾何類型、節(jié)點索引、節(jié)點數(shù)目、弧段索引、弧段數(shù)目、弧段名稱，見表3。目標ID幾何類型點數(shù)點集弧段數(shù)弧段集弧段名稱…………………Obj_IDi1n...Node_IDi...n...ArcIDi...XX…………………數(shù)據(jù)準備表3目標文件結構節(jié)點文件、弧段文件、目標文件構成了網(wǎng)絡的基本信息，而它們之間的相互關系則構成了完整的網(wǎng)絡拓撲關系。三種數(shù)據(jù)之間的相互關系如圖所示。圖

文件結構級相互之間的關系這種拓撲關系數(shù)據(jù)將在數(shù)據(jù)采集時構造，并以文件形式保存下來，直至網(wǎng)絡數(shù)據(jù)發(fā)生變化。若數(shù)據(jù)未發(fā)生變化，每次運算就直接從文件中讀取所需的拓撲關系，這樣有利于檢索和分析速度的提高。數(shù)據(jù)準備二、路徑分析算法設計一、項目概況路徑分析算法設計前面路徑分析中已經(jīng)提到在電子地圖中一般采用Dijkstra算法來實現(xiàn)最短路徑求解問題。原始Dijkstra算法將網(wǎng)絡節(jié)點分為未標記節(jié)點、臨時標記節(jié)點和永久標記節(jié)點3種類型。首先要將網(wǎng)絡中所有節(jié)點初始化為未標記節(jié)點，在搜索過程中和最短路徑節(jié)點相連通的節(jié)點為臨時標記節(jié)點，每一次循環(huán)都是從臨時標記節(jié)點中搜索距源點路徑長度最短的節(jié)點作為永久標記節(jié)點，直至找到目標節(jié)點或者所有節(jié)點都成為永久標記節(jié)點才結束算法。目前在實際應用中，空間存儲問題已不是要考慮的主要問題，因此可以用空間換時間來提高最短路徑算法的效率。鄰接點優(yōu)化算法已經(jīng)被廣泛的應用于電子地圖的路徑分析中，算法效率也優(yōu)于其他優(yōu)化算法。一、項目概況路徑分析算法設計Dijkstra算法的數(shù)據(jù)組織基礎是構造M×N的鄰接矩陣，N是網(wǎng)絡的節(jié)點數(shù)。當網(wǎng)絡的節(jié)點數(shù)很大時，而各節(jié)點的鄰接節(jié)點數(shù)又不多的情況下，有大量的∞元素存在，尤其是對于以真實的地圖為對象的實際應用問題，這樣將占用大量的存儲空間，并且運算也很浪費時間。下面闡述在Dijkstra算法的基礎上,采用鄰接點算法，來提高運算速度。電子地圖中靜態(tài)網(wǎng)絡分析的理論及算法已經(jīng)很完備。但在實際應用中，網(wǎng)絡特征可能時刻會發(fā)生變化，這就需要在算法設計時考慮實時性等因素。而動態(tài)網(wǎng)絡是一個與實際應用結合緊密、發(fā)展前景廣闊的研究領域，隨著研究的不斷深入，