基于深度优先搜索的最小独立闭合环电算优化方法

闭合环的搜索和闭合差计算作为粗差探测重要方式之一，在工程控制网日渐庞大和复杂的情况下，其计算效率问题得以重视。在深度优先算法的基础上，结合计算机编程特性，将深度优先递归算法改变为循环算法，避免函数调用的内存开销，并对数据结构进行了相关优化，显著提高了对大型控制网进行闭合环搜索的效率。

闭合环搜索； 深度优先； 程序优化； 递归算法

P217 A

［定稿日期］2022-05-12

［作者简介］郑健（1984—），男，硕士，高级工程师，主要从事高速铁路工程测量和城市轨道交通监测测量工作。

对于具有多余观测值的测量数据而言，为了获得准确的测量结果，需要对测量数据进行严密平差计算，而在严密平差前需要检核观测值的质量，以避免由仪器、人员、环境等因素产生的粗差导致平差结果产生显著性偏差。在工程控制网中，无论是水平角度观测值还是水准高差观测值，闭合差检查是对观测值进行粗差探测最简便和直观的方法。而今，由于控制网的复杂程度的逐渐增大，观测值的数量更是大幅增加，尤其是铁路轨道控制网（简称CPIII网），其动辄20～30 km长度的网型对工程控制网平差软件来讲，是不小的挑战。因此，如何有效提升闭合环的搜索速率，从而快速剔除观测值粗差，是本文重点讨论的问题。

赵一晗等［1］对临接矩阵变换、生成树和余树、深度优先这3种常见的闭合环搜索算法进行了详细介绍，并得出结论：对于大型控制网，深度优先算法具有更高的效率。由于使用场景的不同，王鹏磊等［2-4］对生成树和余树进行优化，使其在算法的稳定性和效率上取得了一定的进步。游为等［5-6］将临接矩阵变换方法进一步改进，利用条件方程构造信息矩阵来进行闭合环搜索以及闭合差的计算。但在超大型控制网的闭合环搜索效率上，上述2种方法仍与深度优先搜索法有一定差距。因此本文将基于深度优先方法在理论和程序设计上对闭合环线路搜索进行优化。

1 深度优先算法进行闭合环搜索的常规流程及优化方法

1.1 深度优先算法的常规应用

深度优先算法是指在一个多节点的结构树中，指定某顶点为起点，依次添加与其链接的下一层节点，直至节点深度不能增加为止。如图1所示，以A点为起点的深度优先搜索顺序为;A—B—D—C—E—G—F。

将深度优先算法用于闭合环搜索的具体实施过程：

首先，创建存储观测边起终点的二维列表以及空列表用于存儲搜索结果。其次，创建整网的邻接表，遍历网中各点及其子节点存放于二维列表。从第一条观测边开始，搜索由该边组成的最小闭合环。从该边的终点出发，搜索至线路起点，并建立列表存储搜索过程的节点。在这一过程中，应设置并依次增加搜索深度，当所在的节点不是目标点，则向更深处（即子节点）进行搜索，其实际搜索深度加1，若自身已没有子节点或者搜索深度超过限定深度时，退回至其父节点，实际搜索深度减1。这一过程通常采用递归的形式进行［7-8］。当搜索到闭合环时，将该闭合环的所有边进行标记，表明该边已进行过搜索。然后从观测边中找寻未访问过的边，继续进行闭合环搜索过程。直到搜索的闭合环数量达到独立闭合环数，或者网中所有的边均被标记访问。

对于一个控制网，其独立闭合环个数为n=line-piont+1，其中Line为观测边数，Point为控制网中的点数，可将n作为闭合环搜索结束的判定条件。该过程利用最小独立闭合环的某一边开始对环进行搜索，并通过标记已经搜索过的边避免重复搜索。

在搜索过程中，当搜索深度加深时，闭合环搜索的时间将占整个搜索过程中的主要部分。所以有必要考虑其效率。众所周知，递归算法虽然编程逻辑清晰，但是由于需要重复调用递归函数以及堆栈处理，将占用大量内存以分配变量、参数、返回值等。虽然可以通过使用用户栈减少公共数据的初始化，且部分语言的编译器在优化后，对于多次调用的函数处理会有比较好的效率优化，但递归函数的时间复杂度和空间复杂度随着递归深度的增加几乎不可控，仅通过数据结构等优化也并未改变递归的实质。

1.2 深度优先算法优化设计

基于深度优先递归算法在闭合环搜索中存在的不足，笔者对上述闭合环搜索过程进行了优化设计。

1.2.1 提高匹配效率

将控制网中以字符串格式存储的点名匹配为整型，提高匹配效率。建立控制网点名与整数的匹配表，将字符串转换为整型，可以减少搜索和中间过程的匹配时间，以及临时文件存储空间。待整网的闭合环搜索结束后，根据匹配表将搜索结果转换为真实点名。

1.2.2 采用Hashtable（如字典）保存邻接表

由于在深度优先搜索闭合环的过程中，每增加或减少一次搜索深度，都将访问一次邻接表，且需要查找父节点及其相邻的子节点，若采用列表遍历的方式，查找节点的时间复杂度均值为O（n/2），而字典查询的时间复杂度为O（1），因此采用字典将相对减少邻接表的查询时间。

1.2.3 递归迭代算法转换为循环算法

深度优先递归算法转换为循环算法的关键是每查找一个闭合环，需建立一个存贮点号的列表标记该次搜索时网中节点的访问情况。循环算法的具体步骤：

（1）声明必要的过程变量：保存搜索节点的数组temp_road且默认等于需要进行搜索的观测边起点，记录当前搜索深度的变量current_deep=0，标记网中各点在当前搜索中是否已经访问的列表visit，列表长度为网点数，均默认为0。

（2）开始搜索：令temp_road中最后一个点为新的父节点为，从邻接表中找出父节点对应的子节点，并开始遍历子节点，若子节点在visit中的值不为0，表示已访问，则跳过。当不为0时进入下一步并令遍历过的子节点在visit中的值为1，current_deep加1。

（3）判断子节点是否为终点：若为终点，且current_deep等于设置的闭合环搜索深度，则添加子节点到temp_road中，退出循环算法，temp_road中保存的节点即为闭合环路径，将闭合路径中的各边在网的观测边中设置为已访问；若不为终点，且current_deep的值小于设置的搜索深度，将子节点加入temp_road，跳出当前循环遍历，进入步骤2。若在设置的搜索深度下，遍历完当前父节点的最后一个子节点，任未找到终点，则取出temp_road中的最后一个点，令current_deep减1，再次进入步骤2，直至搜索到路径或者temp_road为空。

（4）设定闭合环搜索截至条件。当所有观测边均被标记访问或者搜索到的闭合环数量达到独立闭合环数的要求时停止搜索，避免冗余搜索过程。

（5）深度优先算法缺陷优化。邹进贵等［9］严密论证了对于部分特殊网型采用深度优先搜索时，独立环搜索不完全的问题，秦昆等［10］提出了一种便于实施改进办法：由于闭合环搜索不全的特殊情况只在个别独立环被其他闭合环包围时才会发生，由于被包围的闭合环其所有观测边均被访问过，因此无法进行搜索，但该环的所有边的访问次数均为1。所以，可在搜索时标记各边被访问的次数，当所有边都访问超过1次但独立环个数不足时，从访问次数最小的边开始，再次进行闭合环搜索，当该次搜索结果不在搜索结果中时，加入搜索结果。

将深度优先闭合环搜索优化算法各步骤绘制为流程如图2所示。

2 实验验证

根据本文所述对深度优先闭合环搜索方法的优化设计，笔者基于Python编程语言，进行水准网闭合环搜索的程序设计与编制，实现了水准网最小独立闭合环的搜索以及闭合差计算与精度验证功能。为了验证优化后的算法在大型控制网中的计算效率是否有显著提高，同样对深度优先递归算法进行了程序编译。笔者在基于i5双核CPU、主频1.6 GHz、内存为8 GB的笔记本电脑上进行对比计算实验。

首先，采用科傻COSA示例水准网高差观测文件［11］，分别对采用深度优先算法优化前、优化后的自编软件进行计算效率测试，结果见表1。

从表1看出，优化后的深度优先循环方法计算效率明显高于优化前。由于Python为解释型语言，其循环和编译效率远低于C#、Java等语言，因此在进行算法优化时，可以明显地判断算法的优化对于整个搜索过程效率的提升。

其次，为了验证本文所述的优化方法在大型控制网中闭合环搜索中的适用性，使用一段约60 km的CPIII高程网实测数据进行试算，并分别与铁路工程测量中应用广泛的多款平差软件进行对比。该段CPIII控制網包括3 240个独立高差观测值、2 140个高程点、1 069个独立闭合环。各类软件与采用本文优化方法所编软件的最终对比结果见表2。

通过与HRMAS、铁四院平差软件、中铁咨询平差软件对比的测试数据结果，可得：自编软件的搜索结果正确，各类指标与商业软件完全一致；其次，在大型控制网闭合环搜索中，基于深度优先优化算法的自编软件计算效率较各类铁路工程测量软件有明显的优势，且自编软件仅对算法和数据结构进行了上文所述的优化，并未进行任何基于计算机硬件的提速操作。

3 结论

（1）针对目前大型控制网闭合环搜索效率较低的问题，本文对深度优先算法的编程实施过程进行了优化，将深度优先算法中闭合环搜索中常用的递归算法改为循环算法，并对搜索过程中涉及数据的数据结构及其存储方式进行了优化和说明，并给出了适用于电算的深度优先优化算法详细流程，且优化算法简单、适用于各类编程语言。

（2）通过对优化后的算法进行编程，并由实测数据计算对比表明优化算法可大大降低时间、复杂度，提高闭合环搜索效率。

（3）通过自编软件与铁路控制网平差商用软件试算对比表明，在大型控制网闭合环搜索中，本文所述对深度优先搜索方法的优化设计，可大幅提升运算效率，减少大型控制网的内业数据处理耗时。

参考文献

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

［2］ 王鹏磊，刘长星，张健，等.基于改进的生成树和余树算法控制网最小独立闭合环搜索算法研究［J］.大地测量与地球动力学，2014，34（1）：113-117.

［3］ 马洪磊，刘成龙，余乐义，等.一种高效的最小独立闭合环自动搜索算法［J］.测绘工程，2014，23（8）：70-72+80.

［4］ 郭际明，王磊，罗年学，等.一种改进的测量控制网最小独立环搜索算法［J］.武汉大学学报（信息科学版），2011，36（5）：593-595.

［5］ 游为，范东明，付淑娟.最短独立闭合环与附合路线的快速搜索方法［J］.测绘科学，2009，34（4）：139-140+100.

［6］ 游为，范东明，张云，等.水准网闭合差自动解算的新方法［J］.测绘工程，2007（5）：17-19.

［7］ 周凌焱，刘成龙，张强，等.基于深度和广度优先算法相结合的闭合环自动搜索方法研究［J］.测绘工程，2014，23（5）：24-28+32.

［8］ 蒋宏飞，刘伟东，王文胜.一种自动搜索水准环及计算闭合差的方法研究［J］.测绘科学，2012，37（4）：202-203+212.

［9］ 邹进贵，冯晨.控制网最小独立闭合环搜索算法研究［J］.地理空间信息，2008，6（6）：97-99.

［10］ 秦昆，朱文武，高艳龙，等.最小独立闭合环深度优先算法的一点改进［J］.测绘科学技术学报，2015，32（6）：551-554.

［11］ 李建平，明祖涛，张届，等.CPⅢ高程网最小独立闭合环的一种搜索算法［J］.地理空间信息，2012，10（6）：150-153+1+16.