基于深度優先搜索的最小獨立閉合環電算優化方法

閉合環的搜索和閉合差計算作為粗差探測重要方式之一，在工程控制網日漸龐大和復雜的情況下，其計算效率問題得以重視。在深度優先算法的基礎上，結合計算機編程特性，將深度優先遞歸算法改變為循環算法，避免函數調用的內存開銷，并對數據結構進行了相關優化，顯著提高了對大型控制網進行閉合環搜索的效率。

閉合環搜索； 深度優先； 程序優化； 遞歸算法

P217 A

［定稿日期］2022-05-12

［作者簡介］鄭健（1984—），男，碩士，高級工程師，主要從事高速鐵路工程測量和城市軌道交通監測測量工作。

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

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

1 深度優先算法進行閉合環搜索的常規流程及優化方法

1.1 深度優先算法的常規應用

深度優先算法是指在一個多節點的結構樹中，指定某頂點為起點，依次添加與其鏈接的下一層節點，直至節點深度不能增加為止。如圖1所示，以A點為起點的深度優先搜索順序為;A—B—D—C—E—G—F。

將深度優先算法用于閉合環搜索的具體實施過程：

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

對于一個控制網，其獨立閉合環個數為n=line-piont+1，其中Line為觀測邊數，Point為控制網中的點數，可將n作為閉合環搜索結束的判定條件。該過程利用最小獨立閉合環的某一邊開始對環進行搜索，并通過標記已經搜索過的邊避免重復搜索。

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

1.2 深度優先算法優化設計

基于深度優先遞歸算法在閉合環搜索中存在的不足，筆者對上述閉合環搜索過程進行了優化設計。

1.2.1 提高匹配效率

將控制網中以字符串格式存儲的點名匹配為整型，提高匹配效率。建立控制網點名與整數的匹配表，將字符串轉換為整型，可以減少搜索和中間過程的匹配時間，以及臨時文件存儲空間。待整網的閉合環搜索結束后，根據匹配表將搜索結果轉換為真實點名。

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

由于在深度優先搜索閉合環的過程中，每增加或減少一次搜索深度，都將訪問一次鄰接表，且需要查找父節點及其相鄰的子節點，若采用列表遍歷的方式，查找節點的時間復雜度均值為O（n/2），而字典查詢的時間復雜度為O（1），因此采用字典將相對減少鄰接表的查詢時間。

1.2.3 遞歸迭代算法轉換為循環算法

深度優先遞歸算法轉換為循環算法的關鍵是每查找一個閉合環，需建立一個存貯點號的列表標記該次搜索時網中節點的訪問情況。循環算法的具體步驟：

（1）聲明必要的過程變量：保存搜索節點的數組temp_road且默認等于需要進行搜索的觀測邊起點，記錄當前搜索深度的變量current_deep=0，標記網中各點在當前搜索中是否已經訪問的列表visit，列表長度為網點數，均默認為0。

（2）開始搜索：令temp_road中最后一個點為新的父節點為，從鄰接表中找出父節點對應的子節點，并開始遍歷子節點，若子節點在visit中的值不為0，表示已訪問，則跳過。當不為0時進入下一步并令遍歷過的子節點在visit中的值為1，current_deep加1。

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

（4）設定閉合環搜索截至條件。當所有觀測邊均被標記訪問或者搜索到的閉合環數量達到獨立閉合環數的要求時停止搜索，避免冗余搜索過程。

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

將深度優先閉合環搜索優化算法各步驟繪制為流程如圖2所示。

2 實驗驗證

根據本文所述對深度優先閉合環搜索方法的優化設計，筆者基于Python編程語言，進行水準網閉合環搜索的程序設計與編制，實現了水準網最小獨立閉合環的搜索以及閉合差計算與精度驗證功能。為了驗證優化后的算法在大型控制網中的計算效率是否有顯著提高，同樣對深度優先遞歸算法進行了程序編譯。筆者在基于i5雙核CPU、主頻1.6 GHz、內存為8 GB的筆記本電腦上進行對比計算實驗。

首先，采用科傻COSA示例水準網高差觀測文件［11］，分別對采用深度優先算法優化前、優化后的自編軟件進行計算效率測試，結果見表1。

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

其次，為了驗證本文所述的優化方法在大型控制網中閉合環搜索中的適用性，使用一段約60 km的CPIII高程網實測數據進行試算，并分別與鐵路工程測量中應用廣泛的多款平差軟件進行對比。該段CPIII控制網包括3 240個獨立高差觀測值、2 140個高程點、1 069個獨立閉合環。各類軟件與采用本文優化方法所編軟件的最終對比結果見表2。

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

3 結論

（1）針對目前大型控制網閉合環搜索效率較低的問題，本文對深度優先算法的編程實施過程進行了優化，將深度優先算法中閉合環搜索中常用的遞歸算法改為循環算法，并對搜索過程中涉及數據的數據結構及其存儲方式進行了優化和說明，并給出了適用于電算的深度優先優化算法詳細流程，且優化算法簡單、適用于各類編程語言。

（2）通過對優化后的算法進行編程，并由實測數據計算對比表明優化算法可大大降低時間、復雜度，提高閉合環搜索效率。

（3）通過自編軟件與鐵路控制網平差商用軟件試算對比表明，在大型控制網閉合環搜索中，本文所述對深度優先搜索方法的優化設計，可大幅提升運算效率，減少大型控制網的內業數據處理耗時。

參考文獻

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

［2］ 王鵬磊，劉長星，張健，等.基于改進的生成樹和余樹算法控制網最小獨立閉合環搜索算法研究［J］.大地測量與地球動力學，2014，34（1）：113-117.

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

［4］ 郭際明，王磊，羅年學，等.一種改進的測量控制網最小獨立環搜索算法［J］.武漢大學學報（信息科學版），2011，36（5）：593-595.

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

［6］ 游為，范東明，張云，等.水準網閉合差自動解算的新方法［J］.測繪工程，2007（5）：17-19.

［7］ 周凌焱，劉成龍，張強，等.基于深度和廣度優先算法相結合的閉合環自動搜索方法研究［J］.測繪工程，2014，23（5）：24-28+32.

［8］ 蔣宏飛，劉偉東，王文勝.一種自動搜索水準環及計算閉合差的方法研究［J］.測繪科學，2012，37（4）：202-203+212.

［9］ 鄒進貴，馮晨.控制網最小獨立閉合環搜索算法研究［J］.地理空間信息，2008，6（6）：97-99.

［10］ 秦昆，朱文武，高艷龍，等.最小獨立閉合環深度優先算法的一點改進［J］.測繪科學技術學報，2015，32（6）：551-554.

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