一种基于斯坦纳树的室内水管布线方法、装置及其系统.pdf

(19)国家知识产权局(12)发明专利申请(10)申请公布号CN114818215A(43)申请公布日2022.07.29(21)申请号202210476690.2(22)申请日2022.04.30(71)申请人合肥黎曼信息科技有限公司地址230031安徽省合肥市高新区创新大道2800号创新产业园二期J1栋A座1027室(72)发明人宋艳枝邱安东(74)专利代理机构合肥汇融专利代理有限公司34141专利代理师王秀芳(51)Int.Cl.G06F30/18(2020.01)G06Q10/04(2012.01)G06Q50/06(2012.01)权利要求书2页说明书6页附图4页(54)发明名称一种基于斯坦纳树的室内水管布线方法、装置及其系统(57)摘要本发明涉及建筑设计技术领域，解决了目前无法通过输入相应参数自动生成最优的水管布线方案的技术问题，涉及一种基于斯坦纳树的室内水管布线方法，包括以下过程：获取户型对象数据和管道的铺设成本数据，还涉及一种应用于上述室内水管布线方法的装置，包括：数据获取模块用于获取户型对象数据和管道的铺设成本数据，一种应用于上述室内水管布线方法的系统，包括：处理器；存储器；以及一个或多个程序。本发明达到了通过建立布线带权图后使用最优路径生成算法和多步的布线生成改进算法得到水管布线方案的目的，能够高效快速地提供满足规范，同时节省材料、工程量的水管布线设计方案，提高建筑设计效率。CN114818215ACN114818215A权利要求书1/2页1.一种基于斯坦纳树的室内水管布线方法，其特征在于，包括以下过程：获取户型对象数据和管道的铺设成本数据；根据上述获取的数据主动生成布线带权图；计算水源、水龙头与布线带权图中各节点间的最优路径；在所有已布管道节点与未连入管线的水龙头之间的最优路径中，寻找满足限制条件且新增成本最少的一条并将其并入管道方案中，得到初步水管布线方案；根据初步水管布线方案的节点得到的带权支撑子图；在带权支撑子图上由其最小生成树得到改进水管布线方案；将改进水管布线方案中多余的管道删除得到最终水管布线方案。2.根据权利要求1所述的室内水管布线方法，其特征在于：生成布线带权图包括以下过程：设布线带权图记为(G,w)；构建节点集、边集和边集上的成本函数，分别记为V(G)、E(G)和w；其中，V(G)为水源、各水龙头对应的坐标点和线路潜在拐弯、分岔的坐标点；E(G)由所有以V(G)中能够直接布线相连的两个坐标点为两端点的线段构成；对边集E(G)中的任意一条线段e，任意一条线段e的成本函数值w由管道铺设成本和线段长度、线段需要开槽的长度给出。3.根据权利要求1所述的室内水管布线方法，其特征在于：计算水源、水龙头与布线带权图中各节点间的最优路径包括以下过程：根据最优路径的定义设计边集上的代价函数α；使用布线带权图上的最优路径搜索算法，获得使代价函数α取值最低的最优路径P。4.根据权利要求1或3所述的室内水管布线方法，其特征在于：布线带权图上的最优路径搜索算法为广度优先搜索或动态规划算法。5.根据权利要求1或2所述的室内水管布线方法，其特征在于：根据户型对象数据和管道的铺设成本数据主动生成布线带权图，包括节点集、边集和边集上的成本函数。6.根据权利要求1所述的室内水管布线方法，其特征在于：在得到初步水管布线方案这一步骤中，管道方案中最初只包含水源或某一个水龙头而不包含任何新增的管道，将当前满足限制条件且新增成本最少的一个水龙头或水源及其相连的一段管道纳入到管道方案中，重复该步骤直至管道方案包含水源和所有的水龙头。7.根据权利要求1所述的室内水管布线方法，其特征在于：在根据初步水管布线方案的节点得到的带权支撑子图这一步骤中，带权支撑子图的节点集与初步水管布线方案的节点集相同；在带权支撑子图上由其最小生成树得到改进水管布线方案这一步骤中，带权支撑子图的最小生成树连通、具有与带权支撑子图具有相同的节点集。8.根据权利要求1所述的室内水管布线方法，其特征在于：在将改进水管布线方案中多余的管道删除得到最终水管布线方案这一步骤中，将多余节点定义为水管布线方案中只具有一条相邻边且不为水龙头或水源的节点，多余管道定义为多余节点的邻边构成的集合，并将水管布线方案的节点集和边集中分别删去上述多余节点和多余管道，直到不存在多余管道。2CN114818215A权利要求书2/2页9.一种基于斯坦纳树的室内水管布线装置，其特征在于，包括：数据获取模块(10)，所述数据获取模块(10)用于获取户型对象数据和管道的铺设成本数据；主动生成模块(11)，所述主动生成模块(11)用于根据户型对象数据和管道的铺设成本数据主动生成布线带权图；最优路径计算模块(12)，所述最优路径计算模块(12)用于计算水源、水龙头与布线带权图中各节点间的最优路径；初步方