尹志永

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

基于信息矩陣的最短GPS控制網(wǎng)獨(dú)立閉合環(huán)生成算法

尹志永?

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

針對獨(dú)立閉合環(huán)自動(dòng)生成經(jīng)典算法中多解性和環(huán)長未定兩個(gè)問題，本文應(yīng)用閉合環(huán)網(wǎng)形的信息矩陣，顧及邊長因素，提出基于矩陣運(yùn)算的新算法，生成的閉合環(huán)滿足最短獨(dú)立閉合環(huán)的所有要求。通過兩種算法的GPS控制網(wǎng)閉合環(huán)搜索結(jié)果比較，驗(yàn)證了本文算法結(jié)果的唯一性和環(huán)長最短性。

最短獨(dú)立閉合環(huán)；信息矩陣；閉合差

1 引 言

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

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

2 生成樹余樹算法分析

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

圖1 大地四邊形

圖2 示例

3 環(huán)形連通圖信息矩陣

連通圖由結(jié)點(diǎn)和邊組成，結(jié)點(diǎn)和邊完全描述了連通圖的拓?fù)浣Y(jié)構(gòu)，在計(jì)算機(jī)中的存儲結(jié)構(gòu)為起點(diǎn)、終點(diǎn)、邊、邊長。

圖的存儲結(jié)構(gòu) 表1

以結(jié)點(diǎn)為行，以邊為列，矩陣也能表述連通圖，如圖3所示。

圖3 連通圖

其關(guān)聯(lián)矩陣表示如下:

正1表示起點(diǎn)，負(fù)1表示終點(diǎn)。為了理解方便，圖3引入了方向，但對連通圖本身的拓?fù)浣Y(jié)構(gòu)不產(chǎn)生影響，因此方向可自定義。關(guān)聯(lián)矩陣與長度沒有聯(lián)系，長度信息存儲在另外一維數(shù)組。顯然矩陣G是秩虧的，刪去某一行，即刪去某個(gè)基準(zhǔn)點(diǎn)，如o點(diǎn)，成為滿秩的基本關(guān)聯(lián)矩陣B，如下:

另外，圖3還關(guān)聯(lián)著一個(gè)基本回路矩陣，當(dāng)連通圖的樹確定后，每條余樹邊所對應(yīng)的回路稱為基本回路，該回路方向與余樹方向一致，由全部基本回路構(gòu)成的矩陣稱為基本回路矩陣Cf[7]，假定圖3的樹為4－5－6，余樹1－2－3，則Cf如下:

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

因此可根據(jù)基本關(guān)聯(lián)矩陣來求出基本回路矩陣，而基本回路矩陣的每一行代表一個(gè)獨(dú)立環(huán)，對于基本關(guān)聯(lián)矩陣要求余樹填充于矩陣末列?；娟P(guān)聯(lián)矩陣和基本回路矩陣組成了閉合環(huán)的信息矩陣。

4 最短獨(dú)立閉合環(huán)生成算法

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

4.1 形成關(guān)聯(lián)矩陣

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

得到的生成樹與原來的圖做差就可以得到余樹，初始化基本關(guān)聯(lián)矩陣Bf為零，其行數(shù)為結(jié)點(diǎn)數(shù)減一，列數(shù)為邊數(shù)，從末列開始填充，先將余樹依次填入，接著填入生成樹，并記錄每列對應(yīng)的邊號。

4.2 生成邊數(shù)最小獨(dú)立環(huán)

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

4.3 生成環(huán)長最短獨(dú)立環(huán)

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

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

5 算例分析

5.1 GPS網(wǎng)介紹

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

GPS網(wǎng)形信息 表2

圖4 D級GPS網(wǎng)

5.2 結(jié)果分析

該D級GPS控制網(wǎng)共有16個(gè)最短獨(dú)立閉合環(huán)，最終成果如表3所示，以GPS規(guī)范[8]中的閉合差公式為限差，其中所有環(huán)質(zhì)量均檢驗(yàn)合格。

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

閉合環(huán)檢驗(yàn)結(jié)果 表3

結(jié)果比較 表4

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

6 結(jié) 語

本文通過引入環(huán)的信息矩陣，將獨(dú)立閉合環(huán)的生成轉(zhuǎn)換成矩陣運(yùn)算，思路簡單，算法實(shí)現(xiàn)容易，能夠生成最短獨(dú)立閉合環(huán)，滿足了GPS網(wǎng)閉合環(huán)質(zhì)量的自動(dòng)檢核要求。本文提出的算法同樣適用于其他網(wǎng)結(jié)構(gòu)圖形。

[1] 李征航，黃勁松.GPS測量與數(shù)據(jù)處理[M].武漢，武漢大學(xué)出版社，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ìn)貴，馮晨.控制網(wǎng)最小獨(dú)立閉合環(huán)搜索算法研究[J].地理空間信息，2008(06)

[6] 馮琰，張正祿，羅年學(xué).最小獨(dú)立閉合環(huán)與附合導(dǎo)線的自動(dòng)生成算法[J].武漢測繪科技大學(xué)學(xué)報(bào)，1998，23

[7] 戴一奇，胡冠章，陳衛(wèi).圖論與代數(shù)結(jié)構(gòu)[M].北京，清華大學(xué)出版社，1995:38～56

[8] GB/T 18314－2009.全球定位系統(tǒng)(GPS)測量規(guī)范[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—)，男，高級工程師，主要從事城市測量技術(shù)工作。

1672－8262(2011)05－94－04

P228

A