基于改進(jìn)Prim 算法的路徑規(guī)劃研究

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

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

0 引言

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

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

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

1 算法概述

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

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

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

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

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

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

圖1 Prim 算法示例圖

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

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

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

2.1 算法的改進(jìn)

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

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

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

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

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

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

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

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

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

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

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

圖2 聚類(lèi)中心最小生成樹(shù)

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

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

3.1 原路徑規(guī)劃

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

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

圖4 原Prim 最小生成樹(shù)分布圖

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

3.2 路徑再規(guī)劃

3.2.1 K?Means 聚類(lèi)分析

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

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

由表2 可知：

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

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

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

圖5 二分法聚類(lèi)中心分布圖

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

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

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

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

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

4 結(jié)論

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

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

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

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