一种高效的最小独立闭合环自动搜索算法

马洪磊，刘成龙，余乐义，孟凡超

(西南交通大学 地球科学与环境工程学院，四川 成都 610031)

一种高效的最小独立闭合环自动搜索算法

马洪磊，刘成龙，余乐义，孟凡超

(西南交通大学 地球科学与环境工程学院，四川 成都 610031)

依据图论理论，在基于生成树、余树变换的闭合环搜索算法和基于深度优先的闭合环搜索算法的基础上，提出一种高效且稳定性好的控制网最小独立闭合环自动搜索算法。

生成树；余树；深度优先；闭合环搜索

闭合环搜索及闭合差检查是控制网外业测量数据处理过程中的重要环节，闭合环闭合差的大小是评判控制网外业观测数据好坏的重要指标，此外，闭合差还可用于判断外业测量数据中是否含有系统误差或粗差。传统的人工闭合环搜索方法虽然灵活，但当控制网极其复杂时，人工搜索法效率低，容易出错，因此，寻找一种稳健、高效的闭合环自动搜索算法十分必要。目前，闭合环的自动搜索算法主要有3种：①基于邻接矩阵变换的闭合环搜索法；②基于生成树、余树变换的闭合环搜索法；③基于深度优先搜索的闭合环搜索法。文献[1]中对上述3种闭合环自动搜索算法进行了探讨并得出以下结论：基于邻接矩阵变换的闭合环搜索算法虽然简单，但其时间和空间复杂性较高；基于生成树、余树变换闭合环搜索算法和基于深度优先的闭合环搜索算法的搜索效率相对较高[1]。文献[2]中对基于生成树、余树变换的闭合环搜索算法和基于深度优先的闭合环搜索算法进行了理论分析并得出以下结论：基于生成树、余树变换的闭合环搜索算法能够稳定地搜索出全部独立闭合环，通过改变余枝的添加顺序，可稳定地搜索出一组最小独立闭合环。本文还通过一个实例证明了基于深度优先的闭合环搜索算法具有不稳定的缺点，具体是指：虽然该算法可以保证搜索出的闭合环之间相互独立，但却不一定能够搜索出全部独立闭合环[2]。虽然基于生成树、余树变换的闭合环搜索算法是一种稳定、可靠的闭合环自动搜索算法，但对大型控制网的最小独立闭合环搜索效率不高[3]。针对以上各闭合环搜索算法中存在的不足，本文依据图论中的相关理论并结合现有的基于生成树、余树变换的闭合环搜索算法和基于深度优先的闭合环搜索算法，提出了一种新的闭合环自动搜索算法，为论述方便，本文将该算法简称为新算法。

1 相关概念

生成树：在一个连通图G(V,E)中，其中V是图中顶点的集合，E是图中边的集合。取它的全部顶点V和一部分边E′构成一个子图g(V,E′)，若子图g(V,E′)中的边将图G(V,E)中的所有顶点连通又不形成回路，则称子图g(V,E′)是连通图G(V,E)的一棵生成树[4]。

广度优先生成树：由广度优先搜索得到的生成树为广度优先生成树[4]。

余树：得到连通图G(V,E)的生成树g(V,E′)后，连通图G(V,E)中不在生成树上的边称为图G(V,E)的余枝，余枝的集合称为图G(V,E)的余树[5]。

深度优先搜索算法：是指沿着一条路径从开始顶点到达最后的顶点，然后原路返回，并且沿下一条路径达到最后的顶点，如此继续直到走过所有的顶点[6]。

广度优先搜索算法：又称宽度优先搜索或横向优先搜索，是指从根节点开始，沿着树的宽度遍历树的节点[6]。

冗余搜索:也称多余搜索即不必要的搜索。现有闭合环搜索算法中普遍存在大量的冗余搜索，严重影响了闭合环的搜索效率。

2 新算法原理与步骤

新算法结合了广度优先和深度优先搜索原理，综合了基于生成树、余树变换的闭合环搜索算法和基于深度优先的闭合环搜索算法的优点。其搜索过程可分为两个阶段：①获得一棵广度优先生成树所对应的余树；②对余树中的余枝进行闭合环搜索。阶段1所得余树属于一组独立闭合环，阶段2通过控制余枝的搜索过程，确保得到一组最小独立闭合环。

利用新算法进行最小独立闭合环搜索的具体步骤如下：

1)构建一维数组V和邻接矩阵M分别用来存储图中所有顶点及点间关系(边)的数据。考虑到邻接矩阵对称的特点，可采用下三角方式存储。

2)利用广度优先搜索算法获得一棵广度优先生成树所对应的余树。

3)设置当前搜索深度MD=2。

4)断开余枝R，利用深度优先搜索原理对余枝R两顶点进行最短路径搜索(为便于论述，下文称为对余枝进行闭合环搜索)，若搜索出的闭合环中不包含其他余枝，则记录该闭合环并从余树中删除余枝R(即R不再为余枝)，重复步骤3)和4)；若搜索出的闭合环中包含其他余枝，则断开其他余枝，继续在当前搜索深度MD下对该余枝进行闭合环搜索，直到搜索到的闭合环中不包含其他余枝或闭合环搜索失败为止；若搜索到不包含其他余枝的闭合环，则恢复之前断开的余枝并记录该闭合环，从余树中删除余枝R并重复步骤3)和4)；若搜索失败，则恢复之前断开的余枝并对下一条余枝重复步骤4)。

5)若余树为空，则闭合环搜索完毕，否则执行步骤6)。

6)设置当前搜索深度MD=MD+1，重复步骤4)和5)。

3 新算法分析

上述新算法步骤简单，只对余枝进行闭合环搜索，每搜索到一个闭合环就删除一条余枝，余树为空时闭合环搜索完毕，大大减少了冗余搜索且无需设置最大搜索深度。下面就新算法是否能稳定地搜索出一组最小独立闭合环进行分析、论证。

3.1 稳定性和独立性分析

稳定性是描述算法理论是否严密的方法。如果算法在任何情况下都能得到正确结果，则该算法是稳定的，否则该算法不稳定。

独立性是指对于一组闭合环A，若A中任意闭合环中都至少有一条边不存在于其他任何闭合环中，则认为该组闭合环是一组独立闭合环。

由于新算法与基于生成树、余树变换的闭合环搜索算法都需要获得余树，但前者是在余树范围内，通过对邻接矩阵进行深度优先搜索获得闭合环，后者则是通过余枝回代至生成树中获得闭合环。基于生成树、余树的闭合环搜索算法余枝逐条回代保证了闭合环的独立性，新方法要求每次搜索得到的闭合环中只含有一条余枝，也有效保证了闭合环的独立性。又因为余枝个数等于独立闭合环个数，因此，两种算法均可以稳定获得全部独立闭合环。

3.2 最小性分析

图1为某水准网示意图，图中水准网的树形表示如图2所示。图2中实线集合表示广度优先生成树，虚线集合表示余树，二者的组合为图1所示水准网的另一种表示形式。对图2分析不难发现，当每个闭合环的搜索都从搜索深度MD=2时开始，且满足只含一条余枝的闭合环为搜索结果时，便可保证所得闭合环是一组最小独立闭合环。为验证以上分析的正确性，利用新算法对图1所示水准网进行闭合环搜索，过程如下：

图1 某水准网示意图

图2 图1所示水准网的树形表示

根据广度优先搜索原理获得该水准网图的一棵广度优先生成树及相应余树。依据新算法实施步骤可知，前两个搜到的闭合环为I-H-BM2和E-F-G或E-F-G和I-H-BM2，第3个搜索到的闭合环为I-H-D-C或D-E-G-H，若第3个搜索到的闭合环为I-H-D-C，则第4个搜索到的闭合环为B-D-C,第5个搜索到的闭合环为A-B-D，第6个搜索到的闭合环为D-E-G-H，第7个搜索到的闭合环为A-D-E-F-BM1，至此闭合环搜索完毕，所得闭合环为一组最小独立闭合环。若第3个搜索到的闭合环为D-E-G-H，则第4个搜索到的闭合环为I-H-D-C，第5个搜索到的闭合环为B-C-D，第6个搜索到的闭合环为A-B-D，第7个搜索到的闭合环为A-D-E-F-BM1，至此闭合环搜索完毕，所得闭合环为一组最小独立闭合环。通过该实例，验证了利用新算法进行最小独立闭合环搜索的正确性。

对图2进行分析发现，新算法在编程实现时还可进一步优化，优化方法如下：

在利用广度优先搜索算法生成一棵广度优先生成树时，记录每个顶点所在的层数(如图2中BM2为0层，H和I为1层等)。得到广度优先生成树后，依据余枝中两顶点所在层数之和的大小对余枝集合进行升序排列。此时，通过调整新算法步骤，可进一步减少冗余搜索。假设余树中共有3条余枝且升序排序后顺序为R1，R2，R3，则调整后步骤如下：

设置搜索深度MD=2，对R1进行闭合环搜索，若成功，则重置MD=2，并对下一条余枝R2进行搜索；若失败，则设MD=MD+1，继续对R1进行闭合环搜索。重复以上过程，当R3搜索成功时(即最后一条余枝搜索成功时)，闭合环搜索完毕。

4 对比分析

根据本文提出的新算法，笔者用C#语言在.Net平台上编程实现了水准网最小独立闭合环的自动搜索及闭合差的计算与检核。为检验新算法是否具有较高的搜索效率，笔者还根据基于深度优先的闭合环搜索算法，同样编程实现了水准网最小独立闭合环的自动搜索。为节省存储空间，笔者所编程序中的邻接矩阵均采用下三角方式存储，从而导致搜索时间延长，但这并不影响对新算法搜索效率的对比。自编程序与武汉大学商用平差计算软件COSA及西南交通大学商用轨道控制网数据处理软件CPⅢ DMS进行对比的情况，统计在表1～3中。

表1 CPⅢ高程网的最小独立闭合环搜索结果对比

表2 某水准网的最小独立闭合环搜索结果对比

表3 某水准网的搜索效率对比

以上各表中的统计数据均是在同一台计算机上得到，表3中基于深度优先的闭合环搜索算法是在最大搜索深度为50的情况下得到的。

由表1、表2中闭合环个数及最大闭合环点数的对比可知，本文提出的新算法可准确地搜索出任意水准网的一组最小独立闭合环，验证了新算法的正确性及可行性。

文献[2]中通过3种不同算法搜索时间的对比，发现基于深度优先的闭合环搜索算法是一种较快的闭合环搜索算法。由表3中搜索时间的对比可知，本文所提出的新算法较基于深度优先的闭合环搜索算法搜索时间更短、效率更高。

5 结 论

本文提出的新算法综合了基于深度优先闭合环搜索算法和基于生成树、余树变换的闭合环搜索算法的优点，可理解为是对二者的融合和改进。通过以上理论分析及实例验证得出以下几点结论：

1)本文提出的闭合环自动搜索算法极大地减少了冗余搜索，显著提高了闭合环的搜索效率，是一种适用于大型控制网的最小独立闭合环自动搜索的新算法。

2)本文提出闭合环自动搜索算法虽然也利用了深度优先搜索原理，但改善了基于深度优先的闭合环搜索算法不稳定的缺点且无需设置最大搜索深度，是一种稳定、高效且高度自动化的最小独立闭合环搜索算法。

3)本文提出的最小独立闭合环自动搜索算法不仅能应用于高程网，原则上也适用于任何可化简为无向图的控制网的最小独立闭合环的自动搜索，如GPS基线网及化简后的边角网等。

[1]赵一晗，伍吉仓.控制网闭合环搜索算法的探讨[J].铁道勘察，2006(3)：12-14.

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

[3]游为，范东明，张云，等.水准网闭合差自动解算的新方法[J].测绘工程，2007，16(5)：17-19.

[4]严蔚敏，吴伟民.数据结构[M]. C语言版.北京：清华大学出版社，2007：156-191.

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

[6]杨洪.图论常用算法选编 [M].北京：铁道出版社，1988：110-121.

[责任编辑：刘文霞]

An efficient algorithm of automatic searching for minimum independent closed-loop

MA Hong-lei，LIU Cheng-long，YU Le-yi，MENG Fan-chao

(Faculty of Geosciences and Environmental Engineering, Southwest Jiaotong University， Chengdu 610031, China)

It provides an efficient and stable automatically search algorithm of smallest independent closed loop control network, according to the closed loop search algorithm of spanning tree and spare tree transform, and depth-first closed loop search algorithm on the basis of graph theory.

spanning tree; spare tree; depth-first; closed loop search

2013-08-14

中央高校基本科研业务专项资金资助项目(SWJTU12ZT07)

马洪磊(1989-)，男，硕士研究生.

P221

：A

：1006-7949(2014)08-0070-03