馬洪磊，劉成龍，余樂(lè)義，孟凡超

(西南交通大學(xué) 地球科學(xué)與環(huán)境工程學(xué)院，四川 成都 610031)

一種高效的最小獨(dú)立閉合環(huán)自動(dòng)搜索算法

馬洪磊，劉成龍，余樂(lè)義，孟凡超

(西南交通大學(xué) 地球科學(xué)與環(huán)境工程學(xué)院，四川 成都 610031)

依據(jù)圖論理論，在基于生成樹(shù)、余樹(shù)變換的閉合環(huán)搜索算法和基于深度優(yōu)先的閉合環(huán)搜索算法的基礎(chǔ)上，提出一種高效且穩(wěn)定性好的控制網(wǎng)最小獨(dú)立閉合環(huán)自動(dòng)搜索算法。

生成樹(shù)；余樹(shù)；深度優(yōu)先；閉合環(huán)搜索

閉合環(huán)搜索及閉合差檢查是控制網(wǎng)外業(yè)測(cè)量數(shù)據(jù)處理過(guò)程中的重要環(huán)節(jié)，閉合環(huán)閉合差的大小是評(píng)判控制網(wǎng)外業(yè)觀測(cè)數(shù)據(jù)好壞的重要指標(biāo)，此外，閉合差還可用于判斷外業(yè)測(cè)量數(shù)據(jù)中是否含有系統(tǒng)誤差或粗差。傳統(tǒng)的人工閉合環(huán)搜索方法雖然靈活，但當(dāng)控制網(wǎng)極其復(fù)雜時(shí)，人工搜索法效率低，容易出錯(cuò)，因此，尋找一種穩(wěn)健、高效的閉合環(huán)自動(dòng)搜索算法十分必要。目前，閉合環(huán)的自動(dòng)搜索算法主要有3種：①基于鄰接矩陣變換的閉合環(huán)搜索法；②基于生成樹(shù)、余樹(shù)變換的閉合環(huán)搜索法；③基于深度優(yōu)先搜索的閉合環(huán)搜索法。文獻(xiàn)[1]中對(duì)上述3種閉合環(huán)自動(dòng)搜索算法進(jìn)行了探討并得出以下結(jié)論：基于鄰接矩陣變換的閉合環(huán)搜索算法雖然簡(jiǎn)單，但其時(shí)間和空間復(fù)雜性較高；基于生成樹(shù)、余樹(shù)變換閉合環(huán)搜索算法和基于深度優(yōu)先的閉合環(huán)搜索算法的搜索效率相對(duì)較高[1]。文獻(xiàn)[2]中對(duì)基于生成樹(shù)、余樹(shù)變換的閉合環(huán)搜索算法和基于深度優(yōu)先的閉合環(huán)搜索算法進(jìn)行了理論分析并得出以下結(jié)論：基于生成樹(shù)、余樹(shù)變換的閉合環(huán)搜索算法能夠穩(wěn)定地搜索出全部獨(dú)立閉合環(huán)，通過(guò)改變余枝的添加順序，可穩(wěn)定地搜索出一組最小獨(dú)立閉合環(huán)。本文還通過(guò)一個(gè)實(shí)例證明了基于深度優(yōu)先的閉合環(huán)搜索算法具有不穩(wěn)定的缺點(diǎn)，具體是指：雖然該算法可以保證搜索出的閉合環(huán)之間相互獨(dú)立，但卻不一定能夠搜索出全部獨(dú)立閉合環(huán)[2]。雖然基于生成樹(shù)、余樹(shù)變換的閉合環(huán)搜索算法是一種穩(wěn)定、可靠的閉合環(huán)自動(dòng)搜索算法，但對(duì)大型控制網(wǎng)的最小獨(dú)立閉合環(huán)搜索效率不高[3]。針對(duì)以上各閉合環(huán)搜索算法中存在的不足，本文依據(jù)圖論中的相關(guān)理論并結(jié)合現(xiàn)有的基于生成樹(shù)、余樹(shù)變換的閉合環(huán)搜索算法和基于深度優(yōu)先的閉合環(huán)搜索算法，提出了一種新的閉合環(huán)自動(dòng)搜索算法，為論述方便，本文將該算法簡(jiǎn)稱為新算法。

1 相關(guān)概念

生成樹(shù)：在一個(gè)連通圖G(V,E)中，其中V是圖中頂點(diǎn)的集合，E是圖中邊的集合。取它的全部頂點(diǎn)V和一部分邊E′構(gòu)成一個(gè)子圖g(V,E′)，若子圖g(V,E′)中的邊將圖G(V,E)中的所有頂點(diǎn)連通又不形成回路，則稱子圖g(V,E′)是連通圖G(V,E)的一棵生成樹(shù)[4]。

廣度優(yōu)先生成樹(shù)：由廣度優(yōu)先搜索得到的生成樹(shù)為廣度優(yōu)先生成樹(shù)[4]。

余樹(shù)：得到連通圖G(V,E)的生成樹(shù)g(V,E′)后，連通圖G(V,E)中不在生成樹(shù)上的邊稱為圖G(V,E)的余枝，余枝的集合稱為圖G(V,E)的余樹(shù)[5]。

深度優(yōu)先搜索算法：是指沿著一條路徑從開(kāi)始頂點(diǎn)到達(dá)最后的頂點(diǎn)，然后原路返回，并且沿下一條路徑達(dá)到最后的頂點(diǎn)，如此繼續(xù)直到走過(guò)所有的頂點(diǎn)[6]。

廣度優(yōu)先搜索算法：又稱寬度優(yōu)先搜索或橫向優(yōu)先搜索，是指從根節(jié)點(diǎn)開(kāi)始，沿著樹(shù)的寬度遍歷樹(shù)的節(jié)點(diǎn)[6]。

冗余搜索:也稱多余搜索即不必要的搜索?，F(xiàn)有閉合環(huán)搜索算法中普遍存在大量的冗余搜索，嚴(yán)重影響了閉合環(huán)的搜索效率。

2 新算法原理與步驟

新算法結(jié)合了廣度優(yōu)先和深度優(yōu)先搜索原理，綜合了基于生成樹(shù)、余樹(shù)變換的閉合環(huán)搜索算法和基于深度優(yōu)先的閉合環(huán)搜索算法的優(yōu)點(diǎn)。其搜索過(guò)程可分為兩個(gè)階段：①獲得一棵廣度優(yōu)先生成樹(shù)所對(duì)應(yīng)的余樹(shù)；②對(duì)余樹(shù)中的余枝進(jìn)行閉合環(huán)搜索。階段1所得余樹(shù)屬于一組獨(dú)立閉合環(huán)，階段2通過(guò)控制余枝的搜索過(guò)程，確保得到一組最小獨(dú)立閉合環(huán)。

利用新算法進(jìn)行最小獨(dú)立閉合環(huán)搜索的具體步驟如下：

1)構(gòu)建一維數(shù)組V和鄰接矩陣M分別用來(lái)存儲(chǔ)圖中所有頂點(diǎn)及點(diǎn)間關(guān)系(邊)的數(shù)據(jù)?？紤]到鄰接矩陣對(duì)稱的特點(diǎn)，可采用下三角方式存儲(chǔ)。

2)利用廣度優(yōu)先搜索算法獲得一棵廣度優(yōu)先生成樹(shù)所對(duì)應(yīng)的余樹(shù)。

3)設(shè)置當(dāng)前搜索深度MD=2。

4)斷開(kāi)余枝R，利用深度優(yōu)先搜索原理對(duì)余枝R兩頂點(diǎn)進(jìn)行最短路徑搜索(為便于論述，下文稱為對(duì)余枝進(jìn)行閉合環(huán)搜索)，若搜索出的閉合環(huán)中不包含其他余枝，則記錄該閉合環(huán)并從余樹(shù)中刪除余枝R(即R不再為余枝)，重復(fù)步驟3)和4)；若搜索出的閉合環(huán)中包含其他余枝，則斷開(kāi)其他余枝，繼續(xù)在當(dāng)前搜索深度MD下對(duì)該余枝進(jìn)行閉合環(huán)搜索，直到搜索到的閉合環(huán)中不包含其他余枝或閉合環(huán)搜索失敗為止；若搜索到不包含其他余枝的閉合環(huán)，則恢復(fù)之前斷開(kāi)的余枝并記錄該閉合環(huán)，從余樹(shù)中刪除余枝R并重復(fù)步驟3)和4)；若搜索失敗，則恢復(fù)之前斷開(kāi)的余枝并對(duì)下一條余枝重復(fù)步驟4)。

5)若余樹(shù)為空，則閉合環(huán)搜索完畢，否則執(zhí)行步驟6)。

6)設(shè)置當(dāng)前搜索深度MD=MD+1，重復(fù)步驟4)和5)。

3 新算法分析

上述新算法步驟簡(jiǎn)單，只對(duì)余枝進(jìn)行閉合環(huán)搜索，每搜索到一個(gè)閉合環(huán)就刪除一條余枝，余樹(shù)為空時(shí)閉合環(huán)搜索完畢，大大減少了冗余搜索且無(wú)需設(shè)置最大搜索深度。下面就新算法是否能穩(wěn)定地搜索出一組最小獨(dú)立閉合環(huán)進(jìn)行分析、論證。

3.1 穩(wěn)定性和獨(dú)立性分析

穩(wěn)定性是描述算法理論是否嚴(yán)密的方法。如果算法在任何情況下都能得到正確結(jié)果，則該算法是穩(wěn)定的，否則該算法不穩(wěn)定。

獨(dú)立性是指對(duì)于一組閉合環(huán)A，若A中任意閉合環(huán)中都至少有一條邊不存在于其他任何閉合環(huán)中，則認(rèn)為該組閉合環(huán)是一組獨(dú)立閉合環(huán)。

由于新算法與基于生成樹(shù)、余樹(shù)變換的閉合環(huán)搜索算法都需要獲得余樹(shù)，但前者是在余樹(shù)范圍內(nèi)，通過(guò)對(duì)鄰接矩陣進(jìn)行深度優(yōu)先搜索獲得閉合環(huán)，后者則是通過(guò)余枝回代至生成樹(shù)中獲得閉合環(huán)?；谏蓸?shù)、余樹(shù)的閉合環(huán)搜索算法余枝逐條回代保證了閉合環(huán)的獨(dú)立性，新方法要求每次搜索得到的閉合環(huán)中只含有一條余枝，也有效保證了閉合環(huán)的獨(dú)立性。又因?yàn)橛嘀€(gè)數(shù)等于獨(dú)立閉合環(huán)個(gè)數(shù)，因此，兩種算法均可以穩(wěn)定獲得全部獨(dú)立閉合環(huán)。

3.2 最小性分析

圖1為某水準(zhǔn)網(wǎng)示意圖，圖中水準(zhǔn)網(wǎng)的樹(shù)形表示如圖2所示。圖2中實(shí)線集合表示廣度優(yōu)先生成樹(shù)，虛線集合表示余樹(shù)，二者的組合為圖1所示水準(zhǔn)網(wǎng)的另一種表示形式。對(duì)圖2分析不難發(fā)現(xiàn)，當(dāng)每個(gè)閉合環(huán)的搜索都從搜索深度MD=2時(shí)開(kāi)始，且滿足只含一條余枝的閉合環(huán)為搜索結(jié)果時(shí)，便可保證所得閉合環(huán)是一組最小獨(dú)立閉合環(huán)。為驗(yàn)證以上分析的正確性，利用新算法對(duì)圖1所示水準(zhǔn)網(wǎng)進(jìn)行閉合環(huán)搜索，過(guò)程如下：

圖1 某水準(zhǔn)網(wǎng)示意圖

圖2 圖1所示水準(zhǔn)網(wǎng)的樹(shù)形表示

根據(jù)廣度優(yōu)先搜索原理獲得該水準(zhǔn)網(wǎng)圖的一棵廣度優(yōu)先生成樹(shù)及相應(yīng)余樹(shù)。依據(jù)新算法實(shí)施步驟可知，前兩個(gè)搜到的閉合環(huán)為I-H-BM2和E-F-G或E-F-G和I-H-BM2，第3個(gè)搜索到的閉合環(huán)為I-H-D-C或D-E-G-H，若第3個(gè)搜索到的閉合環(huán)為I-H-D-C，則第4個(gè)搜索到的閉合環(huán)為B-D-C,第5個(gè)搜索到的閉合環(huán)為A-B-D，第6個(gè)搜索到的閉合環(huán)為D-E-G-H，第7個(gè)搜索到的閉合環(huán)為A-D-E-F-BM1，至此閉合環(huán)搜索完畢，所得閉合環(huán)為一組最小獨(dú)立閉合環(huán)。若第3個(gè)搜索到的閉合環(huán)為D-E-G-H，則第4個(gè)搜索到的閉合環(huán)為I-H-D-C，第5個(gè)搜索到的閉合環(huán)為B-C-D，第6個(gè)搜索到的閉合環(huán)為A-B-D，第7個(gè)搜索到的閉合環(huán)為A-D-E-F-BM1，至此閉合環(huán)搜索完畢，所得閉合環(huán)為一組最小獨(dú)立閉合環(huán)。通過(guò)該實(shí)例，驗(yàn)證了利用新算法進(jìn)行最小獨(dú)立閉合環(huán)搜索的正確性。

對(duì)圖2進(jìn)行分析發(fā)現(xiàn)，新算法在編程實(shí)現(xiàn)時(shí)還可進(jìn)一步優(yōu)化，優(yōu)化方法如下：

在利用廣度優(yōu)先搜索算法生成一棵廣度優(yōu)先生成樹(shù)時(shí)，記錄每個(gè)頂點(diǎn)所在的層數(shù)(如圖2中BM2為0層，H和I為1層等)。得到廣度優(yōu)先生成樹(shù)后，依據(jù)余枝中兩頂點(diǎn)所在層數(shù)之和的大小對(duì)余枝集合進(jìn)行升序排列。此時(shí)，通過(guò)調(diào)整新算法步驟，可進(jìn)一步減少冗余搜索。假設(shè)余樹(shù)中共有3條余枝且升序排序后順序?yàn)镽1，R2，R3，則調(diào)整后步驟如下：

設(shè)置搜索深度MD=2，對(duì)R1進(jìn)行閉合環(huán)搜索，若成功，則重置MD=2，并對(duì)下一條余枝R2進(jìn)行搜索；若失敗，則設(shè)MD=MD+1，繼續(xù)對(duì)R1進(jìn)行閉合環(huán)搜索。重復(fù)以上過(guò)程，當(dāng)R3搜索成功時(shí)(即最后一條余枝搜索成功時(shí))，閉合環(huán)搜索完畢。

4 對(duì)比分析

根據(jù)本文提出的新算法，筆者用C#語(yǔ)言在.Net平臺(tái)上編程實(shí)現(xiàn)了水準(zhǔn)網(wǎng)最小獨(dú)立閉合環(huán)的自動(dòng)搜索及閉合差的計(jì)算與檢核。為檢驗(yàn)新算法是否具有較高的搜索效率，筆者還根據(jù)基于深度優(yōu)先的閉合環(huán)搜索算法，同樣編程實(shí)現(xiàn)了水準(zhǔn)網(wǎng)最小獨(dú)立閉合環(huán)的自動(dòng)搜索。為節(jié)省存儲(chǔ)空間，筆者所編程序中的鄰接矩陣均采用下三角方式存儲(chǔ)，從而導(dǎo)致搜索時(shí)間延長(zhǎng)，但這并不影響對(duì)新算法搜索效率的對(duì)比。自編程序與武漢大學(xué)商用平差計(jì)算軟件COSA及西南交通大學(xué)商用軌道控制網(wǎng)數(shù)據(jù)處理軟件CPⅢ DMS進(jìn)行對(duì)比的情況，統(tǒng)計(jì)在表1～3中。

表1 CPⅢ高程網(wǎng)的最小獨(dú)立閉合環(huán)搜索結(jié)果對(duì)比

表2 某水準(zhǔn)網(wǎng)的最小獨(dú)立閉合環(huán)搜索結(jié)果對(duì)比

表3 某水準(zhǔn)網(wǎng)的搜索效率對(duì)比

以上各表中的統(tǒng)計(jì)數(shù)據(jù)均是在同一臺(tái)計(jì)算機(jī)上得到，表3中基于深度優(yōu)先的閉合環(huán)搜索算法是在最大搜索深度為50的情況下得到的。

由表1、表2中閉合環(huán)個(gè)數(shù)及最大閉合環(huán)點(diǎn)數(shù)的對(duì)比可知，本文提出的新算法可準(zhǔn)確地搜索出任意水準(zhǔn)網(wǎng)的一組最小獨(dú)立閉合環(huán)，驗(yàn)證了新算法的正確性及可行性。

文獻(xiàn)[2]中通過(guò)3種不同算法搜索時(shí)間的對(duì)比，發(fā)現(xiàn)基于深度優(yōu)先的閉合環(huán)搜索算法是一種較快的閉合環(huán)搜索算法。由表3中搜索時(shí)間的對(duì)比可知，本文所提出的新算法較基于深度優(yōu)先的閉合環(huán)搜索算法搜索時(shí)間更短、效率更高。

5 結(jié) 論

本文提出的新算法綜合了基于深度優(yōu)先閉合環(huán)搜索算法和基于生成樹(shù)、余樹(shù)變換的閉合環(huán)搜索算法的優(yōu)點(diǎn)，可理解為是對(duì)二者的融合和改進(jìn)。通過(guò)以上理論分析及實(shí)例驗(yàn)證得出以下幾點(diǎn)結(jié)論：

1)本文提出的閉合環(huán)自動(dòng)搜索算法極大地減少了冗余搜索，顯著提高了閉合環(huán)的搜索效率，是一種適用于大型控制網(wǎng)的最小獨(dú)立閉合環(huán)自動(dòng)搜索的新算法。

2)本文提出閉合環(huán)自動(dòng)搜索算法雖然也利用了深度優(yōu)先搜索原理，但改善了基于深度優(yōu)先的閉合環(huán)搜索算法不穩(wěn)定的缺點(diǎn)且無(wú)需設(shè)置最大搜索深度，是一種穩(wěn)定、高效且高度自動(dòng)化的最小獨(dú)立閉合環(huán)搜索算法。

3)本文提出的最小獨(dú)立閉合環(huán)自動(dòng)搜索算法不僅能應(yīng)用于高程網(wǎng)，原則上也適用于任何可化簡(jiǎn)為無(wú)向圖的控制網(wǎng)的最小獨(dú)立閉合環(huán)的自動(dòng)搜索，如GPS基線網(wǎng)及化簡(jiǎn)后的邊角網(wǎng)等。

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

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

[3]游為，范東明，張?jiān)疲?水準(zhǔn)網(wǎng)閉合差自動(dòng)解算的新方法[J].測(cè)繪工程，2007，16(5)：17-19.

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

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

[6]楊洪.圖論常用算法選編 [M].北京：鐵道出版社，1988：110-121.

[責(zé)任編輯：劉文霞]

An efficient algorithm of automatic searching for minimum independent closed-loop

MA Hong-lei，LIU Cheng-long，YU Le-yi，MENG Fan-chao

(Faculty of Geosciences and Environmental Engineering, Southwest Jiaotong University， Chengdu 610031, China)

It provides an efficient and stable automatically search algorithm of smallest independent closed loop control network, according to the closed loop search algorithm of spanning tree and spare tree transform, and depth-first closed loop search algorithm on the basis of graph theory.

spanning tree; spare tree; depth-first; closed loop search

2013-08-14

中央高?；究蒲袠I(yè)務(wù)專項(xiàng)資金資助項(xiàng)目(SWJTU12ZT07)

馬洪磊(1989-)，男，碩士研究生.

P221

：A

：1006-7949(2014)08-0070-03