葉 寶,陳 義

(1.同濟(jì)大學(xué)土木工程學(xué)院,上海 200092;2.蘇州工業(yè)園區(qū)測繪有限責(zé)任公司,江蘇蘇州 215021)

基于邊集數(shù)組的最小獨(dú)立閉合環(huán)搜索算法實(shí)現(xiàn)

葉 寶1,2,陳 義1

(1.同濟(jì)大學(xué)土木工程學(xué)院,上海 200092;2.蘇州工業(yè)園區(qū)測繪有限責(zé)任公司,江蘇蘇州 215021)

控制網(wǎng)的閉合差檢驗(yàn)是平差計(jì)算前的一個(gè)重要步驟,目的是發(fā)現(xiàn)原始觀測數(shù)據(jù)中的粗差并予以剔除,并評估外業(yè)觀測的質(zhì)量。根據(jù)測量控制網(wǎng)的數(shù)據(jù)結(jié)構(gòu)特點(diǎn),提出基于邊集數(shù)組存儲結(jié)構(gòu)的控制網(wǎng)最小獨(dú)立閉合環(huán)搜索算法的實(shí)現(xiàn)原理及具體過程。最后通過不同算例對算法的正確性進(jìn)行驗(yàn)證。

數(shù)據(jù)結(jié)構(gòu);邊集數(shù)組;最小獨(dú)立閉合環(huán);算法

一、引 言

在測量平差計(jì)算前,為保證平差結(jié)果的正確性,防止觀測值可能含有粗差及系統(tǒng)誤差影響平差結(jié)果,無論是傳統(tǒng)的測量控制網(wǎng),如導(dǎo)線網(wǎng)、水準(zhǔn)網(wǎng),還是 GPS控制網(wǎng),都需對控制網(wǎng)中的各種多邊形閉合差進(jìn)行檢核,以探測、剔除粗差,并評定觀測值的質(zhì)量。因此,如何自動搜索出控制網(wǎng)的最小獨(dú)立閉合環(huán)成為一個(gè)核心問題。最小獨(dú)立閉合環(huán)搜索算法目前主要有三種：基于鄰接矩陣變換算法、基于生成樹和余樹變換算法、基于深度優(yōu)先搜索算法[1]。一般都要用到數(shù)據(jù)結(jié)構(gòu)知識,采用鄰接矩陣或鄰接表等存儲結(jié)構(gòu)來實(shí)現(xiàn)。本文根據(jù)控制網(wǎng)的特點(diǎn),采用了更為直觀的邊集數(shù)組的存儲結(jié)構(gòu),對生成樹和余樹變換算法進(jìn)行了編程實(shí)現(xiàn),并通過不同的例子,驗(yàn)證了算法的正確性。

二、控制網(wǎng)的數(shù)據(jù)結(jié)構(gòu)

1.數(shù)據(jù)結(jié)構(gòu)的概念

數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。數(shù)據(jù)結(jié)構(gòu)包含數(shù)據(jù)和數(shù)據(jù)關(guān)系兩方面的基本特征。

如圖 1所示,根據(jù)數(shù)據(jù)元素之間關(guān)系的不同特性,通常有四類基本數(shù)據(jù)結(jié)構(gòu)：集合結(jié)構(gòu)、線性結(jié)構(gòu)、樹形結(jié)構(gòu)、網(wǎng)狀結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的邏輯結(jié)構(gòu) (logic structure)和物理結(jié)構(gòu) (physical structure)。其中數(shù)據(jù)的物理結(jié)構(gòu)包括數(shù)據(jù)元素的表示和存儲以及數(shù)據(jù)元素之間關(guān)系的表示和存儲。通常數(shù)據(jù)結(jié)構(gòu)采用數(shù)組法、鄰接表法、十字鏈表、鄰接多重表等基本的存儲結(jié)構(gòu)表示。

圖1 基本類型的數(shù)據(jù)結(jié)構(gòu)

2.控制網(wǎng)的數(shù)據(jù)結(jié)構(gòu)分析

根據(jù)圖 1和對測量控制網(wǎng)的特點(diǎn)分析,顯然控制點(diǎn)之間是任意的、多對多的復(fù)雜關(guān)系。因此控制網(wǎng)與數(shù)據(jù)結(jié)構(gòu)中的網(wǎng)狀結(jié)構(gòu)的概念一致。通過比較,可以建立控制網(wǎng)和圖之間如表 1所示的概念映射關(guān)系。

表 1 測量控制網(wǎng)與圖的概念間的映射關(guān)系

對于測量控制網(wǎng)而言,可以采用圖的鄰接矩陣等存儲結(jié)構(gòu)表示?？紤]到測量控制網(wǎng)的特點(diǎn),總是由一系列控制點(diǎn)和邊組成的網(wǎng)狀結(jié)構(gòu),因此可以從圖的定義出發(fā),采用點(diǎn)集數(shù)組和邊集數(shù)組的存儲結(jié)構(gòu)(包括數(shù)據(jù)元素和數(shù)據(jù)元素關(guān)系的存儲)。二者均采用結(jié)構(gòu)體數(shù)組,點(diǎn)集數(shù)組存儲控制點(diǎn)的所有信息,邊集數(shù)組存儲邊的所有信息,則所有控制點(diǎn)間的觀測值和相關(guān)關(guān)系都通過邊集數(shù)組來反映,如表 2所示。

表 2 測量控制網(wǎng)結(jié)構(gòu)體數(shù)組存儲結(jié)構(gòu)

三、算法原理分析

1.最小獨(dú)立閉合環(huán)搜索的概念

最小獨(dú)立閉合環(huán)是指控制網(wǎng)中含有觀測邊數(shù)最少且相互獨(dú)立的多邊形閉合環(huán)。是對控制網(wǎng)進(jìn)行各種閉合差檢驗(yàn)、定位粗差的基礎(chǔ)幾何模型。如前所述,測量控制網(wǎng)可映射為圖 (網(wǎng))的數(shù)據(jù)結(jié)構(gòu)。則問題的核心即歸結(jié)為對網(wǎng)的結(jié)構(gòu)進(jìn)行的最小獨(dú)立閉合環(huán)的分析確定。其內(nèi)涵有二：①所搜索確定的閉合環(huán)最小,也即環(huán)的邊數(shù)最小,與網(wǎng)的“最短路徑”的概念一致;②各閉合環(huán)相互獨(dú)立,亦即每一個(gè)環(huán)中都至少有一條不屬于其他環(huán)的邊[2]。需要指出的是,對于一個(gè)網(wǎng)而言,其最小獨(dú)立閉合環(huán)的組合、構(gòu)成情況并不唯一,只要找出其中的一組即可滿足定位粗差及評定觀測值質(zhì)量的需要。

2.生成樹、余樹變換算法的原理

網(wǎng)的最小獨(dú)立閉合環(huán)搜索算法中以生成樹、余樹變換算法最為基礎(chǔ),且搜索結(jié)果穩(wěn)定[3]。該算法采用逆向思維,其原理是：首先對控制網(wǎng)進(jìn)行簡化處理,將其“修剪”為一個(gè)稱為生成樹的樹形結(jié)構(gòu)。所謂生成樹就是一個(gè)連通圖的最小連通子圖,其特點(diǎn)是含有圖中的全部 n個(gè)頂點(diǎn),但只有足以構(gòu)成一棵樹的 n-1條邊,如果在生成樹上添加一條邊,則必定構(gòu)成一個(gè)環(huán),因其使得它所依附的兩個(gè)頂點(diǎn)之間有了第二條路徑。因?yàn)闇y量控制網(wǎng)中不存在孤立的控制點(diǎn),各點(diǎn)之間總是通過一定的觀測量、觀測邊發(fā)生著聯(lián)系,因此,對控制網(wǎng)而言,其總是一個(gè)連通網(wǎng),對應(yīng)的總是可以化簡為一棵生成樹。如圖2所示。

圖2 控制網(wǎng)數(shù)據(jù)結(jié)構(gòu)轉(zhuǎn)化示意圖

因此,對于一個(gè)網(wǎng),總可以通過一定的算法,將其分割為兩個(gè)部分,一是生成樹;二是生成樹的補(bǔ)集,稱為余樹,其中的每一條邊稱為余枝。將每一條余枝回代添加到生成樹上時(shí),即構(gòu)成一組閉合環(huán),取其中路徑最短者為該余枝對應(yīng)的閉合環(huán),則全部余枝分別回代即構(gòu)成一組獨(dú)立閉合環(huán),因?yàn)楦鶕?jù)“獨(dú)立”的定義,每個(gè)余枝對應(yīng)的閉合環(huán)均至少有一條邊(余枝本身)不屬于其他環(huán)。為保證各閉合環(huán)是最小環(huán),需要定義余枝添加到生成樹上的次序規(guī)則。

1)嘗試將全部余枝添加到生成樹上,取其中閉合環(huán)路徑長度最短者,優(yōu)先添加到生成樹上,作為當(dāng)前最小閉合環(huán);

2)在生成樹的添加余枝后的當(dāng)前子圖上,嘗試將其余的余枝添加到當(dāng)前子圖上,取其中閉合環(huán)路徑長度最短者,優(yōu)先添加到生成樹上,作為當(dāng)前最小閉合環(huán);

3)重復(fù)以上過程,直到所有 r個(gè)余枝均添加到生成樹上,即得到一組 r個(gè)最小獨(dú)立閉合環(huán)。

四、算法實(shí)現(xiàn)過程

基于生成樹和余樹變換算法的實(shí)現(xiàn)過程,控制網(wǎng)采用點(diǎn)集數(shù)組 P[n]和邊集數(shù)組 L[m]的結(jié)構(gòu)存儲(均為結(jié)構(gòu)體數(shù)組)。

1)采用BFS(寬度優(yōu)先遍歷)算法,得到控制網(wǎng)的一棵寬度生成樹,生成樹也采用點(diǎn)集數(shù)組、邊集數(shù)組存放,則生成樹的點(diǎn)集與控制網(wǎng)的點(diǎn)集相同,邊集為控制網(wǎng)邊集的子集,將控制網(wǎng)的邊集設(shè)為全集,則生成樹邊集的補(bǔ)集即為生成樹的余樹的邊集數(shù)組。編程中只要將 BFS遍歷經(jīng)過的邊的 V isited值標(biāo)定為 true,即表示生成樹,否則為 false表示余樹,此即實(shí)現(xiàn)了對控制網(wǎng)邊集數(shù)組的分割處理。

2)將余樹中的余枝 (邊集數(shù)組 L[m]中 V isited值為 false的邊)逐一回代、添加到生成樹上(邊集數(shù)組L[m]中 V isited值為 true的邊),每添加一個(gè)余枝,得到一組閉合環(huán),通過網(wǎng)的最短路徑算法求得該余枝兩端點(diǎn)間的最短路徑,比較所有余枝的最短路徑,選擇最短路徑最小的余枝,優(yōu)先添加到生成樹上 (將其邊的Visited值標(biāo)定為 true)。

3)重復(fù)2),直至所有的余枝都添加到生成樹上為止(邊集數(shù)組L[m]中所有邊的Visited值均為 true)。

由上述過程可見,關(guān)鍵是基于邊集數(shù)組的最短路徑算法的實(shí)現(xiàn)。本文采用經(jīng)典的 Dijkstra算法,其實(shí)現(xiàn)過程是：定義兩個(gè)一維工作數(shù)組,一個(gè)是最短路徑長度數(shù)組 PathLength[n],此數(shù)組與點(diǎn)集數(shù)組P[n]相互對應(yīng),用以存放起始點(diǎn) (余枝的一個(gè)端點(diǎn))到生成樹中各頂點(diǎn)的路徑長度;另一個(gè)是最短路徑點(diǎn)名數(shù)組 PathName[n],用以存放起始點(diǎn)到其余各頂點(diǎn)的最短路徑的點(diǎn)序列。

1)初始化 PathLength[n]和 PathName[n]數(shù)組：起始點(diǎn) S到其自身的邊長為 0,與其不相鄰接的點(diǎn)的邊長置為∞,與其相鄰接的點(diǎn),通過一個(gè)成員函數(shù) GetEdge(string PointA,string PointB),求出起始點(diǎn)到該點(diǎn)的邊的長度,并在點(diǎn)集數(shù)組 P[n]中將起始點(diǎn) S的 Visited值標(biāo)定為 true,表示起始點(diǎn)即默認(rèn)為已知的最短路徑終點(diǎn)。

2)掃描 PathLength[n]數(shù)組：查找該數(shù)組中當(dāng)前的最小值,凡是在點(diǎn)集數(shù)組 P[n]中 V isited值為true的點(diǎn),其對應(yīng)的在 PathLength[n]數(shù)組中的值均不予考慮,而在剩余的數(shù)組元素中查找最小值,并將其對應(yīng)的在點(diǎn)集數(shù)組 P[n]中的點(diǎn)的 Visited值標(biāo)定為 true,表示該點(diǎn)為自起始點(diǎn)出發(fā)的、當(dāng)前最短路徑的終點(diǎn),在 PathName[n]數(shù)組中記錄下該點(diǎn) T,并記錄當(dāng)前最短路徑值MinPath。

3)更新 PathLength[n]和 PathName[n]數(shù)組：以 2)中得到的當(dāng)前最短路徑終點(diǎn) T作為新的參考點(diǎn),循環(huán)遍歷點(diǎn)集數(shù)組 P[n],查找計(jì)算 T點(diǎn)到達(dá)其他Visited值為 false的點(diǎn)的邊長 (P[n]中 Visited值為 true的點(diǎn)可視為已知最短路徑終點(diǎn)點(diǎn)集,不予考慮),如果遍歷的點(diǎn)與 T點(diǎn)相鄰接,并且MinPath與該點(diǎn)到 T點(diǎn)的邊長之和小于其在 PathLength[n]中的該點(diǎn)到起始點(diǎn) S的路徑長度,則用MinPath與該點(diǎn)到 T點(diǎn)的邊長之和更新 PathLength[n]中該點(diǎn)到起始點(diǎn) S的當(dāng)前最短路徑長度值。

4)重復(fù)步驟 2)～步驟 3),直至點(diǎn)集數(shù)組P[n]中點(diǎn)的 V isited值全部為 true,即起始點(diǎn)到所有頂點(diǎn)的最短路徑均已查找得到,全部頂點(diǎn)均加入到已知最短路徑終點(diǎn)點(diǎn)集中為止。

最后需要說明的是關(guān)于成員函數(shù) GetEdge (string Poin tA,string PointB),該成員函數(shù)的作用是分析網(wǎng)中各頂點(diǎn)是否相鄰及鄰接的邊長值,用以代替鄰接矩陣。用此函數(shù)省卻了復(fù)雜的構(gòu)造鄰接矩陣的過程,并且避免了當(dāng)網(wǎng)的頂點(diǎn)較多時(shí),隨著鄰接矩陣的快速膨脹,需要大量占用內(nèi)存空間的問題。其實(shí)現(xiàn)過程為,通過遍歷邊集數(shù)組L[m],分析確定出各頂點(diǎn)相鄰與否及鄰接的邊長值。對于無向圖,只要邊的起點(diǎn)和終點(diǎn)之間有一向相通即可視為相鄰,對有向圖,需要起點(diǎn)和終點(diǎn)之間雙向連通,才可視為相鄰。

五、應(yīng)用及驗(yàn)證

本文應(yīng)用上述原理,采用 C#語言進(jìn)行了編程實(shí)現(xiàn)。并采用幾個(gè)算例對算法的正確性進(jìn)行驗(yàn)證。

圖3為某市三等水準(zhǔn)網(wǎng),對該水準(zhǔn)網(wǎng)進(jìn)行閉合環(huán)搜索計(jì)算,共計(jì)算得到水準(zhǔn)閉合環(huán) 23個(gè),與原水準(zhǔn)網(wǎng)中閉合環(huán)的實(shí)際情況完全一致;統(tǒng)計(jì)計(jì)算出的閉合環(huán)長度、閉合差均與水準(zhǔn)網(wǎng)實(shí)際情況全部完全一致。采用其他幾個(gè)算例,同樣取得了準(zhǔn)確的搜索計(jì)算結(jié)果。

圖3 算例

六、結(jié)束語

本文根據(jù)測量控制網(wǎng)的特點(diǎn),采用點(diǎn)集數(shù)組和邊集數(shù)組的存儲結(jié)構(gòu),實(shí)現(xiàn)了對網(wǎng)的最小獨(dú)立閉合環(huán)的自動搜索。避免了使用大矩陣,占用大量存儲空間的問題產(chǎn)生,并且使得數(shù)據(jù)的存儲結(jié)構(gòu)更直觀、易于理解,便于數(shù)據(jù)的輸入存儲管理?？蓱?yīng)用于實(shí)際生產(chǎn)及軟件設(shè)計(jì)中。

[1] 趙一晗,伍吉倉.控制網(wǎng)閉合環(huán)搜索算法的探討[J].鐵道勘察,2006,32(3)：12-14.

[2] 王金嶺,李陸勛.控制網(wǎng)最小閉合環(huán)信息自動生成算法[J].測繪通報(bào),1995(1)：11-15.

[3] 鄒進(jìn)貴,馮晨.控制網(wǎng)最小獨(dú)立閉合環(huán)搜索算法研究[J].地理空間信息,2008,6(6)：97-99.

[4] 馮琰,張正祿.最小獨(dú)立閉合環(huán)與附合導(dǎo)線的自動生成算法 [J].武漢測繪科技大學(xué)學(xué)報(bào),1998,23(3)：255-259.

[5] 武漢測繪科技大學(xué).測量平差基礎(chǔ)[M].3版.北京：測繪出版社,1996.

[6] WATSON K,NAGEL C,等.C#入門經(jīng)典[M].3版.北京：清華大學(xué)出版社,2007.

[7] 嚴(yán)蔚敏.吳偉民,等.數(shù)據(jù)結(jié)構(gòu)[M].C語言版.北京：清華大學(xué)出版社,2007.

Algorithm of Searching forM in imum Independent Closed-loop Based on Array of Edge Set

YE Bao,CHEN Yi

0494-0911(2010)12-0037-03

P207

B

2009-12-10

葉 寶(1977—),男,寧夏鹽池人,碩士生,研究方向?yàn)榇蟮販y量及測量數(shù)據(jù)處理。