基于改进的生成树和余树算法控制网最小独立闭合环搜索算法研究*

王鹏磊 刘长星 张 健 魏春亚

1)西安科技大学测绘学院，西安 710054

2)西安建筑科技大学信控学院，西安710054

1 引言

控制网中存在的多余观测可用来检查闭合环的闭合差是否超限［1］，但需要事先通过已知数据找出其中独立的闭合环。目前，计算机自动搜索最小独立闭合环的算法主要有邻接矩阵变换方法、深度优先搜索算法、生成树和余树算法。然而，这三种方法在搜索闭合环时均未将边长因素考虑在内，在某些情况下并不能使所有搜索到的闭合环均满足最短独立闭合环的要求，当搜索的初始条件不同时，搜索的结果也会不同，使结果具有不确定性［2］。其中，生成树和余树的算法简单易懂，且计算结果稳定，本文基于该算法并进行了改进，使其在考虑边长的因素下，实现最小独立闭合环的自动比较提取。

2 最小独立闭合环形成条件

无论是高程还是平面控制网，所选取的独立的边构成的闭合环均应满足:

1)所有闭合环相互独立，即任何一个闭合环都不能由其他闭合环的线性组合来代替;

2)闭合环中包含的边数最少;

3)边数相同的闭合环，取长度最短的。

满足以上三个条件的闭合环叫做最小独立闭合环。对于一个控制网，其最小独立闭合环的构成情况并不是唯一的，只需找出其中一组即可。

3 改进的最小独立闭合环搜索算法

生成树和余树算法是计算机自动搜索闭合环方法中最稳定的一种。该算法需先将控制网信息通过一定的算法简化为一个生成树。生成树需满足:1)包含闭合环网络图的所有结点;2)为连通图，即图中任意一个结点通过某一支路可以到达另外任意一个结点;3)不包含任何闭合环路。

当网络图较为复杂时，一个网络图会有很多不同的生成树，当然也对应着不同的闭合环路信息。为了减少计算量，最快地得到最小独立闭合环，采用深度优先搜索法生成一颗树，使得构成基本环路的支路数目尽可能少，这样的生成树即为最优树。如图1(a)所示网形，生成最优树的步骤为:

1)计算网中各个结点的度，找出其中度最大的结点，并假设该点为P;

2)以网中度最大的结点P 为起始点，并根据观测数据访问该点的邻接点P1，P2，…，且记录相应的邻接边;

3)分别从P1，P2，…出发，访问它们的未曾被访问过的邻接点，并记录相应的邻接边;

4)若此时尚有未被访问过的结点，则继续访问下一级邻接点，直至所有的结点都被访问完，所记录的所有邻接边组成的图形即为其最优树(图1(b))。

最优树树型结构建立后，通过在生成树上添加余枝得到独立闭合环。然而，对于某些网型，仅通过生成最优树的办法是不能得到所有的最小独立闭合环的。例如图2 所示的图形，无论从哪一点开始搜索或在搜索过程中改变搜索点来建立树，都不能只通过添加余枝的办法形成所有的最小闭合环。

图1 最优树生成示例Fig.1 Examples of the best tree generation

图2 一网形结构及其两种树形Fig.2 A single network structure and its two kinds of trees

为了解决这个问题，笔者对生成树和余树算法进行了改进，在考虑边长因素的情况下，利用MATLAB 编程实现了最小独立环的提取。这种算法是将搜索过程分为两大部分，即正向记录和反向提取。现以将余枝(i，j)添加到树上进而形成闭合环为例，进行说明:

1)正向记录。设存放树枝信息矩阵为A，A 中的树枝包括建立生成树时找到的树枝和已经搜索到最小闭合环的余枝。用数组route(1:size(A，2))记录搜索树枝的信息，搜索前设为0。

从余枝(i，j)的一个端点i 开始搜索，将搜索到的树枝信息用终点点号标记，即将该支路的route 值赋为终点点号。然后在找出的新点上继续搜索，将在新点搜索到的新树枝再用终点点号标记，继续重复搜索，直至搜索到的新点编号为j。

2)反向提取。搜索到j，得到搜到j 的树枝信息route 值，并得到树枝的另一点，提取该点，其编号为树枝信息route 值，由该点判断与其相连的树枝信息route 值，找出不等于该点编号的另一非零值，该非零值即为与该点相连树枝的另一端点，提取该点，重复反推，直至找到i。反向提取过程中，提取的点为余枝(i，j)搜索到的闭合环所经过的点。

如图2(a)，建立的生成树结构如图2(b)，其中一个余枝(1，6)的搜索程序流程见图3。搜索前各树枝信息值设为0，如图3(a)，在搜索过程中，每遇到一个新点，对其支路的编号与该点名相同，此例中从点6 出发，依次对路径数为1、2、3 的支路进行编号⑥、④、⑤，如图3(b)，即完成正向记录;反向提取时，从余枝的另一端点出发逆向寻找，在每个点所连接的支路中与该点点号不同的支路即是闭合环的支路，此例中便是从点1 出发，按条件依次可找到编号为⑤、④、⑥的支路，这些支路加上余枝本身即可构成闭合环。

图3 正向记录与反向提取示例Fig.3 Examples of forward record and reverse extraction

建立树型结构后，余枝数即为独立闭合环的个数，设为n 个，则闭合环搜索的具体算法步骤如下:

1)在生成树和余树结构中，从某一余枝(R1，R2)的一个端点R1出发，依次访问路径数为1，2，…的邻接点，直至被访问的邻接点是余枝的另一端点R2为止，即得到了由这个余枝构成的独立环。

2)分别以剩余的n－1 个余枝代替1)中的余枝(R1，R2)，以同样的方法寻找其对应的独立环。

3)将n 个独立环进行比较，若边数最少的独立环只有一个，则选择其作为搜索到的第一个最小独立闭合环;若最少边数的独立环有个多个，再比较这些闭合环的线路长度，选择线路最短的闭合环作为第一个最小独立闭合环。

4)在第一个最小独立闭合环确定之后，将其对应的余枝信息转化为树枝信息，得到一个新的树型结构，在这个结构中，按同样的过程又可得到n－1个独立环，进而继续在这n－1 个独立环中进行比较，选取第二个最小独立闭合环。

5)依此类推，得到n 个最小独立闭合环。

以图4(a)所示网形为例，说明搜索流程。首先对网形各个支路进行编号，其中支路①边长为5，支路⑧边长为1，其他各支路边长均为3。建立如图4(b)所示的生成树后，余枝分别为①、③、⑥、⑧，然后搜索闭合环得①－②－⑦－⑤，③－④－⑤－⑦，⑥－②－⑦和⑧－④－⑤。边数最少的独立环有两个，即⑥－②－⑦和⑧－④－⑤，两者线路最短的为⑧－④－⑤，故将该环路取出进而得到新的连通图，如图4(c);继续搜索闭合环，得①－②－⑦－⑤，③－⑦－⑧和⑥－②－⑦，取出其中边数最少且线路长度最短的闭合环③－⑦－⑧，连通图如图4(d);继续搜索闭合环得①－②－⑦－⑤和⑥－②－⑦，取出最小独立闭合环⑥－②－⑦，连通图转为图4(e);继续搜索闭合环，只有①－⑥－⑤，将其取出。至此，便得到所有的最小独立闭合环为⑧－④－⑤、③－⑦－⑧、⑥－②－⑦和①－⑥－⑤。

可以看出，本算法大体上由两个循环控制，内层循环负责找出当前树型结构中所有的独立环，外层循环则负责在这些独立环中找出最小独立环，并通过改变树型结构继续进行下一轮搜索，直至找出所有的最小独立闭合环。由于在内层循环搜索时，加入了边长因素的限制，故搜索到的闭合环均满足最小独立闭合环的三个条件。

图4 最小独立闭合环搜索示例Fig.4 Examples of searching with the least independent close loop

4 工程控制网实验与分析

为验证算法的正确性，以文献［2］的部分观测数据为基础进行最小独立闭合环搜索。由于基线的水平分量闭合差检验与垂直分量类似，故仅列出基线垂直分量闭合差检验结果。

图5 共有9 个GPS 控制点，20 条观测边，使用4台GPS 接收机分5 个时段监测，平均观测时段约1小时，每点均测两个时段。从图5 可以看出，该GPS观测网中既有三角形，也有多边形，以此观测网为例进行验证具有较好的代表性。

4.1 控制网信息结构

算例中，使用TGO 软件进行GPS 基线处理，解算出每条基线的长度及高差(表1)。显然描述该网形的信息应包括:基线条数、起点及终点点号、基线长度和高差，将该信息转换为对应的变量信息存储于计算机中(表2)。

4.2 最小独立闭合环搜索

通过自编程序对数据进行处理，在考虑边长情况下共搜索到12 个最小独立闭合环，经检核所有环质量均满足D级GPS 控制网要求(表3)。

图5 某工程GPS 观测网Fig.5 GPS network of a project

表1 已知基线信息Tab.1 Known baseline information

表3 最小独立闭合环搜索处理结果Tab.3 Results of searching least independent close loop

为验证算法的改进效果，通过修改自编程序，在不考虑边长情况下，再次对数据进行处理(表4)，显然8 号环和12 号环不同。

表4 结果比较Tab.4 Comparison of searching results

由表3、4 可见，表4 中的环长大于表3 中相应的环长。另外，一般来说，对于有sd 个结点(包括已知点和未知点)的水准网，若其水准支路个数为gd，则其多余观测数为gd－(sd－1)个，故其最小独立闭合环个数为gd－sd+1。对于此例中GPS 基线垂直分量闭合差检验，其最小独立闭合环个数应为20－9 +1，即12 个，这与我们的搜索结果一致，达到了算法的预期效果。

5 总结

根据改进的生成树和余树算法，将距离因素考虑在搜索闭合环的条件中，实现了最短闭合环路的自动比较提取，并满足搜索得到的闭合环是最短独立闭合环的所有条件。这种算法对于GPS 控制网、平面网和水准网的闭合环搜索及闭合差计算均适用，还可提高数据处理的速度和精度。

1 周小平，姚连壁.基于MATLAB 的控制网平差程序设计［M］.上海:同济大学出版社，2006.(Zhou Xiaoping and Yao Lianbi.Design of adjustment program for a control network based on MATLAB［M］.Shanghai:Tongji University press，2006)

2 李振，朱峰.利用信息矩阵算法搜索GPS 网的最短独立闭合环［J］.武汉大学学报(信息科学版)，2012，37(7):839－842.(Li Zhen and Zhu Feng.Searching least independent close loops in GPS network using Information matrix［J］.Geomatics and Information Science of Wuhan University，2012，37(7):839－842)

3 王玉磊，邱罡.从零开始学MATLAB［M］.北京:中国铁道出版社，2011.(Wang Yulei and Qiu Gang.Learning MATLAB since Zero［M］.Beijing:China Railway Press，2011)

4 游为，范东明，付淑娟.最短独立闭合环与附合路线的快速搜索方法［J］.测绘科学，2009，34(4):139－140.(You Wei，Fan Dongming and Fu Shujuan.An express method to search least independent close loops and connecting traverses［J］.Science of Surveying and Mapping，2009，34(4):139－140)

5 蒋鸿飞，刘伟东，王文胜.一种自动搜索水准环及计算闭合差的方法研究［J］.测绘科学，2012，37(4):202－203.(Jiang Hongfei，Liu Dongwei and Wang Wensheng.A method of automatically searching lever loop and calculating the misclsure［J］.Science of Surveying and Mapping，2012，37(4):202－203.)

6 赵一晗，伍吉仓.控制网闭合环搜索算法的探讨［J］.铁道勘察，2006，3:12－14.(Zhao Yihan and Wu Jicang.Discussion on the methods of searching closed loops in a control network［J］.Railway Investigation and Surveying，2006，3:12－14)

7 冯琰，张正禄，罗年学.最小独立闭合环与附合导线的自动生成算法［J］.武汉测绘科技大学学报，1998，9(33):255－259.(Feng Yan，Zhang Zhenglu and Luo Nianxue.An algorithms to generate least independent close loops and connecting traverses automatically［J］.Journal of Wuhan Technical University of Surveying and Mapping，1998，9(33):255－259)

8 叶宝，陈义.基于边集数组的最小独立闭合环搜索算法实现［J］.测绘通报，2010，12:37－39.(Ye Bao and Chen Yi.An algorithm to search least independent closed-loop based on array of edge set［J］.Bulletin of Surveying and Mapping，2010，12:37－39)

9 姚勤.由计算机自动生成导线网条件信息的通用算法［J］.测绘通报，1988，1:9－13.(Yao Qin.A general algorithm to generate automatically condition information for a wire network?by computer［J］.Bulletin of Surveying and Mapping，1988，1:9－13)

10 陈玉莹.控制网最小独立闭合环的搜索算法［J］.工程勘察，2010，5:65－69.(Chen Yuying.An algorithm to search arithmetically least independent closed loop for a control network［J］.Geotechnical Investigation and Surveying，2010，5:65－69)