基于信息矩阵的最短GPS控制网独立闭合环生成算法

尹志永

(天津市测绘院，天津 300381)

基于信息矩阵的最短GPS控制网独立闭合环生成算法

尹志永∗

(天津市测绘院，天津 300381)

针对独立闭合环自动生成经典算法中多解性和环长未定两个问题，本文应用闭合环网形的信息矩阵，顾及边长因素，提出基于矩阵运算的新算法，生成的闭合环满足最短独立闭合环的所有要求。通过两种算法的GPS控制网闭合环搜索结果比较，验证了本文算法结果的唯一性和环长最短性。

最短独立闭合环；信息矩阵；闭合差

1 引 言

GPS定位技术具有高精度、全天候、测站间无需保持通视等优点，因而基本取代传统方法而成为建立各级平面控制网的主要手段[1]。闭合环差作为GPS控制测量外业质量评定的依据之一，是探测粗差的常用检测量。通常闭合环要求独立且最小，环数和环长越小，可靠性越好，若其检验合格，就可以保证大环的质量合格[2，3]。

最短闭合环应满足3个要求:①所有闭合环是独立的；②闭合环包含的边数最少；③对于边数相同的闭合环，取长度最短的环。目前，独立环的自动生成算法有3种:基于邻接矩阵变换算法，基于生成树和余树变换算法，基于深度优先搜索算法[4]。其中基于生成树和余树的算法的搜索结果稳定，文献[5]对其做了详细的理论分析。然而，作者发现目前的闭合环生成算法都未能有效顾及到环的边长信息，在某些情况下，搜索到的最小独立闭合环只能满足①、②两个条件，当搜索的初始条件不同时，搜索的结果也会不同，使得结果具有不确定性。本文运用图论中环的信息矩阵，加入边长信息，解决了闭合环的唯一性和环长最短性问题。

2 生成树余树算法分析

文献[6]给出了生成树余树算法的实现过程，该算法具有很强的稳定性，即能保证搜索到所有环数最小的独立闭合环[5]。但其中也指出，对于大地四边形，如图1所示，当生成树不同时，得到的闭合环不同，其中独立的最小环有3个，而最小环有4个，因此会出现4种不同的结果。这是未考虑边长因素引起的。在某些算法中，回代余树后用Dijkstra方法来寻找最短路径，但对余数回代的顺序有要求，如图2所示，搜索到的生成树为S1－S2－S3－S5，余树顺序为S4－S6，余树第一条S4回代，寻找最短路径为S4－S3－S2－S1，然而最短路径应为S4－S6－S5－S1，由于余树S6在第一回代中还未出现，不能由Dijkstra算法得到最短路径。当余树顺序为S6－S4时，可搜索到正确最短闭合环S3－S2－S5－S6和S5－S6－S4－S1。基于生成树余树的算法尚未解决最短闭合环的自动比较提取功能。

图1 大地四边形

图2 示例

3 环形连通图信息矩阵

连通图由结点和边组成，结点和边完全描述了连通图的拓扑结构，在计算机中的存储结构为起点、终点、边、边长。

图的存储结构 表1

以结点为行，以边为列，矩阵也能表述连通图，如图3所示。

图3 连通图

其关联矩阵表示如下:

正1表示起点，负1表示终点。为了理解方便，图3引入了方向，但对连通图本身的拓扑结构不产生影响，因此方向可自定义。关联矩阵与长度没有联系，长度信息存储在另外一维数组。显然矩阵G是秩亏的，删去某一行，即删去某个基准点，如o点，成为满秩的基本关联矩阵B，如下:

另外，图3还关联着一个基本回路矩阵，当连通图的树确定后，每条余树边所对应的回路称为基本回路，该回路方向与余树方向一致，由全部基本回路构成的矩阵称为基本回路矩阵Cf[7]，假定图3的树为4－5－6，余树1－2－3，则Cf如下:

该矩阵表明了图3有3个独立环，分别为4－5－1、5－6－2、4－6－3。将矩阵B的列号按照Cf的列号重新排列，得到Bf，由图论知识得按余树对矩阵分块得到:E为单位阵，最后可得，那么:

因此可根据基本关联矩阵来求出基本回路矩阵，而基本回路矩阵的每一行代表一个独立环，对于基本关联矩阵要求余树填充于矩阵末列。基本关联矩阵和基本回路矩阵组成了闭合环的信息矩阵。

4 最短独立闭合环生成算法

该算法分为3个步骤:①广度优先搜索得到生成树集合和余树集合，形成基本关联矩阵Bf；②由式(4)算得Cf，得到所有独立环，通过环间的余树替换，得到所有边数最小独立环；③加入边长信息，比较共用环边且环数相同的环，以短边替换长边。

4.1 形成关联矩阵

连通图的每条边按起点、终点、边的顺序存储，图结构按边依次存储，称为图表。一个连通图的每个结点有不同的度，按广度优先搜索树，以度数最大的结点作为搜索起点则最优。因此先扫描图表，得到度数最大的结点，然后开始广度优先搜索得到生成树，该算法不在这里赘述。

得到的生成树与原来的图做差就可以得到余树，初始化基本关联矩阵Bf为零，其行数为结点数减一，列数为边数，从末列开始填充，先将余树依次填入，接着填入生成树，并记录每列对应的边号。

4.2 生成边数最小独立环

基于环间的替换等价于矩阵行相加或相减的原理，来设计边数最小独立环生成的算法。①将基本回路矩阵的行重新排列，按边数大到小依次递减；②置第1行为当前需要替换的行，计算绝对值之和，依次与下面所有行求和、做差，再做绝对值相加，若结果小于初始绝对值之和，则替换，否则继续与下一行比较；③当第1行处理完毕，继续下一行的处理，直到所有行处理完毕，则生成所有环数最小的独立环。

4.3 生成环长最短独立环

前面两步生成的边数最小独立环与基于生成树余树算法得到的结果一致，在环数最小意义上，搜索已经成功。对于边数不同的环，已经不需要再做处理，边数相同的环，显然由于没有任何约束条件，它们是等价的，导致环的结果多解性。不唯一性给GPS环的质量检查带来不方便，不利于成果的通用性。在环数相同的环间，加入环长最小这一条件，就能得到唯一解，如图1的大地四边形，将得到环长较小的3个环。

算法如下:每次矩阵运算前取绝对值，①对边数相同的环做差，如果边数增大，转③，相等转②，边数减小不可能发生；②计算环长，减小则替换，转④；③寻找与初始环同边数的行做差，如果边数恢复且环长减小则替换，否则转④；④循环操作。直到所有环处理完成后，得到所有最短独立环，且结果唯一。

5 算例分析

5.1 GPS网介绍

测区位于武汉市某工程区，布设了D级GPS控制网，共10个GPS点，平均边长 450 m，使用4台GPS接收机分5个时段测，平均时段为1 h。网形如图4所示，每个点均测两个时段。GPS基线处理使用TGO软件，解算出每条基线的长度以及高差，网形信息如表2所示。由于基线的水平分量闭合差检验类似，不再列出。作者用C＋＋实现了本文提出的算法。

GPS网形信息 表2

图4 D级GPS网

5.2 结果分析

该D级GPS控制网共有16个最短独立闭合环，最终成果如表3所示，以GPS规范[8]中的闭合差公式为限差，其中所有环质量均检验合格。

基于树和余树的算法生成闭合环，其中2、7、9、10号环不同。如表4所示。

闭合环检验结果 表3

结果比较 表4

表4中的环长大于表3中相应的环，在图4中表现为大地四边形的独立环多解性情况，而表3的最小独立环具有唯一性，且满足最短独立闭合环的所有条件，达到了本文算法预期的效果。

6 结 语

本文通过引入环的信息矩阵，将独立闭合环的生成转换成矩阵运算，思路简单，算法实现容易，能够生成最短独立闭合环，满足了GPS网闭合环质量的自动检核要求。本文提出的算法同样适用于其他网结构图形。

[1] 李征航，黄劲松.GPS测量与数据处理[M].武汉，武汉大学出版社，2005

[2] Leick Alfred，Emmons Michael B.Quality Control with Reliability for Large GPS Netw－ork[J].Journal of Surveying Engineering，1994，120(1)，35～41

[3] Eliseo Clementini，Paolino Di Felice.Baseline quality check in GPS Postprocessing and network analysis[C].ACSMASPRS Fall convention，October 28，1991－November 1，1991

[4] Chong A.K.A comparison of methods for representing Topological relationships[J].Info－rmation Sciences，1995，5(3): 49～178

[5] 邹进贵，冯晨.控制网最小独立闭合环搜索算法研究[J].地理空间信息，2008(06)

[6] 冯琰，张正禄，罗年学.最小独立闭合环与附合导线的自动生成算法[J].武汉测绘科技大学学报，1998，23

[7] 戴一奇，胡冠章，陈卫.图论与代数结构[M].北京，清华大学出版社，1995:38～56

[8] GB/T 18314－2009.全球定位系统(GPS)测量规范[S].

Information Matrix Algorithms to Produce Least Independent Close Loops In GPS Control Network

Yin Zhiyong
(Tianjing Institute of Surveying and Mapping，Tianjin 300381，China)

To address the problems of multiple solutions and indefinite ring length in the classical independent closed loop algorithm，using the closed ring－shaped information matrix and taking into account the side element，this paper introduces a new algorithm based on matrix operations.The resulting closed loop meets all the requirements of the least independent closed loops.Through comparing the results of two algorithms in GPS network closed loop researching，the uniqueness of the result and the shortest length of ring are verified.

least independent close loop；information matrix；closure error

2011—05—05

尹志永(1974—)，男，高级工程师，主要从事城市测量技术工作。

1672－8262(2011)05－94－04

P228

A