空间网络分析课件.ppt

1、空间分析空间分析n概述概述n网络分析基础网络分析基础n网络结构分析网络结构分析n最优路径分析最优路径分析n资源分配资源分配n本章小结本章小结1空间网络分析空间网络分析Internet:把路由器看作节点，把光缆看作连接边1.1.概述概述HTTP:把客户机/服务器看作节点，把请求/应答看作边，色彩表示请求量1.1.概述概述WWW:把文档看作节点，把超链接看作边，色彩代表不同公司的商务网把文档看作节点，把超链接看作边，色彩代表不同公司的商务网1.1.概述概述Routes of Airlines:把机场看作节点，把航线看作边把机场看作节点，把航线看作边1.1.概述概述集成电路中元器件是节点，连线是边集

2、成电路中元器件是节点，连线是边1.1.概述概述空间网络分析空间网络分析n通过研究网络的状态以及模拟和分析资源在网络上的流动和分配情况，对网络结构及其资源等的优化问题进行研究的一种空间分析方法71.1.概述概述n主要用来解决两大类问题n研究地理网络的结构，如：优化路径的求解、连通分量求解等问题n研究资源在网络系统中的分配与流动如：资源分配范围或服务范围确定、最大流与最小费用等问题空间网络分析实例空间网络分析实例n从A到B点的最快路线是什么？n哪些房屋距离消防站的车程小于5分钟？n哪辆救护车能够最快对一起事故做出响应？n一支配送或服务车队如何在提高客户服务质量的同时降低运输成本？n如果某家公司必须

3、缩减规模，那么它应该关闭哪家商店才能继续满足最为全面的需求？81.1.概述概述n概述概述n网络分析基础网络分析基础n网络结构分析网络结构分析n最优路径分析最优路径分析n资源分配资源分配n本章小结本章小结9空间网络分析空间网络分析网络的基本要素网络的基本要素n链链：网络中两个结点之间的弧段n结点结点：链的两个端点n站点站点：网络路径上资源增加、减少的地方，是分布于网络链上的结点，如公交站点n中心点中心点：网络中具有一定容量，能够从链上获取资源或发送资源的结点，如水库、商业中心、学校等n障碍障碍：网络中阻断资源流动的结点或链，如禁止通行的道路、交通红灯等n拐角拐角：指网络中资源流动可能发生转向的结

4、点，如禁止左拐的路口102 2.网络分析基础网络分析基础网络基本要素的属性项网络基本要素的属性项n阻碍强度阻碍强度n用于量测资源在网络中流动的费用或阻碍，可以作为网络链、站点和中心点的属性，通常用时间、成本来衡量n资源资源需求量需求量n网络中可被“运输”的资源数量，如沿街道居住的学生人数、某一站点要被运送的货物等n资源资源容量容量n指一个中心可以容纳或可以提供的资源总量，如学校的总人数、停车场的停车位等112 2.网络分析基础网络分析基础网络的存储模型网络的存储模型n邻接矩阵法n用于表示图中任意两点间的邻接关系及其权值的矩阵n两点间有一条弧，则邻接矩阵中对应的元素为1，否则为0122 2.网络

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

6、结点邻接表的集合表示142 2.网络分析基础网络分析基础1234512345242338640600390530470结点号结点信息n概述概述n网络分析基础网络分析基础n网络结构分析网络结构分析n最优路径分析最优路径分析n资源分配资源分配n本章小结本章小结15空间网络分析空间网络分析度与中心度度与中心度n度：指一个结点所连接边的数目，是衡量和刻画网络结点特性最简单又最重要的概念n中心度：衡量结点在网络中所处中心地位程度的一个指标n点度中心度n通过计算结点的度来度量结点在图中的核心地位程度n仅考虑了与该结点直接相连的点数，而忽视了间接相连的点数163.3.网络结构分析网络结构分析BAC度与中心度

7、度与中心度n中心度：衡量结点在网络中所处中心地位程度的一个指标n接近中心性n从距离角度来衡量一个结点的中心地位，认为结点到网络中其它所有点的总距离最小，此时其接近中心性的值越大，则可认为该点是整个网络的中心点 其中，N是结点个数，dij表示结点i到j的距离173.3.网络结构分析网络结构分析BAC度与中心度度与中心度n中心度：衡量结点在网络中所处中心地位程度的一个指标n介数中心性n从信息、物质或能量传输角度看，认为经过最短路径条数最多的边和结点是网络上承载流量最大的边和结点n例如：如果不经过结点v2，结点v3、v4就无法到达v1，这样v2在整个网络中起了很重要的桥梁作用，其中心程度要大于其它结

8、点183.3.网络结构分析网络结构分析路径与回路路径与回路n路径：从一结点到另一结点的一组结点序列n路径长度：路径上所经过边的数目n回路：起点和终点相同的路径n哈密尔顿回路:有且仅有一次通过图中所有结点的回路 如：1,2,4,5,6,3,1n欧拉回路：有且仅有一次通过图中所有边的回路，如：1,2,4,5,2,3,5,6,3,1193.3.网络结构分析网络结构分析连通性与生成树连通性与生成树n连通性：在无向图中，若从结点u到结点v有路径存在，则称u到v是连通的n强连通图：图中任意两个结点之间都连通n图的生成树：一个连通图的极小连通子图 满足：n生成树的边数为n-1（顶点数为N）n树无回路，但不相

9、邻顶点连成一边，就会得到一个回路n树是连通的，如去掉任意一条边，不会变成不连通的203.3.网络结构分析网络结构分析连通性与生成树连通性与生成树n最小生成树：一个连通图众多生成树中边权值之和最小的生成树（minimal spanning tree,MST）n特点：nN-1条边连接N个结点n所有边权值和最小例如：在n个城市间建立通信线路，使得通信网的造价最低213.3.网络结构分析网络结构分析最小生成树算法最小生成树算法Kruskal算法算法n先把图中的各边按权数从小到大重新排列，并取权数最小的一条边为最小生成树中的边n在剩下的边中，按顺序取下一条边。若该边与最小生成树中已有的边，构成回路，则舍

10、去该边，否则选入生成树n重复步骤2，直到有M-1条边被选进生成树中，这M-1条边就构成最小生成树223.3.网络结构分析网络结构分析直径、半径和中心直径、半径和中心n结点半径：从某结点到其它所有结点的最长路径长度n结点v1、v2、v3、v4的半径分别为：2、1、2、2n图的直径：图中任意两个结点间的最长路径n图G的直径是2n图的中心：具有最小半径的结点称为图的中心n中心点是结点v2233.3.网络结构分析网络结构分析v1v2v3v4n概述概述n网络分析基础网络分析基础n网络结构分析网络结构分析n最优路径分析最优路径分析n资源分配资源分配n本章小结本章小结24空间网络分析空间网络分析最优路径的含

11、义最优路径的含义n路径分析是网络分析中一个最基本的问题，也是实际应用中最常见的一个问题n最优路径有多种含义，不仅仅指一般意义上的距离最短，还可指时间最短、费用最少、成本最低等含义n例 1：居民出行利用车辆导航获取距离最近、费用最优的路径n例 2：电力、水力管线的架设管线考虑的是成本最优的路径n最短路径分类n两个结点之间的最短路径n一个结点到图中其它所有结点之间的最短路径n所有结点对之间的最短路径254.4.最优路径分析最优路径分析单源最短路径算法单源最短路径算法Dijkstran基本思想：采用贪心策略，以源点为中心向外层扩展，直到扩展到目标点为止，即从源点依次产生出路径长度递增的最短路径n基本

12、步骤：n将图的结点集合V被分为两组（S和T），其中S存放已经计算出最短路径的结点（初始时只包含源点），T=V-Sn从集合T中选择距离最小的结点u，并将此顶点从集合T移入S中n以u为新的中间点，修改T中结点的最短距离，以保证从源点s到T中并经过结点u的最短路径长度不大于原来不经过顶点u的距离n重复2-3，直到所有顶点都被加入到S中264.4.最优路径分析最优路径分析单源最短路径算法单源最短路径算法Dijkstran示例274.4.最优路径分析最优路径分析043211010050601030200432110100506010302004321101005060103020单源最短路径算法单源最短

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

14、优路径分析最优路径分析TSP算法算法最近邻插入法最近邻插入法n基本基本思想思想：寻找与回路最近邻的结点并加入其中，构造一个结点数逐渐递增的回路，最后得到一个哈密顿回路即为近似解n基本基本步骤（设步骤（设T表示回路中的结点集合，表示回路中的结点集合，S表示回路外的表示回路外的结点）结点）n初始化：T=1，S=2,3,.,nn从S中选择一个结点i 将之加入T中，寻找回路T中的x,y,使得d(x,i)+d(y,i)-d(x,y)值最小，将x,y从回路中删除，同时增加边(x,i)和(i,y),即选择一条使回路长度增加值最小的边加入回路n若S为空，结束，否则转到步骤（2），直到所有结点加入回路中304.

15、4.最优路径分析最优路径分析TSP算法算法最近邻插入法最近邻插入法n示例示例314.4.最优路径分析最优路径分析n概述概述n网络分析基础网络分析基础n网络结构分析网络结构分析n最优路径分析最优路径分析n资源分配资源分配n本章小结本章小结32空间网络分析空间网络分析资源分配通常包括资源分配通常包括定位定位和和分配分配两个问题两个问题n资源定位是指已知需求的分布，确定供应点的最佳位置n资源分配则是已知供应点，确定其为哪些需求点提供服务的问题资源定位问题资源定位问题定位问题也常称为选址问题，涉及两个基本概念：n中心点：到所有点的距离中最大距离达到最小的位置n中位点：点到其它点的距离总和达到最小的位置

16、335.5.资源分配资源分配选址问题选址问题示例：示例：n在该邮区范围内的5个城市选择一个城市作为中心局所在地n计算顶点间的最短距离，得到距离矩阵Rn使用中心点或中位点法确定中心位置中心点法中心点法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)=max(3,3,2,0,1)=3MVV(5)=max(2,4,3,1,0)=4n最大距离的最小值为3，则选城市4 为中心局所在地345.5.资源分配资源分配21543352147120 3 4 3 23 0 1 3 44 1 0 2 33 3 2 0

17、 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=10n最大距离的最小值为3，则选城市4 为中心局所在地355.5.资源分配资源分配21543352147120 3 4 3 23 0 1 3 44 1 0 2 33 3 2 0 12 4 3 1 0R=分配问题分配问题资源分配是一种按照特定原则（如距离、时间等）为供应中心分配需求点的一种分析方法，反映了现实世界中网络资源的一种供需关系n常包含两种含义常包含两种含义

18、n确定中心服务范围在一定限制条件下（如时间、费用或者距离等），服务中心所能提供服务的最大空间领域n确定中心资源分配范围不仅要考虑到服务范围内的总费用不超过中心的最大阻值，而且服务范围内的总需求量也不能超过中心的供应量365.5.资源分配资源分配确定中心服务范围确定中心服务范围n基本思想基本思想 依次求出服务费用不超过中心阻值的路径，组成这些路径的网络节点和边的集合构成了该中心的服务范围n主要步骤主要步骤n根据拓扑关系，计算地理网络的最大邻接节点数n构造邻接节点矩阵和初始判断矩阵描述地理网络结构n应用广度优先搜索算法确定地理网络中心的服务范围375.5.资源分配资源分配确定中心确定中心资源分配范

19、围资源分配范围n基本思想：基本思想：依次求出到服务中心费用不超过中心最大阻值，同时网络的总需求量不超过中心的货源量的路径，组成这些路径的网络结点和边的集合就构成了该中心资源分配的范围n处理时同时考虑到网络和网络结点的需求量，具体处理时与服务范围的搜索方式类似P中心中心定位问题定位问题 在m个候选点中，选择P个供应点，为n个需求点服务，并使得从服务中心到需求点之间的总距离最小n线性规划法求得求最佳结果（计算量及内存需求量巨大）n启发式算法来逼近或求得最佳结果385.5.资源分配资源分配n概述概述n网络分析基础网络分析基础n网络结构分析网络结构分析n最优路径分析最优路径分析n资源分配资源分配n本章小结本章小结39空间网络分析空间网络分析n网络分析基础网络分析基础n基本要素、存储模型基本要素、存储模型n网络结构分析网络结构分析n度与中心度、路径与回路、连通性与生成树度与中心度、路径与回路、连通性与生成树n最优路径分析最优路径分析n最最短路径、旅行商问题短路径、旅行商问题n资源分配资源分配n选址问题、资源分配问题、选址问题、资源分配问题、P P中心定位问题中心定位问题40本章小结本章小结