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

王鹏磊 刘长星 张 健 魏春亚

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

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

1 引言

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

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

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

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

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

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

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

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

生成树和余树算法是计算机自动搜索闭合环方法中最稳定的一种。该算法需先将控制网信息通过一定的算法简化为一个生成树。……