基于深度優(yōu)先搜索的最小獨(dú)立閉合環(huán)電算優(yōu)化方法

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

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

P217 A

［定稿日期］2022-05-12

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

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

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

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

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

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

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

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

1.2.1 提高匹配效率

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

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

由于在深度優(yōu)先搜索閉合環(huán)的過程中，每增加或減少一次搜索深度，都將訪問一次鄰接表，且需要查找父節(jié)點(diǎn)及其相鄰的子節(jié)點(diǎn)，若采用列表遍歷的方式，查找節(jié)點(diǎn)的時(shí)間復(fù)雜度均值為O（n/2），而字典查詢的時(shí)間復(fù)雜度為O（1），因此采用字典將相對減少鄰接表的查詢時(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)的訪問情況。循環(huán)算法的具體步驟：

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

（2）開始搜索：令temp_road中最后一個(gè)點(diǎn)為新的父節(jié)點(diǎn)為，從鄰接表中找出父節(jié)點(diǎn)對應(yīng)的子節(jié)點(diǎn)，并開始遍歷子節(jié)點(diǎn)，若子節(jié)點(diǎn)在visit中的值不為0，表示已訪問，則跳過。當(dāng)不為0時(shí)進(jìn)入下一步并令遍歷過的子節(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)的觀測邊中設(shè)置為已訪問；若不為終點(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)所有觀測邊均被標(biāo)記訪問或者搜索到的閉合環(huán)數(shù)量達(dá)到獨(dú)立閉合環(huán)數(shù)的要求時(shí)停止搜索，避免冗余搜索過程。

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

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

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

根據(jù)本文所述對深度優(yōu)先閉合環(huán)搜索方法的優(yōu)化設(shè)計(jì)，筆者基于Python編程語言，進(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ì)算效率是否有顯著提高，同樣對深度優(yōu)先遞歸算法進(jìn)行了程序編譯。筆者在基于i5雙核CPU、主頻1.6 GHz、內(nèi)存為8 GB的筆記本電腦上進(jìn)行對比計(jì)算實(shí)驗(yàn)。

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

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

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

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

3 結(jié)論

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

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

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

參考文獻(xiàn)

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

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

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

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

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

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

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

［8］ 蔣宏飛，劉偉東，王文勝.一種自動(dòng)搜索水準(zhǔn)環(huán)及計(jì)算閉合差的方法研究［J］.測繪科學(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］.測繪科學(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.