空间网络分析.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,4,空间网络分析,1 空间网络的基本概念,2 空间网络的类型和构成,2.1 类型,2.2 构成,3 空间网络分析的方法,3.1 路径分析,3.2 中心选址分析,网络,模型,1网络分析的基本概念,网络,是一个由点、线的二元关系构成的系统，通常用来描述某种资源或物质沿着路径在空间上的运动。,在,GIS,中，,网络分析,则是依据网络拓扑关系（线性实体之间、线性实体与结点之间、结点与结点之间的连接、连通关系），通过考察网络元素的空间及属性数据，以数学理论模型为基础，对网络的性能特征进行多方面的一种分析计算。其中，,网络图论与数学模型,是网络分析的重要理论基础。,目前，网络分析在电子导航、交通旅游、城市规划管理以及电力、通讯等各种管网管线的布局设计中发挥了重要的作用。,例子,20,V,5,V,0,V,4,V,1,V,3,V,2,100,60,30,10,10,50,5,有向网络,邻接矩阵,网络的数据结构,1,）几何结构：,表示地理分布位置，用点、线表示,2,）拓扑结构：,表示连接性，用图表示,图的定义：,顶点 无序,边,无向图,顶点 有序,弧,有向图,有权重,网络,GIS,要进行网络分析，首先需要解决网络的表达和存储问题。,图或网络的表达：边（弧、链）、点,图或网络的存储：邻接矩阵,1、链（,Link）,网络中流动的管线如街道、河流、水管，其状态属性包括阻力和需求。,2.,1,图或网络的表达：,2、结点（,Node）,网络中链的结点，如港口、车站等，其状态属性包括阻力和需求等。,GIS,要进行网络分析，首先需要解决网络的表达和存储问题。某局部道路网络如图,2,所示，,p1,p9,是结点编号，括号中的数字是道路阻强,1）结点,p5,是一公共汽车站点，平均每天上车人数为,200,人，下车人数为,300,人，具体表达为：,结点号,上载需求量（人）,下载需求量（人）,P5,200,300,2)道路,p1p7,是一双行道，且正向阻强为,40,km/s,，,负向阻强为,35,km/s,，,具体表达为,链弧号,起结点,终结点,正方向阻强（,km/s）,反方向阻强（,km/s）,p1p7,1,7,40,35,3）道路,p6p8,是一单行道，且阻强为20,km/s，,具体表达为：,链弧号,起结点,终结点,正方向阻强（,km/s）,反方向阻强（,km/s）,P6p8,6,8,20,-1(表不通),结点中的特殊类型,障碍（,Barrier），,禁止网络上流动的点。,拐点（,Turn），,出现在网络中的分割点上，其状态有属性和阻力，如拐弯的时间和限制（如在8点到18点不允许左拐）。,中心（,Center），,是接受或分配资源的位置，如水库、商业中心，电站等，其状态包括资源容量（如总量），阻力限额（中心到链的最大距离或时间）。,站点（,Stop），,在路径选择中资源增减的结点，如库房、车站等，其状态属性有资源需求，如产品数量。,拐点,转弯类型,描,述,属性表,0=,无阻强,-1=,不允许拐弯,U,型拐弯指从,6,号弧至,20,号结点并从,20,号结点转,回,6,号弧，这是一个,180,度转弯，花费,20,秒时间,停靠点使得从,6,号弧至其,他弧段,直到,7,号弧，,向左转至,8,号弧，向右转,至,9,号弧的运移减慢,不允许从,6,号弧转至,9,号,弧，并赋予负值阻强；允,许其他方向的转变，其阻,强为正,高架道或地道允许直通,而无延迟，如从,6,号弧,至,7,号弧；但不允许转,弯，此时以负的阻强表,示，如从,6,号弧至,8,、,9,号弧,9,6,8,7,20,U,型转弯,角度,至弧段,从弧段,结点号,时间阻强,/,s,9,6,8,7,20,高架道或地道,9,6,8,7,20,停靠点,9,6,8,7,20,不准转弯,6,6,20,20,0,7,6,20,15,90,8,6,20,20,-90,9,6,20,10,180,7,6,20,0,0,8,6,20,-1,90,9,6,20,-1,-90,9,6,20,-1,-90,7,6,20,5,0,8,6,20,10,90,2.2,图或网络的存储,P170,邻接矩阵,无向图、有向图 有向网络,1,、,0 1,、,&,、,0,3空间网络分析的方法,3.1 路径分析,最短路径分析,连通性分析-最小生成树,3.2 中心选址,3.1.1 最短路径求解,最短路径求解有多种不同的方法，其中,Dijkstra,算法适合于求解某个起点（源点）到网络中的其它各个结点的最佳路径。,例子,20,V,5,V,0,V,4,V,1,V,3,V,2,100,60,30,10,10,50,5,有向网络,例子(思路,),A,C,i,B,i,如图所示，,A,为所求最短距离的起点，其他,Bi,Ci,为终点。,目的,:求,一系列最短距离,。我们先假定这些最短距离互不相等。那么我们可以把这些最短距离按升序（从小到大）排列,步骤:,我们把所有顶点分为两类,C,和,B.,令,A,到,Bi,这些顶点的最短距离,不为无穷大,A,到,Ci,这些顶点的最短距离为,无穷大,这就说明,A,到,Ci,中的点要么不通，要么通过,Bi,中的点与之连接。,例子(思路,),A,C,i,B,i,这样，对于,A,到,Ci,中任何一个点的最小距离，我们总可以在,Bi,中找到一点，使得,A,到这一点的最小距离小于前一个距离。（因为,A,到,Ci,中的点要么不通，要么通过,Bi,中的点与之连通。）,因此，我们可以先不考虑,Ci,中的点。,例子(思路,),于是，对于右图，我们第一步只考虑下图:,V,5,V,0,V,4,V,2,100,30,10,Bi=v2,v4,v5,20,V,5,V,0,V,4,V,1,V,3,V,2,100,60,30,10,10,50,5,例子(思路,),我们用,mindist,这个数组来保存由,v0,到其它顶点的最小距离，这些距离按升序排列。,考虑右图：,第一步，通过比较，我们知道,mindistancev0v2=mindist0=10,（v0-v2),这是我们求出的第一个最小距离,一旦我们得到,v2，,我们就可以知道：,V,5,V,0,V,4,V,2,100,30,10,向量,例子(思路,),V0,跟,v2,直接连通到的点,v3,之间的最小距离不再是无穷大，它应当是,mindistancev0v2+disv2v3,这样我们应当把,v3,放入前面的集合,Bi,中。,（注意：有多少,v2,直接连通到的点,都应当考虑进来。,）,V,5,V,0,V,4,V,3,V,2,100,30,10,50,Bi=v2,v4,v5,v3,例子(思路,),第二步，我们把与,v2,直接连通的点,v3,考虑进来。,dis05=100;dis04=30;,dis02=10;dis03=60;,除10以外，30是最小的。,我们可以证明30是,v0,到其它顶点除10以外最小的。,V,5,V,0,V,4,V,3,V,2,100,30,10,50,向量,例子(思路,),这样我们得到我们的第二个最小距离：,Mindistancev0v4=mindist1=30,(v0-v4),接下来，我们把,v4,与之直接连通的点,考虑进来。,V,5,V,0,V,4,V,3,V,2,100,30,10,50,B,i,例子,以,v,0,为起点，计算它到其它各顶点的最短路径，计算过程中最短路径长度向量,D,的变化见,D,0,-,D,4,，,计算出的各条最短路径。,例子,20,V,5,V,0,V,4,V,1,V,3,V,2,100,60,30,10,10,50,5,有向网络,V0,V1,V2,V3,V4,V5,V0,为起始点,0,(&),(10),(&),(,30),(100),V02=10,0,(&),10,(,60),(,30),(100),V04=30,0,(&),10,(50),30,(,90),V03=50,0,(&),10,50,30,(60),V05=60,0,(&),10,50,30,60,V01=,&,0,&,10,50,30,60,1,2,例子,起点,终点,最短路径,路径长度,v,0,v,1,无,v,2,(,v,0,v,2,),10,v,3,(,v,0,v,4,v,3,),50,v,4,(,v,0,v,4,),30,v,5,(,v,0,v,4,v,3,v,5,),60,20,V,5,V,0,V,4,V,1,V,3,V,2,100,60,30,10,10,50,5,带权有向图,作业1:求,V,0,到,V,5,的最短路径,V0,V1,V2,V3,V4,V5,V0,为起始点,0,(&),(10),(30),(&),(100),V02=10,0,(&),10,(30),(&),(100),V03=30,0,(&),10,30,(&),(40),V05=40,0,(&),10,30,(&),40,V01=,&,0,&,10,30,(&),40,V04=,&,0,&,10,30,&,40,1,2,起点,终点,最短路径,路径长度,v,0,v,1,无,v,2,(,v,0,v,2,),10,v,3,(,v,0,v,3,),30,v,4,无,v,5,(,v,0,v,3,v,5,),40,规律(步骤),制作,N*N,的矩阵,第,m,行就意味着有,m,个值(距离)已经确定,在确定一个点后,与该点相邻接的点的距离重新计算,与该点不相邻的则保持不变(直接照抄之前的),在重新计算点的距离时,只要考虑与该点相邻的,所有点的最短距离,.,v6,v8,v1,v7,v5,v4,v2,v3,8,9,3,6,3,2,5,3,7,5,7,作业2:求,V1,到其他各点的最短路径,V1,V2,V3,V4,V5,V6,V7,V8,V1,为起始点,0,(9),(&),(&),(&),(6),(3),(8),V17=3,0,(9),(&),(&),(8),(6),3,(8),V16=6,0,(9),(&),(&),(8),6,3,(8),V15=8,0,(9),(&),(15),8,6,3,(8),V18=8,0,(9),(&),(15),8,6,3,8,V12=9,0,9,(14),(12),8,6,3,8,V14=12,0,9,(14),12,8,6,3,8,V13=14,0,9,14,12,8,6,3,8,3.1.2,连通性分析-最小生成树,（1）概念,连通图,：在一个图中，任意两个节点之间都存在一条路。,树,：若一个连通图中不存在任何回路，则称为树。,生成树的权数,：生成树中各边的权数之和。,最小生成树,：图的极小连通子图。,（2）应用：通信线路、快递,56,（3）构造最小生成树的,依据,：,在网中选择,N-1,条边连接网的,N,个顶点,尽可能选取权值为最小的边,3.1.2,连通性分析-最小生成树,(4)算法（,Kruskal,，,克罗斯克尔算法，也叫,“,避圈,”,法）,1）先把图中的各边按权数从小到大重新排列，并取权数最小的一条边为最小生成树中的边。,2）在剩下的边中，按顺序取下一条边。若该边与最小生成树中已有的边，构成回路，则舍去该边，否则选中生成树。,3）重复2），直到有,M-1,条边被选进生成树中，这,M-1,条边就构成最小生成树,3.1.2,连通性分析-最小生成树,3.1.2,连通性分析-最小生成树,具体步骤,请应用克罗斯克尔算法确定下图的最小生成树（含步骤）。,1,2,3,4,5,6,4,7,7,10,13,17,18,15,22,28,作业：,8,9,4,6,12,7,5,2,7,15,V6,V1,V2,V3,V4,V5,V7,4.2,中心选址问题,中心点选址问题中，最佳选址位置的判定标准，是使其所在的顶点与图中其它顶点之间的,最大距离,达到最小，或者使其所在的顶点到图中其它顶点之间的,距离之和,达到最小。,这个选址问题实际上就是求网络图的中心点问题。这类选址问题适宜于医院、消防站等服务设施的布局问题。,v6,v8,v1,v7,v5,v4,v2,v3,8,9,3,6,3,2,5,3,7,5,7,中心选址问题的实例,例如，某县要在其所辖的8个乡镇之一修建一个消防站，为8个乡镇服务，,要求消防站至最远乡镇的距离达到最小,。假设该8个乡镇之间的交通网络被抽象为无向赋权连通图，权值为乡镇之间的距离。下面求解消防站应设在哪个乡镇，即哪个顶点？,首先，用,Dijkstra,算法计算出,每一个顶点,v,i,至其它各顶点,v,j,的最短路径长度,d,ij,(,i,j,=1,2,6)，,写出距离矩阵：,中心选址问题的实例,60,61,91,61,52,56,54,73,其次，求距离矩阵中每行的最大值，即各个顶点的最大服务距离，得,e,(,v,1,)=14,e,(,v,2,)=15,e,(,v,3,)=20,e,(,v,4,)=12,e,(,v,5,)=15,e,(,v,6,)=17,e,(,v,7,)=12,e,(,v,8,)=20,最后计算最大服务距离的最小值。显然，,e,(,v,4,)=,e,(,v,7,)=,min,e,(,v,i,)。,所以，,消防站应建在,v,4,或,v,7,点所在的乡镇,。,中心选址问题的实例,60,61,91,61,52,56,54,73,要求消防站至,所有,乡镇的距离达到最小,：,中心选址问题的实例,消防站应建在,v,5,点所在的乡镇,