基于信息矩陣的最短GPS控制網獨立閉合環生成算法

尹志永

(天津市測繪院，天津 300381)

基于信息矩陣的最短GPS控制網獨立閉合環生成算法

尹志永?

(天津市測繪院，天津 300381)

針對獨立閉合環自動生成經典算法中多解性和環長未定兩個問題，本文應用閉合環網形的信息矩陣，顧及邊長因素，提出基于矩陣運算的新算法，生成的閉合環滿足最短獨立閉合環的所有要求。通過兩種算法的GPS控制網閉合環搜索結果比較，驗證了本文算法結果的唯一性和環長最短性。

最短獨立閉合環；信息矩陣；閉合差

1 引 言

GPS定位技術具有高精度、全天候、測站間無需保持通視等優點，因而基本取代傳統方法而成為建立各級平面控制網的主要手段[1]。閉合環差作為GPS控制測量外業質量評定的依據之一，是探測粗差的常用檢測量。通常閉合環要求獨立且最小，環數和環長越小，可靠性越好，若其檢驗合格，就可以保證大環的質量合格[2，3]。

最短閉合環應滿足3個要求:①所有閉合環是獨立的；②閉合環包含的邊數最少；③對于邊數相同的閉合環，取長度最短的環。目前，獨立環的自動生成算法有3種:基于鄰接矩陣變換算法，基于生成樹和余樹變換算法，基于深度優先搜索算法[4]。其中基于生成樹和余樹的算法的搜索結果穩定，文獻[5]對其做了詳細的理論分析。然而，作者發現目前的閉合環生成算法都未能有效顧及到環的邊長信息，在某些情況下，搜索到的最小獨立閉合環只能滿足①、②兩個條件，當搜索的初始條件不同時，搜索的結果也會不同，使得結果具有不確定性。本文運用圖論中環的信息矩陣，加入邊長信息，解決了閉合環的唯一性和環長最短性問題。

2 生成樹余樹算法分析

文獻[6]給出了生成樹余樹算法的實現過程，該算法具有很強的穩定性，即能保證搜索到所有環數最小的獨立閉合環[5]。但其中也指出，對于大地四邊形，如圖1所示，當生成樹不同時，得到的閉合環不同，其中獨立的最小環有3個，而最小環有4個，因此會出現4種不同的結果。這是未考慮邊長因素引起的。在某些算法中，回代余樹后用Dijkstra方法來尋找最短路徑，但對余數回代的順序有要求，如圖2所示，搜索到的生成樹為S1－S2－S3－S5，余樹順序為S4－S6，余樹第一條S4回代，尋找最短路徑為S4－S3－S2－S1，然而最短路徑應為S4－S6－S5－S1，由于余樹S6在第一回代中還未出現，不能由Dijkstra算法得到最短路徑。當余樹順序為S6－S4時，可搜索到正確最短閉合環S3－S2－S5－S6和S5－S6－S4－S1。基于生成樹余樹的算法尚未解決最短閉合環的自動比較提取功能。

圖1 大地四邊形

圖2 示例

3 環形連通圖信息矩陣

連通圖由結點和邊組成，結點和邊完全描述了連通圖的拓撲結構，在計算機中的存儲結構為起點、終點、邊、邊長。

圖的存儲結構 表1

以結點為行，以邊為列，矩陣也能表述連通圖，如圖3所示。

圖3 連通圖

其關聯矩陣表示如下:

正1表示起點，負1表示終點。為了理解方便，圖3引入了方向，但對連通圖本身的拓撲結構不產生影響，因此方向可自定義。關聯矩陣與長度沒有聯系，長度信息存儲在另外一維數組。顯然矩陣G是秩虧的，刪去某一行，即刪去某個基準點，如o點，成為滿秩的基本關聯矩陣B，如下:

另外，圖3還關聯著一個基本回路矩陣，當連通圖的樹確定后，每條余樹邊所對應的回路稱為基本回路，該回路方向與余樹方向一致，由全部基本回路構成的矩陣稱為基本回路矩陣Cf[7]，假定圖3的樹為4－5－6，余樹1－2－3，則Cf如下:

該矩陣表明了圖3有3個獨立環，分別為4－5－1、5－6－2、4－6－3。將矩陣B的列號按照Cf的列號重新排列，得到Bf，由圖論知識得按余樹對矩陣分塊得到:E為單位陣，最后可得，那么:

因此可根據基本關聯矩陣來求出基本回路矩陣，而基本回路矩陣的每一行代表一個獨立環，對于基本關聯矩陣要求余樹填充于矩陣末列。基本關聯矩陣和基本回路矩陣組成了閉合環的信息矩陣。

4 最短獨立閉合環生成算法

該算法分為3個步驟:①廣度優先搜索得到生成樹集合和余樹集合，形成基本關聯矩陣Bf；②由式(4)算得Cf，得到所有獨立環，通過環間的余樹替換，得到所有邊數最小獨立環；③加入邊長信息，比較共用環邊且環數相同的環，以短邊替換長邊。

4.1 形成關聯矩陣

連通圖的每條邊按起點、終點、邊的順序存儲，圖結構按邊依次存儲，稱為圖表。一個連通圖的每個結點有不同的度，按廣度優先搜索樹，以度數最大的結點作為搜索起點則最優。因此先掃描圖表，得到度數最大的結點，然后開始廣度優先搜索得到生成樹，該算法不在這里贅述。

得到的生成樹與原來的圖做差就可以得到余樹，初始化基本關聯矩陣Bf為零，其行數為結點數減一，列數為邊數，從末列開始填充，先將余樹依次填入，接著填入生成樹，并記錄每列對應的邊號。

4.2 生成邊數最小獨立環

基于環間的替換等價于矩陣行相加或相減的原理，來設計邊數最小獨立環生成的算法。①將基本回路矩陣的行重新排列，按邊數大到小依次遞減；②置第1行為當前需要替換的行，計算絕對值之和，依次與下面所有行求和、做差，再做絕對值相加，若結果小于初始絕對值之和，則替換，否則繼續與下一行比較；③當第1行處理完畢，繼續下一行的處理，直到所有行處理完畢，則生成所有環數最小的獨立環。

4.3 生成環長最短獨立環

前面兩步生成的邊數最小獨立環與基于生成樹余樹算法得到的結果一致，在環數最小意義上，搜索已經成功。對于邊數不同的環，已經不需要再做處理，邊數相同的環，顯然由于沒有任何約束條件，它們是等價的，導致環的結果多解性。不唯一性給GPS環的質量檢查帶來不方便，不利于成果的通用性。在環數相同的環間，加入環長最小這一條件，就能得到唯一解，如圖1的大地四邊形，將得到環長較小的3個環。

算法如下:每次矩陣運算前取絕對值，①對邊數相同的環做差，如果邊數增大，轉③，相等轉②，邊數減小不可能發生；②計算環長，減小則替換，轉④；③尋找與初始環同邊數的行做差，如果邊數恢復且環長減小則替換，否則轉④；④循環操作。直到所有環處理完成后，得到所有最短獨立環，且結果唯一。

5 算例分析

5.1 GPS網介紹

測區位于武漢市某工程區，布設了D級GPS控制網，共10個GPS點，平均邊長 450 m，使用4臺GPS接收機分5個時段測，平均時段為1 h。網形如圖4所示，每個點均測兩個時段。GPS基線處理使用TGO軟件，解算出每條基線的長度以及高差，網形信息如表2所示。由于基線的水平分量閉合差檢驗類似，不再列出。作者用C＋＋實現了本文提出的算法。

GPS網形信息 表2

圖4 D級GPS網

5.2 結果分析

該D級GPS控制網共有16個最短獨立閉合環，最終成果如表3所示，以GPS規范[8]中的閉合差公式為限差，其中所有環質量均檢驗合格。

基于樹和余樹的算法生成閉合環，其中2、7、9、10號環不同。如表4所示。

閉合環檢驗結果 表3

結果比較 表4

表4中的環長大于表3中相應的環，在圖4中表現為大地四邊形的獨立環多解性情況，而表3的最小獨立環具有唯一性，且滿足最短獨立閉合環的所有條件，達到了本文算法預期的效果。

6 結 語

本文通過引入環的信息矩陣，將獨立閉合環的生成轉換成矩陣運算，思路簡單，算法實現容易，能夠生成最短獨立閉合環，滿足了GPS網閉合環質量的自動檢核要求。本文提出的算法同樣適用于其他網結構圖形。

[1] 李征航，黃勁松.GPS測量與數據處理[M].武漢，武漢大學出版社，2005

[2] Leick Alfred，Emmons Michael B.Quality Control with Reliability for Large GPS Netw－ork[J].Journal of Surveying Engineering，1994，120(1)，35～41

[3] Eliseo Clementini，Paolino Di Felice.Baseline quality check in GPS Postprocessing and network analysis[C].ACSMASPRS Fall convention，October 28，1991－November 1，1991

[4] Chong A.K.A comparison of methods for representing Topological relationships[J].Info－rmation Sciences，1995，5(3): 49～178

[5] 鄒進貴，馮晨.控制網最小獨立閉合環搜索算法研究[J].地理空間信息，2008(06)

[6] 馮琰，張正祿，羅年學.最小獨立閉合環與附合導線的自動生成算法[J].武漢測繪科技大學學報，1998，23

[7] 戴一奇，胡冠章，陳衛.圖論與代數結構[M].北京，清華大學出版社，1995:38～56

[8] GB/T 18314－2009.全球定位系統(GPS)測量規范[S].

Information Matrix Algorithms to Produce Least Independent Close Loops In GPS Control Network

Yin Zhiyong
(Tianjing Institute of Surveying and Mapping，Tianjin 300381，China)

To address the problems of multiple solutions and indefinite ring length in the classical independent closed loop algorithm，using the closed ring－shaped information matrix and taking into account the side element，this paper introduces a new algorithm based on matrix operations.The resulting closed loop meets all the requirements of the least independent closed loops.Through comparing the results of two algorithms in GPS network closed loop researching，the uniqueness of the result and the shortest length of ring are verified.

least independent close loop；information matrix；closure error

2011—05—05

尹志永(1974—)，男，高級工程師，主要從事城市測量技術工作。

1672－8262(2011)05－94－04

P228

A