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

An improved minimum independent closed loop search algorithm

针对在实际应用中,尤其是面对复杂大型连通图的拓扑关系梳理运算中,现行的最小独立闭合环搜索算法虽然成熟稳定,但在现有的算法框架内难以实现运算效率的数量级提升的问题。该文结合具体问题,即对华北地区路网进行最小闭合环搜索以实现质量检查与控制,以及在其他数据处理应用的实践中发现现行的最小独立闭合环搜索算法无法满足特定运算周期的需求,且容易产生连续计算带来的内存溢出和运算宕机问题。基于此,在树枝-余枝算法基础上进行算法优化,提高算法的鲁棒性和运算效率,以提供一种复杂大型的拓扑学问题最小独立闭合环的检索解决方法。

Aiming at the problem that in practical applications,especially in the topological relation carding operations of super-large and super-complex connected graphs,the existing minimum independent closed-loop algorithm is mature and stable,but it is difficult to achieve an order of magnitude improvement of operation efficiency within the existing algorithm framework.This paper combined the specific problems,that was,the minimum closed-loop searched for national road network to achieve quality inspection and control and other data processing applications in practice found that the existing minimum independent closed-loop search algorithm could not meet the needs of specific operation cycles,and was prone to lead to memory overflow and computational downtime caused by continuous computing.Based on this,four algorithms were optimized based on branch and branch algorithm.It improved the robustness and efficiency of the algorithm.It provided a retrieval solution for minimal and independent closed loop of super complex topology problems.