lecture9网络分析.ppt

空间网络分析 空间对象分类 看得见的线状分布：如河流、道路、铁路、输电线路、供水管道、政区边界等。上述线状分布在三维空间中是实际存在的，是看得见，摸得着的； 看不见的线状分布：如地理区域之间、城市之间、工厂之间的联系，无线通讯网和航空线路等。这些线状分布是不可见的，只有通过设计和调查在相关图件上加以表达。 无论是何种线状分布，它们都是通过线连接在点上的。这些点称为顶点或节点，两个点之间的线称为环、弧或边，节点和环线系统就称为网络。节点和环线是构成网络的两个基本要素。 空间网络的类型 网络图基本概念 有向图和无向图 路与回路 连通性 网络图的矩阵表达 邻接矩阵：G的顶点集V中每两点间的邻接关系唯一确定。（顶点与顶点之间的邻接关系） dij=1 Vi 和Vj邻接 dij=0 Vi和Vj不邻接 关联矩阵：G的v个顶点和e条边的无向关联矩阵。（顶点与边之间的关联关系） aij=1 ei 和Vj邻接 bij=0 ei和Vj不邻接 路径分析 1）静态求最佳路径：在给定每条链上的属性后，求最佳路径。 2）N条最佳路径分析：确定起点或终点，求代价最小的N条路径，因为在实践中最佳路径的选择只是理想情况，由于种种因素而要选择近似最优路径。 3）最短路径或最低耗费路径：确定起点、终点和要经过的中间点、中间连线，求最短路径或最小耗费路径。 4）动态最佳路径分析：实际网络中权值是随权值关系式变化的，可能还会临时出现一些障碍点，需要动态的计算最佳路径。 路径分析 路径分析例题 路径分析（path analysis） 迪克斯查（E.W.Dijkstra）提出的标号法是解决最短路径问题最好的方法。这个方法的突出优点是：它不仅求出了起点到终点的最短路径及其长度，而且求出了起点到图中其它各顶点的最短路径和长度。 路径分析： 设 是一个有向图的网络，对于它的每条边或每一对顶点都可以对应一个数。在实际应用过程中，对于 的取值是这样规定的： 1.如果边以 为起点， 为终点，则取这个边的长度； 2.如果顶点 不是某一条边为起点和终点，那么取值为： 3.如果 ，取值为0。 标号法过程 定位配置分析(location-allocation analysis ) 服务点的最优区位问题 在城市管理中，利用GIS技术确定服务点的最优区位问题十分重要，如确定幼儿园、商场、消防队、医院、交通场站等的最优位置，以达到服务、资源的最优配置。最优服务点的最优区位问题有两种算法供选择 服务点的最优区位问题算法1 设G是一个n有个顶点： m条边： 的无向连通图，那么对于每一个顶点，它与各顶点间的最短路径的长度为： 最大数称为顶点的最大服务距离，用 表示 服务点的最优区位问题算法1 求出一个点 使得 具有最小的值。这样处理数据的含义是很明显的。因为在图上找出这个 点后，把服务点设在这个位置上，对于分散在各个顶点上的服务对象来说，最远的服务对象与服务点之间的距离达到了最小。这个点称为图的中心。 首先计算出的距离表 最后求 ，定出 均是G的中心 服务点的最优区位问题算法2 设G是一个n有个顶点： m条边： 的无向连通图，那么对于每一个顶点，它与各顶点间的最短路径的长度为： 并设每个顶点有一个正负荷 。现求出一个顶点，使得 最小，此点被认为是G点的中央点 首先，计算G的距离方阵 其次求出 P-中心问题 在m个候选点中选择p个供应点，为n个需求点服务，并使得服务中心到各个需求点之间的总距离(时间，费用)为最小。可以描述为： Teitz-Bart算法 选取p个候选点作为起始供应点集Pt:C1,C2,...Cp 将所有的需求点分配给他们最临近的供应点，使其距离最短。计算总的加权距离Bt 从未选取的候选点中选取一候选点Cb 对Pt中的每个供应点Cj用Cb替换之，并计算总加权距离的变化 如果供应点Cj用Cb替换后总加权距离减少，那么就替换总加权距离减少最多的供应点。 重复3-5步，直至未被选取的点集为空 当所有不在Pt中的候选点试过后其结果记为P’t 重复2-7步，直到总加权距离不变为止 中心服