王野

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

關(guān)鍵詞：prim算法；暖氣鋪設(shè)；貪心算法；暖氣運輸路徑

1 計算暖氣片的需求量

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

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

2 建立模型

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

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

3 算法思想

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

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

4 算法實現(xiàn)

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

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

方法：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]，設(shè)置與房間0到房間m的鋪管路徑最短；

（4）初始化nearest[m]，設(shè)置與房間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；若所有的房間被遍歷，則跳轉(zhuǎn)11）步；否則，跳轉(zhuǎn)6）步；

（11）s[j]=1；

（12）輸出結(jié)果；

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

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

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

（16）nearest[t]=j；

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

（18）i=i+1；若所有的房間被遍歷，則結(jié)束；否則，跳轉(zhuǎn)（5）步。

5 運行結(jié)果及說明

根據(jù)算法編寫程序，輸入數(shù)據(jù)。得到的運行結(jié)果如下：

最優(yōu)路徑為：

參考文獻

[1]朱軼韻，劉加平.西北農(nóng)村建筑冬季室內(nèi)熱環(huán)境研究[J].土木工程學(xué)報，2010，（s2）：400-403.

[2]金虹，趙華，王秀萍.嚴寒地區(qū)村鎮(zhèn)住宅冬季室內(nèi)熱舒適環(huán)境研究[J].哈爾濱工業(yè)大學(xué)學(xué)報，2006，38（12）：2108-2111.

[3]趙克誠.環(huán)境條件和散熱量[J].節(jié)能，1986，（8）：26.

（作者單位：西北民族大學(xué) 數(shù)學(xué)與計算機科學(xué)學(xué)院）