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

《基于改进的生成树和余树算法控制网最小独立闭合环搜索算法研究-论文.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第34卷第1期大地测量与地球动力学Vo1．34No．12014年2月JOURNALOFGE0DESYANDGEODYNAMICSFeb．．2014文章编号：1671-5942(2014)01-0113-05基于改进的生成树和余树算法控制网最小独立闭合环搜索算法研究王鹏磊刘长星’张健’魏春亚，1)西安科技大学测绘学院，西安710054、＼2)西安建筑科技大学信控学院，西安710054／摘要给出了最小独立闭合环形成条件，提出了基于改进的生成树和余树算法的最小独立闭合环搜索算法，通过MATLAB编程实现了该算法下最短闭合环的自动比较提取。关键词生成树；余树算法；最优树；正向记录；最小独立闭合环中

2、图分类号：P207文献标识码：ASTUDYoNLEASTINDEPENDENTCLoSELooPSoFCoNTRoLNETWoRKBASEDoNANIMPRoVEDSPANNINGTREEANDCOTREEALGoRITHMWangPenglei¨。LiuChangxing¨，ZhangJianandWeiChunyaf1)InstituteofSurveyingandMappingofXi’anUniversityofScienceandTechnology，Xi’an710054＼＼2)CollegeofInformationandControlofXi’anUniversityofA

3、rchitectureandTechnology，Xi’an710054／AbstractAnimprovedsearchingalgorithmofleastindependentclosedloopandits~rmingconditionsbasedonspanningtreeandcotreewerepresented．ThroughprogramdesigningandverificationwithMATLAB，thegoalofcomparingandextractinformationofleastindependentloopsautomaticallywasrealiz

4、ed．ResultscalculatedwithGPScontrolnetworkdataindicatethattheloopinformationmeetsallrequirementsofleastindependentcloseloops．Keywords：panningtree；cotreealgorithm；besttree；forwardrecord；leastindependentcloseloop立闭合环的要求，当搜索的初始条件不同时，搜索的1引言结果也会不同，使结果具有不确定性_2J。其中，生控制网中存在的多余观测可用来检查闭合环的成树和余树的算法简单易懂，且计算结果稳

5、定，本文闭合差是否超限¨，但需要事先通过已知数据找出基于该算法并进行了改进，使其在考虑边长的因素其中独立的闭合环。目前，计算机自动搜索最小独下，实现最小独立闭合环的自动比较提取。立闭合环的算法主要有邻接矩阵变换方法、深度优2最小独立闭合环形成条件先搜索算法、生成树和余树算法。然而，这三种方法在搜索闭合环时均未将边长因素考虑在内，在某些无论是高程还是平面控制网，所选取的独立的情况下并不能使所有搜索到的闭合环均满足最短独边构成的闭合环均应满足：收稿日期：2013-0710作者简介：王鹏磊，男，1989年生，硕士研究生，研究方向：大地测量学与测量工程．E—mail：254330952@qq．to

6、m114大地测量与地球动力学34卷1)所有闭合环相互独立，即任何一个闭合环都不能由其他闭合环的线性组合来代替；2)闭合环中包含的边数最少；／、＼3)边数相同的闭合环，取长度最短的。＼／5满足以上三个条件的闭合环叫做最小独立闭合(a)网形结构(b)树形一环。对于一个控制网，其最小独立闭合环的构成情况并不是唯一的，只需找出其中一组即可。3改进的最小独立闭合环搜索算法生成树和余树算法是计算机自动搜索闭合环方法中最稳定的一种。该算法需先将控制网信息通过(c)树形二一定的算法简化为一个生成树。生成树需满足：1)包含闭合环网络图的所有结点；2)为连通图，即图图2一网形结构及其两种树形Fig．2Asin

7、glenetworkstructureanditstwokindsoftrees中任意一个结点通过某一支路可以到达另外任意一个结点；3)不包含任何闭合环路。为了解决这个问题，笔者对生成树和余树算法当网络图较为复杂时，一个网络图会有很多不进行了改进，在考虑边长因素的情况下，利用MAT．同的生成树，当然也对应着不同的闭合环路信息。LAB编程实现了最小独立环的提取。这种算法是为了减少计算量，最快地得到最小独立闭合环，采用将搜索