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

王野

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

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

1 計(jì)算暖氣片的需求量

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

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

2 建立模型

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

現(xiàn)在用一個(gè)簡(jiǎn)單的數(shù)學(xué)模型來說明。學(xué)校有48個(gè)部門，在這48個(gè)建筑物間鋪設(shè)暖氣管的帶權(quán)連通圖，圓圈中的數(shù)字1，2……48表示的是建筑物的編號(hào)，這些圓圈間的線段表示各個(gè)建筑物之間直接鋪設(shè)暖氣管道的路徑加上（建筑物i+建筑物j）/2，線段旁的數(shù)字表示權(quán)值，也就是各個(gè)建筑物之間直接鋪設(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è)起點(diǎn)，先將房間0計(jì)入一個(gè)集合S內(nèi)，從房間0開始，遍歷所有的房間，尋找最短的路徑。此時(shí)與房間0相連的1、2、3 三個(gè)房間中，徑最短的為房間0 到房間2的距離，所以將房間2計(jì)入集合S內(nèi)，然后從集合S中的所有房間號(hào)出發(fā)，尋找下一個(gè)路徑最短的且房間號(hào)不在集合S中的房間，此時(shí)最短的有房間2到房間4、房間2到房間5的距離，它們間的路徑都為40個(gè)單位長(zhǎng)。由于在執(zhí)行該算法的過程中，房間編號(hào)采取的是非降次的排列，故先考慮編號(hào)較小的房間%所以采取從房間2到房間4 路徑鋪設(shè)暖氣管，并將房，4計(jì)入集合S內(nèi)。依次類推，直到所有的房間編號(hào)都包含在集合S中，所得到的這整個(gè)鋪設(shè)的路徑即為所要的最佳的方案。

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

4 算法實(shí)現(xiàn)

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

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

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

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

Nearest[m]存儲(chǔ)與房間m的最近的房間的編號(hào)；

E[i][j]存儲(chǔ)房間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鋪管路徑最近的且未被鋪管的房間號(hào)；

（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）鋪管路徑長(zhǎng)；

（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 運(yùn)行結(jié)果及說明

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

最優(yōu)路徑為：

參考文獻(xiàn)

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

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

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

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