基于廣度優(yōu)先的最小獨(dú)立閉合環(huán)搜索及其實(shí)現(xiàn)

夏先勤

（安徽理工大學(xué)空間信息與測(cè)繪工程學(xué)院，安徽 淮南 232001）

水準(zhǔn)網(wǎng)路線環(huán)閉合差自動(dòng)檢核的第一步是找到最小獨(dú)立閉合環(huán)[1]。實(shí)現(xiàn)最小獨(dú)立閉合環(huán)自動(dòng)搜索的主要思想可以歸納為4類(lèi)：基于生成樹(shù)和余樹(shù)的思想[2]、基于深度優(yōu)先的思想[3]、基于廣度優(yōu)先的思想[4]、基于鄰接矩陣變換的思想[5]。本文詳細(xì)闡述了基于廣度優(yōu)先的最小獨(dú)立閉合環(huán)搜索算法，并在此基礎(chǔ)上采用Python（計(jì)算機(jī)編程語(yǔ)言）實(shí)現(xiàn)了水準(zhǔn)網(wǎng)最小獨(dú)立閉合環(huán)搜索及其閉合差檢核的程序設(shè)計(jì)。

1 基于廣度優(yōu)先的最小獨(dú)立閉合環(huán)搜索

基于廣度優(yōu)先的最小獨(dú)立閉合環(huán)搜索在更新鄰接點(diǎn)集合時(shí)將記錄所有的鄰接點(diǎn)，而不會(huì)判斷鄰接點(diǎn)是否被訪問(wèn)過(guò)[6]。以從無(wú)向圖G中搜索以頂點(diǎn)v1，v2，v3組成的最小獨(dú)立閉合環(huán)為例（見(jiàn)圖1），本文基于廣度優(yōu)先搜索的思想來(lái)實(shí)現(xiàn)最小獨(dú)立閉合環(huán)搜索的主要過(guò)程描述如下。

圖1 無(wú)向圖G

步驟一：在圖中選擇起始頂點(diǎn)v1，搜索層次k=1，搜索得到k=1層根節(jié)點(diǎn)v1的所有鄰接點(diǎn)組成的集合為

步驟二：搜索層次k=2，搜索得到k=2層根節(jié)點(diǎn)v2，v3，v5的鄰接點(diǎn)并將鄰接點(diǎn)集合更新為

在每個(gè)子集中刪除k=1層根節(jié)點(diǎn)，得到鄰接點(diǎn)集合為

步驟三：搜索層次k=3，以步驟二中搜索到的3個(gè)鄰接點(diǎn)子集為基礎(chǔ)，搜索得到k=3層根節(jié)點(diǎn)v2，v3，v4，v6的鄰接點(diǎn)并將鄰接點(diǎn)集合更新為

其中v2/v3表示v2或v3，v3/v5同理。

步驟四：此時(shí)n≥3，判斷是否形成最小獨(dú)立閉合環(huán)：步驟三所得到的集合的子集中，集合v1:v2:v3:{v1，v2，v4，v6}與集合v1:v3:v2:{v1，v3，v4}都包含有k=1層根節(jié)點(diǎn)v1；提取各層根節(jié)點(diǎn)組成集合{v1，v2，v3}，此時(shí)認(rèn)為搜索到了最小獨(dú)立閉合環(huán)，最小獨(dú)立閉合環(huán)的頂點(diǎn)即為v1，v2，v3。

2 基于Python的程序設(shè)計(jì)

2.1 水準(zhǔn)網(wǎng)數(shù)據(jù)的組織

將原始水準(zhǔn)網(wǎng)數(shù)據(jù)存儲(chǔ)在“.txt”文件中，已知點(diǎn)數(shù)據(jù)以“#”開(kāi)頭作為標(biāo)記；示例中已知點(diǎn)為F，其高程為11.414 m。已知點(diǎn)數(shù)據(jù)之后為測(cè)段數(shù)據(jù)，以第一個(gè)測(cè)段為例， “A”為測(cè)段后視點(diǎn)， “B”為測(cè)段前視點(diǎn)， “73.795”為測(cè)段高差（單位：m），“20.400”為測(cè)段長(zhǎng)度（單位：m）。水準(zhǔn)網(wǎng)數(shù)據(jù)格式示例如下。

采用Python內(nèi)置的 “.readlines()”函數(shù)將文本文件讀取到列表中，然后對(duì)列表中的每一行采用“.strip()”函數(shù)截取掉所有的回車(chē)字符，進(jìn)而采用“.split(‘ ’)”將得到的整行數(shù)據(jù)分割成元素列表。最終讀取到程序中的水準(zhǔn)網(wǎng)數(shù)據(jù)以二維列表的形式存儲(chǔ)，二維列表中的子列表按順序?qū)?yīng)著文本文件中的某一行。以水準(zhǔn)網(wǎng)數(shù)據(jù)格式示例中的前三行數(shù)據(jù)為例，程序讀取后會(huì)將其存儲(chǔ)為二維列表：[[‘F’，11.414]，[‘A’， ‘B’，73.795，20.400]，[‘A’， ‘D’，14.005，18.800]]。

2.2 程序算法

程序?qū)崿F(xiàn)的基本框架是基于廣度優(yōu)先的最小獨(dú)立閉合環(huán)搜索算法，但如果在程序?qū)崿F(xiàn)過(guò)程中僅采用基于廣度優(yōu)先的最小獨(dú)立閉合環(huán)搜索的話，在某些特殊情況下會(huì)遺漏最小獨(dú)立閉合環(huán)[7]。以無(wú)向圖G′的最小獨(dú)立閉合環(huán)搜索為例（見(jiàn)圖2），采用基于廣度優(yōu)先的最小獨(dú)立閉合環(huán)搜索算法進(jìn)行搜索時(shí)，無(wú)論是以{v1，v2，v3，v4，v5，v6，v7，v8}哪一個(gè)結(jié)點(diǎn)作為搜索的起始頂點(diǎn)，都只能搜索到{{v1，v5，v6},{v2，v6，v7},{v3，v7，v8},{v4，v5，v8}}這4個(gè)最小獨(dú)立閉合環(huán)中的一個(gè)，而中間四頂點(diǎn)的最小獨(dú)立閉合環(huán){v5，v6，v7，v8}將被遺漏[8]。

圖2 無(wú)向圖G'

為此，本文在具體程序?qū)崿F(xiàn)時(shí)在基于廣度優(yōu)先的最小獨(dú)立閉合環(huán)搜索算法中嵌入“深度搜索”的過(guò)程[9]，這一過(guò)程僅在當(dāng)前搜索到的最小獨(dú)立閉合環(huán)已經(jīng)存在的情況下執(zhí)行。進(jìn)行“深度搜索”的具體流程見(jiàn)圖3。

圖3 深度搜索流程圖

3 實(shí)例驗(yàn)證

為驗(yàn)證本文中所設(shè)計(jì)的算法的正確性與有效性，選取某次工程應(yīng)用中的二等水準(zhǔn)網(wǎng)實(shí)例數(shù)據(jù)對(duì)其進(jìn)行測(cè)試[10]。所選取的水準(zhǔn)網(wǎng)共有21個(gè)水準(zhǔn)點(diǎn)，37個(gè)測(cè)段，其中BM1，BM2，BM3，BM4與BM5為已知點(diǎn)，見(jiàn)圖4。

圖4 二等水準(zhǔn)網(wǎng)實(shí)例

通過(guò)自編程序?qū)?shù)據(jù)進(jìn)行處理，成功搜索到全部的17個(gè)最小獨(dú)立閉合環(huán)，經(jīng)檢核，水準(zhǔn)網(wǎng)中最小獨(dú)立閉合環(huán)的環(huán)線閉合差均滿(mǎn)足二等水準(zhǔn)測(cè)量的要求。運(yùn)行程序的計(jì)算機(jī)配置為Intel酷睿i5-8250U CPU，內(nèi)存頻率為2 133 MHz，平均運(yùn)行時(shí)間為0.01 s。為了進(jìn)一步驗(yàn)證搜索結(jié)果，采用傳統(tǒng)的COSA軟件進(jìn)行閉合差檢核也得到了相同的結(jié)果。

4 結(jié)束語(yǔ)

本文提出了基于廣度優(yōu)先的最小獨(dú)立閉合環(huán)搜索算法，針對(duì)基于單一的廣度優(yōu)先進(jìn)行最小獨(dú)立閉合環(huán)搜索時(shí)可能會(huì)遺漏最小獨(dú)立閉合環(huán)的問(wèn)題，在廣度優(yōu)先搜索中嵌入了“深度搜索”的過(guò)程，最后的實(shí)例驗(yàn)證表明本文提出的算法能夠在較短的時(shí)間內(nèi)正確搜索并完成水準(zhǔn)網(wǎng)的環(huán)閉合差檢核工作。只要稍加改進(jìn)，這一算法同樣也能夠應(yīng)用于GPS控制網(wǎng)和平面三角網(wǎng)的環(huán)閉合差檢核工作。