《空间网络分析精.ppt》由会员分享，可在线阅读，更多相关《空间网络分析精.ppt（46页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、空间网络分析第1页，本讲稿共46页网络模型第2页，本讲稿共46页1网络分析的基本概念网络分析的基本概念 网络网络是一个由点、线的二元关系构成的系统，通常用来描述某种是一个由点、线的二元关系构成的系统，通常用来描述某种资源或物质沿着路径在空间上的运动。资源或物质沿着路径在空间上的运动。在在GISGIS中，中，网络分析网络分析则是依据网络拓扑关系（线性实体之间、则是依据网络拓扑关系（线性实体之间、线性实体与结点之间、结点与结点之间的连接、连通关系），通线性实体与结点之间、结点与结点之间的连接、连通关系），通过考察网络元素的空间及属性数据，以数学理论模型为基础，对过考察网络元素的空间及属性数据，以数
2、学理论模型为基础，对网络的性能特征进行多方面的一种分析计算。其中，网络的性能特征进行多方面的一种分析计算。其中，网络图论与网络图论与数学模型数学模型是网络分析的重要理论基础。是网络分析的重要理论基础。目前，网络分析在电子导航、交通旅游、城市规划管理以及目前，网络分析在电子导航、交通旅游、城市规划管理以及电力、通讯等各种管网管线的布局设计中发挥了重要的作用。电力、通讯等各种管网管线的布局设计中发挥了重要的作用。第3页，本讲稿共46页例子例子20V5V0V4V1V3V210060301010505有向网络有向网络邻接矩阵邻接矩阵第4页，本讲稿共46页网络的数据结构网络的数据结构1）几何结构：表示地
3、理分布位置，用点、线表示2）拓扑结构：表示连接性，用图表示第5页，本讲稿共46页图的定义：图的定义：顶点顶点 无序无序边边无向图无向图顶点顶点 有序有序弧弧有向图有向图 有权重有权重网络网络GISGIS要进行网络分析，首先需要解决网络的表达和存要进行网络分析，首先需要解决网络的表达和存要进行网络分析，首先需要解决网络的表达和存要进行网络分析，首先需要解决网络的表达和存储问题。储问题。储问题。储问题。图或网络的表达：边（弧、链）、点图或网络的表达：边（弧、链）、点图或网络的存储：邻接矩阵图或网络的存储：邻接矩阵第6页，本讲稿共46页1 1 1 1、链（、链（、链（、链（LinkLinkLinkL
4、ink）网络中流动的管网络中流动的管线如街道、河流、水线如街道、河流、水管，其状态属性包括管，其状态属性包括阻力和需求。阻力和需求。2.1 图或网络的表达：2 2 2 2、结点（、结点（、结点（、结点（NodeNodeNodeNode）网络中链的结点，如港口、车站等，其状态属性包括网络中链的结点，如港口、车站等，其状态属性包括阻力和需求等。阻力和需求等。第7页，本讲稿共46页GISGIS要进行网络分析，首先需要解决网络的表达和存储问题。某要进行网络分析，首先需要解决网络的表达和存储问题。某局部道路网络如图局部道路网络如图2 2所示，所示，p1p1p9p9是结点编号，括号中的数字是道是结点编号，
5、括号中的数字是道路阻强路阻强 第8页，本讲稿共46页1 1）结结点点p5p5是是一一公公共共汽汽车车站站点点，平平均均每每天天上上车车人人数数为为200200人人，下下车车人数为人数为300300人，具体表达为：人，具体表达为：结点号结点号上载需求量（人）上载需求量（人）下载需求量（人）下载需求量（人）P5P5200200300300第9页，本讲稿共46页 2)2)道道路路p1p7p1p7是是一一双双行行道道，且且正正向向阻阻强强为为4040km/skm/s，负负向向阻阻强强为为3535km/skm/s，具体表达为具体表达为链链 弧弧号号起起 结结点点终终 结结点点正正 方方 向向 阻阻 强强
6、（km/skm/s）反反 方方 向向 阻阻 强强（km/skm/s）p1p7p1p71 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），），在路径选择中资源增减的结点，如库房、车站等，其状在路径选择中资源增减的结点，如库房、车站等，其状
8、态属性有资源需求，如产品数量。态属性有资源需求，如产品数量。第11页，本讲稿共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
9、停靠点968720不准转弯662020076201590862020-909620101807620008620-1909620-1-909620-1-9076205086201090第13页，本讲稿共46页2.2 图或网络的存储 P170邻接矩阵无向图、有向图 有向网络1、0 1、&、0第14页，本讲稿共46页3空间网络分析的方法空间网络分析的方法3.13.1路径分析路径分析v v最短路径分析最短路径分析v v连通性分析连通性分析-最小生成树最小生成树3.23.2中心选址中心选址第15页，本讲稿共46页 3.1.1 3.1.1 最短路径求解最短路径求解v最短路径求解有多种不同的方法，其中最短
10、路径求解有多种不同的方法，其中DijkstraDijkstra算算法适合于求解某个起点（源点）到网络中的其它各个法适合于求解某个起点（源点）到网络中的其它各个结点的最佳路径。结点的最佳路径。第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中找中
12、找到一点，使得到一点，使得A A到这一点的最小距离到这一点的最小距离小于前一个距离。（因为小于前一个距离。（因为A A到到CiCi中的中的点要么不通，要么通过点要么不通，要么通过BiBi中的点与之中的点与之连通。连通。）因此，我们可以先不考虑因此，我们可以先不考虑CiCi中中的点。的点。第19页，本讲稿共46页例子例子(思路思路)于是，对于右图，我们第一步只考于是，对于右图，我们第一步只考虑下图虑下图:V5V0V4V21003010Bi=v2,v4,v520V5V0V4V1V3V210060301010505第20页，本讲稿共46页例子例子(思路思路)我们用我们用我们用我们用mindistmi
13、ndistmindistmindist这个数组来保存由这个数组来保存由这个数组来保存由这个数组来保存由v0v0v0v0到其它顶点的最小距离，这些距离按到其它顶点的最小距离，这些距离按到其它顶点的最小距离，这些距离按到其它顶点的最小距离，这些距离按升序排列。升序排列。升序排列。升序排列。考虑右图：考虑右图：考虑右图：考虑右图：第一步，通过比较，我们知道第一步，通过比较，我们知道第一步，通过比较，我们知道第一步，通过比较，我们知道 mindistancev0v2=mindist0=mindistancev0v2=mindist0=mindistancev0v2=mindist0=mindistan
14、cev0v2=mindist0=10,10,10,10,（v0-v2)v0-v2)v0-v2)v0-v2)这是我们求出的第一个最小距离这是我们求出的第一个最小距离这是我们求出的第一个最小距离这是我们求出的第一个最小距离一旦我们得到一旦我们得到v2v2，我们就可以知道：我们就可以知道：V5V0V4V21003010向量第21页，本讲稿共46页例子例子(思路思路)V0V0跟跟 v2v2直接连通到的点直接连通到的点v3v3 之间的最之间的最小距离不再是无穷大，它应当是小距离不再是无穷大，它应当是mindistancev0v2+disv2v3mindistancev0v2+disv2v3,这样我们应当
15、把这样我们应当把v3v3放入前面的集合放入前面的集合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
16、是是v0v0到其它顶点到其它顶点除除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页V0V0V1V1V2V2V3V3V4V4V5V5V0V0为起始点为起始点为起始点为起始点0 0(&)(&)(10)(10)(&)(&)(30)30)(100(100)V02=10V02=100 0(&)(&)1010(60)60)(30)30)(100(100)V04=30V04=300 0(&)(&)1010(50)(50)3030(90)90)V03=50V03=500 0(&)(&)101050503030(60)(60)
18、V05=60V05=600 0(&)(&)1010505030306060V01=V01=&0 0&101050503030606012第27页，本讲稿共46页例子例子起点起点终点终点最短路径最短路径路路径径长长度度v0v1无无v2(v0,v2)10v3(v0,v4,v3)50v4(v0,v4)30v5(v0,v4,v3,v5)60第28页，本讲稿共46页20V5V0V4V1V3V210060301010505带权有向图带权有向图作业作业1:1:求求V0到到V5的最短路径的最短路径第29页，本讲稿共46页V0V0V1V1V2V2V3V3V4V4V5V5V0V0为起始点为起始点为起始点为起始点0
19、 0(&)(&)(10)(10)(30)(30)(&)(&)(100)(100)V02=10V02=100 0(&)(&)1010(30)(30)(&)(&)(100)(100)V03=30V03=300 0(&)(&)10103030(&)(&)(40)(40)V05=40V05=400 0(&)(&)10103030(&)(&)4040V01=V01=&0 0&10103030(&)(&)4040V04=V04=&0 0&10103030&404012第30页，本讲稿共46页起点起点终点终点最短路径最短路径路路径径长长度度v0v1无无v2(v0,v2)10v3(v0,v3)30v4无无v5
20、(v0,v3,v5)40第31页，本讲稿共46页规律规律(步骤步骤)制作制作制作制作N*NN*N的矩阵的矩阵的矩阵的矩阵第第第第mm行就意味着有行就意味着有行就意味着有行就意味着有mm个值个值个值个值(距离距离距离距离)已经确定已经确定已经确定已经确定在确定一个点后在确定一个点后在确定一个点后在确定一个点后,与该点相邻接的点的距离重新计算与该点相邻接的点的距离重新计算与该点相邻接的点的距离重新计算与该点相邻接的点的距离重新计算,与该点与该点与该点与该点不相邻的则保持不变不相邻的则保持不变不相邻的则保持不变不相邻的则保持不变(直接照抄之前的直接照抄之前的直接照抄之前的直接照抄之前的)在重新计算点
21、的距离时在重新计算点的距离时在重新计算点的距离时在重新计算点的距离时,只要考虑与该点相邻的只要考虑与该点相邻的只要考虑与该点相邻的只要考虑与该点相邻的所有点所有点所有点所有点的最短距离的最短距离的最短距离的最短距离.第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
22、)(&)(&)(&)(&)(8)(8)(6)(6)3 3(8)(8)V16=6V16=60 0(9)(9)(&)(&)(&)(&)(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
23、第34页，本讲稿共46页3.1.2 连通性分析-最小生成树（1）概念连通图：在一个图中，任意两个节点之间都存在一条路。树：若一个连通图中不存在任何回路，则称为树。生成树的权数：生成树中各边的权数之和。最小生成树：图的极小连通子图。（2 2）应用：通信线路、快递）应用：通信线路、快递56第35页，本讲稿共46页（3 3）构造最小生成树的）构造最小生成树的依据依据：v v在网中选择在网中选择N-1N-1条边连接网的条边连接网的N N个顶点个顶点v v尽可能选取权值为最小的边尽可能选取权值为最小的边3.1.2 连通性分析-最小生成树第36页，本讲稿共46页(4)(4)算法（算法（KruskalKru
24、skal，克罗斯克尔算法，也叫克罗斯克尔算法，也叫“避圈避圈”法）法）1 1）先把图中的各边按权数从小到大重新排列，并取权数最小的一）先把图中的各边按权数从小到大重新排列，并取权数最小的一条边为最小生成树中的边。条边为最小生成树中的边。2 2）在剩下的边中，按顺序取下一条边。若该边与最小生）在剩下的边中，按顺序取下一条边。若该边与最小生成树中已有的边，构成回路，则舍去该边，否则选中生成树中已有的边，构成回路，则舍去该边，否则选中生成树。成树。3 3）重复）重复2 2），直到有），直到有M-1M-1条边被选进生成树中，这条边被选进生成树中，这M-1M-1条边就条边就构成最小生成树构成最小生成树3
25、.1.2 连通性分析连通性分析-最小生成树最小生成树第37页，本讲稿共46页3.1.2 3.1.2 连通性分析-最小生成树具体步骤具体步骤第38页，本讲稿共46页请请应应用用克克罗罗斯斯克克尔尔算算法法确确定定下下图图的的最最小小生生成成树树（含步骤）。（含步骤）。12345647710131718152228作业：作业：第39页，本讲稿共46页894612752715V6V1V2V3V4V5V7第40页，本讲稿共46页4.2 中心选址问题 中心点选址问题中，最佳选址位置的判定标准，是使其所在的顶点与图中其它顶点之间的最大距离达到最小，或者使其所在的顶点到图中其它顶点之间的距离之和达到最小。这
26、个选址问题实际上就是求网络图的中心点问题。这类选址问题适宜于医院、消防站等服务设施的布局问题。第41页，本讲稿共46页v6v8v1v7v5v4v2v389363253757中心选址问题的实例例如，某县要在其所辖的8个乡镇之一修建一个消防站，为8个乡镇服务，要要求求消消防防站站至至最最远远乡乡镇镇的的距距离离达达到到最最小小。假设该8个乡镇之间的交通网络被抽象为无向赋权连通图，权值为乡镇之间的距离。下面求解消防站应设在哪个乡镇，即哪个顶点？第42页，本讲稿共46页首先，用首先，用DijkstraDijkstra算法计算出算法计算出每一个顶点每一个顶点每一个顶点每一个顶点v vi i至其它各顶点至
27、其它各顶点v vj j的最短的最短路径长度路径长度d dijij(i i,j j=1,2,=1,2,6),6)，写出距离矩阵：写出距离矩阵：中心选址问题的实例6061916152565473第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,)
28、=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页