李耀東，苗春艷，高 健，劉辛垚

（1.呼倫貝爾市氣象局，內(nèi)蒙古 呼倫貝爾 021008；2.呼倫貝爾市阿榮旗氣象局，內(nèi)蒙古 呼倫貝爾 162700；3.烏蘭浩特市氣象局，內(nèi)蒙古 烏蘭浩特 137400）

0 引言

路徑規(guī)劃問題可以被形式化為在一個離散或連續(xù)的狀態(tài)空間中找到一條從起點(diǎn)到終點(diǎn)的最優(yōu)路徑。路徑規(guī)劃在很多領(lǐng)域都具有廣泛的應(yīng)用，如：在高新科技領(lǐng)域包括無人機(jī)的避障飛行、導(dǎo)彈躲避雷達(dá)搜索、突防爆破等；在日常生活領(lǐng)域包括GPS 導(dǎo)航、道路規(guī)劃等；在決策領(lǐng)域包括物流管理中的車輛問題（VRP)等；通信技術(shù)領(lǐng)域的路由問題；等等。凡是可拓?fù)錇辄c(diǎn)線網(wǎng)絡(luò)的規(guī)劃問題基本上都可以采用路徑規(guī)劃的方法來解決[1]。

路徑規(guī)劃的核心就是算法的設(shè)計，路徑規(guī)劃算法目前已經(jīng)得到了廣泛的關(guān)注，算法更加智能[2]。根據(jù)對環(huán)境信息的把握程度，可把路徑規(guī)劃劃分為基于先驗(yàn)完全信息的全局路徑規(guī)劃和基于傳感器信息的局部路徑規(guī)劃兩種類型[3?5]。最小生成樹（MST）作為圖論中最經(jīng)典的算法之一，由于具有諸多優(yōu)勢，在規(guī)劃、網(wǎng)絡(luò)和醫(yī)學(xué)等各個領(lǐng)域的路徑規(guī)劃中得到了廣泛的應(yīng)用[6]。在最小生成樹算法中，Prim 算法給出了一個尋找最小生成樹的算法，適用于稠密圖，并能夠?qū)⑶蠼獾臅r間復(fù)雜度最小化[7]。

本文主要研究Prim 算法的路徑規(guī)劃，屬于靜態(tài)路徑規(guī)劃范疇。

1 算法概述

圖論中將連通所有站點(diǎn)的無向圖稱為生成樹，最小生成樹是一幅有加權(quán)但是無方向的最小連通子圖。

在一個給定的無向圖G=（V,E）中，（u,v）∈E，代表連接頂點(diǎn)u和v的邊，w（u,v）代表此邊的權(quán)重，若T?E，即存在T為E的子集，且（V,T）為樹，使得w（T）=Σ（u,v）最小，則此T為G的最小生成樹。

Prim 算法由美國計算機(jī)科學(xué)家羅伯特·普林（Robert Prim）在1957 年提出，它是求解無向帶權(quán)圖的最小生成樹的經(jīng)典算法，可以應(yīng)用于網(wǎng)絡(luò)設(shè)計、城市規(guī)劃、交通規(guī)劃等領(lǐng)域。該算法最初是為了解決通信網(wǎng)絡(luò)中的連通性問題而設(shè)計的，后來被廣泛應(yīng)用于圖論領(lǐng)域，特別是最小生成樹問題。

Prim 算法是一種貪婪算法，用于查找加權(quán)無向圖的最小生成樹。其主要思想是以點(diǎn)選邊，適用于稠密圖。Prim 算法首先從任意頂點(diǎn)開始，然后向樹中添加權(quán)重值最小的邊，這個最小的邊的另一端頂點(diǎn)尚未在樹中，若已在樹中則將該邊舍去，從余下的邊中再選最小的邊進(jìn)行添加，直到所有頂點(diǎn)都在樹中。Prim 算法的關(guān)鍵是在每一步做出局部最優(yōu)選擇，從而找到全局最優(yōu)解，這種貪婪的策略保證了最終樹是最小生成樹[8?9]。

如圖1 所示，5 個頂點(diǎn)A、B、C、D和E之間的邊帶有權(quán)重，用數(shù)字表示，各頂點(diǎn)間的權(quán)重如表1 所示。

表1 各頂點(diǎn)間權(quán)重計算表

圖1 Prim 算法示例圖

由表1 可知，采用Prim 算法計算的最小生成樹是連接所有頂點(diǎn)的最小成本路徑，這個路徑的總成本是1+2+5+3=11。原始Prim 算法時間復(fù)雜度為O（V2），其中V是節(jié)點(diǎn)的數(shù)量，因?yàn)樵诿恳徊街行枰闅v所有與最小生成樹相鄰的節(jié)點(diǎn)以找到距離最短的節(jié)點(diǎn)。

除了Prim 算法，還有其他求解最小生成樹問題的算法，比如Kruskal 算法[10]等，但這些算法各有優(yōu)缺點(diǎn)。

2 改進(jìn)的Prim 算法

2.1 算法的改進(jìn)

在實(shí)際應(yīng)用中，Prim 算法存在一些缺點(diǎn)，例如對于大規(guī)模稠密圖，其時間復(fù)雜度較高，且在圖的結(jié)構(gòu)發(fā)生變化時，需要重新計算整個最小生成樹。為了解決這些問題，學(xué)者們提出了一系列改進(jìn)Prim 算法的方法：一種改進(jìn)是使用堆來維護(hù)所有與最小生成樹相鄰的節(jié)點(diǎn)，以便快速找到距離最短的節(jié)點(diǎn)；另一種改進(jìn)是使用斐波那契堆來維護(hù)所有與最小生成樹相鄰的節(jié)點(diǎn)[11?13]，其中最為重要的是基于聚類分析的改進(jìn)。聚類分析是一種無監(jiān)督學(xué)習(xí)算法，主要用于處理無標(biāo)簽數(shù)據(jù)。聚類分析的目的是通過將相似的數(shù)據(jù)點(diǎn)分為一組來形成聚類，從而有助于了解數(shù)據(jù)的內(nèi)在結(jié)構(gòu)，識別異常數(shù)據(jù)，找到數(shù)據(jù)中的模式等。雖然Prim 算法和聚類分析在處理數(shù)據(jù)類型和目的上有所不同，但它們都是數(shù)據(jù)分析領(lǐng)域中非常重要的算法。在實(shí)際應(yīng)用中，可以將它們結(jié)合起來使用，比如通過聚類分析對數(shù)據(jù)進(jìn)行分類后，再使用Prim算法構(gòu)建聚類中心之間的最小生成樹，以便更好地了解數(shù)據(jù)之間的關(guān)系和結(jié)構(gòu)[14]。本文探討如何將這兩種算法結(jié)合起來，計算聚類分析中的最小生成樹。

下面是使用聚類分析改進(jìn)的Prim 算法最小生成樹的基本步驟：

1）將所有節(jié)點(diǎn)分成若干個聚類；

2）選取一個聚類中心點(diǎn)作為起始點(diǎn)；

3）找到與該點(diǎn)最相似的另一個聚類中心點(diǎn)，將其作為下一個點(diǎn)；

4）對于其他尚未加入最小生成樹的聚類中心點(diǎn)，計算它們與最小生成樹上所有點(diǎn)之間的相似度，并選擇其中最小的那個點(diǎn)作為下一個點(diǎn)；

5）將新加入的點(diǎn)與最小生成樹上已有的點(diǎn)連接起來，形成一條邊，并將其加入最小生成樹；

6）重復(fù)步驟4）、步驟5），直到所有聚類中心點(diǎn)都被加入到最小生成樹中為止。

通過構(gòu)建聚類中心之間的Prim 最小生成樹，對稠密圖路徑規(guī)劃復(fù)雜性進(jìn)行分解，還可以以多個聚類中心為基點(diǎn)，再聚類構(gòu)建更小范圍的Prim 最小生成樹，有助于進(jìn)行路徑規(guī)劃數(shù)據(jù)的分析和決策。

2.2 改進(jìn)算法的局部最優(yōu)

使用改進(jìn)的Prim 算法計算無向圖的最小生成樹，將最小生成樹劃分成若干個簇，其中每個簇對應(yīng)于一條或多條連接相似節(jié)點(diǎn)的路徑。下面用一個簡單的例子來說明聚類分析改進(jìn)的Prim 算法的實(shí)現(xiàn)過程，如圖2所示。

圖2 聚類中心最小生成樹

如圖2 所示，構(gòu)建一個包含6 個節(jié)點(diǎn)的最小生成樹。首先，將每個節(jié)點(diǎn)看作一個聚類，并計算節(jié)點(diǎn)之間的距離；然后，按照距離度量的大小，將最小的兩個聚類合并成一個新的聚類；接著，繼續(xù)按照距離度量的大小，將最小的兩個聚類合并成一個新的聚類；最終，得到整個圖的最小生成樹。有6 個聚類中心，分別是：C1、C2、C3、C4、C5和C6，這些聚類中心之間連接了一些邊，這些邊的權(quán)重是一個正整數(shù)。這些邊被用于構(gòu)建最小生成樹，是連接所有聚類中心的最小成本路徑。在最小生成樹問題中，聚類分析可以用來快速判斷兩個節(jié)點(diǎn)之間是否連通，并將節(jié)點(diǎn)分成若干個聚類，從而減少Prim 算法的計算量。通過聚類分析的改進(jìn)，Prim 算法的時間復(fù)雜度得到了大大優(yōu)化，尤其是在處理大規(guī)模稠密圖時，其效果更加明顯。此外，基于聚類分析的改進(jìn)Prim 算法還具有較強(qiáng)的魯棒性，能夠適應(yīng)圖的結(jié)構(gòu)變化。

3 路徑規(guī)劃實(shí)踐

3.1 原路徑規(guī)劃

目前，呼倫貝爾市各類自動氣象站遍布全市各個鄉(xiāng)鎮(zhèn)，如圖3 所示。利用歐幾里德距離公式，以站網(wǎng)中各站點(diǎn)經(jīng)緯度計算各站間距，以各站間距為站點(diǎn)間邊界的權(quán)重計算原Prim 最小生成樹，如圖4 所示。

圖3 呼倫貝爾市氣象站點(diǎn)分布圖

圖4 原Prim 最小生成樹分布圖

由圖3、圖4 可知，經(jīng)過在地理信息系統(tǒng)Arcgis 上計算，原Prim 最小生成樹連通的全部站點(diǎn)的連通路徑長度為5 178 km。呼倫貝爾市氣象站網(wǎng)中站點(diǎn)分布零散，僅在縣（區(qū)）域政府周邊站點(diǎn)路徑集中，圖上有明顯的連通中心，位于呼倫貝爾市中部。原Prim 最小生成樹雖對站點(diǎn)路徑連通情況做了初步規(guī)劃，但對站網(wǎng)中站點(diǎn)分布狀態(tài)并沒有量化的判別，站點(diǎn)分布狀態(tài)判別只是以定性判別為主。

3.2 路徑再規(guī)劃

3.2.1 K?Means 聚類分析

利用K?Means 算法將呼倫貝爾市氣象站網(wǎng)進(jìn)行聚類劃分，計算站點(diǎn)與類簇質(zhì)心的距離，與類簇質(zhì)心相近的站點(diǎn)劃分為同一類簇。通過站點(diǎn)間的距離來衡量它們之間的相似度，兩個站點(diǎn)距離越遠(yuǎn)，則相似度越低；否則，相似度越高。由圖3、圖4 可知，呼倫貝爾市氣象站網(wǎng)中站點(diǎn)分布既有密較集的中心區(qū)，又有孤立的站點(diǎn)，通過聚類分析可以很好地將站點(diǎn)密集區(qū)與孤立站點(diǎn)定量化表示出來。為達(dá)到上述目的，在K?Means 聚類分析中以二分法不斷遞減選擇站點(diǎn)聚類中心（n為站點(diǎn)個數(shù)，X為指數(shù)，偶數(shù)時聚類中心個數(shù)為n×2-X，奇數(shù)時聚類中心個數(shù)為n×2-X+1），因站網(wǎng)中站點(diǎn)個數(shù)為313 個，所以本次在二分法中X=1，即選擇聚類中心個數(shù)為313×2-1+1=157 個，經(jīng)過計算生成表2。

表2 站點(diǎn)個數(shù)＞1 的聚類中心統(tǒng)計表

由表2 可知：

1）站點(diǎn)個數(shù)＞1 的聚類中心共有74 個，聚類中心平均站點(diǎn)個數(shù)約為3 個，中位數(shù)為3 個，眾數(shù)為2 個，聚類中心站點(diǎn)個數(shù)最多的為9 個，站點(diǎn)合計數(shù)為230 個，占總站點(diǎn)的73.5%。

2）站點(diǎn)距各聚類中心平均距離5.87 km，站點(diǎn)距各聚類中心4～6 km距離最多，最大11.76 km，最小為2.08 km。

3）站點(diǎn)個數(shù)為1 個的聚類中心，其分布孤立，離其他聚類中心較遠(yuǎn)，如圖5 所示，可見，此次聚類可以很好地對原站點(diǎn)空間分布特征進(jìn)行定量表述。

圖5 二分法聚類中心分布圖

3.2.2 聚類中心間路徑規(guī)劃

如圖6 所示，改進(jìn)的Prim 最小生成樹連通全部聚類中心，呼倫貝爾市各縣域中心在站網(wǎng)路徑規(guī)劃中連通作用明顯，是站網(wǎng)路徑連通的關(guān)鍵點(diǎn)，呼倫貝爾市海拉爾區(qū)是整個站網(wǎng)連通的中心。

圖6 改進(jìn)的Prim 最小生成樹分布圖

經(jīng)過計算，改進(jìn)的最小生成樹的連通路徑長度為4 620 km，路徑長度縮短10.8%，各聚類中心中站點(diǎn)至各中心平均距離為5.87 km，改進(jìn)后的Prim 最小生成樹達(dá)到優(yōu)化路徑的目的。

改進(jìn)的Prim 算法的基本思想與標(biāo)準(zhǔn)Prim 算法相同，但是它在選擇下一個頂點(diǎn)時使用了一種更加高效的方法。標(biāo)準(zhǔn)Prim 算法通過檢查所有的邊來選擇下一個頂點(diǎn)，這個過程的時間復(fù)雜度是O（n2）。其中，n是無向連通圖頂點(diǎn)個數(shù)。改進(jìn)的Prim 算法是將稠密圖轉(zhuǎn)向稀疏圖，將Prim 算法的時間復(fù)雜度無限接近于Kruskal（克魯斯卡爾）算法，時間復(fù)雜度為O（ElogV）。其中，E是邊數(shù)，V是頂點(diǎn)數(shù)。改進(jìn)的算法減小了E和V，降低了空間復(fù)雜度。

4 結(jié)論

本文提出的基于聚類分析改進(jìn)Prim 最小生成樹的路徑規(guī)劃算法適用于稠密圖。首先采用二分法將氣象站網(wǎng)中的站點(diǎn)先聚類，形成微小的站點(diǎn)聚類中心，再以各聚類中心進(jìn)行Prim 最小生成樹路徑規(guī)劃，從而達(dá)到路徑規(guī)劃的目的。

原站網(wǎng)布局中站點(diǎn)的分布雜亂零散，分布特征多定性描述，難以定量化分析；而改進(jìn)的Prim 最小生成樹算法仍遵循局部最優(yōu)達(dá)到全局最優(yōu)原則，先簡化了站網(wǎng)中因站點(diǎn)分布不均勻而產(chǎn)生的復(fù)雜度，通過聚類分析的聚類中心，以二分法指數(shù)遞減聚合站點(diǎn)，形成新的站網(wǎng)布局。

在呼倫貝爾市新的聚類站網(wǎng)布局中，站點(diǎn)個數(shù)大于1 個聚類中心占總聚類中心的47%，站點(diǎn)總數(shù)占站網(wǎng)的73.5%，聚類中心中站點(diǎn)距各聚類中心平均距離為5.87 km，最小生成樹路徑長度縮短10.8%?？梢姡倪M(jìn)后的算法定量化了站點(diǎn)空間分布特征，通過聚類增強(qiáng)了最優(yōu)解，從而達(dá)到減小路徑長度的目的。

需要注意的是：改進(jìn)Prim 算法需要根據(jù)具體應(yīng)用場景和問題規(guī)模來選擇合適的指數(shù)，對于更加稠密的站網(wǎng)，指數(shù)選擇應(yīng)大于1，這樣才可以更好地簡化站網(wǎng)布局，將Prim 算法的時間復(fù)雜度無限接近于Kruskal 算法，降低算法的空間復(fù)雜度，以達(dá)到更好的實(shí)際應(yīng)用目的。