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

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

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

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

4、條弧，則鄰接矩陣中對應的元素為1，否則為0122.網(wǎng)絡分析基礎123450 1 1 0 00 0 0 1 00 1 0 0 00 0 1 0 10 0 1 1 0網(wǎng)絡的存儲模型關聯(lián)矩陣法描述圖形中結點與各條邊之間的鄰接關系，每行對應圖的一個節(jié)點，每列對應圖的一條弧關聯(lián)矩陣中1對應結點弧的起點，-1對應弧的終點；若結點與一條弧不關聯(lián)，則關聯(lián)矩陣中對應的元素為0132.網(wǎng)絡分析基礎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)絡的存儲模型鄰接表法用所有結點鄰接表的

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

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

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

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

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

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

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

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

13、絡分析資源分配通常包括定位和分配兩個問題資源定位是指已知需求的分布，確定供應點的最佳位置資源分配則是已知供應點，確定其為哪些需求點提供服務的問題資源定位問題定位問題也常稱為選址問題，涉及兩個基本概念：中心點：到所有點的距離中最大距離達到最小的位置中位點：點到其它點的距離總和達到最小的位置335.資源分配選址問題示例：在該郵區(qū)范圍內的5個城市選擇一個城市作為中心局所在地計算頂點間的最短距離，得到距離矩陣R使用中心點或中位點法確定中心位置中心點法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=選址問題示例：中位點法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=分配問題資源分配是一種按照特定原則（如距離、時間等）為供應中心分配需求點的一種分析方法，反映了現(xiàn)實世界中網(wǎng)絡資源的一種供需關系常包含兩種含義確定中心服務范圍在一定限制條件下（如時間、費用或者距離等），服務中心所能提供服務的最大空間領域確定中心資源分配范圍不僅要考慮到服務范圍內的總費用不超過中心的最大阻值，而且服務范圍內的總需求量也不能超過中心的供應量365.資源分配確定中心服務范圍基本思想 依次求出服務費用不超過中心阻值的路徑，組成這些路徑的網(wǎng)絡節(jié)點和邊的集合構成了該中心的服務范圍主要步驟根據(jù)拓撲關系，計算地理網(wǎng)絡的最大鄰接節(jié)點數(shù)構造鄰接節(jié)點矩陣和初始判斷矩陣描述地理網(wǎng)絡結構應用廣度優(yōu)先搜索算法確定地理網(wǎng)絡中心的服務范圍375.資源分配確定中心資源分配范圍基本思想：依次求出到服務中心費用不超過中心最大阻值，同時網(wǎng)絡的總需求量不超過中心的貨源量的路徑，組成這些路徑的網(wǎng)絡結點和邊的集合就構成了該中心資源分配的范圍處理時同時考慮到網(wǎng)絡和網(wǎng)絡結點