（计算机应用技术专业论文）大数据量gis网络分析算法的实现和优化研究.pdf

摘要 近年来，随着国民经济的迅猛发展，水利、石油、交通、海运、城市信息化 等各行业对空间信息处理的要求越来越迫切。用于处理空间信息的软件地理 信息系统( g e o g r a p h i ci n f o r m a t i o ns y s t e m 简称g i s ) 基础平台的开发成为关键。 g i s 网络分析是g i s 系统中最常用的分析功能之一。g i s 网络分析的应用领域也 很广泛。在企业应用方面，河流水域管理、城市生命线控制、交通物流运输、电 力网络监控、城市设施建设等诸多领域有强烈的需求和应用；在公共社会方面， 出行线路选择、公交线路查询，旅游景点的搜索等等也属于g i s 网络分析解决 的问题。 本文主要研究如何实现高效率的、用于处理海量空间数据的网络分析算法， 取得如下成果； 1 研究了不同应用领域中g i s 网络特点，设计了一个可满足市政网络和水 利网络的统一的网络模型，并设计了对应的逻辑结构和分析结构，研发 了基于配对堆的网络分析算法； 2 归纳和总结了网络分析算法，按照网络分析属性对算法进行分类，研究 了不同算法之间的共同点和差异性； 3 使用面向对象的思想对目前流行的网络分析算法进行模型设计，提出了 算法的继承模型和算法的依赖模型，这种面向对象模型的优点是易于扩 展、易于修改，便于复用，从而可以有效提高编码效率； 4 分析了网络分析算法的流程特点，利用缓存技术对算法进行了性能优 化，并对优化算法进行了测试，对比优化前后的算法效率，在使用两点 间最短路径缓存后，算法的效率提高非常明显，节点越多算法效率越高。 5 使用c + + 语言，编写了空间信息类库( s i c ) 和网络分析的算法，代码 量1 0 万多行。 本文所有的研究工作都是在开发自主知识版权的织女星地理信息系统 ( v e g a g i s ) 的过程中完成。所有算法效果和测试结果也是在该系统下运行得出。 关键词：地理信息系统( g i s ) 、网络模型、网络分析算法、缓存技术、最短路 径、d i j k s t r a 、配对堆、旅行商问题( t s p ) 、性能优化、织女星地理信息系统 i m p l e m e n ta n do p t i m i z a t i o nr e s e a r c ho fg i sn e t w o r k a n a l y s i sa l g o r i t h m sf o r l a r g e a m o u n t so f d a t a z h a n gl i n g n a n g ( c o m p u t e r a p p l i c a t i o n ) d i r e c t e db yf a n gj i n y u n i nr e c e n ty e a r s ，t h er a p i dd e v e l o p m e n to fn a t i o ne c o n o m yr a i s e st h ed e m a n d si n s p a t i a li n f o r m a t i o n , s u c ha si r r i g a t i o n , p e t r o l e u m , t r a n s p o r t a t i o n , s e as h i p p i n ga n dc i t y i n f o r m a t i o n a ls y s t e m t h eg e o g r a p h i ci n f o r m a t i o ns y s t e m ( o l s ) ，w h i c hi st h e s o f t w a r eo fm a n a g i n gs p a t i a ld a m , b e c o m e st h ep r i n c i p l et od e v e l o pt h e s ei n f o r m a t i o n s y s t e m s n e t w o r k a n a l y s i si st h em o s tf r e q u e n t l yp r a c t i c e df u n c t i o ni ng i s i ti sw i d e l yu s e di n f i e l d si n c l u d i n ge n t e r p r i s ea p p l i c a t i o n ，w a t e ra r e am a n a g e m e n t , c i t ys u p p l i e sc o n 虹o l t r a n s p o r t a t i o nr e d e p l o y m e n t ，e l e c t r i c a ln e t w o r ks u r v e i l l a n c e ，c i t yf a c i f i t yc o n s t r u c t i o n i nt h ep u b l i cs e r v i c ea r e a , n e t w o r ka n a l y s i so fg i sa l w a y sc o u l db ea p p l i e di n o u t g o i n gp a t hs e l e c t i o n , b u sl i n eq u e r ya n dt r a v e ls i t es e a r c h t h i sp a p e rm a i n l yf o c u s e so nt h ei m p l e m e n to fe f f i c i e n ta l g o r i t h m so fg i sn e t w o r k a n a l y s i sf o rl a r g e rs p a t i a ld a t a t h er e s e a r c h i n gr e s u l t sa r ea sf o l l o w s ： 1 t h er e s e a r c hi so nd i f f e r e n tg i sn e t w o r k sa n dd e s i g n sau n i f o r mn e t w o r km o d e l t os a t i s f yt h em u n i c i p a ln e t w o r ka n dw a t e rr e s o u r c en e t w o r k t h er e s e a r c h e r b u i l d st h el o g i c a ls t r u c t u r e sa n da n a l y s i ss t r u c t u r e sa n dd e v e l o p s a n a l y s i s a l g o r i t h m sb yp a i r i n gh e a p 2 t h er e s e a r c h e rs u n m 3 a r i z e st h ea n a l y s i sa l g o r i t h m sb yt h en e t w o r kt r a i t sa n dd o e s r e s e a r c ho nt h ec o m m o na n dd i f f e r e n tc h a r a c t e r sb e t w e e nd i f f e r e n c ea l g o r i t h m s 3 t h er e s e a r c h e ru s e st h eo b j e c t - o r i e n t e di d e o l o g yt od e s i g nt h em o d u l ef o rt h e n e t w o r ka n a l y s i sa l g o r i t h m sw h i c ha l eu s e df r e q u e n t l y i tp r o p o s e sa ni n h e r i t a n c e m o d u l ea n dar e l i a n c em o d u l e w h i c ha r ee a s yt oe x t e n da n dm o d i f y , a n dc a l l i m p r o v e sc o d i n ge f f i c i e n c y 4 t h er e s e a r c h e ra n a l y z e st h ep r o c e s sc h a r a c t e r i s t i c so fn e t w o r ka n a l y s i sa l g o r i t h m s a n da p p l i e sc a c h et e c h n o l o g yt o o p t i m i z e t h ea l g o r i t h m s t h ea l g o r i t h m s e f f i c i e n c yh a sb e e ni m p r o v e do b v i o u s l yw h e nu s i n gt h es h o r t e s t - p a t hc a c h e b e t w e e nt w op o i n t s ，e s p e c i a l l yw h e nt h en e t w o r kh a sm o r ev e r t e x e s 5 t h i sp a p e ru s e sc + + l a n g u a g et ob u i l das p a t i a li n f o r m a t i o nl i b r a r y ( s 1 9 i n c l u d i n ga s e to fn e t w o r ka n a l y s i sa l g o r i t h m s t h i sl i b r a r yh a so v e r1 0 0 ，0 0 0l i n e s o f c o d e t h er e s e a r c hi sa c c o m p l i s h e di nv e g a g i s ，ag i sd e v e l o p e db yi n s t i t u t eo fc o m p u t i n g t e c h n o l o g y , c h i n e s ea c a d e m yo fs c i e n c e s i t i si n d e p e n d e n ti n t e l l e c t u a lp r o p e r t y t h u s ，a l lt h ee x p e r i m e n t a lr e s u l t sa r eg o tf r o mt h i sg i ss y s t e m k e y w o r d s ：g i s ，n e t w o r km o d e l , n e t w o r ka n a l y s i s ，c a c h e ，s h o r t e s t p a t h , d i j k s t r a , p a r i n gh e a p ，t s p , p e r f o r m a n c eo p t i m i z a t i o n , v c g a g i s - 图表目录 图表1 基于w e b 的交通线路查询。 图表2 柯尼斯堡桥中的图形理论模型 图表3 无向图与有向图 图表4 从交通道路抽象出来的网络模型 图表5 网络要素继承关系 图表6 节点的组成 图表7 弧段的组成 图表8 路口转向示例 图表9 转向表和转向记录 图表l o 网络图层的组成 图表1 1 网络分析属性结构 图表1 2 网络路径和网络图 图表1 3 网络路径 图表1 4 网络图。 图表1 5 计算源汇方向 图表1 6 长江的上游流域追踪 图表1 7 两点间最短路径 图表1 8 查找5 个最近的加油站 图表1 9 服务区分析示意图 图表2 0 长江的源头分析 图表2 1 具有2 0 个送货点的交通网络图 图表2 2t s p 问题的最优解搜索过程 图表2 3 规划选址示意图 图表2 4 最短路径与最近设施查找算法代码 图表2 5 算法的继承模型 图表2 6 广度遍历算法流程的执行 图表2 7 算法的依赖模型 图表2 8 网络分析算法的依赖关系模型 图表2 9 一个配对堆的例子。 8 9 9 1 0 1 0 1 1 1 2 1 3 。1 3 1 4 1 8 。1 9 1 9 2 0 2 1 2 2 2 4 。2 6 2 6 2 7 2 9 3 0 3 0 3 1 图表3 0 配对堆节点的数据结构 图表3 1 配对堆节点的指针关联 图表3 2 两个子配对堆的“合并”操作 图表3 3 配对堆的“降级”操作 2 6 7 8 图表3 4 网络节点与配对堆节点的对应关系 图表3 5 改进的d i j k s t r a 算法流程 图表3 6 基于缓存技术的算法优化 图表3 7 为最短路径算法增加权值字段索引缓存 图表3 8 改变获取权值数据的方式 图表3 9 网络图层的转向表 图表4 0 转向表建立索引表 图表4 1 为t s p 算法增加两点最短路径缓存 。3 9 。3 9 4 0 4 0 图表4 2 调用两点间最短路径缓存的最短路径算法。4 2 图表4 3 多车送货问题的多级缓存优化4 3 图表4 4 地图编辑器 图表4 5 图示符号库 图表4 6 虚拟空间数据客户端 图表4 7 灌区地理信息系统 图表4 8 测试数据一 图表4 9 测试数据二 图表5 0 测试数据三 图表5 1 最短路径算法测试一 图表5 2 最短路径算法测试二 图表5 3 最短路径算法测试三 图表5 4 最短路径算法的测试结果 图表5 5 测试结果图 图表5 6 t s p 测试一 图表5 7 t s p 测试= 图表5 8 旅行商问题的测试 4 7 4 7 4 8 4 8 4 9 4 9 5 1 声明 我声明本论文是我本人在导师指导下进行的研究工作及取得的 研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，本论 文中不包含其他人已经发表或撰写过的研究成果。与我一同工作的同 志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了 谢意。 作者签名： 拍抟7 论文版权使用授权书 日期：刍r 一f 节 本人授权中国科学院计算技术研究所可以保留并向国家有关部 门或机构送交本论文的复印件和电子文档，允许本论文被查阅和借 阅，可以将本论文的全部或部分内容编入有关数据库进行检索，可以 采用影印、缩印或扫描等复制手段保存、汇编本论文。 ( 保密论文在解密后适用本授权书。) i ， 作者签名：拊够导师签耖甜乙日期形 矽 中国科学院硕士学位论文大数据量g i s 网络分析算法的实现和优化研究 第一章引言 随着国民经济的迅猛发展，水利、石油、交通、海运、城市信息化等各行业 对空间信息处理的要求迫切。空间信息在整个国家信息化建设中起到重要作用。 空间基础数据库建设是国家电子政务系统的四大主题数据库内容之一。用于处理 空间信息的软件一地理信息系统( g e o g r a p h i ci n f o r m a t i o ns y s t e m 简称g i s ) 的开发成为国家信息化建设中一个不可或缺的重要内容。在地理信息系统中，最 常用的分析功能之一就是g i s 网络分析。g i s 网络分析的应用领域很广。在企业 应用方面，河流水域管理、石油地下管线控制、交通物流运输、电力网络监控、 城市设施建设等很多领域有强烈的需求和应用；在公共社会方面，出行线路选择、 公交线路查询，旅游景点的搜索等也属于g i s 网络分析解决的问题。 1 1 问题的提出与背景 本文是在国家十五“8 6 3 ”计划“面向网络海量空间信息大型g i s ”支持下完 成的，根据合同要求主要完成如下网络分析功能： 1 动态分段 2 路径分析 a ) 最短路径( 有向，无向) b ) 最优路径( 有向，无向) c ) 动态路径分析 3 地址匹配 4 资源分配 a ) 最近设施 b 1 选址分析 c 1 服务区分析 5 追踪分析 a ) 上溯追踪 b 1 下溯追踪 c 1 扩散追踪 1 中国科学院硕士学位论文大数据量q s 网络分析算法的实现和优化研究 本文已完成了路径分析中的最短路径( 有向，无向) 和最优路径( 有向无向) 功能、资源分配和追踪分析中的全部功能。 虽然现行的商业g i s 软件中或专业网络分析软件中网络分析功能很多，但真 正能实际应用的功能还仅限于其中的一部分，主要原因是某些网络分析算法在处 理海量空间数据的效率比较低，算法不实用 在交通网络应用中，最常用的功能就是查询两点问最短路径普通单机版软 件对算法的性能要求不高，但在网络上基于w e b 的查询方式，不仅要求算法的 一次搜索的速度快，而且对同一时间、多次查询有非常高的要求。因为在互联网 上，一个地图网站每天可能接受上百万次的查询。同时，查询交通最短路径，不 仅要考虑路段的时问花费，还要计算路口停留和转向的花费时间，这也增加了算 法的执行时间。 图爱1 墨于w e b 的交通线路置询 另外，一些计算复杂度高的算法n p 完全问题，如车辆送货( t s p 问题) 、设 施选址( 需要计算全源最短路径) 等，计算量大，时间花费多，内存需求量也大。 一个具有2 1 1 ，2 9 3 个节点、2 0 1 ，6 4 7 个弧段的城市交通网络为例，全源最短路径 的数据量可以达到8 3 1 g ；一个具有2 0 个送货点的出行路线组合能够达到2 0 1 = 2 4 3 2 9 0 2 0 0 8 1 7 6 6 4 0 0 0 0 条 中国科学院硕士学位论文一太数据量g i s 网络分析算法的实现和优化研究 其次，对于不同领域的网络模型，虽然存在共同点，但也存在一定的差异性。 交通网络具有弧段双向、转向花费等特征；河流网络具有弧段单向、上下游方向 特征；电力网络具有连通性特征；等等。如果对每一种网络都实现一套算法，不 仅增加了工作量和维护的复杂性，也不利于算法的抽象、独立和可复用。 因此，需要设计合理的网络模型和网络分析算法，同时要满足海量空问数据 处理的需求 1 2 国内外研究现状 对于g i s 网络分析功能，大型的g i s 平台软件均提供了通用的网络分析模 块。主要的国外g i s 平台软件有a r c g i s 、m a p l n f o ；国内的有s u p e r m a p 、m a p g i s 等。这些软件网络分析功能的特点是，简单、通用，用户可以使用其二次开发功 能来完成自己特定的需求。但这些软件的网络分析功能不能满足特定领域的需 要，因此出现了面向特定领域的网络分析软件。例如：面向交通网络的t r a n s c a d 、 面向电力网络的s m a u w o r l d 等。这些专业网络分析软件的特点是，面向领域的 分析功能丰富，特定的网络分析算法的执行效率高、复杂、并且种类多。 一些已有的网络分析算法在数学结构、算法理论上研究非常引1 1 ，但对基于 g i s 空间信息方面的研究相对较少，如交通网络中对路口的转向花费的支持。对 独立的分析算法优化研究较1 2 1 ，但从全局上对不同算法进行统一优化的研究还 较少。在公用w e b 服务上还主要以搜索类型的算法服务为主，如公交换乘、行 驶导引、设施查找。对于大数据量的空间信息，一些复杂的分析算法由于效率问 题还不能得到有效的应用，如车辆送货问题、设施选择问题等。 1 3 研究主要目标和内容 本文研究的主要目标就是实现高效率的、用于处理海量空间数据g i s 网络分 析算法具体内容包括： ( 1 ) 研究不同应用领域中g i s 网络特点，设计合理的、统一的网络逻辑结 构和网络分析结构，使之更有效的用于网络分析算法。 g i s 网络的基础结构模型来源于图论中的拓扑几何结构，它最基本的组成数 据结构就是节点和弧段在g i s 系统中，不同领域的网络分析对数模型有不同的 中国科学院硕士学位论文大数据量g i s 网络分析算法的实现和优化研究 要求。对于交通道路网络，它要求模型能够描述经过道路和路口的花费信息；对 于河流网络，它要求模型能够描述河流的流向、源头信息；对于电力传输网络， 它要求模型能够控制网络节点的开关、闭合等虽然不同网络具有一定差异性， 但用于分析它们的算法是相同的因此，需要设计一个统一的网络模型能够兼容 所有的网络，又能够满足不同网络的特殊需求。 ( 2 ) 归纳和总结网络分析算法，按照网络分析属性特点对算法进行分类， 研究不同算法之间的共同点和差异性。 网络分析算法是和网络的属性相关的。网络的方向性有无向、单向、双向三 种情况；网络权值包括节点权值、弧段权值和转向权值三种类型。圊一种分析功 能在实现不同属性网络下算法是不完全相同的。对算法所适于的网络属性类型进 行归纳分类，有利于设计和实现算法。 ( 3 ) 使用面向对象的思想对所有算法进行模型设计，设计继承模型提取算 法之间的共同部分，设计依赖模型实现算法之间的引用。 网络分析的算法种类很多，实现同一种算法的方法也有很多。面向对象的思 想是将所有客观的事物当对象看待，对象包括用于操作对象的过程方法和属性数 据。面向对象的最大好处就是提供了封装性和继承性，封装性将对象的所有改变 限制在类中，继承性将共同属性抽象到基类中，而不同的差异派生到子类中。将 算法按面向对象的思想设计有利于提取不同算法之间的共同点，也利于不同算法 差异的修改。 ( 4 ) 对最基本的网络分析算法一d i j k s t r a 算法进行优化。主要是优化用于 实现算法的可降级优先队列结构，采用了配对堆来实现可降级的优先队列，并对 改进后的d i j k s t r a 算法进行了分析。 ( 5 ) 分析网络分析算法的过程特点，利用缓存技术对算法进行性能优化， 详细介绍了优化的具体过程。 缓存技术广泛用于硬件系统的数据读取的性能优化，包括c p u 的数据缓存、 高速磁盘缓存、显卡缓存等该技术对数据读取性能优化明显，也广泛用于处理 大型数据的软件系统，包括数据库系统、w w w 访问、w e b 服务等。将缓存技 术应用到网络分析算法的优化中，能够提高网络分析算法在处理海量数据的效 率 中国科学院硕士学位论文一大数据量g i s 翩络分析算法的实现和优化研究 ( 6 ) 使用一批数据来测试网络分析算法，对比优化前后的算法效率，并给 出优化的结论 算法的优化效果如何，还得靠实际的数据运行来验证。通过分析实际数据的 计算结果，也能够发现不同优化方法的好坏了，在实际应用中也可以有目的选择 不同的优化方法使用 1 4 论文的组织结构 本文的第一章是引言，介绍了论文的研究背景、研究现状以及研究的主要目 标和内容；第二章介绍了g i s 网络模型，分别介绍了图论中的网络模型，本文实 现的g i s 网络模型和用于算法分析的动态结构；第三章介绍了主要的网络分析算 法，包括无向无权值算法、有向无权值算法、带权值算法、旅行商问题和设施选 址问题；第四章通过对网络分析算法的归纳和分析，借鉴面向对象的思想，提出 了算法的继承模型和依赖模型；第五章是基于配对堆改进的d i j k s t r a 算法，介绍 了d i j k s t r a 算法的思想、配对堆的概念、操作和算法复杂度，以及改进后的算法 流程；第六章介绍了基于缓存技术的算法优化方法，利用缓存技术对网络分析算 法进行了性能优化，详述了对最短路径算法和旅行商问题的优化方法；第七章对 使用缓存优化的算法进行了测试，介绍了测试环境、测试数据和测试内容方法， 给出了使用缓存的前后的对比结果，并分析了其对算法性能的影响；最后一章对 。 本文进行了总结，提出了下一步的工作方向 中国科学院硕士学位论文一大数据量g i s 弼络分析算法的实现和优化研究 第二章g i s 网络模型 在g i s 网络分析系统中，网络模型直接影响网络分析算法的设计与实现 g i s 网络模型是对现实世界中具有网络意义的事物的抽象。好的网络模型具有通 用性和一般性，能兼顾不同领域的网络特点，能够使算法的设计更灵活、独立。 2 1 图论中的网络模型 g i s 网络模型的数学基础是图论中的网络拓扑系统【引网络拓扑系统中研究 的创始人被公认为数学家欧拉( l e o n a r de u l e r ，1 7 0 7 - - 1 7 8 3 ) ，他在1 7 3 6 年解决 了当时一个著名的问题，叫做柯尼斯堡( k o n i g s b e r g ) 桥问题，也叫七桥问题1 4 】。 下图显示了该桥的一个概略的路线图。该问题就是找到一个循环的路，该路只穿 过其中每个桥一次，最后返回到起点。一些实验表明这项任务是不可能的，然而， 从认为没有这样的路线到说明它的步骤并不是这样容易的。 图表2 柯尼斯堡桥中的图形理论模型 七桥问题实质是一笔画问题，也是一个几何问题，但该问题中线条的长短曲 直都无关紧要，要紧的只是点线之间的相关位置或互相联结的情况，故欧拉把这 类几何问题的研究叫做位置几何学。欧拉对一笔画问题的进一步研究，终于找到 了可以鉴别任意图形能不能一笔画出的简便原则，即欧拉定理1 5 】( 一个网络能一 笔画的充要条件是：它连通并且奇顶点的个数是0 或2 ) 。 一般在几何上，将图定义为空间一些点( 顶点或节点) 和连接这些点的线( 边 或弧段) 的集合，可以表示为一个偶对g - - ( v ，e ) ，其中v 表示顶点的集合， e 表示边的集合，因此下图中的( 1 ) 可以表示为： 婺 中国科学院硕士学位论文一大数据量g i s 网络分析算法的实现和优化研究 v = v l ，v 2 ，v 3 ，v 4 ，v 5 ，e = e l ，e 2 ，e 3 ，e 4 ，e 5 ，e 6 ，e 7 v ( 1 ) 图表3 无向图与有向图 e ， ( 2 如果边的两个顶点是无序的，称为无向图；如果每条边有一个方向，这样的 图称为有向图对于有向图，有向边e 用与其关联的顶点的有序对来表示，即 e = ( u ，v ) ，u 表示边的起点，v 表示边的终点，因此上图( 2 ) 可以表示为： g = ( v ，e ) ，v = a ，b ，c ，d ) e = ( a ，a ) ，( a ，b ) ，( a ，b ) ，( a ，d ) ，( d ，c ) ，( c ，d ) ，( c ，b ) 如果顶点v 是边c 的一个端点，则称边c 和顶点v 相“关联”；对于顶点v 和v ，若( u ，v ) e ，则称u 和v 是“邻接”的；若两条边有共同的顶点，也称这 两条边是邻接的；和顶点v 相关联的边的数日成为v 的“度”。 应用中还需要为图中的边赋值，这个值称为“权”。它可以表示边的各种不 同的意义；如经过边的是一条道路，则权就可能是它的长度，也可能是它的修建 费用等。设边e ，的权为w 。则e 可以表示为： e = ( c 1 ，w d ，( c 2 ，w 2 ) ，( e 3 ，w 3 ) ) 或者设 w = w l ，w 2 ，w 3 则g 可以表示为一个三元组：g = 以上介绍了图论中的有关网络的基本概念和表示法。g i s 网络模型以图论中 的网络为基础，但在实际应用中需要对其进行了扩展，以便于更好的适应于网络 分析算法。 中国科学院硕士学位论：妤一大数据量g i s 网络分析算法的实现和优化研究 2 2g l s 网络模型 g i s 网络模型主要用于描述g i s 网络的静态信息，表征g i s 几何模型的空间 拓扑关系，是实现网络分析算法所需要的基本数据结构。g i s 网络模型的设计以 图论中的网络模型为基础，从应用中抽象出具有现实意义的结构而实现。 固 2 2 1 节点和弧段 图表4 从交通道路抽象出来的网络模型 节点( n e t v e r t e x ) 和弧段( n c t e d g c ) 是最基本的网络结构。节点表示网络 中具有点几何意义的地理要素；弧段表示网络中具有线几何意义的地理要素。节 点和弧段均抽象于网络要素( n e t f e a t u r e ) 。网络要素主要描述了节点和弧段的共 同特征。它们的继承关系如下： 图表5 网络要素继承关系 8 一 中国科学院硕士学位论文一大数据量g i s 嘲络分析算法的实现和优化研究 所有的网络要素都不包含具体几何图形坐标信息，它保存了一个几何要素的 关联指针对于节点，它关联的是一个点几何要素；对于弧段，它关联的是一个 线几何要素。网络要素用独立d 来表示网络中唯一身份网络要素本身也是一 个具有空间意义的要素，因此也具备外包信息。另外，为了编辑和实现网络分析 算法，网络要素还包括了有效性信息、方向信息等。 对于节点，它包含了所有与之连接的弧段信息连接的弧段的个数称之为节 点的“度”，对应弧段d 数组的大小。 图表6 节点的组成 对于弧段，它包含起始节点d 和终止节点d 。从起始节点到终止节点的弧 段逻辑方向称为“正向”，反之称为“反向”。弧段本身还具有附加的方向性，可 以人为规定，规定的方向是用于网络分析算法。如果规定的方向与弧段逻辑方向 相同，那么起始节点成为“源节点”或“上游节点”，终止节点称为“汇节点” 或“下游节点”，也就是节点的“源汇性”。节点也可以人为规定源汇性，如果同 一弧段的起始节点和终止节点规定了相同的源汇性，那么弧段的方向性是不确定 的。 r 知 图表7 弧段的组成 在连接节点的弧段中，如果节点是弧段的终止节点，那么该弧段称为节点的 “入弧段”；如果节点是弧段的起始节点，那么该弧段称为节点的。出弧段”。入 弧段的个数称为节点的。入度”；出弧段的个数称为节点的“出度” 中国科学院硕士学位论文丈数据量g l s 网络分析算法的实现和优化研究 2 2 2 转向 “转向”描述过了节点的转向信息在交通网络中，转向表示的就是车辆通 过路口的状态。转向的表示包括：“起始弧段、节点信息、终止弧段”。如下图， 经过的所有转向可以表示为“a a b ”、“b b b ”和“b a c ”。 司 0 介 = = = = = = c 9u i _ 图表8 路口转向示例 b ，、6 一 a “转向”还包括相应的权值属性，主要描述从不同弧段过节点所产生的不同 花费和状态，因此“转向”的结构是以转向记录( n c t t u m r e c o r d ) 的形式保存 在转向表( n c t t u m t a b l e ) 中的。一个“转向”信息对应转向表中的一条转向记 录，转向表就是转向记录的集合。 i d f r o m e d g e i dv e r t e x l dt o e d g e i dw e i g h t lw e i g h t 2 1 1233 4 5 ；2124 。 3 3 4 3 3243 0 8 4 233 3 2 1 5234 3 1 8 2 2 3 拓扑关系表达 图表9 转向表和转向记录 g i s 网络模型与图论中的网络模型的区别就在于：g i s 网络模型表达网络的 拓扑关系的多样化。表达g i s 网络模型拓扑关系的主要方式有； 中国科学院硕士学位论文一大数据量g i s 网络分析算法的实现和优化研究 1 节点和弧段的几何关联这种关系跟图论中的网络模型类似，产生的拓 扑关系源于g i s 空间位置； 2 节点和弧段的有效性信息。如果一个节点或弧段无效，即使它存在于网 络中，也不参加具体的算法分析，相当于不存在这个网络要素； 3 转向。转向也描述了一种拓扑关系，在具有转向属性的算法分析中，如 果从某一弧段到另一邻接弧段的转向不存在，那么也相当于这两个弧段 是不连通的； 4 权值属性不管是节点，弧段，还是转向，如果对应的权值属性字段的 值为负，在某些特定分析算法中相当于不连通的关系，这个节点、弧段 或转向也属于无效。 2 2 4 网络图层 网络图层( n e t l a y c r ) 是网络要素的组织结构，是一个完整的网络数据的集 合它包括一个网络的所有节点、弧段和它们之间的关系数据，还包括网络要素 的权值属性数据和转向属性数据网络图层是一个逻辑结构，它把来自于不同图 层的几何数据通过g i s 网络拓扑关系组织在一起。所有的网络分析算法都是针对 一个网络图层进行计算的。 网络图层 点图层l 点图层2 线图层1 线图层2 图表1 0 网络图层的组成 中国科学院硕士学位论文一大数据量g i s 网络分析算法的实现和优化研究 2 3 动态网络分析结构 网络分析结构主要用于g i s 网络分析算法，能够为算法提供必要的输入信 息，能够返回算法的运行结果，在g i s 网络系统中也具备一定的物理意义。网络 分析结构主要包括用于算法输入的“网络分析属性”，用于算法结果返回的“网 络路径”和“网络图”这些结构不属于g i s 网络的静态数据，也不保存在网络 存储中，属于动态数据结构。 2 3 1 网络分析属性 网络分析属性结构( n e t p r o p e r t y ) 描述用于分析的网络图层的属性信息，包 括网络的类型，节点、弧段以和转向的权值字段信息。任何一个网络都必须有一 个方向属性；如果权值字段为空，表示网络不包括这种权值类型的属性信息。 图表1 1 网络分析属性结构 网络分析属性属于动态信息，对于不同的分析算法，它的内容可能不同。例 如，求交通的时间最短路径，典型的网络分析属性为“双向图、弧段权值字段 ( t i m e ) 、转向权值字段( t i m e ) ”；对于分析河流的源头，其网络分析属性为 “单向图、弧段权值字段( l e n g t h ) ” 中国科学院硕士学位论文一大数据量g i s 网络分析算法的实现和优化研究 网络的逻辑数据中不包括用于网络分析的属性，网络分析属性只有在进行网 络分析时才动态的指定在设计网络分析算法时，不针对具体的网络类型实现， 而是利用网络分析属性结构设计通用的算法。这样，使用动态的网络分析属性结 构，就可以使网络分析算法更好的独立于网络模型本身。 2 3 2 网络路径和网络图 述。 网络路径( n e t p a t h ) 和网络图( n e t g r a p h ) 主要用于网络分析算法的结果描 图表1 2 网络路径和网络图 网络路径是由一系列连续的节点和节点之间的弧段描述，表示网络图层中的 一条线路。对于有权值的网络分析算法，它还包括这条路径的权值累加和。网络 路径中的节点和弧段可以重复，但是有先后顺序最短路径分析的结果就是一条 网络路径；多车送货分析算法的结果是多个网络路径。 r 火彳x ， 图表1 3 网络路径 网络图也是由网络节点和弧段描述，但是图中的节点和弧段不能重复。它主 中国科学院硕士学位论文一大数据量g i s 网络分析算法的实现和优化研究 要表示的是网络图层中一个范围或若干区域内的网络要素数据，可以看作一个子 网络。网络图的一个重要属性就是它的凸包信息，所有节点和弧段在地图上所处 的最小多边形就是它的凸包。网络图的凸包是一个几何区域，描述的是这个图的 几何信息，包括它的面积等。网络图也有权值得概念，它是这个图中所有节点和 弧段的权值和，表示该网络图的统计信息。对于网络分析算法，服务区分析、连 通性分析等算法的结果就是网络图。 图表1 4 网络图 中国科学院硕士学位论文一大数据量g i s 网络分析算法的实现和优化研究 第三章g l s 网络分析算法 g i s 网络分析算法是对g i s 网络模型进行分析运算，为人们提供决策。传统 上，网络分析算法一般是按照其功能进行分类【6 】，如；路径分析、资源分配、连 通分析、流分析和选址分析而本章所述的算法，是根据网络属性的特点，按照 图的方向性、权值类型把网络分析算法分为：无向无权值算法，有向无权值算法 和带权值算法，以及利用这些算法实现的旅行商问题和设施选址问题。 3 1 无向无权值算法 无向无权值算法指的是网络的弧段没有方向、没有权值花费，仅通过节点和 弧段之间的连接拓扑关系进行分析的算法主要包括查找性算法和连通性算法。 3 1 1 查找性算法 查找性算法是找到网络图层中具有某一特征的网络要素查找孤立节点，即 返回所有没有弧段相连的网络节点，一般情况是一些错误的网络节点。查找端节 点，即找到一些只连接一个弧段的节点，一般是网络的源头节点或汇合节点。查 找性算法一般用于网络的错误检查、河流源头分析等 3 1 2 连通性分析算法 连通性算法是分析节点和弧段的连通关系的算法。主要包括：查找所有与给 定节点连通的节点和弧段；查找所有与给定节点不连通的节点和弧段；查找所有 与给定节点连通的环。连通性算法主要用于电力、交通等网络的分析。 3 2 有向无权值算法 有向无权值算法主要指的是网络中的弧段没有权值花费，但具有一定的方 向，利用网络中节点或弧段的方向属性进行的分析算法。主要包括方向分析算法 和追踪算法。 中国科学院硕士学位论文一大数据量g i s 网络分析算法的实现和优化研究 3 2 1 方向分析算法 某些网络在初始时没有任何方向属性的设定，但是通过设定几个节点的方向 属性，可以根据连通关系可以动态的计算出弧段的方向属性以河流的网络为例， 任何河流只有一个汇合点，要么是湖泊，要么是入海口，其他网络端节点都是河 流的起始源头；从起始源头到汇合点之间的河流的流向都是固定的。因此设定了 河流的汇合点，通过方向分析算法就可以动态计算出网络中弧段的方向。方向分 析算法主要用于河流的流向和源头分析。 3 2 2 追踪算法 图表1 5 计算源汇方向 追踪算法是利用网络中弧段已有的方向属性进行的连通性分析的算法。即给 定一个节点，可以求得所有与该节点正向连通或反向连通的节点和弧段。追踪算 法也主要用于河流网络的分析。 中国科学院硕士学位论文一大数据量g i s 网络分析算法的实现和优化研究 3 3 带权值算法 图表1 6 长江的上游流域追踪 带权值算法是使用最多、应用最广的网络分析算法。网络中的每个弧段甚至 每个节点都具备一定的权值花费。通过弧段就要累计该弧段的花费，因此从一节 点到另一节点的连通路径都具备一定的权值和。根据不同的需要，产生不同类型 的网络分析算法。常用的带权值算法包括；最短路径算法、最近设施查找算法、 服务区分析算法、最长路径算法等。 3 3 1 最短路径算法 最短路径算法是最常用的网络分析算法最基本的最短路径算法是，网络中 的每一个弧段都有一个长度，求两个节点之间的连通路径中最短的一条。如果权 值的类型不同，那么最短路径算法求得的结果可以不是距离最短以时间属性作 为权值就是时间最短，以金钱花费为权值，就是花费最短。不同权值的最短路径 算法也称为最优路径算法或最佳路径算法。 最短路径算法在交通领域的应用最广例如；给定一个始发地点和一个目的 地点，计算出两地的最优出行路线或最佳的公车换乘方式 中国科学院硕士学位论文大数据量g i s 网络分析算法的实现和优化研究 3 3 2 最近设施查找算法 图表1 7 两点问最短路径 最近设施查找算法是以最短路径算法为基础的算法。已知一些设施节点，任 意给定一起始节点，求出距离这个节点最近的一个或几个设施节点。 可以计算出起始节点到每个设施节点的最短路径的距离，通过距离排序取得 需要的设施，但这样产生了许多不必要节点的计算。一种高效的算法也是最小生 成树算法的交体。通过对起始节点的广度遍历，计算已经访问到的设施节点，直 到访问的设施个数达到所需要的个数即停止遍历，得到需要个数的结果。 最近设施查找算法的应用给出行带带了极大方便。在任意一地点，可以迅速 查找到最近的加油站、商店、医院、火车站等。 图表1 8 查找5 个最近的加油站 中国科学院硕士学位论文一大数据量g i s 网络分析算法的实现和优化研究 3 3 3 服务区分析算法 服务区分析算法是指给定一节点位置和一权值的限制范围，求出所有在限制 范围内从该节点出发所能到达的节点这些结果节点组成了一个区域称为起始节 点的服务区服务区分析算法实际上是求出了一系列的在给定权值范围内的路 径。它也是使用最小生成树算法，对节点的遍历设置权值限制，来控制算法遍历 的节点个数。服务区分析算法主要应用在土地规划建设方面，它能够计算出一个 服务场所所能覆盖的区域范围，供决策者使用 3 3 4 最长路径算法 图表1 9 服务区分析示意图 最长路径算法是指以一个节点起始，到达所有能够连通的最短路径中，距离 最长的一条路径。利用单源最短路径算法中保存最长的路径信息可以求得。最长 路径算法的典型应用就是求河流的源头 图表2 0 长江的源头分析 中国科学院硕士学位论文一大数据量g l s 网络分析算法的实现和优