空間網(wǎng)絡(luò)分析課件

1、空間分析概述網(wǎng)絡(luò)分析基礎(chǔ)網(wǎng)絡(luò)結(jié)構(gòu)分析最優(yōu)路徑分析資源分配本章小結(jié)1空間網(wǎng)絡(luò)分析Internet:把路由器看作節(jié)點(diǎn)，把光纜看作連接邊1.概述HTTP:把客戶機(jī)/服務(wù)器看作節(jié)點(diǎn)，把請(qǐng)求/應(yīng)答看作邊，色彩表示請(qǐng)求量1.概述WWW: 把文檔看作節(jié)點(diǎn)，把超鏈接看作邊，色彩代表不同公司的商務(wù)網(wǎng)1.概述Routes of Airlines: 把機(jī)場(chǎng)看作節(jié)點(diǎn)，把航線看作邊1.概述集成電路中元器件是節(jié)點(diǎn)，連線是邊1.概述空間網(wǎng)絡(luò)分析通過(guò)研究網(wǎng)絡(luò)的狀態(tài)以及模擬和分析資源在網(wǎng)絡(luò)上的流動(dòng)和分配情況，對(duì)網(wǎng)絡(luò)結(jié)構(gòu)及其資源等的優(yōu)化問(wèn)題進(jìn)行研究的一種空間分析方法71.概述主要用來(lái)解決兩大類問(wèn)題研究地理網(wǎng)絡(luò)的結(jié)構(gòu)，如：優(yōu)化路徑

2、的求解、連通分量求解等問(wèn)題研究資源在網(wǎng)絡(luò)系統(tǒng)中的分配與流動(dòng)如：資源分配范圍或服務(wù)范圍確定、最大流與最小費(fèi)用等問(wèn)題空間網(wǎng)絡(luò)分析實(shí)例從A到B點(diǎn)的最快路線是什么？哪些房屋距離消防站的車程小于5分鐘？哪輛救護(hù)車能夠最快對(duì)一起事故做出響應(yīng)？一支配送或服務(wù)車隊(duì)如何在提高客戶服務(wù)質(zhì)量的同時(shí)降低運(yùn)輸成本？如果某家公司必須縮減規(guī)模，那么它應(yīng)該關(guān)閉哪家商店才能繼續(xù)滿足最為全面的需求？81.概述概述網(wǎng)絡(luò)分析基礎(chǔ)網(wǎng)絡(luò)結(jié)構(gòu)分析最優(yōu)路徑分析資源分配本章小結(jié)9空間網(wǎng)絡(luò)分析網(wǎng)絡(luò)的基本要素鏈：網(wǎng)絡(luò)中兩個(gè)結(jié)點(diǎn)之間的弧段結(jié)點(diǎn)：鏈的兩個(gè)端點(diǎn)站點(diǎn)：網(wǎng)絡(luò)路徑上資源增加、減少的地方，是分布于網(wǎng)絡(luò)鏈上的結(jié)點(diǎn)，如公交站點(diǎn)中心點(diǎn)：網(wǎng)絡(luò)中具有一定

3、容量，能夠從鏈上獲取資源或發(fā)送資源的結(jié)點(diǎn)，如水庫(kù)、商業(yè)中心、學(xué)校等障礙：網(wǎng)絡(luò)中阻斷資源流動(dòng)的結(jié)點(diǎn)或鏈，如禁止通行的道路、交通紅燈等拐角：指網(wǎng)絡(luò)中資源流動(dòng)可能發(fā)生轉(zhuǎn)向的結(jié)點(diǎn)，如禁止左拐的路口102.網(wǎng)絡(luò)分析基礎(chǔ)網(wǎng)絡(luò)基本要素的屬性項(xiàng)阻礙強(qiáng)度用于量測(cè)資源在網(wǎng)絡(luò)中流動(dòng)的費(fèi)用或阻礙，可以作為網(wǎng)絡(luò)鏈、站點(diǎn)和中心點(diǎn)的屬性，通常用時(shí)間、成本來(lái)衡量資源需求量網(wǎng)絡(luò)中可被“運(yùn)輸”的資源數(shù)量，如沿街道居住的學(xué)生人數(shù)、某一站點(diǎn)要被運(yùn)送的貨物等資源容量指一個(gè)中心可以容納或可以提供的資源總量，如學(xué)校的總?cè)藬?shù)、停車場(chǎng)的停車位等112.網(wǎng)絡(luò)分析基礎(chǔ)網(wǎng)絡(luò)的存儲(chǔ)模型鄰接矩陣法用于表示圖中任意兩點(diǎn)間的鄰接關(guān)系及其權(quán)值的矩陣兩點(diǎn)間有一

4、條弧，則鄰接矩陣中對(duì)應(yīng)的元素為1，否則為0122.網(wǎng)絡(luò)分析基礎(chǔ)123450 1 1 0 00 0 0 1 00 1 0 0 00 0 1 0 10 0 1 1 0網(wǎng)絡(luò)的存儲(chǔ)模型關(guān)聯(lián)矩陣法描述圖形中結(jié)點(diǎn)與各條邊之間的鄰接關(guān)系，每行對(duì)應(yīng)圖的一個(gè)節(jié)點(diǎn)，每列對(duì)應(yīng)圖的一條弧關(guān)聯(lián)矩陣中1對(duì)應(yīng)結(jié)點(diǎn)弧的起點(diǎn)，-1對(duì)應(yīng)弧的終點(diǎn)；若結(jié)點(diǎn)與一條弧不關(guān)聯(lián)，則關(guān)聯(lián)矩陣中對(duì)應(yīng)的元素為0132.網(wǎng)絡(luò)分析基礎(chǔ)12345 1 1 0 0 0 0 0 0-1 0 1 -1 0 0 0 00 -1 0 1 -1 0 -1 00 0 -1 0 1 1 0 -1 0 0 0 0 0 -1 1 1網(wǎng)絡(luò)的存儲(chǔ)模型鄰接表法用所有結(jié)點(diǎn)鄰接表的

5、集合表示142.網(wǎng)絡(luò)分析基礎(chǔ)1234512345242338640600390530470結(jié)點(diǎn)號(hào)結(jié)點(diǎn)信息概述網(wǎng)絡(luò)分析基礎(chǔ)網(wǎng)絡(luò)結(jié)構(gòu)分析最優(yōu)路徑分析資源分配本章小結(jié)15空間網(wǎng)絡(luò)分析度與中心度度：指一個(gè)結(jié)點(diǎn)所連接邊的數(shù)目，是衡量和刻畫(huà)網(wǎng)絡(luò)結(jié)點(diǎn)特性最簡(jiǎn)單又最重要的概念中心度：衡量結(jié)點(diǎn)在網(wǎng)絡(luò)中所處中心地位程度的一個(gè)指標(biāo)點(diǎn)度中心度通過(guò)計(jì)算結(jié)點(diǎn)的度來(lái)度量結(jié)點(diǎn)在圖中的核心地位程度僅考慮了與該結(jié)點(diǎn)直接相連的點(diǎn)數(shù)，而忽視了間接相連的點(diǎn)數(shù)163.網(wǎng)絡(luò)結(jié)構(gòu)分析BAC度與中心度中心度：衡量結(jié)點(diǎn)在網(wǎng)絡(luò)中所處中心地位程度的一個(gè)指標(biāo)接近中心性從距離角度來(lái)衡量一個(gè)結(jié)點(diǎn)的中心地位，認(rèn)為結(jié)點(diǎn)到網(wǎng)絡(luò)中其它所有點(diǎn)的總距離最小，此時(shí)其接

6、近中心性的值越大，則可認(rèn)為該點(diǎn)是整個(gè)網(wǎng)絡(luò)的中心點(diǎn) 其中，N是結(jié)點(diǎn)個(gè)數(shù)，dij表示結(jié)點(diǎn)i到j(luò)的距離173.網(wǎng)絡(luò)結(jié)構(gòu)分析BAC度與中心度中心度：衡量結(jié)點(diǎn)在網(wǎng)絡(luò)中所處中心地位程度的一個(gè)指標(biāo)介數(shù)中心性從信息、物質(zhì)或能量傳輸角度看，認(rèn)為經(jīng)過(guò)最短路徑條數(shù)最多的邊和結(jié)點(diǎn)是網(wǎng)絡(luò)上承載流量最大的邊和結(jié)點(diǎn)例如：如果不經(jīng)過(guò)結(jié)點(diǎn)v2，結(jié)點(diǎn)v3、v4就無(wú)法到達(dá)v1，這樣v2在整個(gè)網(wǎng)絡(luò)中起了很重要的橋梁作用，其中心程度要大于其它結(jié)點(diǎn)183.網(wǎng)絡(luò)結(jié)構(gòu)分析路徑與回路路徑：從一結(jié)點(diǎn)到另一結(jié)點(diǎn)的一組結(jié)點(diǎn)序列路徑長(zhǎng)度：路徑上所經(jīng)過(guò)邊的數(shù)目回路：起點(diǎn)和終點(diǎn)相同的路徑哈密爾頓回路: 有且僅有一次通過(guò)圖中所有結(jié)點(diǎn)的回路 如：1, 2,

7、4, 5, 6, 3, 1歐拉回路：有且僅有一次通過(guò)圖中所有邊的回路， 如：1, 2, 4, 5, 2, 3, 5, 6, 3, 1193.網(wǎng)絡(luò)結(jié)構(gòu)分析連通性與生成樹(shù)連通性：在無(wú)向圖中，若從結(jié)點(diǎn)u到結(jié)點(diǎn)v有路徑存在，則稱u到v是連通的強(qiáng)連通圖：圖中任意兩個(gè)結(jié)點(diǎn)之間都連通圖的生成樹(shù)：一個(gè)連通圖的極小連通子圖 滿足：生成樹(shù)的邊數(shù)為n-1（頂點(diǎn)數(shù)為N）樹(shù)無(wú)回路，但不相鄰頂點(diǎn)連成一邊，就會(huì)得到一個(gè)回路樹(shù)是連通的，如去掉任意一條邊，不會(huì)變成不連通的203.網(wǎng)絡(luò)結(jié)構(gòu)分析連通性與生成樹(shù)最小生成樹(shù)：一個(gè)連通圖眾多生成樹(shù)中邊權(quán)值之和最小的生成樹(shù)（minimal spanning tree, MST）特點(diǎn)：N-1

8、條邊連接N個(gè)結(jié)點(diǎn)所有邊權(quán)值和最小例如：在n個(gè)城市間建立通信線路， 使得通信網(wǎng)的造價(jià)最低213.網(wǎng)絡(luò)結(jié)構(gòu)分析最小生成樹(shù)算法Kruskal算法先把圖中的各邊按權(quán)數(shù)從小到大重新排列，并取權(quán)數(shù)最小的一條邊為最小生成樹(shù)中的邊在剩下的邊中，按順序取下一條邊。若該邊與最小生成樹(shù)中已有的邊，構(gòu)成回路，則舍去該邊，否則選入生成樹(shù)重復(fù)步驟2，直到有M-1條邊被選進(jìn)生成樹(shù)中，這M-1條邊就構(gòu)成最小生成樹(shù)223.網(wǎng)絡(luò)結(jié)構(gòu)分析直徑、半徑和中心結(jié)點(diǎn)半徑：從某結(jié)點(diǎn)到其它所有結(jié)點(diǎn)的最長(zhǎng)路徑長(zhǎng)度結(jié)點(diǎn)v1、v2、v3、v4的半徑分別為：2、1、2、2圖的直徑：圖中任意兩個(gè)結(jié)點(diǎn)間的最長(zhǎng)路徑圖G的直徑是2圖的中心：具有最小半徑的結(jié)點(diǎn)

9、稱為圖的中心中心點(diǎn)是結(jié)點(diǎn)v2233.網(wǎng)絡(luò)結(jié)構(gòu)分析v1v2v3v4概述網(wǎng)絡(luò)分析基礎(chǔ)網(wǎng)絡(luò)結(jié)構(gòu)分析最優(yōu)路徑分析資源分配本章小結(jié)24空間網(wǎng)絡(luò)分析最優(yōu)路徑的含義路徑分析是網(wǎng)絡(luò)分析中一個(gè)最基本的問(wèn)題，也是實(shí)際應(yīng)用中最常見(jiàn)的一個(gè)問(wèn)題最優(yōu)路徑有多種含義，不僅僅指一般意義上的距離最短，還可指時(shí)間最短、費(fèi)用最少、成本最低等含義例 1：居民出行利用車輛導(dǎo)航獲取距離最近、費(fèi)用最優(yōu)的路徑例 2：電力、水力管線的架設(shè)管線考慮的是成本最優(yōu)的路徑最短路徑分類兩個(gè)結(jié)點(diǎn)之間的最短路徑一個(gè)結(jié)點(diǎn)到圖中其它所有結(jié)點(diǎn)之間的最短路徑所有結(jié)點(diǎn)對(duì)之間的最短路徑254.最優(yōu)路徑分析單源最短路徑算法Dijkstra基本思想： 采用貪心策略，以源點(diǎn)

10、為中心向外層擴(kuò)展，直到擴(kuò)展到目標(biāo)點(diǎn)為止，即從源點(diǎn)依次產(chǎn)生出路徑長(zhǎng)度遞增的最短路徑基本步驟：將圖的結(jié)點(diǎn)集合V被分為兩組（S和T），其中S存放已經(jīng)計(jì)算出最短路徑的結(jié)點(diǎn)（初始時(shí)只包含源點(diǎn)），T=V-S從集合T中選擇距離最小的結(jié)點(diǎn)u，并將此頂點(diǎn)從集合T移入S中以u(píng)為新的中間點(diǎn)，修改T中結(jié)點(diǎn)的最短距離，以保證從源點(diǎn)s到T中并經(jīng)過(guò)結(jié)點(diǎn)u的最短路徑長(zhǎng)度不大于原來(lái)不經(jīng)過(guò)頂點(diǎn)u的距離重復(fù)2-3，直到所有頂點(diǎn)都被加入到S中264.最優(yōu)路徑分析單源最短路徑算法Dijkstra示例274.最優(yōu)路徑分析04321101005060103020043211010050601030200432110100506010302

11、0單源最短路徑算法Dijkstra示例284.最優(yōu)路徑分析043211010050601030200432110100506010302004321101005060103020旅行商問(wèn)題（travelling salesman problem，TSP） 一個(gè)商品推銷員要去若干個(gè)城市推銷商品，該推銷員從一個(gè)城市出發(fā)，需要經(jīng)過(guò)每一個(gè)城市并且只經(jīng)過(guò)一次，最后回到出發(fā)地，該如何選擇行進(jìn)的線路使得總旅程距離最短？TSP算法分類精確算法（時(shí)間代價(jià)巨大）分支界定法、線性規(guī)劃法、動(dòng)態(tài)規(guī)劃法等啟發(fā)式算法 插入法、 隨機(jī)貪婪法、模擬退火法、遺傳法、神經(jīng)網(wǎng)絡(luò)法、蟻群算法294.最優(yōu)路徑分析TSP算法最近鄰插入法基

12、本思想：尋找與回路最近鄰的結(jié)點(diǎn)并加入其中，構(gòu)造一個(gè)結(jié)點(diǎn)數(shù)逐漸遞增的回路，最后得到一個(gè)哈密頓回路即為近似解基本步驟（設(shè)T表示回路中的結(jié)點(diǎn)集合，S表示回路外的結(jié)點(diǎn)）初始化：T=1，S=2,3, ., n從S中選擇一個(gè)結(jié)點(diǎn)i 將之加入T中，尋找回路T中的x,y,使得d(x,i)+d(y,i)-d(x,y) 值最小，將x,y從回路中刪除，同時(shí)增加邊(x,i)和(i,y), 即選擇一條使回路長(zhǎng)度增加值最小的邊加入回路若S為空，結(jié)束，否則轉(zhuǎn)到步驟（2），直到所有結(jié)點(diǎn)加入回路中304.最優(yōu)路徑分析TSP算法最近鄰插入法示例314.最優(yōu)路徑分析概述網(wǎng)絡(luò)分析基礎(chǔ)網(wǎng)絡(luò)結(jié)構(gòu)分析最優(yōu)路徑分析資源分配本章小結(jié)32空間網(wǎng)

13、絡(luò)分析資源分配通常包括定位和分配兩個(gè)問(wèn)題資源定位是指已知需求的分布，確定供應(yīng)點(diǎn)的最佳位置資源分配則是已知供應(yīng)點(diǎn)，確定其為哪些需求點(diǎn)提供服務(wù)的問(wèn)題資源定位問(wèn)題定位問(wèn)題也常稱為選址問(wèn)題，涉及兩個(gè)基本概念：中心點(diǎn)：到所有點(diǎn)的距離中最大距離達(dá)到最小的位置中位點(diǎn)：點(diǎn)到其它點(diǎn)的距離總和達(dá)到最小的位置335.資源分配選址問(wèn)題示例：在該郵區(qū)范圍內(nèi)的5個(gè)城市選擇一個(gè)城市作為中心局所在地計(jì)算頂點(diǎn)間的最短距離，得到距離矩陣R使用中心點(diǎn)或中位點(diǎn)法確定中心位置中心點(diǎn)法MVV(1)=max(0,3,4,3,2)=4MVV(2)=max(3,0,1,3,4)=4MVV(3)=max(4,1,0,2,3)=4MVV(4)=m

14、ax(3,3,2,0,1)=3MVV(5)=max(2,4,3,1,0)=4最大距離的最小值為3，則選城市4 為中心局所在地345.資源分配21543352147120 3 4 3 2 0 1 3 44 1 0 2 33 3 2 0 12 4 3 1 0R=選址問(wèn)題示例：中位點(diǎn)法SVV(1)=3+4+3+2=12SVV(2)=3+1+3+4=11SVV(3)=4+1+2+3=10SVV(4)=3+3+2+1=9SVV(5)=2+4+3+1=10最大距離的最小值為3，則選城市4 為中心局所在地355.資源分配21543352147120 3 4 3 2 0 1 3 44 1 0 2 33 3 2

15、 0 12 4 3 1 0R=分配問(wèn)題資源分配是一種按照特定原則（如距離、時(shí)間等）為供應(yīng)中心分配需求點(diǎn)的一種分析方法，反映了現(xiàn)實(shí)世界中網(wǎng)絡(luò)資源的一種供需關(guān)系常包含兩種含義確定中心服務(wù)范圍在一定限制條件下（如時(shí)間、費(fèi)用或者距離等），服務(wù)中心所能提供服務(wù)的最大空間領(lǐng)域確定中心資源分配范圍不僅要考慮到服務(wù)范圍內(nèi)的總費(fèi)用不超過(guò)中心的最大阻值，而且服務(wù)范圍內(nèi)的總需求量也不能超過(guò)中心的供應(yīng)量365.資源分配確定中心服務(wù)范圍基本思想 依次求出服務(wù)費(fèi)用不超過(guò)中心阻值的路徑，組成這些路徑的網(wǎng)絡(luò)節(jié)點(diǎn)和邊的集合構(gòu)成了該中心的服務(wù)范圍主要步驟根據(jù)拓?fù)潢P(guān)系，計(jì)算地理網(wǎng)絡(luò)的最大鄰接節(jié)點(diǎn)數(shù)構(gòu)造鄰接節(jié)點(diǎn)矩陣和初始判斷矩陣描述地理網(wǎng)絡(luò)結(jié)構(gòu)應(yīng)用廣度優(yōu)先搜索算法確定地理網(wǎng)絡(luò)中心的服務(wù)范圍375.資源分配確定中心資源分配范圍基本思想：依次求出到服務(wù)中心費(fèi)用不超過(guò)中心最大阻值，同時(shí)網(wǎng)絡(luò)的總需求量不超過(guò)中心的貨源量的路徑，組成這些路徑的網(wǎng)絡(luò)結(jié)點(diǎn)和邊的集合就構(gòu)成了該中心資源分配的范圍處理時(shí)同時(shí)考慮到網(wǎng)絡(luò)和網(wǎng)絡(luò)結(jié)點(diǎn)