基于prim算法的暖氣輸送路徑問題

王野

摘 要：本文通過應用貪心算法中的最小生成樹問題的prim算法，對于面積的考慮，我們是根據建筑面積的熱量散失計算暖氣片的需求量，將暖氣片的需求量簡單地當作建筑內鋪設長度來計算，通過將面積轉化為長度，再加上我們實地測量的距離，給出帶權連通圖，繼而通過貪心算法求解，最終給出最優的暖氣運輸路徑。

關鍵詞：prim算法；暖氣鋪設；貪心算法；暖氣運輸路徑

1 計算暖氣片的需求量

有以上可知面積若以16m2計算，散熱功率大約在1 850W，又通過查相關數據得知該散熱器每組散熱量為170W。暖氣片需求量計算公式如下：

按照公式可得：編號1，2，3，4，5，6，7，8，9，10的暖氣片需求量分別為390，3856，1338，965，2523，4766，2540，1225，486，486。

2 建立模型

在某公司m個房間鋪設暖氣管，只需要架設m-1條線路即可。

現在用一個簡單的數學模型來說明。學校有48個部門，在這48個建筑物間鋪設暖氣管的帶權連通圖，圓圈中的數字1，2……48表示的是建筑物的編號，這些圓圈間的線段表示各個建筑物之間直接鋪設暖氣管道的路徑加上（建筑物i+建筑物j）/2，線段旁的數字表示權值，也就是各個建筑物之間直接鋪設暖氣管道的路徑加上（建筑物i+建筑物j）/2，各建筑物間沒有直接路徑的，則它們間的路徑視為無窮大，可得：1-2，1-4，2-1，2-3，2-4，2-5，3-2，3-5，3-6，3-7的權值為2298，833，2298，2839，2636，3369，2839，2231，3310，2236。

3 算法思想

將房間0視為暖氣管道的鋪設起點，先將房間0計入一個集合S內，從房間0開始，遍歷所有的房間，尋找最短的路徑。此時與房間0相連的1、2、3 三個房間中，徑最短的為房間0 到房間2的距離，所以將房間2計入集合S內，然后從集合S中的所有房間號出發，尋找下一個路徑最短的且房間號不在集合S中的房間，此時最短的有房間2到房間4、房間2到房間5的距離，它們間的路徑都為40個單位長。由于在執行該算法的過程中，房間編號采取的是非降次的排列，故先考慮編號較小的房間%所以采取從房間2到房間4 路徑鋪設暖氣管，并將房，4計入集合S內。依次類推，直到所有的房間編號都包含在集合S中，所得到的這整個鋪設的路徑即為所要的最佳的方案。

為實現這個算法需設置一個輔助數組來記錄一些數據。其中，owestcost[m]記錄的是從S到V-S中具有最小權值的邊，即，兩房間之間的最短的路徑值；對每個頂點也需設置輔助數組記錄，s[m]為設置標志的數組，值為1表示房間m鋪設了暖氣管，為0表示沒有鋪設暖氣管；nearest[m]的值表示與房間m的最近的房間的編號。

4 算法實現

輸入：房間個數；各房間之間鋪管的路徑值。

輸出：最優路徑；包括起始的房間號、終止的房間號和兩房間之間的路徑值。

方法：s[m]標志為1表示為已鋪管的房間；

Lowestcost[m]存儲兩房間之間鋪管的最短路徑值；

Nearest[m]存儲與房間m的最近的房間的編號；

E[i][j]存儲房間i、j之間鋪管的路徑值。

（1）輸入房間i到房間j間鋪管的路徑值e[i][j]={}；

（2）初始化s[m]為0，即所有的房間都未鋪管；

（3）初始化lowestcost[m]，設置與房間0到房間m的鋪管路徑最短；

（4）初始化nearest[m]，設置與房間m鋪管最近的房間為房間0；

（5）從房間i（i=0，1，2，… …，m）開始，尋找與房間i鋪管路徑最近的且未被鋪管的房間號；

（6）將房間i到其他未被鋪管的房間k（k=1，2，… …，m）的鋪管路徑作比較；

（7）若房間i到最近的房間k的路徑值小于最小路徑值min；

（8）Min=lowestcost[k]；

（9）j=k；

（10）k=k+1；若所有的房間被遍歷，則跳轉11）步；否則，跳轉6）步；

（11）s[j]=1；

（12）輸出結果；

（13）從房間j出發，比較房間j到其他的未鋪設管道房間t=（t=1，2，… …，m）鋪管路徑長；

（14）若從房間j到房間t的鋪管路徑小于房間i到它的鋪管路徑；

（15）lowestcost[t]=e[j][t]；

（16）nearest[t]=j；

（17）t=t+1；若所有的房間被遍歷，則跳轉（18）步；否則，跳轉（13）步；

（18）i=i+1；若所有的房間被遍歷，則結束；否則，跳轉（5）步。

5 運行結果及說明

根據算法編寫程序，輸入數據。得到的運行結果如下：

最優路徑為：

參考文獻

[1]朱軼韻，劉加平.西北農村建筑冬季室內熱環境研究[J].土木工程學報，2010，（s2）：400-403.

[2]金虹，趙華，王秀萍.嚴寒地區村鎮住宅冬季室內熱舒適環境研究[J].哈爾濱工業大學學報，2006，38（12）：2108-2111.

[3]趙克誠.環境條件和散熱量[J].節能，1986，（8）：26.

（作者單位：西北民族大學 數學與計算機科學學院）