空间网络分析优秀PPT.ppt

《空间网络分析优秀PPT.ppt》由会员分享，可在线阅读，更多相关《空间网络分析优秀PPT.ppt（46页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、空间网络分析现在学习的是第1页，共46页网络模型现在学习的是第2页，共46页1网络分析的基本概念网络分析的基本概念 网络网络是一个由点、线的二元关系构成的系统，通常用来描是一个由点、线的二元关系构成的系统，通常用来描述某种资源或物质沿着路径在空间上的运动。述某种资源或物质沿着路径在空间上的运动。在在GISGIS中，中，网络分析网络分析则是依据网络拓扑关系（线性实体之间、则是依据网络拓扑关系（线性实体之间、线性实体与结点之间、结点与结点之间的连接、连通关系），通过线性实体与结点之间、结点与结点之间的连接、连通关系），通过考察网络元素的空间及属性数据，以数学理论模型为基础，对网络考察网络元素的空间

2、及属性数据，以数学理论模型为基础，对网络的性能特征进行多方面的一种分析计算。其中，的性能特征进行多方面的一种分析计算。其中，网络图论与数学模网络图论与数学模型型是网络分析的重要理论基础。是网络分析的重要理论基础。目前，网络分析在电子导航、交通旅游、城市规划管理以及电力、目前，网络分析在电子导航、交通旅游、城市规划管理以及电力、通讯等各种管网管线的布局设计中发挥了重要的作用。通讯等各种管网管线的布局设计中发挥了重要的作用。现在学习的是第3页，共46页例子例子20V5V0V4V1V3V210060301010505有向网络有向网络邻接矩阵邻接矩阵现在学习的是第4页，共46页网络的数据结构网络的数据

3、结构1）几何结构：表示地理分布位置，用点、线表示2）拓扑结构：表示连接性，用图表示现在学习的是第5页，共46页图的定义：图的定义：顶点顶点 无序无序边无向图顶点顶点 有序有序弧弧有向图有向图 有权重有权重网络GIS要进行网络分析，首先需要解决网络的表达和要进行网络分析，首先需要解决网络的表达和存储问题。存储问题。图或网络的表达：边（弧、链）、点图或网络的表达：边（弧、链）、点图或网络的存储：邻接矩阵现在学习的是第6页，共46页1 1 1 1、链（、链（、链（、链（LinkLinkLinkLink）网络中流动的管线网络中流动的管线如街道、河流、水管，如街道、河流、水管，其状态属性包括阻力和其状态

4、属性包括阻力和需求。需求。2.1 图或网络的表达：2 2 2 2、结点（、结点（、结点（、结点（NodeNodeNodeNode）网络中链的结点，如港口、车站等，其状态属性包括网络中链的结点，如港口、车站等，其状态属性包括阻力和需求等。阻力和需求等。现在学习的是第7页，共46页GISGIS要进行网络分析，首先需要解决网络的表达和存储问题。某要进行网络分析，首先需要解决网络的表达和存储问题。某局部道路网络如图局部道路网络如图2 2所示，所示，p1p1p9p9是结点编号，括号中的数字是道是结点编号，括号中的数字是道路阻强路阻强 现在学习的是第8页，共46页1 1）结结点点p5p5是是一一公公共共汽

5、汽车车站站点点，平平均均每每天天上上车车人人数数为为200200人人，下车人数为下车人数为300300人，具体表达为：人，具体表达为：结点号结点号上载需求量（人）上载需求量（人）下载需求量（人）下载需求量（人）P5P5200200300300现在学习的是第9页，共46页 2)2)道道路路p1p7p1p7是是一一双双行行道道，且且正正向向阻阻强强为为4040km/skm/s，负负向向阻阻强强为为3535km/skm/s，具体表达为具体表达为链链 弧弧号号起起 结结点点终终 结结点点正正 方方 向向 阻阻 强强（km/skm/s）反反 方方 向向 阻阻 强强（km/skm/s）p1p7p1p71

6、17 7404035353 3）道路）道路p6p8p6p8是一单行道，且阻强为是一单行道，且阻强为2020km/skm/s，具体表达为：具体表达为：链弧号链弧号起结点起结点终终 结结点点正正 方方 向向 阻阻 强强（km/skm/s）反反 方方 向向 阻阻 强强（km/skm/s）P6p8P6p86 68 82020-1(-1(表不通表不通)现在学习的是第10页，共46页结点中的特殊类型障碍（障碍（BarrierBarrier），），禁止网络上流动的点。禁止网络上流动的点。拐点（拐点（TurnTurn），），出现在网络中的分割点上，其状态有属性和阻力，出现在网络中的分割点上，其状态有属性和阻力

7、，如拐弯的时间和限制（如在如拐弯的时间和限制（如在8 8点到点到1818点不允许左拐）。点不允许左拐）。中心（中心（CenterCenter），），是接受或分配资源的位置，如水库、商业中是接受或分配资源的位置，如水库、商业中心，电站等，其状态包括资源容量（如总量），阻力限额（中心，电站等，其状态包括资源容量（如总量），阻力限额（中心到链的最大距离或时间）。心到链的最大距离或时间）。站点（站点（StopStop），），在路径选择中资源增减的结点，如库房、车站等，其在路径选择中资源增减的结点，如库房、车站等，其状态属性有资源需求，如产品数量。状态属性有资源需求，如产品数量。现在学习的是第11页，共

8、46页拐点拐点现在学习的是第12页，共46页转弯类型 描 述属性表 0=无阻强-1=不允许拐弯U型拐弯指从6号弧至20号结点并从20号结点转回6号弧，这是一个180度转弯，花费20秒时间停靠点使得从6号弧至其他弧段直到 7 号弧，向左转至8号弧，向右转至9号弧的运移减慢不允许从 6 号弧转至 9 号弧，并赋予负值阻强；允许其他方向的转变，其阻强为正高架道或地道允许直通而无延迟，如从6号弧至7号弧；但不允许转弯，此时以负的阻强表示，如从6号弧至8、9号弧968720U型转弯角度至弧段从弧段结点号时间阻强/s968720高架道或地道968720停靠点968720不准转弯66202007620159

9、0862020-909620101807620008620-1909620-1-909620-1-9076205086201090现在学习的是第13页，共46页2.2 图或网络的存储 P170邻接矩阵无向图、有向图 有向网络1、0 1、&、0现在学习的是第14页，共46页3空间网络分析的方法空间网络分析的方法3.13.1路径分析路径分析v v最短路径分析最短路径分析v连通性分析连通性分析-最小生成树最小生成树3.23.2中心选址中心选址现在学习的是第15页，共46页 3.1.1 3.1.1 最短路径求解最短路径求解v最短路径求解有多种不同的方法，其中最短路径求解有多种不同的方法，其中Dijks

10、traDijkstra算法算法适合于求解某个起点（源点）到网络中的其它各适合于求解某个起点（源点）到网络中的其它各个结点的最佳路径。个结点的最佳路径。现在学习的是第16页，共46页例子例子20V5V0V4V1V3V210060301010505有向网络有向网络现在学习的是第17页，共46页例子(思路)ACiBi 如图所示，如图所示，A A为所求最短距离的起点，其他为所求最短距离的起点，其他Bi,Bi,Ci Ci 为终点。为终点。目的目的:求求一系列最短距离一系列最短距离。我们先假定这些最短距。我们先假定这些最短距离互不相等。那么我们可以把这些最短距离按升离互不相等。那么我们可以把这些最短距离按

11、升序（从小到大）排列序（从小到大）排列步骤步骤:我们把所有顶点分为两类我们把所有顶点分为两类C C和和B.B.令令A A到到BiBi这些这些顶点的最短距离顶点的最短距离不为无穷大不为无穷大,A A到到CiCi这些顶点的最这些顶点的最短距离为短距离为无穷大无穷大 这就说明这就说明A A到到CiCi中的点要么不通，要么通过中的点要么不通，要么通过BiBi中的点与之连接。中的点与之连接。现在学习的是第18页，共46页例子例子(思路思路)ACiBi 这样，对于这样，对于A A到到CiCi中任何一个点中任何一个点的最小距离，我们总可以在的最小距离，我们总可以在BiBi中找到中找到一点，使得一点，使得A

12、A到这一点的最小距离到这一点的最小距离小于前一个距离。（因为小于前一个距离。（因为A A到到CiCi中中的点要么不通，要么通过的点要么不通，要么通过BiBi中的点中的点与之连通。与之连通。）因此，我们可以先不考虑因此，我们可以先不考虑CiCi中中的点。的点。现在学习的是第19页，共46页例子例子(思路思路)于是，对于右图，我们第一步只考虑于是，对于右图，我们第一步只考虑下图下图:V5V0V4V21003010Bi=v2,v4,v520V5V0V4V1V3V210060301010505现在学习的是第20页，共46页例子例子(思路思路)我们用我们用我们用我们用mindistmindistmind

13、istmindist这个数组来保存由这个数组来保存由这个数组来保存由这个数组来保存由v0v0v0v0到其它顶点的最小距离，这些距到其它顶点的最小距离，这些距到其它顶点的最小距离，这些距到其它顶点的最小距离，这些距离按升序排列。离按升序排列。离按升序排列。离按升序排列。考虑右图：考虑右图：考虑右图：考虑右图：第一步，通过比较，我们知道第一步，通过比较，我们知道第一步，通过比较，我们知道第一步，通过比较，我们知道 mindistancev0v2=mindist0=10mindistancev0v2=mindist0=10mindistancev0v2=mindist0=10mindistancev

14、0v2=mindist0=10,（v0-v2)v0-v2)v0-v2)v0-v2)这是我们求出的第一个最小距离这是我们求出的第一个最小距离这是我们求出的第一个最小距离这是我们求出的第一个最小距离一旦我们得到一旦我们得到v2v2，我们就可以知道：我们就可以知道：V5V0V4V21003010向量现在学习的是第21页，共46页例子例子(思路思路)V0V0跟跟 v2v2直接连通到的点直接连通到的点v3v3 之间的之间的最小距离不再是无穷大，它应当是最小距离不再是无穷大，它应当是mindistancev0v2+disv2v3mindistancev0v2+disv2v3,这样我们应当把这样我们应当把v

15、3v3放入前面的集合放入前面的集合BiBi中。中。（注意：有多少（注意：有多少v2v2直接连通到的点直接连通到的点都应当考虑进来。都应当考虑进来。）V5V0V4V3V2100301050Bi=v2,v4,v5,v3现在学习的是第22页，共46页例子例子(思路思路)第二步，我们把与第二步，我们把与v2v2直接连通的点直接连通的点v3v3考虑进考虑进来。来。dis05=100;dis04=30;dis05=100;dis04=30;dis02=10;dis03=60;dis02=10;dis03=60;除除1010以外，以外，3030是最小的。是最小的。我们可以证明我们可以证明3030是是v0v0

16、到其它顶点除到其它顶点除1010以外最小的。以外最小的。V5V0V4V3V2100301050向量现在学习的是第23页，共46页例子例子(思路思路)这样我们得到我们的第二个最小距离：这样我们得到我们的第二个最小距离：Mindistancev0v4=mindist1=30 Mindistancev0v4=mindist1=30,(v0-v4),(v0-v4)接下来，我们把接下来，我们把v4v4与之直接连通的点与之直接连通的点考虑进考虑进来。来。V5V0V4V3V2100301050Bi现在学习的是第24页，共46页例子以v0为起点，计算它到其它各顶点的最短路径，计算过程中最短路径长度向量D的变化

17、见D0-D4，计算出的各条最短路径。现在学习的是第25页，共46页例子例子20V5V0V4V1V3V210060301010505有向网络有向网络现在学习的是第26页，共46页V0V1V2V3V4V5V0V0为起始点为起始点为起始点为起始点0(&)(10)(&)(30)(100)V02=100(&)10(60)(30)(100)V04=300(&)10(50)30(90)V03=500(&)105030(60)V05=600(&)10503060V01=&0&1050306012现在学习的是第27页，共46页例子例子起点起点终点终点最短路径最短路径路路径径长长度度v0v1无无v2(v0,v2)

18、10v3(v0,v4,v3)50v4(v0,v4)30v5(v0,v4,v3,v5)60现在学习的是第28页，共46页20V5V0V4V1V3V210060301010505带权有向图带权有向图作业作业1:1:求求V0到到V5的最短路径的最短路径现在学习的是第29页，共46页V0V1V2V3V4V5V0V0为起始点为起始点为起始点为起始点0(&)(10)(30)(&)(100)V02=100(&)10(30)(&)(100)V03=300(&)1030(&)(40)V05=400(&)1030(&)40V01=&0&1030(&)40V04=&0&1030&4012现在学习的是第30页，共46

19、页起点起点终点终点最短路径最短路径路路径径长长度度v0v1无无v2(v0,v2)10v3(v0,v3)30v4无无v5(v0,v3,v5)40现在学习的是第31页，共46页规律规律(步骤步骤)制作制作制作制作N*NN*N的矩阵的矩阵第第第第m行就意味着有行就意味着有mm个值个值(距离距离)已经确定已经确定在确定一个点后在确定一个点后,与该点相邻接的点的距离重新计算与该点相邻接的点的距离重新计算,与该点不相邻的则保持不变与该点不相邻的则保持不变(直接照抄之前的直接照抄之前的)在重新计算点的距离时在重新计算点的距离时在重新计算点的距离时在重新计算点的距离时,只要考虑与该点相邻的只要考虑与该点相邻的

20、只要考虑与该点相邻的只要考虑与该点相邻的所有点的最所有点的最短距离短距离.现在学习的是第32页，共46页v6v8v1v7v5v4v2v389363253757作业作业2:2:求求V1V1到其他各点的最短路径到其他各点的最短路径现在学习的是第33页，共46页V1V1V2V2V3V3V4V4V5V5V6V6V7V7V8V8V1V1为起始点为起始点0 0(9)(9)(&)(&)(&)(&)(&)(&)(6)(6)(3)(3)(8)(8)V17=3V17=30 0(9)(9)(&)(&)(&)(&)(8)(8)(6)(6)3 3(8)(8)V16=6V16=60 0(9)(9)(&)(&)(&)(&)

21、(8)(8)6 63 3(8)(8)V15=8V15=80 0(9)(9)(&)(&)(15)(15)8 86 63 3(8)(8)V18=8V18=80 0(9)(9)(&)(&)(15)(15)8 86 63 38 8V12=9V12=90 09 9(14)(14)(12)(12)8 86 63 38 8V14=12V14=120 09 9(14)(14)12128 86 63 38 8V13=14V13=140 09 9141412128 86 63 38 8现在学习的是第34页，共46页3.1.2 连通性分析-最小生成树（1）概念连通图：在一个图中，任意两个节点之间都存在一条路。树：若

22、一个连通图中不存在任何回路，则称为树。生成树的权数：生成树中各边的权数之和。最小生成树：图的极小连通子图。（2 2）应用：通信线路、快递）应用：通信线路、快递56现在学习的是第35页，共46页（3 3）构造最小生成树的）构造最小生成树的依据依据：v v在网中选择在网中选择N-1条边连接网的条边连接网的N N个顶点个顶点v v尽可能选取权值为最小的边尽可能选取权值为最小的边3.1.2 连通性分析-最小生成树现在学习的是第36页，共46页(4)(4)算法（算法（KruskalKruskal，克罗斯克尔算法，也叫克罗斯克尔算法，也叫“避圈避圈”法）法）1 1）先把图中的各边按权数从小到大重新排列，并

23、取权数最小）先把图中的各边按权数从小到大重新排列，并取权数最小的一条边为最小生成树中的边。的一条边为最小生成树中的边。2 2）在剩下的边中，按顺序取下一条边。若该边与最小生成树中）在剩下的边中，按顺序取下一条边。若该边与最小生成树中已有的边，构成回路，则舍去该边，否则选中生成树。已有的边，构成回路，则舍去该边，否则选中生成树。3 3）重复）重复2 2），直到有），直到有M-1M-1条边被选进生成树中，这条边被选进生成树中，这M-1M-1条边就构条边就构成最小生成树成最小生成树3.1.2 连通性分析-最小生成树现在学习的是第37页，共46页3.1.2 连通性分析-最小生成树具体步骤具体步骤现在学

24、习的是第38页，共46页请应用克罗斯克尔算法确定下图的最小生成树（含步骤）。12345647710131718152228作业：作业：现在学习的是第39页，共46页894612752715V6V1V2V3V4V5V7现在学习的是第40页，共46页4.2 中心选址问题 中心点选址问题中，最佳选址位置的判定标准，是使其所在的顶点与图中其它顶点之间的最大距离达到最小，或者使其所在的顶点到图中其它顶点之间的距离之和达到最小。这个选址问题实际上就是求网络图的中心点问题。这类选址问题适宜于医院、消防站等服务设施的布局问题。现在学习的是第41页，共46页v6v8v1v7v5v4v2v389363253757

25、中心选址问题的实例例如，某县要在其所辖的8个乡镇之一修建一个消防站，为8个乡镇服务，要要求求消消防防站站至至最最远远乡乡镇镇的的距距离离达达到到最最小小。假设该8个乡镇之间的交通网络被抽象为无向赋权连通图，权值为乡镇之间的距离。下面求解消防站应设在哪个乡镇，即哪个顶点？现在学习的是第42页，共46页首先，用首先，用DijkstraDijkstra算法计算出算法计算出每一个顶点每一个顶点每一个顶点每一个顶点v vi i至其它各顶点至其它各顶点v vj j的最的最短路径长度短路径长度d dijij(i i,j j=1,2,=1,2,6),6)，写出距离矩阵：写出距离矩阵：中心选址问题的实例6061

26、916152565473现在学习的是第43页，共46页其其次次，求求距距离离矩矩阵阵中中每每行行的的最最大大值值，即即各各个个顶顶点点的的最最大大服服务务距离，得距离，得e e(v v1 1)=14,)=14,e e(v v2 2)=15,)=15,e e(v v3 3)=20,)=20,e e(v v4 4)=12,)=12,e e(v v5 5)=15,)=15,e e(v v6 6)=17,)=17,e e(v v7 7)=12,)=12,e e(v v8 8)=20)=20最最后后计计算算最最大大服服务务距距离离的的最最小小值值。显显然然，e e(v v4 4)=e e(v v7 7)=)=minmin e e(v vi i)。所以，所以，消防站应建在消防站应建在消防站应建在消防站应建在v v v v4 4 4 4或或或或v v v v7 7 7 7点所在的乡镇点所在的乡镇点所在的乡镇点所在的乡镇。中心选址问题的实例现在学习的是第44页，共46页6061916152565473要求消防站至要求消防站至所有所有乡镇的距离达到最小乡镇的距离达到最小：中心选址问题的实例消防站应建在消防站应建在消防站应建在消防站应建在v v v v5 5 5 5点所在的乡镇点所在的乡镇点所在的乡镇点所在的乡镇现在学习的是第45页，共46页现在学习的是第46页，共46页