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

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

0 引言

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

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

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

1 算法概述

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

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

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

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

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

表1 各頂點間權重計算表

圖1 Prim 算法示例圖

由表1 可知，采用Prim 算法計算的最小生成樹是連接所有頂點的最小成本路徑，這個路徑的總成本是1+2+5+3=11。原始Prim 算法時間復雜度為O（V2），其中V是節(jié)點的數(shù)量，因為在每一步中需要遍歷所有與最小生成樹相鄰的節(jié)點以找到距離最短的節(jié)點。

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

2 改進的Prim 算法

2.1 算法的改進

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

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

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

2）選取一個聚類中心點作為起始點；

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

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

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

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

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

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

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

圖2 聚類中心最小生成樹

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

3 路徑規(guī)劃實踐

3.1 原路徑規(guī)劃

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

圖3 呼倫貝爾市氣象站點分布圖

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

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

3.2 路徑再規(guī)劃

3.2.1 K?Means 聚類分析

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

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

由表2 可知：

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

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

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

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

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

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

圖6 改進的Prim 最小生成樹分布圖

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

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

4 結論

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

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

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

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