閉合環(huán)的搜索和閉合差計(jì)算作為粗差探測(cè)重要方式之一，在工程控制網(wǎng)日漸龐大和復(fù)雜的情況下，其計(jì)算效率問(wèn)題得以重視。在深度優(yōu)先算法的基礎(chǔ)上，結(jié)合計(jì)算機(jī)編程特性，將深度優(yōu)先遞歸算法改變?yōu)檠h(huán)算法，避免函數(shù)調(diào)用的內(nèi)存開(kāi)銷(xiāo)，并對(duì)數(shù)據(jù)結(jié)構(gòu)進(jìn)行了相關(guān)優(yōu)化，顯著提高了對(duì)大型控制網(wǎng)進(jìn)行閉合環(huán)搜索的效率。

閉合環(huán)搜索； 深度優(yōu)先； 程序優(yōu)化； 遞歸算法

P217 A

［定稿日期］2022-05-12

［作者簡(jiǎn)介］鄭健（1984—），男，碩士，高級(jí)工程師，主要從事高速鐵路工程測(cè)量和城市軌道交通監(jiān)測(cè)測(cè)量工作。

對(duì)于具有多余觀測(cè)值的測(cè)量數(shù)據(jù)而言，為了獲得準(zhǔn)確的測(cè)量結(jié)果，需要對(duì)測(cè)量數(shù)據(jù)進(jìn)行嚴(yán)密平差計(jì)算，而在嚴(yán)密平差前需要檢核觀測(cè)值的質(zhì)量，以避免由儀器、人員、環(huán)境等因素產(chǎn)生的粗差導(dǎo)致平差結(jié)果產(chǎn)生顯著性偏差。在工程控制網(wǎng)中，無(wú)論是水平角度觀測(cè)值還是水準(zhǔn)高差觀測(cè)值，閉合差檢查是對(duì)觀測(cè)值進(jìn)行粗差探測(cè)最簡(jiǎn)便和直觀的方法。而今，由于控制網(wǎng)的復(fù)雜程度的逐漸增大，觀測(cè)值的數(shù)量更是大幅增加，尤其是鐵路軌道控制網(wǎng)（簡(jiǎn)稱CPIII網(wǎng)），其動(dòng)輒20～30 km長(zhǎng)度的網(wǎng)型對(duì)工程控制網(wǎng)平差軟件來(lái)講，是不小的挑戰(zhàn)。因此，如何有效提升閉合環(huán)的搜索速率，從而快速剔除觀測(cè)值粗差，是本文重點(diǎn)討論的問(wèn)題。

趙一晗等［1］對(duì)臨接矩陣變換、生成樹(shù)和余樹(shù)、深度優(yōu)先這3種常見(jiàn)的閉合環(huán)搜索算法進(jìn)行了詳細(xì)介紹，并得出結(jié)論：對(duì)于大型控制網(wǎng)，深度優(yōu)先算法具有更高的效率。由于使用場(chǎng)景的不同，王鵬磊等［2-4］對(duì)生成樹(shù)和余樹(shù)進(jìn)行優(yōu)化，使其在算法的穩(wěn)定性和效率上取得了一定的進(jìn)步。游為等［5-6］將臨接矩陣變換方法進(jìn)一步改進(jìn)，利用條件方程構(gòu)造信息矩陣來(lái)進(jìn)行閉合環(huán)搜索以及閉合差的計(jì)算。但在超大型控制網(wǎng)的閉合環(huán)搜索效率上，上述2種方法仍與深度優(yōu)先搜索法有一定差距。因此本文將基于深度優(yōu)先方法在理論和程序設(shè)計(jì)上對(duì)閉合環(huán)線路搜索進(jìn)行優(yōu)化。

1 深度優(yōu)先算法進(jìn)行閉合環(huán)搜索的常規(guī)流程及優(yōu)化方法

1.1 深度優(yōu)先算法的常規(guī)應(yīng)用

深度優(yōu)先算法是指在一個(gè)多節(jié)點(diǎn)的結(jié)構(gòu)樹(shù)中，指定某頂點(diǎn)為起點(diǎn)，依次添加與其鏈接的下一層節(jié)點(diǎn)，直至節(jié)點(diǎn)深度不能增加為止。如圖1所示，以A點(diǎn)為起點(diǎn)的深度優(yōu)先搜索順序?yàn)?A—B—D—C—E—G—F。

將深度優(yōu)先算法用于閉合環(huán)搜索的具體實(shí)施過(guò)程：

首先，創(chuàng)建存儲(chǔ)觀測(cè)邊起終點(diǎn)的二維列表以及空列表用于存儲(chǔ)搜索結(jié)果。其次，創(chuàng)建整網(wǎng)的鄰接表，遍歷網(wǎng)中各點(diǎn)及其子節(jié)點(diǎn)存放于二維列表。從第一條觀測(cè)邊開(kāi)始，搜索由該邊組成的最小閉合環(huán)。從該邊的終點(diǎn)出發(fā)，搜索至線路起點(diǎn)，并建立列表存儲(chǔ)搜索過(guò)程的節(jié)點(diǎn)。在這一過(guò)程中，應(yīng)設(shè)置并依次增加搜索深度，當(dāng)所在的節(jié)點(diǎn)不是目標(biāo)點(diǎn)，則向更深處（即子節(jié)點(diǎn)）進(jìn)行搜索，其實(shí)際搜索深度加1，若自身已沒(méi)有子節(jié)點(diǎn)或者搜索深度超過(guò)限定深度時(shí)，退回至其父節(jié)點(diǎn)，實(shí)際搜索深度減1。這一過(guò)程通常采用遞歸的形式進(jìn)行［7-8］。當(dāng)搜索到閉合環(huán)時(shí)，將該閉合環(huán)的所有邊進(jìn)行標(biāo)記，表明該邊已進(jìn)行過(guò)搜索。然后從觀測(cè)邊中找尋未訪問(wèn)過(guò)的邊，繼續(xù)進(jìn)行閉合環(huán)搜索過(guò)程。直到搜索的閉合環(huán)數(shù)量達(dá)到獨(dú)立閉合環(huán)數(shù)，或者網(wǎng)中所有的邊均被標(biāo)記訪問(wèn)。

對(duì)于一個(gè)控制網(wǎng)，其獨(dú)立閉合環(huán)個(gè)數(shù)為n=line-piont+1，其中Line為觀測(cè)邊數(shù)，Point為控制網(wǎng)中的點(diǎn)數(shù)，可將n作為閉合環(huán)搜索結(jié)束的判定條件。該過(guò)程利用最小獨(dú)立閉合環(huán)的某一邊開(kāi)始對(duì)環(huán)進(jìn)行搜索，并通過(guò)標(biāo)記已經(jīng)搜索過(guò)的邊避免重復(fù)搜索。

在搜索過(guò)程中，當(dāng)搜索深度加深時(shí)，閉合環(huán)搜索的時(shí)間將占整個(gè)搜索過(guò)程中的主要部分。所以有必要考慮其效率。眾所周知，遞歸算法雖然編程邏輯清晰，但是由于需要重復(fù)調(diào)用遞歸函數(shù)以及堆棧處理，將占用大量?jī)?nèi)存以分配變量、參數(shù)、返回值等。雖然可以通過(guò)使用用戶棧減少公共數(shù)據(jù)的初始化，且部分語(yǔ)言的編譯器在優(yōu)化后，對(duì)于多次調(diào)用的函數(shù)處理會(huì)有比較好的效率優(yōu)化，但遞歸函數(shù)的時(shí)間復(fù)雜度和空間復(fù)雜度隨著遞歸深度的增加幾乎不可控，僅通過(guò)數(shù)據(jù)結(jié)構(gòu)等優(yōu)化也并未改變遞歸的實(shí)質(zhì)。

1.2 深度優(yōu)先算法優(yōu)化設(shè)計(jì)

基于深度優(yōu)先遞歸算法在閉合環(huán)搜索中存在的不足，筆者對(duì)上述閉合環(huán)搜索過(guò)程進(jìn)行了優(yōu)化設(shè)計(jì)。

1.2.1 提高匹配效率

將控制網(wǎng)中以字符串格式存儲(chǔ)的點(diǎn)名匹配為整型，提高匹配效率。建立控制網(wǎng)點(diǎn)名與整數(shù)的匹配表，將字符串轉(zhuǎn)換為整型，可以減少搜索和中間過(guò)程的匹配時(shí)間，以及臨時(shí)文件存儲(chǔ)空間。待整網(wǎng)的閉合環(huán)搜索結(jié)束后，根據(jù)匹配表將搜索結(jié)果轉(zhuǎn)換為真實(shí)點(diǎn)名。

1.2.2 采用Hashtable（如字典）保存鄰接表

由于在深度優(yōu)先搜索閉合環(huán)的過(guò)程中，每增加或減少一次搜索深度，都將訪問(wèn)一次鄰接表，且需要查找父節(jié)點(diǎn)及其相鄰的子節(jié)點(diǎn)，若采用列表遍歷的方式，查找節(jié)點(diǎn)的時(shí)間復(fù)雜度均值為O（n/2），而字典查詢的時(shí)間復(fù)雜度為O（1），因此采用字典將相對(duì)減少鄰接表的查詢時(shí)間。

1.2.3 遞歸迭代算法轉(zhuǎn)換為循環(huán)算法

深度優(yōu)先遞歸算法轉(zhuǎn)換為循環(huán)算法的關(guān)鍵是每查找一個(gè)閉合環(huán)，需建立一個(gè)存貯點(diǎn)號(hào)的列表標(biāo)記該次搜索時(shí)網(wǎng)中節(jié)點(diǎn)的訪問(wèn)情況。循環(huán)算法的具體步驟：

（1）聲明必要的過(guò)程變量：保存搜索節(jié)點(diǎn)的數(shù)組temp_road且默認(rèn)等于需要進(jìn)行搜索的觀測(cè)邊起點(diǎn)，記錄當(dāng)前搜索深度的變量current_deep=0，標(biāo)記網(wǎng)中各點(diǎn)在當(dāng)前搜索中是否已經(jīng)訪問(wèn)的列表visit，列表長(zhǎng)度為網(wǎng)點(diǎn)數(shù)，均默認(rèn)為0。

（2）開(kāi)始搜索：令temp_road中最后一個(gè)點(diǎn)為新的父節(jié)點(diǎn)為，從鄰接表中找出父節(jié)點(diǎn)對(duì)應(yīng)的子節(jié)點(diǎn)，并開(kāi)始遍歷子節(jié)點(diǎn)，若子節(jié)點(diǎn)在visit中的值不為0，表示已訪問(wèn)，則跳過(guò)。當(dāng)不為0時(shí)進(jìn)入下一步并令遍歷過(guò)的子節(jié)點(diǎn)在visit中的值為1，current_deep加1。

（3）判斷子節(jié)點(diǎn)是否為終點(diǎn)：若為終點(diǎn)，且current_deep等于設(shè)置的閉合環(huán)搜索深度，則添加子節(jié)點(diǎn)到temp_road中，退出循環(huán)算法，temp_road中保存的節(jié)點(diǎn)即為閉合環(huán)路徑，將閉合路徑中的各邊在網(wǎng)的觀測(cè)邊中設(shè)置為已訪問(wèn)；若不為終點(diǎn)，且current_deep的值小于設(shè)置的搜索深度，將子節(jié)點(diǎn)加入temp_road，跳出當(dāng)前循環(huán)遍歷，進(jìn)入步驟2。若在設(shè)置的搜索深度下，遍歷完當(dāng)前父節(jié)點(diǎn)的最后一個(gè)子節(jié)點(diǎn)，任未找到終點(diǎn)，則取出temp_road中的最后一個(gè)點(diǎn)，令current_deep減1，再次進(jìn)入步驟2，直至搜索到路徑或者temp_road為空。

（4）設(shè)定閉合環(huán)搜索截至條件。當(dāng)所有觀測(cè)邊均被標(biāo)記訪問(wèn)或者搜索到的閉合環(huán)數(shù)量達(dá)到獨(dú)立閉合環(huán)數(shù)的要求時(shí)停止搜索，避免冗余搜索過(guò)程。

（5）深度優(yōu)先算法缺陷優(yōu)化。鄒進(jìn)貴等［9］嚴(yán)密論證了對(duì)于部分特殊網(wǎng)型采用深度優(yōu)先搜索時(shí)，獨(dú)立環(huán)搜索不完全的問(wèn)題，秦昆等［10］提出了一種便于實(shí)施改進(jìn)辦法：由于閉合環(huán)搜索不全的特殊情況只在個(gè)別獨(dú)立環(huán)被其他閉合環(huán)包圍時(shí)才會(huì)發(fā)生，由于被包圍的閉合環(huán)其所有觀測(cè)邊均被訪問(wèn)過(guò)，因此無(wú)法進(jìn)行搜索，但該環(huán)的所有邊的訪問(wèn)次數(shù)均為1。所以，可在搜索時(shí)標(biāo)記各邊被訪問(wèn)的次數(shù)，當(dāng)所有邊都訪問(wèn)超過(guò)1次但獨(dú)立環(huán)個(gè)數(shù)不足時(shí)，從訪問(wèn)次數(shù)最小的邊開(kāi)始，再次進(jìn)行閉合環(huán)搜索，當(dāng)該次搜索結(jié)果不在搜索結(jié)果中時(shí)，加入搜索結(jié)果。

將深度優(yōu)先閉合環(huán)搜索優(yōu)化算法各步驟繪制為流程如圖2所示。

2 實(shí)驗(yàn)驗(yàn)證

根據(jù)本文所述對(duì)深度優(yōu)先閉合環(huán)搜索方法的優(yōu)化設(shè)計(jì)，筆者基于Python編程語(yǔ)言，進(jìn)行水準(zhǔn)網(wǎng)閉合環(huán)搜索的程序設(shè)計(jì)與編制，實(shí)現(xiàn)了水準(zhǔn)網(wǎng)最小獨(dú)立閉合環(huán)的搜索以及閉合差計(jì)算與精度驗(yàn)證功能。為了驗(yàn)證優(yōu)化后的算法在大型控制網(wǎng)中的計(jì)算效率是否有顯著提高，同樣對(duì)深度優(yōu)先遞歸算法進(jìn)行了程序編譯。筆者在基于i5雙核CPU、主頻1.6 GHz、內(nèi)存為8 GB的筆記本電腦上進(jìn)行對(duì)比計(jì)算實(shí)驗(yàn)。

首先，采用科傻COSA示例水準(zhǔn)網(wǎng)高差觀測(cè)文件［11］，分別對(duì)采用深度優(yōu)先算法優(yōu)化前、優(yōu)化后的自編軟件進(jìn)行計(jì)算效率測(cè)試，結(jié)果見(jiàn)表1。

從表1看出，優(yōu)化后的深度優(yōu)先循環(huán)方法計(jì)算效率明顯高于優(yōu)化前。由于Python為解釋型語(yǔ)言，其循環(huán)和編譯效率遠(yuǎn)低于C#、Java等語(yǔ)言，因此在進(jìn)行算法優(yōu)化時(shí)，可以明顯地判斷算法的優(yōu)化對(duì)于整個(gè)搜索過(guò)程效率的提升。

其次，為了驗(yàn)證本文所述的優(yōu)化方法在大型控制網(wǎng)中閉合環(huán)搜索中的適用性，使用一段約60 km的CPIII高程網(wǎng)實(shí)測(cè)數(shù)據(jù)進(jìn)行試算，并分別與鐵路工程測(cè)量中應(yīng)用廣泛的多款平差軟件進(jìn)行對(duì)比。該段CPIII控制網(wǎng)包括3 240個(gè)獨(dú)立高差觀測(cè)值、2 140個(gè)高程點(diǎn)、1 069個(gè)獨(dú)立閉合環(huán)。各類(lèi)軟件與采用本文優(yōu)化方法所編軟件的最終對(duì)比結(jié)果見(jiàn)表2。

通過(guò)與HRMAS、鐵四院平差軟件、中鐵咨詢平差軟件對(duì)比的測(cè)試數(shù)據(jù)結(jié)果，可得：自編軟件的搜索結(jié)果正確，各類(lèi)指標(biāo)與商業(yè)軟件完全一致；其次，在大型控制網(wǎng)閉合環(huán)搜索中，基于深度優(yōu)先優(yōu)化算法的自編軟件計(jì)算效率較各類(lèi)鐵路工程測(cè)量軟件有明顯的優(yōu)勢(shì)，且自編軟件僅對(duì)算法和數(shù)據(jù)結(jié)構(gòu)進(jìn)行了上文所述的優(yōu)化，并未進(jìn)行任何基于計(jì)算機(jī)硬件的提速操作。

3 結(jié)論

（1）針對(duì)目前大型控制網(wǎng)閉合環(huán)搜索效率較低的問(wèn)題，本文對(duì)深度優(yōu)先算法的編程實(shí)施過(guò)程進(jìn)行了優(yōu)化，將深度優(yōu)先算法中閉合環(huán)搜索中常用的遞歸算法改為循環(huán)算法，并對(duì)搜索過(guò)程中涉及數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)及其存儲(chǔ)方式進(jìn)行了優(yōu)化和說(shuō)明，并給出了適用于電算的深度優(yōu)先優(yōu)化算法詳細(xì)流程，且優(yōu)化算法簡(jiǎn)單、適用于各類(lèi)編程語(yǔ)言。

（2）通過(guò)對(duì)優(yōu)化后的算法進(jìn)行編程，并由實(shí)測(cè)數(shù)據(jù)計(jì)算對(duì)比表明優(yōu)化算法可大大降低時(shí)間、復(fù)雜度，提高閉合環(huán)搜索效率。

（3）通過(guò)自編軟件與鐵路控制網(wǎng)平差商用軟件試算對(duì)比表明，在大型控制網(wǎng)閉合環(huán)搜索中，本文所述對(duì)深度優(yōu)先搜索方法的優(yōu)化設(shè)計(jì)，可大幅提升運(yùn)算效率，減少大型控制網(wǎng)的內(nèi)業(yè)數(shù)據(jù)處理耗時(shí)。

參考文獻(xiàn)

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

［2］ 王鵬磊，劉長(zhǎng)星，張健，等.基于改進(jìn)的生成樹(shù)和余樹(shù)算法控制網(wǎng)最小獨(dú)立閉合環(huán)搜索算法研究［J］.大地測(cè)量與地球動(dòng)力學(xué)，2014，34（1）：113-117.

［3］ 馬洪磊，劉成龍，余樂(lè)義，等.一種高效的最小獨(dú)立閉合環(huán)自動(dòng)搜索算法［J］.測(cè)繪工程，2014，23（8）：70-72+80.

［4］ 郭際明，王磊，羅年學(xué)，等.一種改進(jìn)的測(cè)量控制網(wǎng)最小獨(dú)立環(huán)搜索算法［J］.武漢大學(xué)學(xué)報(bào)（信息科學(xué)版），2011，36（5）：593-595.

［5］ 游為，范東明，付淑娟.最短獨(dú)立閉合環(huán)與附合路線的快速搜索方法［J］.測(cè)繪科學(xué)，2009，34（4）：139-140+100.

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

［7］ 周凌焱，劉成龍，張強(qiáng)，等.基于深度和廣度優(yōu)先算法相結(jié)合的閉合環(huán)自動(dòng)搜索方法研究［J］.測(cè)繪工程，2014，23（5）：24-28+32.

［8］ 蔣宏飛，劉偉東，王文勝.一種自動(dòng)搜索水準(zhǔn)環(huán)及計(jì)算閉合差的方法研究［J］.測(cè)繪科學(xué)，2012，37（4）：202-203+212.

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

［10］ 秦昆，朱文武，高艷龍，等.最小獨(dú)立閉合環(huán)深度優(yōu)先算法的一點(diǎn)改進(jìn)［J］.測(cè)繪科學(xué)技術(shù)學(xué)報(bào)，2015，32（6）：551-554.

［11］ 李建平，明祖濤，張屆，等.CPⅢ高程網(wǎng)最小獨(dú)立閉合環(huán)的一種搜索算法［J］.地理空間信息，2012，10（6）：150-153+1+16.