謝海燕，王 超

(上海巖土工程勘察設(shè)計(jì)研究院有限公司,上海 200438)

基于余枝搜索的最小獨(dú)立閉合環(huán)自動(dòng)搜索算法

謝海燕，王 超

(上海巖土工程勘察設(shè)計(jì)研究院有限公司,上海 200438)

在控制測(cè)量、水準(zhǔn)測(cè)量數(shù)據(jù)處理中，為實(shí)現(xiàn)快速有效的進(jìn)行最小獨(dú)立閉合環(huán)的自動(dòng)搜索，基于生成樹(shù)和余樹(shù)，利用數(shù)組的存儲(chǔ)結(jié)構(gòu)，由余枝兩端向外搜索，遇同名點(diǎn)后獲得閉合環(huán)，再通過(guò)閉合環(huán)的獨(dú)立性判斷，實(shí)現(xiàn)最小獨(dú)立閉合環(huán)的快速有效搜索.進(jìn)而利用該程序?qū)?011年上海市閘北區(qū)水利普查項(xiàng)目中的部分水準(zhǔn)測(cè)量結(jié)果進(jìn)行進(jìn)行驗(yàn)證，證明所搜索的閉合環(huán)在常規(guī)網(wǎng)型中可以有效的做到最小和獨(dú)立.

最小獨(dú)立閉合環(huán)；生成樹(shù)；自動(dòng)搜索；算法

在測(cè)量的數(shù)據(jù)處理中，為保證平差結(jié)果的正確性，防止觀測(cè)值可能含有粗差及系統(tǒng)誤差影響平差結(jié)果，無(wú)論是導(dǎo)線網(wǎng)、水準(zhǔn)網(wǎng)，還是GPS控制網(wǎng)，都需要對(duì)控制網(wǎng)中的各種多邊形進(jìn)行閉合差檢核，以探測(cè)、剔除粗差，并評(píng)定觀測(cè)值的質(zhì)量[1].最小獨(dú)立閉合環(huán)的確定是這一工作得以展開(kāi)的首要工作，通常通過(guò)手工方法雖然也能完成閉合環(huán)的確定，但對(duì)于較為復(fù)雜的網(wǎng)型而言，這種方法容易出錯(cuò)，且不易做到最小性與獨(dú)立性，而且數(shù)據(jù)處理時(shí)其效率較為低下，不能滿足高質(zhì)、高效的要求.因此，在進(jìn)行最小獨(dú)立閉合環(huán)搜索時(shí)，利用計(jì)算機(jī)實(shí)現(xiàn)最小獨(dú)立閉合環(huán)的自動(dòng)生成在數(shù)據(jù)處理中具有重要意義.

利用計(jì)算機(jī)進(jìn)行最小獨(dú)立閉合環(huán)的搜索時(shí)一般有以下幾種方法：李光炎等[2]闡釋了基于鄰接矩陣變換的閉合環(huán)搜索算法；白征東[3]給出了基于深度優(yōu)先的閉合環(huán)搜索算法；呂光楣[4]將網(wǎng)型信息簡(jiǎn)化為拓?fù)鋱D，利用圖論的相關(guān)算法知識(shí)進(jìn)行搜索；姚連璧[5]利用網(wǎng)型信息構(gòu)建一生成樹(shù)，同時(shí)得到余枝信息，然后以余枝為基礎(chǔ)搜索最小獨(dú)立閉合環(huán)；趙一晗等[6]確定了基于鄰接矩陣的搜索算法.這些方法雖然都實(shí)現(xiàn)了最小獨(dú)立閉合環(huán)的自動(dòng)搜索，但其各具優(yōu)缺點(diǎn).基于鄰接矩陣的搜索算法雖然簡(jiǎn)單，但其時(shí)間復(fù)雜性與空間復(fù)雜性高，導(dǎo)致其計(jì)算時(shí)間長(zhǎng)、效率較低；基于深度優(yōu)先算法，在采用鄰接表后，雖節(jié)省時(shí)間和空間，但在判斷兩端點(diǎn)是否直連時(shí)，不太方便；對(duì)于利用圖論的相關(guān)算法進(jìn)行搜索，編程復(fù)雜，不易實(shí)現(xiàn)；基于生成樹(shù)和余樹(shù)搜索算法雖然理論簡(jiǎn)單，但該搜索算法還可以進(jìn)一步優(yōu)化.

本文是基于生成樹(shù)和余樹(shù)搜索算法，利用二維數(shù)組存儲(chǔ)結(jié)構(gòu)，將原先由余枝一端先搜索閉合環(huán)，再判斷選擇的基本思路，改為由余枝兩端同時(shí)搜索對(duì)方端點(diǎn)，遇同名點(diǎn)即得最小閉合環(huán)，最后再通過(guò)獨(dú)立性判斷，實(shí)現(xiàn)最小獨(dú)立閉合環(huán)的自動(dòng)搜索.本方法避免了原算法中將其它邊數(shù)較大的閉合環(huán)先搜索出來(lái)再排除的冗余計(jì)算，從而在一定程度上減少了計(jì)算量，在閉合環(huán)獨(dú)立性分析中，給出了幾類(lèi)較常見(jiàn)的獨(dú)立性問(wèn)題，并給出了相應(yīng)的解決方法，最終實(shí)現(xiàn)最小獨(dú)立閉合環(huán)的自動(dòng)搜索.

1 生成樹(shù)和余枝搜索算法原理

1.1 最優(yōu)樹(shù)的建立算法

面對(duì)一個(gè)網(wǎng)型，可以建立很多種樹(shù).為了有利于閉合環(huán)的搜索，所建立的樹(shù)應(yīng)使得構(gòu)成基本環(huán)路的支路數(shù)目盡可能地少，并稱(chēng)這樣的樹(shù)為最優(yōu)樹(shù).其具體建立步驟為[7]：

(1)計(jì)算網(wǎng)中各個(gè)節(jié)點(diǎn)(指網(wǎng)中所有點(diǎn))的度，并找出度最大的結(jié)點(diǎn)，度最大的結(jié)點(diǎn)不止一個(gè)時(shí)，此時(shí)可任意選取一個(gè)，假設(shè)該點(diǎn)為V.

(2)以網(wǎng)中度最大的接點(diǎn)為起點(diǎn)，即先訪問(wèn)度最大的結(jié)點(diǎn)，再訪問(wèn)該點(diǎn)的鄰節(jié)點(diǎn)V1，V2，…，且記錄相應(yīng)的鄰接邊.

(3)分別從V1，V2，…出發(fā)，訪問(wèn)它們未被訪問(wèn)過(guò)的鄰接點(diǎn)，記錄相應(yīng)的鄰接邊.

(4)若此時(shí)尚有未被訪問(wèn)過(guò)的接點(diǎn)，則繼續(xù)訪問(wèn)下一級(jí)鄰接點(diǎn)，直到所有的結(jié)點(diǎn)都被訪問(wèn)過(guò)為止.

以上算法搜索出的樹(shù)枝的集合即為所建立的最優(yōu)樹(shù)，同時(shí)，網(wǎng)中未被訪問(wèn)過(guò)的邊組成的集合即為余枝.基于余枝搜算法正是在所建立的最優(yōu)樹(shù)枝和余枝的基礎(chǔ)上進(jìn)行的.利用已經(jīng)建立的最優(yōu)樹(shù)的余枝進(jìn)行搜索，一方面，可以利用余枝的獨(dú)立性來(lái)達(dá)到所搜索閉合環(huán)的獨(dú)立性；另一方面，可以利用余枝數(shù)目同最小獨(dú)立閉合環(huán)的數(shù)目相同來(lái)達(dá)到搜索的全面性.基于本余枝搜索的算法，在此處進(jìn)行調(diào)整，得到適合數(shù)組存儲(chǔ)結(jié)構(gòu)的新算法.

1.2 最小獨(dú)立閉合環(huán)

最小獨(dú)立閉合環(huán)的選取必須滿足以下3個(gè)條件：

(1)所有閉合環(huán)應(yīng)該是相互獨(dú)立(線性無(wú)關(guān))的，任何一個(gè)閉合環(huán)都不能由其它閉合環(huán)線性合成；

(2)閉合環(huán)中包含的邊數(shù)最少，這樣可以提高探測(cè)粗差的能力；

(3)對(duì)于邊數(shù)相同的閉合環(huán)，應(yīng)取長(zhǎng)度最短的環(huán).

上述方法是姚連璧等[8]給出的一種典型的獨(dú)立閉合環(huán)的搜索算法，本文算法在此算法的基礎(chǔ)上進(jìn)行了改進(jìn)優(yōu)化.

1.3 多邊形獨(dú)立閉合環(huán)數(shù)

皺進(jìn)貴等[9]給出了最小獨(dú)立閉合環(huán)數(shù)確定的方法.對(duì)于一個(gè)有n個(gè)測(cè)站點(diǎn)，其中有任意一個(gè)點(diǎn)的高程為已知，m條觀測(cè)邊的高程控制網(wǎng)，其必要的觀測(cè)個(gè)數(shù)為n-1，實(shí)際觀測(cè)個(gè)數(shù)為m，故其自由度(條件方程個(gè)數(shù))為m-(n-1)，即m-n+1個(gè).在圖網(wǎng)G=(n,m)中，由圖論知識(shí)可知，非生成樹(shù)邊的個(gè)數(shù)必為m-n+1個(gè)，因此所有最小獨(dú)立閉合環(huán)的個(gè)數(shù)為m-n+1.

2 基于余枝搜索的閉合環(huán)搜索算法

2.1 算法原理

傳統(tǒng)的余枝搜索算法在進(jìn)行獨(dú)立閉合環(huán)的搜索時(shí)，雖然其能夠?qū)崿F(xiàn)閉合環(huán)的搜索，但該方法將包括余枝的所有閉合環(huán)都搜索出來(lái)，然后選擇合適的環(huán).而在實(shí)際生產(chǎn)應(yīng)用中，并不需要包含余枝的所有閉合環(huán)，一般只需要邊數(shù)最小的獨(dú)立環(huán).為此，本文設(shè)計(jì)從余枝的兩邊同時(shí)向外搜索，遇到同名點(diǎn)則停止，如此既避免了對(duì)其它無(wú)用環(huán)的搜索，同時(shí)減小了程序的運(yùn)算量，再則所得閉合環(huán)可以保證邊數(shù)最小.以下算法根據(jù)圖1中的水準(zhǔn)網(wǎng)給出了相應(yīng)的算法步驟.

圖1 水準(zhǔn)網(wǎng)例圖

(1)建立最優(yōu)樹(shù)并將樹(shù)枝信息存于數(shù)組B中，同時(shí)得到余枝，余枝信息存于數(shù)組A中.

(2)以余枝(i，j)的兩端點(diǎn)為搜索起點(diǎn)，以i為起點(diǎn)搜索其鄰節(jié)點(diǎn)g1、h1、j…，剔除節(jié)點(diǎn)j，搜索信息存放于數(shù)組C中；以j為起點(diǎn)搜索其鄰節(jié)點(diǎn)h1、g12、i…，剔除節(jié)點(diǎn)i，信息存放于數(shù)組D中.在存儲(chǔ)搜索信息的數(shù)組中，第一列存放余枝的起點(diǎn)，后續(xù)的每一列均為前一列的鄰節(jié)點(diǎn)，每一列代表一種可能路徑.設(shè)置整數(shù)n，表示第n次遇到同名點(diǎn)時(shí)停止搜索(一般為1，特殊情況n加1).

(3)比較新搜索出的相鄰節(jié)點(diǎn)間有無(wú)同名點(diǎn)，若有n減1.若n=0時(shí)，停止搜索，n>0則轉(zhuǎn)下一步.

(4)以C的最后一列節(jié)點(diǎn)分別為起點(diǎn)，搜索其鄰節(jié)點(diǎn)，并存于C的下一列中，以C的當(dāng)前最后一列和D的倒數(shù)第二列和倒數(shù)第一列比較，遇同名點(diǎn)n減1，同時(shí)判斷是否停止；若沒(méi)有同名點(diǎn)則以D的最后列分為起點(diǎn)，搜索其鄰節(jié)點(diǎn)，并存于D的下一列中，以D的當(dāng)前最后一列和C的倒數(shù)第二非零列和倒數(shù)第一非零列比較，若遇同名點(diǎn)n減1，并判斷是否停止.

(5)重復(fù)第四步直到搜索到符合要求的閉合環(huán)，將C、D數(shù)組中對(duì)應(yīng)有同名點(diǎn)的相應(yīng)行摘錄出，即可組成該余枝下邊數(shù)最少的閉合環(huán)，將余枝和其對(duì)應(yīng)環(huán)存入數(shù)組E中.

(6)對(duì)于E中一條余枝對(duì)應(yīng)一個(gè)環(huán)的，優(yōu)先選擇存入最小獨(dú)立環(huán)數(shù)組F中，在存儲(chǔ)時(shí)要判斷和F中已有環(huán)之間的獨(dú)立性；若某條余枝對(duì)應(yīng)多條閉合環(huán)的，逐個(gè)將各環(huán)和F中的入選環(huán)比較，若其和某一環(huán)是同一環(huán)的則刪除.若比較結(jié)束后該余枝對(duì)應(yīng)的閉合環(huán)還不唯一，則計(jì)算各環(huán)距離，取距離最短的存入F中.

(7)若經(jīng)過(guò)第(6)步的比較，某一余枝對(duì)應(yīng)環(huán)全部被刪除時(shí)，n加1，對(duì)于該余枝需要再次搜索，重復(fù)上述步驟直到得到合格的閉合環(huán).

本算法的對(duì)應(yīng)流程圖(見(jiàn)圖2).

2.2 獨(dú)立性判斷

基于上述算法，雖然對(duì)于一條余枝可以搜索出一條閉合環(huán)，但在獨(dú)立性方面還無(wú)法保證.包含余枝的閉合環(huán)之間不一定是獨(dú)立環(huán)，因?yàn)樵谀承┣闆r下，包含本條余枝的情況下可能還包含有其它的余枝，同時(shí)這兩條余枝所搜索出的閉合環(huán)有可能是同一條閉合環(huán).

根據(jù)圖3所示，黑色實(shí)線為樹(shù)枝，虛線為余枝.圖3中，余枝(8,9)和余枝(9,10)在搜索時(shí)所得到的閉合環(huán)為8-10-9-8和9-8-10-9，雖然都包含各自的余枝，但它們實(shí)質(zhì)為同一環(huán)，這對(duì)于本文所要求的獨(dú)立性還不滿足,這是此類(lèi)方法所遇到的第一類(lèi)獨(dú)立性問(wèn)題.為此，在以余枝進(jìn)行搜索時(shí)，每搜索出新的閉合環(huán)，將其與已經(jīng)搜索出的閉合環(huán)中邊數(shù)相同的環(huán)比較，當(dāng)包含相同節(jié)點(diǎn)名的應(yīng)當(dāng)剔除，如此可消除上述提出的第一類(lèi)獨(dú)立性問(wèn)題.

圖2 最小獨(dú)立閉合環(huán)自動(dòng)搜索算法圖

圖3 圖1最優(yōu)樹(shù)

第二類(lèi)獨(dú)立性問(wèn)題是上述算法第(7)步所謂的特殊情況.對(duì)于這種情況，可將這種余枝單獨(dú)重新搜索，逐漸增加它同名點(diǎn)相遇的次數(shù)(n++)，以此擴(kuò)大環(huán)的邊數(shù)，得到其它的獨(dú)立環(huán)，以實(shí)現(xiàn)每條余枝都能搜索到一條閉合環(huán).

在進(jìn)行獨(dú)立性判斷時(shí)，主要是判斷當(dāng)前的環(huán)和已經(jīng)判斷篩選過(guò)的環(huán)之間是否獨(dú)立.對(duì)于某些特殊的余枝，它們需要通過(guò)增大相遇點(diǎn)的次數(shù)來(lái)得到閉合環(huán).為避免所得到的環(huán)由其它獨(dú)立環(huán)線性組合的情況，也可以由該余枝通過(guò)樹(shù)枝去搜索，在第一次遇到同名點(diǎn)時(shí)獲取閉合環(huán)，而且可以肯定該環(huán)和其它環(huán)一定是獨(dú)立的.這種辦法雖然能保證獨(dú)立性，但所得到的閉合環(huán)不一定是最小的.

對(duì)于上述方法，由于是從余枝兩端向外搜索，遇到同名點(diǎn)則停止，個(gè)別特殊的余枝需要增加所遇到同名點(diǎn)的次數(shù)經(jīng)搜索后停止，因此所搜索的閉合環(huán)邊數(shù)滿足最小.在獨(dú)立性方面，由于每個(gè)環(huán)包含一條不為其它環(huán)所具有的余枝，因此滿足獨(dú)立性的要求.

3 算 例

根據(jù)上述算法，編制了最小獨(dú)立閉合環(huán)的自動(dòng)搜索程序.下面利用該程序針對(duì)2011年海市閘北區(qū)水利普查項(xiàng)目中的部分水準(zhǔn)測(cè)量結(jié)果進(jìn)行水準(zhǔn)環(huán)自動(dòng)搜索，實(shí)測(cè)水準(zhǔn)網(wǎng)圖(見(jiàn)圖4).搜索結(jié)果為：

圖4 實(shí)測(cè)水準(zhǔn)網(wǎng)圖

經(jīng)核查，該方法所搜索出的閉合環(huán)均滿足邊數(shù)最小，閉合環(huán)數(shù)目亦符合理論要求，且各環(huán)之間互相獨(dú)立.

4 結(jié) 論

本文根據(jù)測(cè)量控制網(wǎng)的特點(diǎn)，以數(shù)組的存儲(chǔ)結(jié)構(gòu)，給出了一種新的余枝搜索算法.為避免原先算法計(jì)算量大、效率低下的缺點(diǎn)，同時(shí)考慮到所需閉合環(huán)最小的特點(diǎn)，采用由余枝兩端雙向搜索、尋求同點(diǎn)的思路設(shè)計(jì)算法，最終實(shí)現(xiàn)最小閉合環(huán)的搜索.本文針對(duì)本算法的獨(dú)立性展開(kāi)進(jìn)一步的分析，列舉了2種比較特殊的情況，并給出了較為有效的解決方法.本算法避開(kāi)了深?yuàn)W的理論知識(shí)，以直觀、易于理解的邏輯判斷進(jìn)行搜索，對(duì)于所搜索的閉合環(huán)在常規(guī)網(wǎng)型中可以有效地做到最小和獨(dú)立，算例部分也正驗(yàn)證了這一點(diǎn).

[1] 葉寶義,陳 義.基于邊集數(shù)組的最小獨(dú)立閉合環(huán)搜索算法實(shí)現(xiàn)[J].測(cè)繪通報(bào)，2010(12):37-39.

[2] 李光炎,王解先.閉合環(huán)搜索方法的探討[J].工程勘察,2004(6)：52-53.

[3] 白征東.GPS網(wǎng)中最小獨(dú)立閉合環(huán)的自動(dòng)搜索[J].測(cè)繪科技動(dòng)態(tài)，1994(2)：18-21.

[4] 呂光楣.單源點(diǎn)最短路徑的一種新算法[J].微機(jī)算機(jī)應(yīng)用，1990(2):51-54.

[5] 姚連璧.平面控制網(wǎng)閉合環(huán)的自動(dòng)尋找[J].鐵道勘察，2006(12)：55-58.

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

[7] 歐 龍.一種新的閉合環(huán)自動(dòng)搜索算法[J].柳州師專(zhuān)學(xué)報(bào),2014,29(1):117-120.

[8] 姚連璧,周小平.基于MATLAB的控制網(wǎng)平差程序設(shè)計(jì)[M].上海：同濟(jì)大學(xué)出版社，2006.

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

A Method of Auto-searching Least Closed Loops Based on Spare Branch

XIE Hai-yan, WANG Chao

(Shanghai Investigation and Design Institute Co., Ltd. of Geotechnical Engineering, Shanghai 200438, China)

In the data processing of control surveying and leveling, in order to quickly and effectively carry out auto-search least closed loop, based on spanning tree and spare branch, a 2-D array storage structure is used to search at both ends of spare branch and to get closed loop when meeting the same point. The independent judge of the new closed loop realizes fast and effective auto-searching least closed loops, which is proved to be effective by some leveling results of water census in Zhabei district of Shanghai city.

the least closed loop; the spanning tree; automatic searching; algorithm

P211

A

1008-536X(2017)03-0068-04

2017-02-13

謝海燕(1983-)，男，江西吉安人，工程師，研究方向?yàn)楣こ虦y(cè)量、變形測(cè)量.