空间网络分析课件_第1页
空间网络分析课件_第2页
空间网络分析课件_第3页
空间网络分析课件_第4页
空间网络分析课件_第5页
已阅读5页,还剩36页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、空间分析概述网络分析基础网络结构分析最优路径分析资源分配本章小结1空间网络分析Internet:把路由器看作节点,把光缆看作连接边1.概述HTTP:把客户机/服务器看作节点,把请求/应答看作边,色彩表示请求量1.概述WWW: 把文档看作节点,把超链接看作边,色彩代表不同公司的商务网1.概述Routes of Airlines: 把机场看作节点,把航线看作边1.概述集成电路中元器件是节点,连线是边1.概述空间网络分析通过研究网络的状态以及模拟和分析资源在网络上的流动和分配情况,对网络结构及其资源等的优化问题进行研究的一种空间分析方法71.概述主要用来解决两大类问题研究地理网络的结构,如:优化路径

2、的求解、连通分量求解等问题研究资源在网络系统中的分配与流动如:资源分配范围或服务范围确定、最大流与最小费用等问题空间网络分析实例从A到B点的最快路线是什么?哪些房屋距离消防站的车程小于5分钟?哪辆救护车能够最快对一起事故做出响应?一支配送或服务车队如何在提高客户服务质量的同时降低运输成本?如果某家公司必须缩减规模,那么它应该关闭哪家商店才能继续满足最为全面的需求?81.概述概述网络分析基础网络结构分析最优路径分析资源分配本章小结9空间网络分析网络的基本要素链:网络中两个结点之间的弧段结点:链的两个端点站点:网络路径上资源增加、减少的地方,是分布于网络链上的结点,如公交站点中心点:网络中具有一定

3、容量,能够从链上获取资源或发送资源的结点,如水库、商业中心、学校等障碍:网络中阻断资源流动的结点或链,如禁止通行的道路、交通红灯等拐角:指网络中资源流动可能发生转向的结点,如禁止左拐的路口102.网络分析基础网络基本要素的属性项阻碍强度用于量测资源在网络中流动的费用或阻碍,可以作为网络链、站点和中心点的属性,通常用时间、成本来衡量资源需求量网络中可被“运输”的资源数量,如沿街道居住的学生人数、某一站点要被运送的货物等资源容量指一个中心可以容纳或可以提供的资源总量,如学校的总人数、停车场的停车位等112.网络分析基础网络的存储模型邻接矩阵法用于表示图中任意两点间的邻接关系及其权值的矩阵两点间有一

4、条弧,则邻接矩阵中对应的元素为1,否则为0122.网络分析基础123450 1 1 0 00 0 0 1 00 1 0 0 00 0 1 0 10 0 1 1 0网络的存储模型关联矩阵法描述图形中结点与各条边之间的邻接关系,每行对应图的一个节点,每列对应图的一条弧关联矩阵中1对应结点弧的起点,-1对应弧的终点;若结点与一条弧不关联,则关联矩阵中对应的元素为0132.网络分析基础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网络的存储模型邻接表法用所有结点邻接表的

5、集合表示142.网络分析基础1234512345242338640600390530470结点号结点信息概述网络分析基础网络结构分析最优路径分析资源分配本章小结15空间网络分析度与中心度度:指一个结点所连接边的数目,是衡量和刻画网络结点特性最简单又最重要的概念中心度:衡量结点在网络中所处中心地位程度的一个指标点度中心度通过计算结点的度来度量结点在图中的核心地位程度仅考虑了与该结点直接相连的点数,而忽视了间接相连的点数163.网络结构分析BAC度与中心度中心度:衡量结点在网络中所处中心地位程度的一个指标接近中心性从距离角度来衡量一个结点的中心地位,认为结点到网络中其它所有点的总距离最小,此时其接

6、近中心性的值越大,则可认为该点是整个网络的中心点 其中,N是结点个数,dij表示结点i到j的距离173.网络结构分析BAC度与中心度中心度:衡量结点在网络中所处中心地位程度的一个指标介数中心性从信息、物质或能量传输角度看,认为经过最短路径条数最多的边和结点是网络上承载流量最大的边和结点例如:如果不经过结点v2,结点v3、v4就无法到达v1,这样v2在整个网络中起了很重要的桥梁作用,其中心程度要大于其它结点183.网络结构分析路径与回路路径:从一结点到另一结点的一组结点序列路径长度:路径上所经过边的数目回路:起点和终点相同的路径哈密尔顿回路: 有且仅有一次通过图中所有结点的回路 如:1, 2,

7、4, 5, 6, 3, 1欧拉回路:有且仅有一次通过图中所有边的回路, 如:1, 2, 4, 5, 2, 3, 5, 6, 3, 1193.网络结构分析连通性与生成树连通性:在无向图中,若从结点u到结点v有路径存在,则称u到v是连通的强连通图:图中任意两个结点之间都连通图的生成树:一个连通图的极小连通子图 满足:生成树的边数为n-1(顶点数为N)树无回路,但不相邻顶点连成一边,就会得到一个回路树是连通的,如去掉任意一条边,不会变成不连通的203.网络结构分析连通性与生成树最小生成树:一个连通图众多生成树中边权值之和最小的生成树(minimal spanning tree, MST)特点:N-1

8、条边连接N个结点所有边权值和最小例如:在n个城市间建立通信线路, 使得通信网的造价最低213.网络结构分析最小生成树算法Kruskal算法先把图中的各边按权数从小到大重新排列,并取权数最小的一条边为最小生成树中的边在剩下的边中,按顺序取下一条边。若该边与最小生成树中已有的边,构成回路,则舍去该边,否则选入生成树重复步骤2,直到有M-1条边被选进生成树中,这M-1条边就构成最小生成树223.网络结构分析直径、半径和中心结点半径:从某结点到其它所有结点的最长路径长度结点v1、v2、v3、v4的半径分别为:2、1、2、2图的直径:图中任意两个结点间的最长路径图G的直径是2图的中心:具有最小半径的结点

9、称为图的中心中心点是结点v2233.网络结构分析v1v2v3v4概述网络分析基础网络结构分析最优路径分析资源分配本章小结24空间网络分析最优路径的含义路径分析是网络分析中一个最基本的问题,也是实际应用中最常见的一个问题最优路径有多种含义,不仅仅指一般意义上的距离最短,还可指时间最短、费用最少、成本最低等含义例 1:居民出行利用车辆导航获取距离最近、费用最优的路径例 2:电力、水力管线的架设管线考虑的是成本最优的路径最短路径分类两个结点之间的最短路径一个结点到图中其它所有结点之间的最短路径所有结点对之间的最短路径254.最优路径分析单源最短路径算法Dijkstra基本思想: 采用贪心策略,以源点

10、为中心向外层扩展,直到扩展到目标点为止,即从源点依次产生出路径长度递增的最短路径基本步骤:将图的结点集合V被分为两组(S和T),其中S存放已经计算出最短路径的结点(初始时只包含源点),T=V-S从集合T中选择距离最小的结点u,并将此顶点从集合T移入S中以u为新的中间点,修改T中结点的最短距离,以保证从源点s到T中并经过结点u的最短路径长度不大于原来不经过顶点u的距离重复2-3,直到所有顶点都被加入到S中264.最优路径分析单源最短路径算法Dijkstra示例274.最优路径分析04321101005060103020043211010050601030200432110100506010302

11、0单源最短路径算法Dijkstra示例284.最优路径分析043211010050601030200432110100506010302004321101005060103020旅行商问题(travelling salesman problem,TSP) 一个商品推销员要去若干个城市推销商品,该推销员从一个城市出发,需要经过每一个城市并且只经过一次,最后回到出发地,该如何选择行进的线路使得总旅程距离最短?TSP算法分类精确算法(时间代价巨大)分支界定法、线性规划法、动态规划法等启发式算法 插入法、 随机贪婪法、模拟退火法、遗传法、神经网络法、蚁群算法294.最优路径分析TSP算法最近邻插入法基

12、本思想:寻找与回路最近邻的结点并加入其中,构造一个结点数逐渐递增的回路,最后得到一个哈密顿回路即为近似解基本步骤(设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.最优路径分析TSP算法最近邻插入法示例314.最优路径分析概述网络分析基础网络结构分析最优路径分析资源分配本章小结32空间网

13、络分析资源分配通常包括定位和分配两个问题资源定位是指已知需求的分布,确定供应点的最佳位置资源分配则是已知供应点,确定其为哪些需求点提供服务的问题资源定位问题定位问题也常称为选址问题,涉及两个基本概念:中心点:到所有点的距离中最大距离达到最小的位置中位点:点到其它点的距离总和达到最小的位置335.资源分配选址问题示例:在该邮区范围内的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=分配问题资源分配是一种按照特定原则(如距离、时间等)为供应中心分配需求点的一种分析方法,反映了现实世界中网络资源的一种供需关系常包含两种含义确定中心服务范围在一定限制条件下(如时间、费用或者距离等),服务中心所能提供服务的最大空间领域确定中心资源分配范围不仅要考虑到服务范围内的总费用不超过中心的最大阻值,而且服务范围内的总需求量也不能超过中心的供应量365.资源分配确定中心服务范围基本思想 依次求出服务费用不超过中心阻值的路径,组成这些路径的网络节点和边的集合构成了该中心的服务范围主要步骤根据拓扑关系,计算地理网络的最大邻接节点数构造邻接节点矩阵和初始判断矩阵描述地理网络结构应用广度优先搜索算法确定地理网络中心的服务范围375.资源分配确定中心资源分配范围基本思想:依次求出到服务中心费用不超过中心最大阻值,同时网络的总需求量不超过中心的货源量的路径,组成这些路径的网络结点和边的集合就构成了该中心资源分配的范围处理时同时考虑到网络和网络结点

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论