基于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.

（作者单位：西北民族大学 数学与计算机科学学院）