(19)中华 人民共和国 国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202111532087.3 (22)申请日 2021.12.15 (71)申请人 惠州学院 地址 516007 广东省惠州市惠城区河南岸 冷水坑 (72)发明人 骆伟忠　吴志攀　汪华斌　 (74)专利代理 机构 广州三环 专利商标代理有限 公司 44202 代理人 邓聪权 (51)Int.Cl. G06F 17/10(2006.01) G06Q 10/04(2012.01) (54)发明名称 一种高度受限的有向斯坦纳树构造方法及 存储介质 (57)摘要 本发明涉及斯坦纳树构造技术领域， 特别涉 及一种高度受限的有向斯坦纳树构造方法及存 储介质， 该构造方法利用动态规划技术， 采用自 底向上策略来得出问题的最优解。 当网络的目标 节点个数远远小于网络规模时， 该方法具有较好 的时间效率， 能够在关于问题 规模的多项式时间 内实际求 解得到问题的最优解。 权利要求书2页 说明书5页 附图1页 CN 114398586 A 2022.04.26 CN 114398586 A 1.一种高度受限的有向斯 坦纳树构造方法， 其特 征在于， 包括以下步骤： S1， 产生高度受限有向斯坦纳树下的一个问题 实例(G， r， S， h)， 其中G＝(V， E)为边加权 的有向图； S2， 枚举目标节点集合S的子集X， 以及节点集合V中任一节点v的所有组合， 计算实现 (v， S， 0)的斯 坦纳树权值； S3， 枚举树高度i， 以及目标节点集合S的子集X， 以及节点集合V中任一节点v的所有组 合， 并利用动态规划技 术计算实现(v， X， i)的斯 坦纳树的权值 W(v， X， i)； S4， 基于权值W(v， X， i)， 利用回溯法构造代价 为W(r， S， h)、 实现(r， S， h)的斯 坦纳树T； 其中， 步骤S1与步骤S2中的V为顶点集合， E为边的集合； 源节点r为G中的任一顶点； 目 标节点集合S为V的任一子集； h＞0(h∈n)； 步骤S3与步骤S4中0＜i≤ h(i∈n)。 2.根据权利要求1所述的一种高度受限的有向斯坦纳树构造方法， 其特征在于， 所述步 骤S2具体包括： S21， 判断X＝ ＝{v}是否成立， 若是则将W(v， S， 0)赋值 为零， 若否则执 行下一步； S22， 将W(v， S， 0)赋值 为无穷大。 3.根据权利要求2所述的一种高度受限的有向斯坦纳树构造方法， 其特征在于， 所述步 骤S3具体包括： S31， 计算实现(v， X， i)中， 且 v的度至少为2个最小代价 树的权值； S32， 计算实现(v， X， i)的斯 坦纳树的权值。 4.根据权利要求3所述的一种高度受限的有向斯坦纳树构造方法， 其特征在于， 所述步 骤S31具体包括： S311， 判断X中顶点个数 是否大于等于2， 若是则执 行步骤S312， 若否则执 行步骤S313； S312， 枚举X的所有真子集X ’， 利用实现(v， X ’， i)的斯坦纳树权值计算实现(v， X， i)、 且 v≥2的最小代价 树的权值 Wc(v， X， i)， 计算公式为， S313， 将Wc(v， X， i)赋值 为正无穷大。 5.根据权利要求4所述的一种高度受限的有向斯坦纳树构造方法， 其特征在于， 所述步 骤S32具体包括： S321， 判断v是否属于V\X， 若是则执 行步骤S32 2， 若否则执 行步骤S323； S322， 利用第一预设公式计算实现(v， X， i)的斯 坦纳树权值 W(v， X， i)； S323， 进一步判断X中的定点个数是否大于等于2， 若是则利用第二预设公式计算所述W (v， X， i)， 若否则执 行下一步； S324， 设置所述 W(v， X， i)为 零。 6.根据权利要求5所述的一种高度受限的有向斯 坦纳树构造方法， 其特 征在于： 所述步骤S322中， 第一预设公式为， 所述步骤S323中， 第二预设公式为，权　利　要　求　书 1/2 页 2 CN 114398586 A 2其中， 第二预设公式中， No(v)表示顶点v所有出邻接顶点的集合， w([v， u])表示边[v， u] 的权值。 7.一种存储介质， 其特征在于： 所述存储介质内存储有用于实现权利要求1～6所述的 斯坦纳树构造方法的程序语言。权　利　要　求　书 2/2 页 3 CN 114398586 A 3