網(wǎng)絡(luò)分析的實(shí)現(xiàn)

電子地圖分析與導(dǎo)航網(wǎng)絡(luò)分析的實(shí)現(xiàn)《電子地圖分析與導(dǎo)航》課程組目錄CONTENTS數(shù)據(jù)準(zhǔn)備算法思想0102數(shù)據(jù)準(zhǔn)備01在現(xiàn)實(shí)生活中，常將空間事物抽象成點(diǎn)、線、面等幾何要素。點(diǎn)、線建立拓?fù)潢P(guān)系，可以組成網(wǎng)絡(luò)。網(wǎng)絡(luò)在幾何上由邊連成，邊的端點(diǎn)、交點(diǎn)是網(wǎng)絡(luò)的節(jié)點(diǎn)。例如，道路網(wǎng)可以定義為幾何上的“網(wǎng)”，行車路線可以定義為網(wǎng)絡(luò)的“邊”，車站站點(diǎn)可以定義為網(wǎng)絡(luò)的“節(jié)點(diǎn)”。這樣就把現(xiàn)實(shí)世界中的客觀對(duì)象抽象成網(wǎng)絡(luò)、節(jié)點(diǎn)、邊之間的關(guān)系。對(duì)應(yīng)幾何特征又有相應(yīng)的屬性特征，例如道路網(wǎng)中的行車路線的距離等特征，轉(zhuǎn)向點(diǎn)的通行規(guī)則等特征。一般，網(wǎng)絡(luò)在數(shù)學(xué)和計(jì)算機(jī)領(lǐng)域中是被抽象為“圖”這個(gè)概念的，所以其基礎(chǔ)是圖的存儲(chǔ)表示。01數(shù)據(jù)準(zhǔn)備網(wǎng)絡(luò)分析是建立在拓?fù)潢P(guān)系基礎(chǔ)上的，因此要進(jìn)行網(wǎng)絡(luò)分析就要建立相應(yīng)拓?fù)潢P(guān)系，這就決定了需要什么樣的數(shù)據(jù)，應(yīng)該怎么組織。以交通道路網(wǎng)為例，要對(duì)其進(jìn)行網(wǎng)絡(luò)分析，就必須構(gòu)建交通道路拓?fù)渚W(wǎng)絡(luò)。01數(shù)據(jù)準(zhǔn)備交通道路拓?fù)渚W(wǎng)圖本次內(nèi)容以城市交通道路網(wǎng)為基礎(chǔ)，以求最短路徑為實(shí)例，說(shuō)明在電子地圖中網(wǎng)絡(luò)分析功能的實(shí)現(xiàn)。1)數(shù)據(jù)分類對(duì)于給定的城市交通道路網(wǎng)，要在其基礎(chǔ)上進(jìn)行最短路徑分析，最佳乘車方案分析，就必須構(gòu)建道路拓?fù)渚W(wǎng)絡(luò)，這才能進(jìn)行最基本的分析。從而就決定了我們所需要的數(shù)據(jù)，為了更好地組織數(shù)據(jù)，我們需要對(duì)數(shù)據(jù)進(jìn)行分類。01數(shù)據(jù)準(zhǔn)備1)數(shù)據(jù)分類以城市公交網(wǎng)絡(luò)為例，數(shù)據(jù)分類如下:(1)公交路線線段：是公交網(wǎng)絡(luò)中的最小線單元，以公交連接點(diǎn)為端點(diǎn)。(2)公交連接點(diǎn)：是公交路線線段端點(diǎn)。(3)公交路線：是一組公交路線線段的有序排列，為公交車輛行駛構(gòu)建一個(gè)物理路徑。其定義了公交網(wǎng)絡(luò)中的一個(gè)有向路徑。(4)公交線路：是復(fù)雜要素，指一組具有共同名稱或編號(hào)的公交路線。大多數(shù)情況下，公交線路包含兩個(gè)公交路線，每個(gè)代表不同的方向。01數(shù)據(jù)準(zhǔn)備1)數(shù)據(jù)分類以城市公交網(wǎng)絡(luò)為例，數(shù)據(jù)分類如下:(5)公交車站：是乘客上下公交車輛的地點(diǎn)。(6)公交換乘區(qū)：由一個(gè)或多個(gè)鄰近的公交車站所構(gòu)成。是乘客可在步行距離內(nèi)換乘公交線路的公交車站的集合。(7)公交點(diǎn)：是公交網(wǎng)絡(luò)中可設(shè)定地址的位置。該點(diǎn)可以有明確的物理意義，如景觀點(diǎn)。01數(shù)據(jù)準(zhǔn)備2)數(shù)據(jù)組織假設(shè)右圖為一個(gè)公交網(wǎng)絡(luò)。圖中的每個(gè)小方塊表示一個(gè)車站站點(diǎn)，邊表示各站點(diǎn)之間的距離。如何用一定的數(shù)據(jù)結(jié)構(gòu)來(lái)存儲(chǔ)該網(wǎng)絡(luò)圖呢？可以采用“結(jié)點(diǎn)-弧段（可有多條弧段）-結(jié)點(diǎn)”的數(shù)據(jù)組織方式，按照公共汽車線路選擇所經(jīng)過(guò)的“站點(diǎn)-路線-站點(diǎn)”形成路徑分析中的有向線。01數(shù)據(jù)準(zhǔn)備2)數(shù)據(jù)組織一般網(wǎng)絡(luò)都是由節(jié)點(diǎn)、弧段兩大基本要素組成。為了便于分析我們把這些信息組織成最基本的三類文件，即節(jié)點(diǎn)文件、弧段文件、目標(biāo)文件。節(jié)點(diǎn)文件主要記錄每個(gè)屬于節(jié)點(diǎn)集的點(diǎn)，其數(shù)據(jù)項(xiàng)包括：點(diǎn)的ID、點(diǎn)的地理坐標(biāo)、點(diǎn)的名稱、類型標(biāo)識(shí)碼等。01數(shù)據(jù)準(zhǔn)備節(jié)點(diǎn)文件結(jié)構(gòu)2)數(shù)據(jù)組織弧段文件主要記錄弧段的ID、起始節(jié)點(diǎn)、終止節(jié)點(diǎn)編號(hào)、中間點(diǎn)串以及弧段權(quán)值（可描述弧段各種屬性信息，一般主要用來(lái)描述距離信息）。01數(shù)據(jù)準(zhǔn)備弧段文件結(jié)構(gòu)2)數(shù)據(jù)組織目標(biāo)文件主要記錄以點(diǎn)目標(biāo)為端點(diǎn)，在兩個(gè)端點(diǎn)之間加入若干點(diǎn)目標(biāo)和弧段目標(biāo)形成一種有方向的線（如公交線路）,如果考慮到現(xiàn)實(shí)生活中線路的有向性還可以由已經(jīng)存在的有向線目標(biāo)反向形成。對(duì)于每條有向線，記錄其ID、幾何類型、節(jié)點(diǎn)索引、節(jié)點(diǎn)數(shù)目、弧段索引、弧段數(shù)目、弧段名稱。01數(shù)據(jù)準(zhǔn)備目標(biāo)文件結(jié)構(gòu)2)數(shù)據(jù)組織節(jié)點(diǎn)文件、弧段文件、目標(biāo)文件構(gòu)成了網(wǎng)絡(luò)的基本信息，而它們之間的相互關(guān)系則構(gòu)成了完整的網(wǎng)絡(luò)拓?fù)潢P(guān)系。01數(shù)據(jù)準(zhǔn)備文件結(jié)構(gòu)及相互之間的關(guān)系2)數(shù)據(jù)組織這種拓?fù)潢P(guān)系數(shù)據(jù)將在數(shù)據(jù)采集時(shí)構(gòu)造，并以文件形式保存下來(lái)，直至網(wǎng)絡(luò)數(shù)據(jù)發(fā)生變化。若數(shù)據(jù)未發(fā)生變化，每次運(yùn)算就直接從文件中讀取所需的拓?fù)潢P(guān)系，這樣有利于檢索和分析速度的提高。01數(shù)據(jù)準(zhǔn)備算法思想02在電子地圖中一般采用Dijkstra算法來(lái)實(shí)現(xiàn)最短路徑求解問(wèn)題。原始Dijkstra算法將網(wǎng)絡(luò)節(jié)點(diǎn)分為未標(biāo)記節(jié)點(diǎn)、臨時(shí)標(biāo)記節(jié)點(diǎn)和永久標(biāo)記節(jié)點(diǎn)3種類型。首先要將網(wǎng)絡(luò)中所有節(jié)點(diǎn)初始化為未標(biāo)記節(jié)點(diǎn)，在搜索過(guò)程中和最短路徑節(jié)點(diǎn)相連通的節(jié)點(diǎn)為臨時(shí)標(biāo)記節(jié)點(diǎn)，每一次循環(huán)都是從臨時(shí)標(biāo)記節(jié)點(diǎn)中搜索距源點(diǎn)路徑長(zhǎng)度最短的節(jié)點(diǎn)作為永久標(biāo)記節(jié)點(diǎn)，直至找到目標(biāo)節(jié)點(diǎn)或者所有節(jié)點(diǎn)都成為永久標(biāo)記節(jié)點(diǎn)才結(jié)束算法。而在原始Dijkstra算法中，臨時(shí)標(biāo)記節(jié)點(diǎn)無(wú)序地存儲(chǔ)在無(wú)序表中，這無(wú)疑成為Dijkstra算法的瓶頸，因?yàn)槊看卧谂R時(shí)標(biāo)記點(diǎn)中搜索路徑最短的節(jié)點(diǎn)時(shí)，都要遍歷所有的臨時(shí)標(biāo)記節(jié)點(diǎn)。因此，要保證算法執(zhí)行效率就必須對(duì)原始Dijkstra算法進(jìn)行改進(jìn)和優(yōu)化。02算法思想目前在實(shí)際應(yīng)用中，空間存儲(chǔ)問(wèn)題已不是要考慮的主要問(wèn)題，因此可以用空間換時(shí)間來(lái)提高最短路徑算法的效率。鄰接點(diǎn)優(yōu)化算法已經(jīng)被廣泛的應(yīng)用于電子地圖的路徑分析中，算法效率也優(yōu)于其他優(yōu)化算法。下面將介紹鄰接點(diǎn)優(yōu)化算法的思想。02算法思想Dijkstra算法的數(shù)據(jù)組織基礎(chǔ)是構(gòu)造N×N的鄰接矩陣，N是網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)。當(dāng)網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)很大時(shí)，而各節(jié)點(diǎn)的鄰接節(jié)點(diǎn)數(shù)又不多的情況下，有大量的∞元素存在，尤其是對(duì)于以真實(shí)的地圖為對(duì)象的實(shí)際應(yīng)用問(wèn)題，這樣將占用大量的存儲(chǔ)空間，并且運(yùn)算也很浪費(fèi)時(shí)間。下面具體闡述在Dijkstra算法的基礎(chǔ)上，采用鄰接點(diǎn)算法，來(lái)提高運(yùn)算速度。02算法思想一個(gè)網(wǎng)絡(luò)中，各節(jié)點(diǎn)的鄰接節(jié)點(diǎn)的最大值稱為該網(wǎng)絡(luò)的最大鄰接節(jié)點(diǎn)數(shù)。取網(wǎng)絡(luò)的最大鄰接節(jié)點(diǎn)數(shù)作為矩陣的列，網(wǎng)絡(luò)的節(jié)點(diǎn)總數(shù)作為矩陣的行，構(gòu)造鄰接節(jié)點(diǎn)矩陣來(lái)描述網(wǎng)絡(luò)結(jié)構(gòu)。鄰接節(jié)點(diǎn)矩陣的行按節(jié)點(diǎn)號(hào)從小到大順序排列與節(jié)點(diǎn)i鄰接的節(jié)點(diǎn)號(hào)寫在矩陣的第i行，如果節(jié)點(diǎn)i的鄰接節(jié)點(diǎn)數(shù)小于最大鄰接節(jié)點(diǎn)數(shù)，則以零填充，直到填滿矩陣。對(duì)照鄰接節(jié)點(diǎn)矩陣，把鄰接節(jié)點(diǎn)矩陣中各元素鄰接關(guān)系對(duì)應(yīng)的邊的權(quán)值填在同一位置上（∞對(duì)應(yīng)零元素）,構(gòu)造相應(yīng)的初始判斷矩陣。鄰接節(jié)點(diǎn)矩陣節(jié)省了存儲(chǔ)空間，為在計(jì)算機(jī)實(shí)現(xiàn)過(guò)程中進(jìn)一步提高運(yùn)算速度，提供了更加有效的網(wǎng)絡(luò)結(jié)構(gòu)組織方式。02算法思想值得注意的是，在實(shí)際應(yīng)用中，網(wǎng)絡(luò)特征可能時(shí)刻會(huì)發(fā)生變化，這就需要在算法設(shè)計(jì)時(shí)考慮實(shí)時(shí)性等因素。例如，在城市交通網(wǎng)絡(luò)中，交通特征的實(shí)時(shí)變化（如發(fā)生堵車，或臨時(shí)特定的路口不能轉(zhuǎn)彎等）都是電子地圖網(wǎng)絡(luò)分析所需要考慮的因素。而動(dòng)態(tài)網(wǎng)絡(luò)是一個(gè)與實(shí)際應(yīng)用結(jié)合緊密、發(fā)展前景廣闊的研究領(lǐng)域，隨著研究的不斷深入，其理論成果不僅