空间网络分析PPT讲稿.ppt

空间网络分析第1页，共46页，编辑于2022年，星期日网络模型第2页，共46页，编辑于2022年，星期日1网络分析的基本概念网络分析的基本概念 网络网络是一个由点、线的二元关系构成的系统，通常用来描述某是一个由点、线的二元关系构成的系统，通常用来描述某种资源或物质沿着路径在空间上的运动。种资源或物质沿着路径在空间上的运动。在在GISGIS中，中，网络分析网络分析则是依据网络拓扑关系（线性实体之间、线则是依据网络拓扑关系（线性实体之间、线性实体与结点之间、结点与结点之间的连接、连通关系），通过考性实体与结点之间、结点与结点之间的连接、连通关系），通过考察网络元素的空间及属性数据，以数学理论模型为基础，对网络的察网络元素的空间及属性数据，以数学理论模型为基础，对网络的性能特征进行多方面的一种分析计算。其中，性能特征进行多方面的一种分析计算。其中，网络图论与数学模型网络图论与数学模型是网络分析的重要理论基础。是网络分析的重要理论基础。目前，网络分析在电子导航、交通旅游、城市规划管理以及目前，网络分析在电子导航、交通旅游、城市规划管理以及电力、通讯等各种管网管线的布局设计中发挥了重要的作用。电力、通讯等各种管网管线的布局设计中发挥了重要的作用。第3页，共46页，编辑于2022年，星期日例子例子20V5V0V4V1V3V210060301010505有向网络有向网络邻接矩阵邻接矩阵第4页，共46页，编辑于2022年，星期日网络的数据结构网络的数据结构1）几何结构：表示地理分布位置，用点、线表示2）拓扑结构：表示连接性，用图表示第5页，共46页，编辑于2022年，星期日图的定义：图的定义：顶点顶点 无序无序边边无向图无向图顶点顶点 有序有序弧弧有向图 有权重有权重网络网络GISGIS要进行网络分析，首先需要解决网络的表达和存要进行网络分析，首先需要解决网络的表达和存要进行网络分析，首先需要解决网络的表达和存要进行网络分析，首先需要解决网络的表达和存储问题。储问题。储问题。储问题。图或网络的表达：边（弧、链）、点图或网络的表达：边（弧、链）、点图或网络的存储：邻接矩阵第6页，共46页，编辑于2022年，星期日1 1 1 1、链（、链（、链（、链（LinkLinkLinkLink）网络中流动的管网络中流动的管线如街道、河流、水线如街道、河流、水管，其状态属性包括管，其状态属性包括阻力和需求。阻力和需求。2.1 图或网络的表达：2 2 2 2、结点（、结点（、结点（、结点（NodeNodeNodeNode）网络中链的结点，如港口、车站等，其状态属性包括阻力和需网络中链的结点，如港口、车站等，其状态属性包括阻力和需求等。求等。第7页，共46页，编辑于2022年，星期日GISGIS要进行网络分析，首先需要解决网络的表达和存储问题。要进行网络分析，首先需要解决网络的表达和存储问题。某局部道路网络如图某局部道路网络如图2 2所示，所示，p1p1p9p9是结点编号，括号中的数是结点编号，括号中的数字是道路阻强字是道路阻强 第8页，共46页，编辑于2022年，星期日1 1）结结点点p5p5是是一一公公共共汽汽车车站站点点，平平均均每每天天上上车车人人数数为为200200人人，下车人数为下车人数为300300人，具体表达为：人，具体表达为：结点号结点号上载需求量（人）上载需求量（人）下载需求量（人）下载需求量（人）P5P5200200300300第9页，共46页，编辑于2022年，星期日 2)2)道道路路p1p7p1p7是是一一双双行行道道，且且正正向向阻阻强强为为4040km/skm/s，负负向向阻阻强强为为3535km/skm/s，具体表达为具体表达为链链 弧弧号号起起 结结点点终终 结结点点正正 方方 向向 阻阻 强强（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页，编辑于2022年，星期日结点中的特殊类型障碍（障碍（BarrierBarrier），），禁止网络上流动的点。禁止网络上流动的点。拐点（拐点（TurnTurn），），出现在网络中的分割点上，其状态有属性和阻力，出现在网络中的分割点上，其状态有属性和阻力，如拐弯的时间和限制（如在如拐弯的时间和限制（如在8 8点到点到1818点不允许左拐）。点不允许左拐）。中心（中心（CenterCenter），），是接受或分配资源的位置，如水库、商业中心，电是接受或分配资源的位置，如水库、商业中心，电站等，其状态包括资源容量（如总量），阻力限额（中心到链的最站等，其状态包括资源容量（如总量），阻力限额（中心到链的最大距离或时间）。大距离或时间）。站点（站点（StopStop），），在路径选择中资源增减的结点，如库房、车站等，在路径选择中资源增减的结点，如库房、车站等，其状态属性有资源需求，如产品数量。其状态属性有资源需求，如产品数量。第11页，共46页，编辑于2022年，星期日拐点拐点第12页，共46页，编辑于2022年，星期日转弯类型描述属性表0=无阻强-1=不允许拐弯U型拐弯指从6号弧至20号结点并从20号结点转回6号弧，这是一个180度转弯，花费20秒时间停靠点使得从6号弧至其他弧段直到7号弧，向左转至8号弧，向右转至9号弧的运移减慢不允许从6号弧转至9号弧，并赋予负值阻强；允许其他方向的转变，其阻强为正高架道或地道允许直通而无延迟，如从6号弧至7号弧；但不允许转弯，此时以负的阻强表示，如从6号弧至8、9号弧968720U型转弯角度至弧段从弧段结点号时间阻强/s968720高架道或地道968720停靠点968720不准转弯662020076201590862020-909620101807620008620-1909620-1-909620-1-9076205086201090第13页，共46页，编辑于2022年，星期日2.2 图或网络的存储 P170邻接矩阵无向图、有向图 有向网络1、0 1、&、0第14页，共46页，编辑于2022年，星期日3空间网络分析的方法空间网络分析的方法3.13.1路径分析路径分析v v最短路径分析最短路径分析v连通性分析-最小生成树3.23.2中心选址中心选址第15页，共46页，编辑于2022年，星期日 3.1.1 3.1.1 最短路径求解最短路径求解v最短路径求解有多种不同的方法，其中最短路径求解有多种不同的方法，其中Dijkstra算法算法适合于求解某个起点（源点）到网络中的其它各个结适合于求解某个起点（源点）到网络中的其它各个结点的最佳路径。点的最佳路径。第16页，共46页，编辑于2022年，星期日例子20V5V0V4V1V3V210060301010505有向网络有向网络第17页，共46页，编辑于2022年，星期日例子例子(思路思路)ACiBi 如图所示，如图所示，A A为所求最短距离的起点，其他为所求最短距离的起点，其他Bi,Bi,Ci Ci 为终点。为终点。目的目的:求求一系列最短距离一系列最短距离。我们先假定这些最短距。我们先假定这些最短距离互不相等。那么我们可以把这些最短距离按升序离互不相等。那么我们可以把这些最短距离按升序（从小到大）排列（从小到大）排列步骤步骤:我们把所有顶点分为两类我们把所有顶点分为两类C C和和B.B.令令A A到到BiBi这些这些顶点的最短距离顶点的最短距离不为无穷大不为无穷大,A A到到CiCi这些顶点的最这些顶点的最短距离为短距离为无穷大无穷大 这就说明这就说明A A到到CiCi中的点要么不通，要么通过中的点要么不通，要么通过BiBi中中的点与之连接。的点与之连接。第18页，共46页，编辑于2022年，星期日例子(思路)ACiBi 这样，对于这样，对于A A到到CiCi中任何一个点的中任何一个点的最小距离，我们总可以在最小距离，我们总可以在BiBi中找到一中找到一点，使得点，使得A A到这一点的最小距离小于前到这一点的最小距离小于前一个距离。（因为一个距离。（因为A A到到CiCi中的点要么中的点要么不通，要么通过不通，要么通过BiBi中的点与之连通。中的点与之连通。）因此，我们可以先不考虑因此，我们可以先不考虑CiCi中的中的点。点。第19页，共46页，编辑于2022年，星期日例子(思路)于是，对于右图，我们第一步只考虑于是，对于右图，我们第一步只考虑下图下图:V5V0V4V21003010Bi=v2,v4,v520V5V0V4V1V3V210060301010505第20页，共46页，编辑于2022年，星期日例子例子(思路思路)我们用我们用我们用我们用mindistmindistmindistmindist这个数组来保存由这个数组来保存由这个数组来保存由这个数组来保存由v0v0v0v0到其它顶点的最小距离，这些距离到其它顶点的最小距离，这些距离到其它顶点的最小距离，这些距离到其它顶点的最小距离，这些距离按升序排列。按升序排列。按升序排列。按升序排列。考虑右图：考虑右图：考虑右图：考虑右图：第一步，通过比较，我们知道第一步，通过比较，我们知道第一步，通过比较，我们知道第一步，通过比较，我们知道 mindistancev0v2=mindist0=10mindistancev0v2=mindist0=10mindistancev0v2=mindist0=10mindistancev0v2=mindist0=10,（v0-v2)v0-v2)v0-v2)v0-v2)这是我们求出的第一个最小距离这是我们求出的第一个最小距离这是我们求出的第一个最小距离这是我们求出的第一个最小距离一旦我们得到一旦我们得到v2v2，我们就可以知道：我们就可以知道：V5V0V4V21003010向量第21页，共46页，编辑于2022年，星期日例子(思路)V0V0跟跟 v2v2直接连通到的点直接连通到的点v3v3 之间的之间的最小距离不再是无穷大，它应当是最小距离不再是无穷大，它应当是mindistancev0v2+disv2v3,mindistancev0v2+disv2v3,这样我们应当把这样我们应当把v3v3放入前面的集合放入前面的集合BiBi中。中。（注意：有多少（注意：有多少v2v2直接连通到的点直接连通到的点都应当考虑进来。）都应当考虑进来。）V5V0V4V3V2100301050Bi=v2,v4,v5,v3第22页，共46页，编辑于2022年，星期日例子(思路)第二步，我们把与第二步，我们把与v2v2直接连通的点直接连通的点v3v3考虑进考虑进来。来。dis05=100;dis04=30;dis05=100;dis04=30;dis02=10;dis03=60;dis02=10;dis03=60;除除1010以外，以外，3030是最小的。是最小的。我们可以证明我们可以证明3030是是v0v0到其它顶到其它顶点除点除1010以外最小的。以外最小的。V5V0V4V3V2100301050向量第23页，共46页，编辑于2022年，星期日例子(思路)这样我们得到我们的第二个最小距离：这样我们得到我们的第二个最小距离：Mindistancev0v4=mindist1=30 Mindistancev0v4=mindist1=30,(v0-v4),(v0-v4)接下来，我们把接下来，我们把v4v4与之直接连通的点与之直接连通的点考虑进来。考虑进来。V5V0V4V3V2100301050Bi第24页，共46页，编辑于2022年，星期日例子例子以v0为起点，计算它到其它各顶点的最短路径，计算过程中最短路径长度向量D的变化见D0-D4，计算出的各条最短路径。第25页，共46页，编辑于2022年，星期日例子例子20V5V0V4V1V3V210060301010505有向网络有向网络第26页，共46页，编辑于2022年，星期日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页，编辑于2022年，星期日例子起点起点终点终点最短路径最短路径路路径径长长度度v0v1无无v2(v0,v2)10v3(v0,v4,v3)50v4(v0,v4)30v5(v0,v4,v3,v5)60第28页，共46页，编辑于2022年，星期日20V5V0V4V1V3V210060301010505带权有向图带权有向图作业作业1:1:求求V0到到V5的最短路径的最短路径第29页，共46页，编辑于2022年，星期日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页，编辑于2022年，星期日起点起点终点终点最短路径最短路径路路径径长长度度v0v1无无v2(v0,v2)10v3(v0,v3)30v4无无v5(v0,v3,v5)40第31页，共46页，编辑于2022年，星期日规律规律(步骤步骤)制作制作制作制作N*NN*N的矩阵的矩阵的矩阵的矩阵第第第第mm行就意味着有行就意味着有行就意味着有行就意味着有mm个值个值个值个值(距离距离距离距离)已经确定已经确定已经确定已经确定在确定一个点后在确定一个点后在确定一个点后在确定一个点后,与该点相邻接的点的距离重新计算与该点相邻接的点的距离重新计算与该点相邻接的点的距离重新计算与该点相邻接的点的距离重新计算,与该点与该点与该点与该点不相邻的则保持不变不相邻的则保持不变不相邻的则保持不变不相邻的则保持不变(直接照抄之前的直接照抄之前的直接照抄之前的直接照抄之前的)在重新计算点的距离时在重新计算点的距离时在重新计算点的距离时在重新计算点的距离时,只要考虑与该点相邻的只要考虑与该点相邻的只要考虑与该点相邻的只要考虑与该点相邻的所有点的最所有点的最所有点的最所有点的最短距离短距离短距离短距离.第32页，共46页，编辑于2022年，星期日v6v8v1v7v5v4v2v389363253757作业2:求V1到其他各点的最短路径到其他各点的最短路径第33页，共46页，编辑于2022年，星期日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)(&)(&)(&)(&)(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页，编辑于2022年，星期日3.1.2 连通性分析-最小生成树（1）概念连通图：在一个图中，任意两个节点之间都存在一条路。树：若一个连通图中不存在任何回路，则称为树。生成树的权数：生成树中各边的权数之和。最小生成树：图的极小连通子图。（2 2）应用：通信线路、快递）应用：通信线路、快递56第35页，共46页，编辑于2022年，星期日（3 3）构造最小生成树的）构造最小生成树的依据依据：v v在网中选择在网中选择N-1N-1条边连接网的条边连接网的N个顶点v v尽可能选取权值为最小的边尽可能选取权值为最小的边3.1.2 连通性分析-最小生成树第36页，共46页，编辑于2022年，星期日(4)(4)算法（算法（KruskalKruskal，克罗斯克尔算法，也叫克罗斯克尔算法，也叫“避圈避圈”法）法）1 1）先把图中的各边按权数从小到大重新排列，并取权数最）先把图中的各边按权数从小到大重新排列，并取权数最小的一条边为最小生成树中的边。小的一条边为最小生成树中的边。2 2）在剩下的边中，按顺序取下一条边。若该边与最小生成树）在剩下的边中，按顺序取下一条边。若该边与最小生成树中已有的边，构成回路，则舍去该边，否则选中生成树。中已有的边，构成回路，则舍去该边，否则选中生成树。3 3）重复）重复2 2），直到有），直到有M-1M-1条边被选进生成树中，这条边被选进生成树中，这M-1M-1条边就构条边就构成最小生成树成最小生成树3.1.2 连通性分析-最小生成树第37页，共46页，编辑于2022年，星期日3.1.2 连通性分析-最小生成树具体步骤具体步骤第38页，共46页，编辑于2022年，星期日请请应应用用克克罗罗斯斯克克尔尔算算法法确确定定下下图图的的最最小小生生成成树树（含含步骤）。步骤）。12345647710131718152228作业：作业：第39页，共46页，编辑于2022年，星期日894612752715V6V1V2V3V4V5V7第40页，共46页，编辑于2022年，星期日4.2 中心选址问题 中心点选址问题中，最佳选址位置的判定标准，是使其所在的顶点与图中其它顶点之间的最大距离达到最小，或者使其所在的顶点到图中其它顶点之间的距离之和达到最小。这个选址问题实际上就是求网络图的中心点问题。这类选址问题适宜于医院、消防站等服务设施的布局问题。第41页，共46页，编辑于2022年，星期日v6v8v1v7v5v4v2v389363253757中心选址问题的实例例如，某县要在其所辖的8个乡镇之一修建一个消防站，为8个乡镇服务，要要求求消消防防站站至至最最远远乡乡镇镇的的距距离离达达到到最最小小。假设该8个乡镇之间的交通网络被抽象为无向赋权连通图，权值为乡镇之间的距离。下面求解消防站应设在哪个乡镇，即哪个顶点？第42页，共46页，编辑于2022年，星期日首先，用首先，用DijkstraDijkstra算法计算出算法计算出每一个顶点每一个顶点每一个顶点每一个顶点v vi i至其它各顶点至其它各顶点v vj j的最短的最短路径长度路径长度d dijij(i i,j j=1,2,=1,2,6),6)，写出距离矩阵：写出距离矩阵：中心选址问题的实例6061916152565473第43页，共46页，编辑于2022年，星期日其其次次，求求距距离离矩矩阵阵中中每每行行的的最最大大值值，即即各各个个顶顶点点的的最最大大服服务务距距离，得离，得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页，编辑于2022年，星期日6061916152565473要求消防站至要求消防站至所有所有乡镇的距离达到最小乡镇的距离达到最小：中心选址问题的实例消防站应建在消防站应建在消防站应建在消防站应建在v v v v5 5 5 5点所在的乡镇点所在的乡镇点所在的乡镇点所在的乡镇第45页，共46页，编辑于2022年，星期日第46页，共46页，编辑于2022年，星期日