李建平，明祖濤，張 屆，游振興

（中國(guó)地質(zhì)大學(xué)（武漢）信息工程學(xué)院，湖北武漢430074）

CPⅢ高程網(wǎng)最小獨(dú)立閉合環(huán)的一種搜索算法

李建平，明祖濤，張 屆，游振興

（中國(guó)地質(zhì)大學(xué)（武漢）信息工程學(xué)院，湖北武漢430074）

水準(zhǔn)測(cè)量結(jié)束后，對(duì)觀測(cè)成果進(jìn)行往返較差、附合路線及閉合環(huán)的閉合差檢查是必不可少的工作。CPⅢ高程控制網(wǎng)網(wǎng)形獨(dú)特，它部分邊含有往返測(cè)或雙次觀測(cè)且屬于大型控制網(wǎng)（觀測(cè)邊可能含有數(shù)千條）。根據(jù)最小獨(dú)立閉合環(huán)及最小獨(dú)立附合路線的限制條件，依據(jù)CPⅢ高程控制網(wǎng)的特點(diǎn)，利用Dijkstra算法思想，提出了最小路徑搜索法并進(jìn)行編程實(shí)現(xiàn)，通過算例驗(yàn)證了其正確性和高效性。

最小獨(dú)立閉合環(huán)；最小獨(dú)立附合路線；最小路徑搜索法；閉合差

水準(zhǔn)測(cè)量外業(yè)數(shù)據(jù)采集完成后，有可能觀測(cè)結(jié)果不符合限差要求，甚至?xí)写植罨烊肫渲?，影響平差成果的正確性和可靠性，且相關(guān)規(guī)范也要求進(jìn)行每km水準(zhǔn)測(cè)量高差全中誤差的計(jì)算，這就要求對(duì)水準(zhǔn)網(wǎng)進(jìn)行各種閉合差計(jì)算。對(duì)于小型簡(jiǎn)單的水準(zhǔn)控制網(wǎng)而言，可以人工檢查閉合差，但在控制網(wǎng)較復(fù)雜或網(wǎng)形很大時(shí)，如果采用人工計(jì)算，不但計(jì)算量大，而且極容易出現(xiàn)2類錯(cuò)誤：一是閉合環(huán)或附合路線找不完全；二是所找閉合環(huán)間或附合路線間存在相關(guān)關(guān)系[1]。為避免人工計(jì)算的繁瑣和易出現(xiàn)的錯(cuò)誤，利用計(jì)算機(jī)進(jìn)行最小獨(dú)立閉合環(huán)及最小獨(dú)立附合路線的自動(dòng)搜索是最好的方式。目前，已經(jīng)有多種有益的最小獨(dú)立閉合環(huán)的搜索算法。文獻(xiàn) [2]采用圖論的方法來進(jìn)行閉合環(huán)的搜索，算法結(jié)構(gòu)復(fù)雜，需要具備很好的數(shù)據(jù)結(jié)構(gòu)知識(shí)，且主要針對(duì)平面控制網(wǎng)，未能充分考慮水準(zhǔn)網(wǎng)的各種情況，如CPⅢ高程控制網(wǎng)是單程矩形閉合環(huán)，部分邊有往返測(cè)。文獻(xiàn)[3]探討了3種閉合環(huán)搜索算法：基于鄰接矩陣變換的方法、基于生成樹和余樹變換的方法、基于深度優(yōu)先搜索的方法。第1種方法只能搜索獨(dú)立閉合環(huán)，后 2種搜索到的是長(zhǎng)度最短的獨(dú)立閉合環(huán)，不一定邊數(shù)最少。文獻(xiàn) [4]中基于迭代加深搜索的算法不穩(wěn)定，有時(shí)無法搜索所有的閉合環(huán)。而對(duì)于最小獨(dú)立附合路線，以往文獻(xiàn)則較少研究，部分算法也只是能搜索出獨(dú)立附合路線,如文獻(xiàn) [5]中基于最小生成樹的算法，有些控制網(wǎng)對(duì)附合路線的長(zhǎng)度也有要求，如CPⅢ高程控制網(wǎng)精密水準(zhǔn)測(cè)量要求附合路線長(zhǎng)度不大于3 km，所以搜索最小獨(dú)立附合路線仍具有較大意義。本文根據(jù)最小獨(dú)立閉合環(huán)及最小獨(dú)立附合路線的特點(diǎn)，利用Dijkstra算法思想，討論了最小路徑搜索法，并通過編程實(shí)現(xiàn)。

1 最小路徑搜索法思想

1）最小獨(dú)立閉合環(huán)和附合路線的條件及個(gè)數(shù)的確定。

對(duì)于水準(zhǔn)網(wǎng)而言，設(shè)觀測(cè)邊（即觀測(cè)高差）個(gè)數(shù)為 gd，其中有往返觀測(cè)或雙次觀測(cè)的獨(dú)立邊個(gè)數(shù)為sgd，已知點(diǎn)個(gè)數(shù)為yd，未知點(diǎn)個(gè)數(shù)為wd。最小獨(dú)立閉合環(huán)應(yīng)滿足如下條件[6]：

①所有閉合環(huán)應(yīng)該是相互獨(dú)立的（線性無關(guān)），即任何一個(gè)閉合環(huán)都不能由其他閉合環(huán)線性合成。滿足獨(dú)立性的要求既可避免重復(fù)計(jì)算，也可以避免遺漏，一般而言，水準(zhǔn)網(wǎng)的獨(dú)立閉合環(huán)個(gè)數(shù)為：

②閉合環(huán)所包含的邊數(shù)最少，這樣可以提高檢測(cè)粗差的能力。

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

對(duì)于最小獨(dú)立附合路線，也應(yīng)滿足上述3個(gè)條件，水準(zhǔn)網(wǎng)的獨(dú)立附合路線個(gè)數(shù)為：f=yd 1。顯然，需要計(jì)算往返較差或雙次同向觀測(cè)較差的觀測(cè)路線個(gè)數(shù)為：w=sgd。

那么，往返較差或雙次同向較差、獨(dú)立閉合環(huán)、獨(dú)立附合路線的總個(gè)數(shù)為：

這正好等于條件平差時(shí)條件方程式的個(gè)數(shù)。如圖1所示，A,C,F為已知點(diǎn)，其余點(diǎn)為未知點(diǎn)，觀測(cè)高差個(gè)數(shù)為gd=20,有往返測(cè)或雙次同向觀測(cè)的觀測(cè)邊個(gè)數(shù)為sgd=4，已知點(diǎn)個(gè)數(shù)為yd=3，未知點(diǎn)個(gè)數(shù)為wd=8。則獨(dú)立閉合環(huán)個(gè)數(shù)為b=(gd sgd)(yd+wd)+1=6，獨(dú)立附合路線個(gè)數(shù)為f=yd 1=2，往返觀測(cè)或雙次同向觀測(cè)路線個(gè)數(shù)為 w=sgd=4，總共需要計(jì)算的閉合差個(gè)數(shù)為b+f+w=gd w d=12。

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

2）閉合環(huán)與附合路線的相互轉(zhuǎn)化。水準(zhǔn)測(cè)量中，觀測(cè)路線實(shí)測(cè)高差與理論高差經(jīng)常不相符合，形成閉合差，具體可分為往返較差（或雙次同向觀測(cè)較差），環(huán)線閉合差和附合路線閉合差。設(shè) k1、k2為2個(gè)已知點(diǎn)，高程值分別為H1、H2,有1組觀測(cè)高差h1、h2、h3、…、hn。

若h1、h2的起點(diǎn)、終點(diǎn)相反（或相同），則往返較差（或雙次同向觀測(cè)較差）為：fh=±h1±h2；

若h1、h2、h3、…、hn起閉于k1點(diǎn)，則環(huán)線閉合差公式為：fh=±h1±h2±h3±…±hn；

若h1、h2、h3、…、hn起始于k1點(diǎn)，終止于k2點(diǎn)，則附合路線閉合差公式為：

式中，正負(fù)號(hào)取決于觀測(cè)路線的方向。由環(huán)線閉合差公式和附合路線閉合差公式可以看出，兩者有些類似，事實(shí)上，兩者可以相互轉(zhuǎn)化。如圖1所示，有路線A→B→C，其中A、C為已知點(diǎn)，B為未知點(diǎn)，設(shè)A、C的高程分別為HA、HC,則附合路線閉合差為fh=h1+h2（HCHA）。

若在A、C之間增加1條虛擬觀測(cè)值hAC，并令hAC= HCHA,方向?yàn)锳→C，A、C之間的距離設(shè)為SAC=0,C點(diǎn)變?yōu)槲粗c(diǎn)；則閉合路線A→B→C→A的環(huán)線閉合差公式為fh=h1+h2hAC=h1+h2（HCHA）。對(duì)于整個(gè)水準(zhǔn)網(wǎng)，未知點(diǎn)個(gè)數(shù)增加1，已知點(diǎn)個(gè)數(shù)減少1，獨(dú)立閉合環(huán)增加1，獨(dú)立附合路線減少1，觀測(cè)高差個(gè)數(shù)增加1，則總共需要計(jì)算的閉合差個(gè)數(shù)為 gd wd=12，保持不變。若重復(fù)下去，使水準(zhǔn)網(wǎng)已知點(diǎn)個(gè)數(shù)減少到1個(gè)，則整個(gè)網(wǎng)只需計(jì)算環(huán)線閉合差及往返較差。

同理，閉合環(huán)也可以轉(zhuǎn)化為附合路線。如圖 1所示，閉合環(huán)A→J→B→A中，閉合差為fh=-h1+h4h8,令A(yù)、B高程分別為HA，HB=h1+HA，則h1=HBHA,刪除高差 h1，則A→B的附和路線閉合差為fh=-h8+h4（HBHA）=-h8+h4h，如此，整個(gè)水準(zhǔn)網(wǎng)，未知點(diǎn)個(gè)數(shù)減少1，已知點(diǎn)個(gè)數(shù)增加1，獨(dú)立閉合環(huán)個(gè)數(shù)減少1，獨(dú)立附合路線個(gè)數(shù)增加1，需要計(jì)算的閉合差總數(shù)不變。

由以上可以看出，附合路線和閉合環(huán)聯(lián)系緊密，相同之處是都要搜索最小路徑（邊數(shù)最少，長(zhǎng)度最短），這使得設(shè)計(jì)算法時(shí)可以一起考慮。

3）最小路徑搜索法。為記錄水準(zhǔn)網(wǎng)中閉合環(huán)或附合路線搜索的路徑，需用“鄰接點(diǎn)”來表示，這里的鄰接點(diǎn)不同于數(shù)據(jù)結(jié)構(gòu)中的鄰接點(diǎn)。如圖 1所示，以A點(diǎn)作為源目標(biāo)點(diǎn)，尋找其他點(diǎn)到A點(diǎn)的最小路徑（邊數(shù)最少，距離最短）。網(wǎng)中B、J、H、I與A點(diǎn)直接相連，其余點(diǎn)沒有與A點(diǎn)直接相連，它們必須借助其他點(diǎn)才能與目標(biāo)點(diǎn)聯(lián)系。如果一個(gè)點(diǎn)借助另一個(gè)點(diǎn)與目標(biāo)點(diǎn)發(fā)生了聯(lián)系，稱另一個(gè)點(diǎn)是這個(gè)點(diǎn)的“鄰接點(diǎn)”[7]，如C點(diǎn)借助B點(diǎn)與A點(diǎn)發(fā)生了聯(lián)系，則C點(diǎn)的鄰接點(diǎn)為B。而B點(diǎn)的鄰接點(diǎn)為A，可以理解為B點(diǎn)通過A點(diǎn)與A點(diǎn)發(fā)生了聯(lián)系；同理A點(diǎn)的鄰接點(diǎn)為A。

根據(jù)最小獨(dú)立閉合環(huán)和最小獨(dú)立附合路線的條件，鄰接點(diǎn)也應(yīng)該唯一確定。例如，K點(diǎn)的鄰接點(diǎn)可以是B,也可以是J,則先判斷B，J到A點(diǎn)的邊數(shù)，邊數(shù)少的為K點(diǎn)的鄰接點(diǎn)。若邊數(shù)相同則判斷K→B→A與K→J→A的距離，距離短的為K的鄰接點(diǎn)。如此，一般情況下便可唯一確定鄰接點(diǎn)。

綜上所述，最小路徑搜索法可利用鄰接點(diǎn)標(biāo)記搜索路徑，利用 Dijkstra算法思想，設(shè)目標(biāo)點(diǎn)點(diǎn)號(hào)為 k,搜索各點(diǎn)到k點(diǎn)的最小路徑的具體計(jì)算流程如下：

①開辟3個(gè)數(shù)組：名為neighbor的數(shù)組，記錄每點(diǎn)的鄰接點(diǎn)號(hào)；名為edgen的數(shù)組，記錄每點(diǎn)到目標(biāo)點(diǎn)邊的個(gè)數(shù)；名為S的數(shù)組，記錄每點(diǎn)到目標(biāo)點(diǎn)的距離。其中neighbor（k）=k，edgen（k）=0，S(k)=0，其余各點(diǎn)neighbor數(shù)組的值為-1（表示沒有鄰接點(diǎn)），edgen數(shù)組和S數(shù)組值為100000（表示邊數(shù)和距離無窮大）。

②依次訪問每一個(gè)高差觀測(cè)值（若該觀測(cè)邊含有往返觀測(cè)或雙次同向觀測(cè)，則與當(dāng)前路線方向相反的高差觀測(cè)值或雙次同向觀測(cè)值中距離較長(zhǎng)者不參與最小路徑搜索），記錄后視點(diǎn)號(hào)（設(shè)為 p1）和前視點(diǎn)號(hào)（設(shè)為p2），兩點(diǎn)間的距離為s12，根據(jù)p1點(diǎn)和p2點(diǎn)到目標(biāo)點(diǎn)k的邊數(shù)e1和e2以及距離s1和s2，判斷p1是否可以作為p2的鄰接點(diǎn)以及p2是否可以作為p1的鄰接點(diǎn)。p1可以作為p2的鄰接點(diǎn)的條件是

p2可以作為p1的鄰接點(diǎn)的條件是

若 (1)式成立，則neighbor(p2)=p1，S(p2)=S (p1)+s12，edgen(p2)=edgen(p1)+1；若 (2)式成立，則neighbor(p1)=p2，S(p1)=S(p2)+s12，edgen(p1) =edgen(p2)+1。

③一般情況下，依次訪問每一個(gè)觀測(cè)值之后一些點(diǎn)到目標(biāo)點(diǎn)不是最小路徑，有些點(diǎn)還沒有找到鄰接點(diǎn)，這時(shí)需要重復(fù)步驟②，直到所有觀測(cè)高差均不再滿足式(1)及式 (2)，這時(shí)各點(diǎn)到目標(biāo)點(diǎn)的最小路徑搜索完成。

依據(jù)上述方法，可在計(jì)算機(jī)上編寫最小路徑搜索函數(shù)，為方便論述，設(shè)函數(shù)名為FindM inPath。

2 最小獨(dú)立閉合環(huán)及最小獨(dú)立附合路線的搜索

搜索最小獨(dú)立閉合環(huán)和最小獨(dú)立附合路線之前，應(yīng)先進(jìn)行觀測(cè)高差的往返較差檢查或雙次同向觀測(cè)高差較差檢查，并對(duì)有往返觀測(cè)的邊和雙次同向觀測(cè)的邊進(jìn)行標(biāo)記。

對(duì)于最小獨(dú)立附合路線，搜索過程如下：

1）已知點(diǎn)個(gè)數(shù)為 yd，已知點(diǎn)號(hào)依次為 0、1、2、…、yd 1。建立一個(gè)雙重循環(huán)，依次選取已知點(diǎn)i=0、1、2、…、yd 2。選取某一已知點(diǎn) i后，調(diào)用最小路徑搜索函數(shù)FindM inPath，搜索出任意其他點(diǎn)到i點(diǎn)的最小路徑。判斷剩余的點(diǎn)j=i+1，i+2，…，yd 1中到i點(diǎn)邊數(shù)最少，距離最短的點(diǎn)。設(shè)此點(diǎn)點(diǎn)號(hào)為 imin，則搜索出了一條最小路徑的附合路線，即從已知點(diǎn)i，經(jīng)過若干未知點(diǎn)到達(dá)已知點(diǎn)imin。

2）選取已知點(diǎn)i的下一個(gè)點(diǎn)，令i=i+1，繼續(xù)調(diào)用最小路徑搜索函數(shù)FindM inPath，在剩余的已知點(diǎn)中找到離i點(diǎn)邊數(shù)最少，距離最短的點(diǎn)，此時(shí)又搜索出一條最小路徑的附和路線；繼續(xù)選取下一已知點(diǎn)，令i=i+1；如此繼續(xù)直到已知點(diǎn) i=yd 2（包括此點(diǎn)），則共搜索出yd 1條最小獨(dú)立附合路線，搜索完畢。

如圖1所示，A→J→B→A為一條最小閉合環(huán)。最小閉合環(huán)搜索思路為：刪除高差h1，搜索A到B點(diǎn)的最小路徑，類似于搜索最小附和路線。易知最小路徑為A→J→B,與h1合并后即得到最小閉合環(huán)A→J→B→A。最小獨(dú)立閉合環(huán)的具體搜索過程為：

1）觀測(cè)高差個(gè)數(shù)為gd，各觀測(cè)高差序號(hào)為0、1、2、…、gd 1，依次遍歷各觀測(cè)高差。設(shè)選取觀測(cè)高差的序號(hào)為i=0，以前視點(diǎn)為目標(biāo)點(diǎn)調(diào)用最小路徑搜索函數(shù) FindM inPath，搜索出后視點(diǎn)到前視點(diǎn)的最小路徑，其中不參與搜索最小路徑的觀測(cè)高差序號(hào)為i。這樣搜索出了包括觀測(cè)高差i的最小閉合環(huán)。為保證最小閉合環(huán)是獨(dú)立的，對(duì)搜索出的最小閉合環(huán)各個(gè)觀測(cè)高差都標(biāo)記為已經(jīng)使用。

2）選擇下一個(gè)觀測(cè)高差，令 i=i+1。若這個(gè)觀測(cè)高差是雙次同向觀測(cè)高差中距離較長(zhǎng)者或已經(jīng)使用，則繼續(xù)選擇下一個(gè)觀測(cè)高差，否則以前視點(diǎn)為目標(biāo)點(diǎn)調(diào)用最小路徑搜索函數(shù) FindM inPath，限制條件與 1)中相同。若現(xiàn)在的觀測(cè)高差是往返觀測(cè)邊中的一個(gè)且最小路徑方向與當(dāng)前觀測(cè)高差異向，則退出，繼續(xù)選擇下一個(gè)觀測(cè)高差，否則此時(shí)就搜索到了包含觀測(cè)高差i的最小閉合環(huán)，如此下去直到遍歷各個(gè)觀測(cè)高差。最終搜索到的最小獨(dú)立閉合環(huán)的個(gè)數(shù)為b=水準(zhǔn)網(wǎng)邊數(shù)-水準(zhǔn)網(wǎng)點(diǎn)數(shù)+1。

3 算例分析

上面原理已經(jīng)用VisualBasic平臺(tái)編程實(shí)現(xiàn)，且已經(jīng)應(yīng)用于大量算例進(jìn)行驗(yàn)證。水準(zhǔn)網(wǎng)數(shù)據(jù)格式采用科傻 in1標(biāo)準(zhǔn)格式，讀入觀測(cè)文件后自動(dòng)計(jì)算已知點(diǎn)個(gè)數(shù)、未知點(diǎn)個(gè)數(shù)、觀測(cè)高差個(gè)數(shù)等。讀入圖1中的水準(zhǔn)網(wǎng)數(shù)據(jù)后界面如圖2所示。

圖2 水準(zhǔn)網(wǎng)閉合差檢查界面

由圖1可知，水準(zhǔn)網(wǎng)往返較差個(gè)數(shù)為4，獨(dú)立閉合環(huán)個(gè)數(shù)為6，獨(dú)立附合環(huán)個(gè)數(shù)為2，利用上述方法解算結(jié)果如表1所示。

表1 水準(zhǔn)網(wǎng)往返較差、最小獨(dú)立閉合環(huán)、最小獨(dú)立附合路線結(jié)果/mm

由表1可知，搜索的閉合環(huán)和附合路線個(gè)數(shù)均正確，且均是最小獨(dú)立閉合環(huán)或附合路線，其中附合路線F→E→C，往返較差A(yù)→H以及閉合環(huán)F→G→K→E→F閉合差超限。附合路線F→E→C和閉合環(huán)F→G→K→E→F有1條公共邊F-E，推斷F→E可能超限，由閉合環(huán)B→K→E→C→B閉合差沒有超限可判斷邊E→D觀測(cè)值是合格的，故推斷F→E超限，需重測(cè)。閉合環(huán)H→A→J→H閉合差合格，說明各邊均合格，而A→H的往返較差超限，說明觀測(cè)邊A-H中的距離較長(zhǎng)的觀測(cè)高差不合格，查看觀測(cè)文件后判斷出 H→A觀測(cè)高差超限，需重測(cè)。

又如，實(shí)測(cè)了某高速鐵路CPⅢ高程控制網(wǎng)，網(wǎng)形如圖3所示，網(wǎng)的長(zhǎng)度大約為20 km，其中觀測(cè)高差個(gè)數(shù)為1 414，有往返測(cè)的邊個(gè)數(shù)為363，已知點(diǎn)個(gè)數(shù)為21，未知點(diǎn)個(gè)數(shù)為688，用前面所述的方法成功搜索出了20條最小獨(dú)立附合路線，363條往返路線和343條最小獨(dú)立閉合環(huán)，以精密工程測(cè)量要求設(shè)置限差，結(jié)果全部合格，不需重測(cè)。

圖3 CPⅢ高程控制網(wǎng)示意圖

4 結(jié) 語(yǔ)

本文所提出的算法不僅簡(jiǎn)單易懂，而且只需已知點(diǎn)信息和觀測(cè)值信息即可編程實(shí)現(xiàn)，無需其他附加信息，自動(dòng)化程度高。根據(jù)閉合環(huán)和附合路線的特點(diǎn)，將兩者結(jié)合起來，不僅搜索出最小獨(dú)立閉合環(huán)，而且完整正確地搜索出最小獨(dú)立附合路線，最大限度地探測(cè)粗差并評(píng)定觀測(cè)結(jié)果的質(zhì)量。而且顧及到了CPⅢ高程控制網(wǎng)部分邊有往返測(cè)的特點(diǎn)，搜索閉合環(huán)和附合路線更科學(xué)，更易檢測(cè)粗差。另外，根據(jù)CPⅢ高程控制網(wǎng)的實(shí)例，觀測(cè)高差個(gè)數(shù)為1414個(gè)時(shí)搜索閉合環(huán)和附合路線只需10 s左右，說明此方法搜索速度較快。解算出的往返較差、最小閉合環(huán)和最小附合路線相互獨(dú)立，包含條件平差的所有信息，且使得系數(shù)矩陣最大程度的成為稀疏矩陣，可依此列立條件方程式進(jìn)行平差，提高水準(zhǔn)網(wǎng)的解題容量和速度。最后，本文所提出的方法原理也完全適用于GPS網(wǎng)，對(duì)平面網(wǎng)的角度閉合差、距離閉合差等的計(jì)算也有借鑒意義。

[1] 馬文靜，劉成龍.自動(dòng)計(jì)算水準(zhǔn)網(wǎng)中閉合差的圖論解決方法及應(yīng)用[J].鐵道勘察,2006（2）：10-11

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

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

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

[5] 劉曉云,張世娟,胡秀珍.水準(zhǔn)網(wǎng)閉合環(huán)自動(dòng)生成技術(shù)的研究[J].測(cè)繪技術(shù)裝備,2010,12(1):3-5

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

[7] 宋力杰.測(cè)量平差程序設(shè)計(jì)[M].北京:國(guó)防工業(yè)出版社,2009

Searching Algorithm of the Independence Minimal Closed Loop in CPⅢElevation Control Net

by LI Jianping

After the end of leveling survey,misclosure checking about the observed results of round trip difference,annexed line,closed loop is essential.CPⅢvertical control network form a unique network,part of its edges contain round trip measured and double observations,and it is a large control network(the observation side may contain thousands).According to the constraints of the smallest independent closed loop and the smallest independent annexed line,takinginto account the characteristics of the CPⅢvertical control network,and using the idea of the Dijkstra algorithm,this paper proposed the minimum path search method and achieved it by writing a program.In this paper,an example proved its correctness and efficiency.

minimum independent closed loop，minimum independent annexed routes，minimum path search method，misclosure

2012-07-12

P224

B

1672-4623(2012)06-0150-04

李建平，碩士，研究方向?yàn)榇蟮販y(cè)量學(xué)與測(cè)量工程。