(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210693461.6 (22)申请日 2022.06.17 (71)申请人 合肥黎曼信息科技有限公司 地址 230031 安徽省合肥市高新区创新大 道2800号创新产业园二期J1栋A座 1027室 (72)发明人 宋艳枝　邱安东　 (74)专利代理 机构 合肥汇融专利代理有限公司 34141 专利代理师 王秀芳 (51)Int.Cl. G06F 30/18(2020.01) G06F 30/13(2020.01) G06F 30/20(2020.01) G06Q 10/04(2012.01)G06F 111/06(2020.01) G06F 113/04(2020.01) G06F 113/16(2020.01) (54)发明名称 一种基于最小生成树的室内强电回路布线 方法及其系统 (57)摘要 本发明涉及建筑室内家装设计技术领域， 解 决了目前室内强电回路布线设计效率低以及线 路长度过长的技术问题， 涉及一种基于最小生成 树的室内强电回路布线方法， 包括以下过程： S1、 根据户型对象数据和各类线路费数据用建立布 线网络； S2、 计算电箱与各插座、 插座与插座间的 最优路径； S3、 构建电箱和各插座间的距离网络； S4、 计算距离网络的最小生成树； 还涉及一种基 于最小生成树的室内强电回路布线系统， 包括： 布线网络建立模块， 所述布线网络建立模块用于 根据户型对象数据和各类线路费数据用建立布 线网络。 本发 明能够提供节省材料的强电回路布 线方案， 并且提高室内家装设计效率。 权利要求书2页 说明书6页 附图6页 CN 115034024 A 2022.09.09 CN 115034024 A 1.一种基于最小生成树的室内强电回路布线方法， 其特 征在于， 包括以下 过程： S1、 根据户型对象数据和各类线路费数据用建立布线网络； S2、 计算电箱与各插座、 插座与插座间的最优路径； S3、 构建电箱和各插座间的距离网络； S4、 计算距离网络的最小生成树； S5、 根据最小生成树中各边对应的电箱与各插座间或插座与插座间的线路导出强电回 路布线方案 。 2.根据权利要求1所述的室内强电回路布线方法， 其特征在于： 在步骤S2中， 计算最优 路径包括以下步骤： S21、 根据最优路径的定义设计边 集上的代价 函数α； S22、 使用布线网络上的最优路径搜索算法， 获得从起点A到每个节点v的最优路径对应 的总成本d(v)、 直线段 数b(v)、 前继集 合f(v)； S23、 根据最优路径上各节点的总 成本d(v)、 直线段数b(v)和前继集合f(v)， 采用回溯 法获得使代价 函数α 取值 最低的最优路径。 3.根据权利要求2所述的室内强电回路布线方法， 其特征在于： 在步骤S23中， 采用回溯 法获得最小的最优路径包括以下步骤： S231、 根据d(B)、 b(B)、 f(B)的计算结果 值确定AB间的最小的最优路径的解空间树； S232、 以深度优先 方式搜索上述的解空间树获得AB间的最优路径。 4.根据权利要求3所述的室内强电回路布线方法， 其特征在于： 在步骤S233中， 深度优 先方式为递归回溯或者迭代回溯， 搜索解空间树过程中采用剪枝函数避免无效搜索。 5.根据权利要求2所述的室内强电回路布线方法， 其特征在于： 在步骤S22中， 最优路径 搜索算法为广 度优先搜索或者动态规划算法。 6.根据权利要求1所述的室内强电回路布线方法， 其特征在于： 在步骤S3中， 构建电箱 和各插座间的距离网络包括以下 过程： S31、 将电箱和所有插座对应的坐标点构成的集 合作为距离网络的节点 集为S； S32、 节点集S中任意两不 同节点构成的节点对为v,v ′， 节点对v,v ′对应于距离网络中 的一条边 为边集为2S； S33、 根据节点 集S和边集2S构建距离网络 。 7.根据权利要求1所述的室内强电回路布线方法， 其特征在于： 在步骤S4中， 采用Prim 算法计算距离网络的最小生成树。 8.根据权利要求1所述的室内强电回路布线方法， 其特征在于： 在步骤S5中， 导出强电 回路布线方案的方法包括以下步骤： S51、 将距离网络的最小生成树中的每一条边中相应的最优路径， 对应着沿该最优路径 依次连接 两个节点， 其中包 含火线、 零线、 地线各一 根的一条线管； S52、 按照上述对应关系， 由距离网络的最小生成树的边集导出所有线管和电线的布置 路径， 得到该强电回路的布线方案 。 9.一种基于最小生成树的室内强电回路布线系统， 其特 征在于， 包括： 布线网络建立模块(100)， 所述布线网络建立模块(100)用于根据户型对象数据和各类 线路费数据用建立布线网络；权　利　要　求　书 1/2 页 2 CN 115034024 A 2最优路径计算模块(200)， 所述最优路径计算模块(200)用于计算电箱与各插座、 插座 与插座间的最优路径； 距离网络构建模块(300)， 所述距离网络构 建模块(300)用于构建电箱和各插座间 的距 离网络； 最小生成树计算模块(400)， 所述最小生成树计算模块(400)用于计算距离 网络的最小 生成树； 强电回路布线方案导出模块(500)， 所述强电回路布线方案导出模块(500)用于根据 最 小生成树中各边对应的电箱与各插座间或插座与插座间的线路导出强电回路布线方案 。权　利　要　求　书 2/2 页 3 CN 115034024 A 3