基于圖論的測量控制網(wǎng)拓?fù)浞治鱿到y(tǒng)的研究

宇 偉，李曉莉

(合肥工業(yè)大學(xué)土木與水利工程學(xué)院測量工程系，安徽合肥230009)

一、引 言

在研究測量控制網(wǎng)的機(jī)理、健康和安全時(shí)，首先需要解決的一個(gè)關(guān)鍵問題就是正確地識別或判斷測量控制網(wǎng)工作時(shí)的圖形參數(shù)，測量控制網(wǎng)的圖形參數(shù)是研究控制網(wǎng)形變機(jī)理、健康監(jiān)測和安全評估的基礎(chǔ)和依據(jù)。測量控制網(wǎng)參數(shù)的識別屬于系統(tǒng)識別范疇，一般意義上講，就是在識別系統(tǒng)輸入(激勵(lì))和輸出(響應(yīng))數(shù)據(jù)的基礎(chǔ)上，對系統(tǒng)確定一個(gè)數(shù)學(xué)模型，要求這個(gè)模型盡可能精確地反映測量控制網(wǎng)的結(jié)構(gòu)特性，從而達(dá)到識別測量控制網(wǎng)系統(tǒng)的目的?；趫D論的測量控制網(wǎng)拓?fù)浞治鱿到y(tǒng)是建立在系統(tǒng)輸入和輸出數(shù)據(jù)的基礎(chǔ)上的，它實(shí)現(xiàn)了由控制網(wǎng)圖形的映射、響應(yīng)，以識別其圖形參數(shù)，是一種方便、便宜和可行的方法，可以實(shí)現(xiàn)測量控制網(wǎng)的拓?fù)鋺?yīng)用，具有明顯的優(yōu)點(diǎn)和顯著的特色。

現(xiàn)在的測繪數(shù)據(jù)的處理一般是基于一定格式的觀測文件，而后建立間接方程。通過觀測文件的一定格式可以識別站點(diǎn)和其他點(diǎn)的拓?fù)潢P(guān)系，這是建立方程的基礎(chǔ)。但是這種方式缺乏對整個(gè)控制網(wǎng)的拓?fù)浞治?，本文以圖論為基礎(chǔ)，旨在提高控制網(wǎng)拓?fù)浞治瞿芰?，并建立相?yīng)的應(yīng)用。

二、基于圖論的控制網(wǎng)拓?fù)浞治鱿到y(tǒng)的設(shè)計(jì)

1．思 路

圖論中點(diǎn)與點(diǎn)之間、點(diǎn)與線之間、線與線之間的拓?fù)潢P(guān)系主要有：①并聯(lián)與鄰聯(lián)關(guān)系;②相交關(guān)系;③相離關(guān)系。如果兩點(diǎn)存在聯(lián)系可用直線相連兩點(diǎn)，否則兩點(diǎn)不連。測量控制網(wǎng)中，點(diǎn)與點(diǎn)之間、點(diǎn)與線之間及線與線之間的聯(lián)系同圖論中情況相似。測量控制網(wǎng)中，點(diǎn)與點(diǎn)間的聯(lián)系參數(shù)包含高差、距離、角度，這就使控制網(wǎng)在拓?fù)渥R別的基礎(chǔ)上還要建立與之相對應(yīng)的觀測數(shù)據(jù)文件，以建立觀測值和測量控制網(wǎng)圖形的映射關(guān)系，實(shí)現(xiàn)控制網(wǎng)的拓?fù)鋺?yīng)用。

2．尋找拓?fù)湫蔚乃惴ㄟ^程

(1)數(shù)據(jù)結(jié)構(gòu)的建立

在一般的儀器測量過程中，會(huì)產(chǎn)生以站點(diǎn)為結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)，可以在此數(shù)據(jù)結(jié)構(gòu)上進(jìn)行拓?fù)浞治?，也可以轉(zhuǎn)化為其他的數(shù)據(jù)結(jié)構(gòu)進(jìn)行分析。本文以鄰接矩陣來表示控制網(wǎng)的數(shù)據(jù)結(jié)構(gòu)，并在其基礎(chǔ)上按照一定的算法建立控制網(wǎng)的生成樹，并在其基礎(chǔ)上尋找閉合圈、附合路徑等拓?fù)錀l件，再以整個(gè)測量控制網(wǎng)為基礎(chǔ)，對控制網(wǎng)進(jìn)行拓?fù)浞治?，這樣可在拓?fù)湫紊线M(jìn)行數(shù)據(jù)處理，算法的基本過程如圖1所示。

圖1 算法的基本過程

(2)參數(shù)的初始化

未知參數(shù)的初始化主要是根據(jù)遍歷控制網(wǎng)生成樹進(jìn)行的。遍歷從已知點(diǎn)開始，按照廣探法逐級遍歷。即從已知點(diǎn)開始，將未知點(diǎn)初始化，再將其作為已知點(diǎn)初始化下一級未知點(diǎn)，直至未知點(diǎn)被全部初始化。

(3)附合路徑的尋找

附合路徑的尋找主要是尋找已知點(diǎn)和已知點(diǎn)間的路線，由于測量控制網(wǎng)中的已知點(diǎn)固定，可以建立從第一個(gè)已知點(diǎn)出發(fā)的廣探法遍歷，遍歷的過程中建立記錄遍歷過程的數(shù)據(jù)結(jié)構(gòu)，然后根據(jù)其他已知點(diǎn)在遍歷中的次序，按一定算法找到附合路徑。具體算法如下(若已知點(diǎn)數(shù)為n)：

1)從第一個(gè)已知點(diǎn)出發(fā)建立廣探生成樹，同時(shí)要記錄生成樹的路徑。

2)生成樹建立以后，根據(jù)其他已知點(diǎn)在遍歷產(chǎn)生數(shù)據(jù)結(jié)構(gòu)的位置，建立它們和第一個(gè)已知點(diǎn)的路徑。

3)依次尋找n-1條路徑為止。

(4)基本閉合圈的尋找

基本閉合圈是構(gòu)成控制網(wǎng)中最基本非冗余的圈，即組成其他圈的最簡單圈?；救Φ膶ふ乙钥刂凭W(wǎng)的生成樹為基礎(chǔ)，控制網(wǎng)中沒有在生成樹中的邊會(huì)和生成樹構(gòu)成基本圈。具體算法如下：

1)按廣探法建立控制網(wǎng)的生成樹，同時(shí)要記錄生成樹的路徑。

2)尋找出不在控制網(wǎng)生成樹中的邊。

3)根據(jù)構(gòu)成這些邊是兩點(diǎn)進(jìn)行回溯，直到回溯到同一點(diǎn)，建立起到該點(diǎn)的兩條路徑，合并這兩條路徑就組成基本圈。

(5)粗差的檢測和定位

測量控制網(wǎng)的拓?fù)湫螤畹淖R別，如閉合圈、附合路徑均為多余條件，都可按一定的精度要求對拓?fù)湫沃械挠^測值進(jìn)行粗差檢測，如閉合差等。如果檢測結(jié)果超限，則表明該拓?fù)湫螤钪泻写植?。如果控制網(wǎng)中多個(gè)拓?fù)湫螤罹从吵鰴z測超限的情況，則粗差很可能出現(xiàn)在各拓?fù)湫蔚慕患稀Ｆ渌惴ㄈ缦拢?/p>

1)按照前述的算法找出各拓?fù)湫巍?/p>

2)按一定的精度要求對拓?fù)湫芜M(jìn)行檢測。

3)若拓?fù)湫纬霈F(xiàn)粗差，進(jìn)行交集分析，定位粗差的范圍。

3．算法過程的主要代碼

三、試驗(yàn)結(jié)果及分析

為使問題簡便，現(xiàn)對一結(jié)點(diǎn)控制網(wǎng)展開討論。某一控制網(wǎng)其網(wǎng)形(可取用水準(zhǔn)網(wǎng)或是未記角度的導(dǎo)線網(wǎng))，如圖2所示，該網(wǎng)形的鄰接矩陣(對稱陣)為

圖2

首先由廣探法建立控制網(wǎng)的生成樹，進(jìn)行初始化。通過拓?fù)浞治龊?，可尋找到的拓?fù)湫螢椋孩?附合路線1，2，3，4，10; ② 閉合路線分別為：閉合圈一1，2，3，6，5，1，閉合圈二1，5，6，9，8，7，1，閉合圈三3，4，10，9，6，3。這些圖形條件找出后，可以用于建立條件方程和誤差分析等，如：如果5—6段存在粗差，則通過分析，粗差可能在1—5或5—6段;如果是6—9段存在粗差，則可直接確定6-9段。

四、結(jié)束語

在控制網(wǎng)數(shù)據(jù)處理中引入拓?fù)浞治?，增?qiáng)了對控制網(wǎng)圖形條件的使用，實(shí)現(xiàn)了數(shù)據(jù)處理的自動(dòng)化和簡單化，避免了繁雜的數(shù)據(jù)處理。由于引入拓?fù)浞治?，將改變方程建立模式，對控制網(wǎng)的精度和可靠性分析也會(huì)產(chǎn)生變化，如對控制網(wǎng)進(jìn)行拓?fù)浞治觯@樣可在拓?fù)湫紊线M(jìn)行數(shù)據(jù)處理，實(shí)現(xiàn)條件方程的建立和粗差的檢測與定位等應(yīng)用。然而，就控制網(wǎng)拓?fù)湫螌ふ叶?，也有其?fù)雜性，如建立條件方程的圓周條件和極條件的尋找時(shí)就要同時(shí)利用觀測文件和圖論中的數(shù)據(jù)結(jié)構(gòu)，或者建立特殊的數(shù)據(jù)結(jié)構(gòu)，分析也是有一定的難度，但是對于一般的水準(zhǔn)網(wǎng)、導(dǎo)線網(wǎng)及GPS網(wǎng)的拓?fù)浞治鲞€是比較簡單的。

[1]項(xiàng)榮武，劉艷杰，胡忠盛．圖論中最短路徑問題的解法[J]．沈陽航空工業(yè)學(xué)院學(xué)報(bào) ，2004，21(2)：86-88．

[2]朱力杰，楊元喜．論粗差修正與粗差剔除[J]．測繪通報(bào)，1999(6)：5-6．

[3]柴登峰，張登榮．前N條最短路徑問題的算法及應(yīng)用[J]．浙江大學(xué)學(xué)報(bào)：工學(xué)版，2002，36(5)：531-534．

[4]劉瓚武．應(yīng)用圖論[M]．長沙：國防科技大學(xué)出版社，2006．

[5]李明．?dāng)?shù)據(jù)結(jié)構(gòu)(C++版)[M]．北京：清華大學(xué)出版社，2005．

[6]武漢大學(xué)測繪學(xué)院測量平差學(xué)科組．誤差理論與測量平差基礎(chǔ)[M]．武漢：武漢大學(xué)出版社，2009．