王鵬磊 劉長星 張 健 魏春亞

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

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

1 引言

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

2 最小獨立閉合環(huán)形成條件

無論是高程還是平面控制網(wǎng)，所選取的獨立的邊構成的閉合環(huán)均應滿足:

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

2)閉合環(huán)中包含的邊數(shù)最少;

3)邊數(shù)相同的閉合環(huán)，取長度最短的。

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

3 改進的最小獨立閉合環(huán)搜索算法

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

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

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

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

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

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

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

圖1 最優(yōu)樹生成示例Fig.1 Examples of the best tree generation

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 工程控制網(wǎng)實驗與分析

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

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

4.1 控制網(wǎng)信息結構

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

4.2 最小獨立閉合環(huán)搜索

通過自編程序?qū)?shù)據(jù)進行處理，在考慮邊長情況下共搜索到12 個最小獨立閉合環(huán)，經(jīng)檢核所有環(huán)質(zhì)量均滿足D級GPS 控制網(wǎng)要求(表3)。

圖5 某工程GPS 觀測網(wǎng)Fig.5 GPS network of a project

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

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

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

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

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

5 總結

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

1 周小平，姚連壁.基于MATLAB 的控制網(wǎng)平差程序設計［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 網(wǎng)的最短獨立閉合環(huán)［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 游為，范東明，付淑娟.最短獨立閉合環(huán)與附合路線的快速搜索方法［J］.測繪科學，2009，34(4):139－140.(You Wei，F(xiàn)an 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 蔣鴻飛，劉偉東，王文勝.一種自動搜索水準環(huán)及計算閉合差的方法研究［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 趙一晗，伍吉倉.控制網(wǎng)閉合環(huán)搜索算法的探討［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 馮琰，張正祿，羅年學.最小獨立閉合環(huán)與附合導線的自動生成算法［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 葉寶，陳義.基于邊集數(shù)組的最小獨立閉合環(huán)搜索算法實現(xiàn)［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 姚勤.由計算機自動生成導線網(wǎng)條件信息的通用算法［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 陳玉瑩.控制網(wǎng)最小獨立閉合環(huán)的搜索算法［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)