基于改進的生成樹和余樹算法控制網最小獨立閉合環搜索算法研究*

王鵬磊 劉長星 張 健 魏春亞

1)西安科技大學測繪學院，西安 710054

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

1 引言

控制網中存在的多余觀測可用來檢查閉合環的閉合差是否超限［1］，但需要事先通過已知數據找出其中獨立的閉合環。目前，計算機自動搜索最小獨立閉合環的算法主要有鄰接矩陣變換方法、深度優先搜索算法、生成樹和余樹算法。然而，這三種方法在搜索閉合環時均未將邊長因素考慮在內，在某些情況下并不能使所有搜索到的閉合環均滿足最短獨立閉合環的要求，當搜索的初始條件不同時，搜索的結果也會不同，使結果具有不確定性［2］。其中，生成樹和余樹的算法簡單易懂，且計算結果穩定，本文基于該算法并進行了改進，使其在考慮邊長的因素下，實現最小獨立閉合環的自動比較提取。

2 最小獨立閉合環形成條件

無論是高程還是平面控制網，所選取的獨立的邊構成的閉合環均應滿足:

1)所有閉合環相互獨立，即任何一個閉合環都不能由其他閉合環的線性組合來代替;

2)閉合環中包含的邊數最少;

3)邊數相同的閉合環，取長度最短的。

滿足以上三個條件的閉合環叫做最小獨立閉合環。對于一個控制網，其最小獨立閉合環的構成情況并不是唯一的，只需找出其中一組即可。

3 改進的最小獨立閉合環搜索算法

生成樹和余樹算法是計算機自動搜索閉合環方法中最穩定的一種。該算法需先將控制網信息通過一定的算法簡化為一個生成樹。生成樹需滿足:1)包含閉合環網絡圖的所有結點;2)為連通圖，即圖中任意一個結點通過某一支路可以到達另外任意一個結點;3)不包含任何閉合環路。

當網絡圖較為復雜時，一個網絡圖會有很多不同的生成樹，當然也對應著不同的閉合環路信息。為了減少計算量，最快地得到最小獨立閉合環，采用深度優先搜索法生成一顆樹，使得構成基本環路的支路數目盡可能少，這樣的生成樹即為最優樹。如圖1(a)所示網形，生成最優樹的步驟為:

1)計算網中各個結點的度，找出其中度最大的結點，并假設該點為P;

2)以網中度最大的結點P 為起始點，并根據觀測數據訪問該點的鄰接點P1，P2，…，且記錄相應的鄰接邊;

3)分別從P1，P2，…出發，訪問它們的未曾被訪問過的鄰接點，并記錄相應的鄰接邊;

4)若此時尚有未被訪問過的結點，則繼續訪問下一級鄰接點，直至所有的結點都被訪問完，所記錄的所有鄰接邊組成的圖形即為其最優樹(圖1(b))。

最優樹樹型結構建立后，通過在生成樹上添加余枝得到獨立閉合環。然而，對于某些網型，僅通過生成最優樹的辦法是不能得到所有的最小獨立閉合環的。例如圖2 所示的圖形，無論從哪一點開始搜索或在搜索過程中改變搜索點來建立樹，都不能只通過添加余枝的辦法形成所有的最小閉合環。

圖1 最優樹生成示例Fig.1 Examples of the best tree generation

圖2 一網形結構及其兩種樹形Fig.2 A single network structure and its two kinds of trees

為了解決這個問題，筆者對生成樹和余樹算法進行了改進，在考慮邊長因素的情況下，利用MATLAB 編程實現了最小獨立環的提取。這種算法是將搜索過程分為兩大部分，即正向記錄和反向提取。現以將余枝(i，j)添加到樹上進而形成閉合環為例，進行說明:

1)正向記錄。設存放樹枝信息矩陣為A，A 中的樹枝包括建立生成樹時找到的樹枝和已經搜索到最小閉合環的余枝。用數組route(1:size(A，2))記錄搜索樹枝的信息，搜索前設為0。

從余枝(i，j)的一個端點i 開始搜索，將搜索到的樹枝信息用終點點號標記，即將該支路的route 值賦為終點點號。然后在找出的新點上繼續搜索，將在新點搜索到的新樹枝再用終點點號標記，繼續重復搜索，直至搜索到的新點編號為j。

2)反向提取。搜索到j，得到搜到j 的樹枝信息route 值，并得到樹枝的另一點，提取該點，其編號為樹枝信息route 值，由該點判斷與其相連的樹枝信息route 值，找出不等于該點編號的另一非零值，該非零值即為與該點相連樹枝的另一端點，提取該點，重復反推，直至找到i。反向提取過程中，提取的點為余枝(i，j)搜索到的閉合環所經過的點。

如圖2(a)，建立的生成樹結構如圖2(b)，其中一個余枝(1，6)的搜索程序流程見圖3。搜索前各樹枝信息值設為0，如圖3(a)，在搜索過程中，每遇到一個新點，對其支路的編號與該點名相同，此例中從點6 出發，依次對路徑數為1、2、3 的支路進行編號⑥、④、⑤，如圖3(b)，即完成正向記錄;反向提取時，從余枝的另一端點出發逆向尋找，在每個點所連接的支路中與該點點號不同的支路即是閉合環的支路，此例中便是從點1 出發，按條件依次可找到編號為⑤、④、⑥的支路，這些支路加上余枝本身即可構成閉合環。

圖3 正向記錄與反向提取示例Fig.3 Examples of forward record and reverse extraction

建立樹型結構后，余枝數即為獨立閉合環的個數，設為n 個，則閉合環搜索的具體算法步驟如下:

1)在生成樹和余樹結構中，從某一余枝(R1，R2)的一個端點R1出發，依次訪問路徑數為1，2，…的鄰接點，直至被訪問的鄰接點是余枝的另一端點R2為止，即得到了由這個余枝構成的獨立環。

2)分別以剩余的n－1 個余枝代替1)中的余枝(R1，R2)，以同樣的方法尋找其對應的獨立環。

3)將n 個獨立環進行比較，若邊數最少的獨立環只有一個，則選擇其作為搜索到的第一個最小獨立閉合環;若最少邊數的獨立環有個多個，再比較這些閉合環的線路長度，選擇線路最短的閉合環作為第一個最小獨立閉合環。

4)在第一個最小獨立閉合環確定之后，將其對應的余枝信息轉化為樹枝信息，得到一個新的樹型結構，在這個結構中，按同樣的過程又可得到n－1個獨立環，進而繼續在這n－1 個獨立環中進行比較，選取第二個最小獨立閉合環。

5)依此類推，得到n 個最小獨立閉合環。

以圖4(a)所示網形為例，說明搜索流程。首先對網形各個支路進行編號，其中支路①邊長為5，支路⑧邊長為1，其他各支路邊長均為3。建立如圖4(b)所示的生成樹后，余枝分別為①、③、⑥、⑧，然后搜索閉合環得①－②－⑦－⑤，③－④－⑤－⑦，⑥－②－⑦和⑧－④－⑤。邊數最少的獨立環有兩個，即⑥－②－⑦和⑧－④－⑤，兩者線路最短的為⑧－④－⑤，故將該環路取出進而得到新的連通圖，如圖4(c);繼續搜索閉合環，得①－②－⑦－⑤，③－⑦－⑧和⑥－②－⑦，取出其中邊數最少且線路長度最短的閉合環③－⑦－⑧，連通圖如圖4(d);繼續搜索閉合環得①－②－⑦－⑤和⑥－②－⑦，取出最小獨立閉合環⑥－②－⑦，連通圖轉為圖4(e);繼續搜索閉合環，只有①－⑥－⑤，將其取出。至此，便得到所有的最小獨立閉合環為⑧－④－⑤、③－⑦－⑧、⑥－②－⑦和①－⑥－⑤。

可以看出，本算法大體上由兩個循環控制，內層循環負責找出當前樹型結構中所有的獨立環，外層循環則負責在這些獨立環中找出最小獨立環，并通過改變樹型結構繼續進行下一輪搜索，直至找出所有的最小獨立閉合環。由于在內層循環搜索時，加入了邊長因素的限制，故搜索到的閉合環均滿足最小獨立閉合環的三個條件。

圖4 最小獨立閉合環搜索示例Fig.4 Examples of searching with the least independent close loop

4 工程控制網實驗與分析

為驗證算法的正確性，以文獻［2］的部分觀測數據為基礎進行最小獨立閉合環搜索。由于基線的水平分量閉合差檢驗與垂直分量類似，故僅列出基線垂直分量閉合差檢驗結果。

圖5 共有9 個GPS 控制點，20 條觀測邊，使用4臺GPS 接收機分5 個時段監測，平均觀測時段約1小時，每點均測兩個時段。從圖5 可以看出，該GPS觀測網中既有三角形，也有多邊形，以此觀測網為例進行驗證具有較好的代表性。

4.1 控制網信息結構

算例中，使用TGO 軟件進行GPS 基線處理，解算出每條基線的長度及高差(表1)。顯然描述該網形的信息應包括:基線條數、起點及終點點號、基線長度和高差，將該信息轉換為對應的變量信息存儲于計算機中(表2)。

4.2 最小獨立閉合環搜索

通過自編程序對數據進行處理，在考慮邊長情況下共搜索到12 個最小獨立閉合環，經檢核所有環質量均滿足D級GPS 控制網要求(表3)。

圖5 某工程GPS 觀測網Fig.5 GPS network of a project

表1 已知基線信息Tab.1 Known baseline information

表3 最小獨立閉合環搜索處理結果Tab.3 Results of searching least independent close loop

為驗證算法的改進效果，通過修改自編程序，在不考慮邊長情況下，再次對數據進行處理(表4)，顯然8 號環和12 號環不同。

表4 結果比較Tab.4 Comparison of searching results

由表3、4 可見，表4 中的環長大于表3 中相應的環長。另外，一般來說，對于有sd 個結點(包括已知點和未知點)的水準網，若其水準支路個數為gd，則其多余觀測數為gd－(sd－1)個，故其最小獨立閉合環個數為gd－sd+1。對于此例中GPS 基線垂直分量閉合差檢驗，其最小獨立閉合環個數應為20－9 +1，即12 個，這與我們的搜索結果一致，達到了算法的預期效果。

5 總結

根據改進的生成樹和余樹算法，將距離因素考慮在搜索閉合環的條件中，實現了最短閉合環路的自動比較提取，并滿足搜索得到的閉合環是最短獨立閉合環的所有條件。這種算法對于GPS 控制網、平面網和水準網的閉合環搜索及閉合差計算均適用，還可提高數據處理的速度和精度。

1 周小平，姚連壁.基于MATLAB 的控制網平差程序設計［M］.上海:同濟大學出版社，2006.(Zhou Xiaoping and Yao Lianbi.Design of adjustment program for a control network based on MATLAB［M］.Shanghai:Tongji University press，2006)

2 李振，朱峰.利用信息矩陣算法搜索GPS 網的最短獨立閉合環［J］.武漢大學學報(信息科學版)，2012，37(7):839－842.(Li Zhen and Zhu Feng.Searching least independent close loops in GPS network using Information matrix［J］.Geomatics and Information Science of Wuhan University，2012，37(7):839－842)

3 王玉磊，邱罡.從零開始學MATLAB［M］.北京:中國鐵道出版社，2011.(Wang Yulei and Qiu Gang.Learning MATLAB since Zero［M］.Beijing:China Railway Press，2011)

4 游為，范東明，付淑娟.最短獨立閉合環與附合路線的快速搜索方法［J］.測繪科學，2009，34(4):139－140.(You Wei，Fan Dongming and Fu Shujuan.An express method to search least independent close loops and connecting traverses［J］.Science of Surveying and Mapping，2009，34(4):139－140)

5 蔣鴻飛，劉偉東，王文勝.一種自動搜索水準環及計算閉合差的方法研究［J］.測繪科學，2012，37(4):202－203.(Jiang Hongfei，Liu Dongwei and Wang Wensheng.A method of automatically searching lever loop and calculating the misclsure［J］.Science of Surveying and Mapping，2012，37(4):202－203.)

6 趙一晗，伍吉倉.控制網閉合環搜索算法的探討［J］.鐵道勘察，2006，3:12－14.(Zhao Yihan and Wu Jicang.Discussion on the methods of searching closed loops in a control network［J］.Railway Investigation and Surveying，2006，3:12－14)

7 馮琰，張正祿，羅年學.最小獨立閉合環與附合導線的自動生成算法［J］.武漢測繪科技大學學報，1998，9(33):255－259.(Feng Yan，Zhang Zhenglu and Luo Nianxue.An algorithms to generate least independent close loops and connecting traverses automatically［J］.Journal of Wuhan Technical University of Surveying and Mapping，1998，9(33):255－259)

8 葉寶，陳義.基于邊集數組的最小獨立閉合環搜索算法實現［J］.測繪通報，2010，12:37－39.(Ye Bao and Chen Yi.An algorithm to search least independent closed-loop based on array of edge set［J］.Bulletin of Surveying and Mapping，2010，12:37－39)

9 姚勤.由計算機自動生成導線網條件信息的通用算法［J］.測繪通報，1988，1:9－13.(Yao Qin.A general algorithm to generate automatically condition information for a wire network?by computer［J］.Bulletin of Surveying and Mapping，1988，1:9－13)

10 陳玉瑩.控制網最小獨立閉合環的搜索算法［J］.工程勘察，2010，5:65－69.(Chen Yuying.An algorithm to search arithmetically least independent closed loop for a control network［J］.Geotechnical Investigation and Surveying，2010，5:65－69)