收稿日期:20190716; 修回日期:20190907 基 金 项目: 国 家自 然 科学 基 金资 助 项目 (71401106);上海 市 一 流 学 科 建 设 项 目
(S1201YLXK)
作者简介:胡沁(1994),男,江苏南通人,硕士研究生,主要研究方向为算法、系统工程(guyue9433@163.com);宁爱兵(1972),男,湖南邵东
人,副教授,博士,主要 研 究 方 向 为 算 法 设 计、系 统 工 程;苟 海 雯 (1995),男,四 川 达 州 人,硕 士 研 究 生,主 要 研 究 方 向 为 算 法、系 统 工 程;
张惠珍(1979),女,山西忻州人,副教授,博士,主要研究方向为优化算法.
节点加权的 Steiner树问题的降阶回溯算法
胡 沁,宁爱兵,苟海雯,张惠珍
(上海理工大学 管理学院,上海 200093)
摘 要:节点加权的 Steiner树问题是组合优化中一个经典的 NPhard问题,现有算法研究该问题时存在时间复
杂性高或无法得到最优解的缺点。针对现有算法的不足,提出了一个基于降阶技术的回溯算法。首先研究该问
题的数学性质,利用数学性质对该问题进行降阶以缩小问题的规模;接着提出上界子算法和下界子算法,利用上
下界子算法对该问题的解空间树进行剪枝,提高搜索效率;最后利用上下界子算法和数学性质设计了一个回溯
算法求解该问题。示例分析以及实验的结果表明,该算法不仅时间复杂性较低而且可以得到问题的最优解。
关键词:节点加权的 Steiner树;上界;下界;回溯算法
中图分类号:TP301.6 文献标志码:A 文章编号:10013695(2020)11021330705
doi:10.19734/j.issn.10013695.2019.07.0262
BacktrackingalgorithmwithreductionfornodeweightedSteinertreeproblem
HuQin,NingAibing,GouHaiwen,ZhangHuizhen
(BusinessSchool,UniversityofShanghaiforScience&Technology,Shanghai200093,China)
Abstract:ThenodeweightedSteinertreeproblemisaclassicNPhardprobleminthecombinatorialoptimization.Theexisting
algorithmsforstudyingtheproblemhavethedisadvantagesofhightimecomplexityandunavailabilityoftheoptimalsolution.In
viewoftheshortcomingsofexistingalgorithms
,thispaperpresentedabacktrackingalgorithm basedonreducedordertech
nique.Firstly,thispaperstudiedthemathematicalpropertiesofthenodeweightedSteinertreeproblemandutilizeditsmathe
maticalpropertiestoreducethescaleoftheproblem.Then
,itdesignedanupperboundsubalgorithmandalowerboundsub
algorithmandutilizedsuchsubalgorithmstoprunethesolutionspacetreeoftheproblemandimprovedthesearchefficiency.
Finally,itdesignedabacktrackingalgorithmtosolvetheabovementionedproblembyutilizingtheupperandlowerboundsub
algorithmsandmathematicalproperties.Exampleanalysisandexperimentalresultsdemonstratethatthealgorithm isnotonly
withlowertimecomplexity,butalsocanobtaintheoptimalsolutionoftheproblem.
Keywords:nodeweightedSteinertree(NWST);upperbound;lowerbound;backtrackingalgorithm
0 引言
图 的 Steiner最 小 树 (graphicalSteinerminimum tree,
GSMT)是经典的组合优化问题,在 1971年由 Hakimi等人
[1]
提
出。
1987年 Segev
[2]
提出节点加权的 Steiner树问题(NWST),
该问题又称为扩展
Steiner树问题,是对经典图的 Steiner最小
树问题的扩展,它不仅要考虑边上的权值,还要考虑节点上的
权值,当节点的权值都为 0时,此时节点加权的 Steiner树问题
变为图的
Steiner最小树问题。节点加权的 Steiner树问题同样
是 NPhard问题,除非 P=NP,否则不存在多项式时间算法。
节点加权的 Steiner树问题及其各种变形问题在组合优化、计
算机科学和工业工程等领域被广泛研究。例如针对无线传感
器网络的研究
[3]
,在过去的研究中,传感场被划分为方形网
格,传感器只能部署在网格的中心,然而在实际情况中,传感器
可以部署在传感场的任何位置,并且由于传感器价格昂贵,只
能使用有限数量的传感器对传感场进行部署,所以关键区域必
须根据其重要性进行加权,从而使覆盖的关键网格的总权重最
大化。文献[3]的研究结果表明,节点加权的 Steiner树可以较
好地对该问题进行建模,并应用于实际问题。除此之外,节点
加权的
Steiner树问题在电路设计、通信网络、交通运输和生物
学等诸多领域亦具有非常广泛的应用,因此节点加权的 Steiner
树问题具有极其重要的应用价值和研究意义。
目前求解节点加权的 Steiner树问题的算法主要分为三类:
a)精确算法,主要有动态规划、分支定界和分支切割等经
典算法。梁东敏等人
[4]
利用动态规划技术求解 NWST问题;
文献[
5,6]提出了一个分支定界算法求解该问题,并且提出了
松弛切割算法求解
NWST问题的变形问题,该精确算法由于没
有利用问题本身的数学性质,求解速度慢、求解时间长。
b)近似算法。Klein等人
[7]
给出 NWST问题的贪婪近似
算法,该算法的近似比率为
2lnk,并提出了“蜘蛛”的概念;文
献[8]在文献[7]的思路上进行了改进,并将近似指标降低到
135(1+
ε
)lnk;Krumke等人
[9]
又进一步改进了文献[8]的结
果,将求解 NWST问题 近 似 解 的 近 似 算 法 性 能 比 率 降 低 到
2lnk(
槡
e/
2|K|),这是目前已知的最好结果。近似算法可以
在多项式时间内得到一个常数近似比的解,但是一般情况下无
法得到该问题的最优解。
c)启发式算法,如禁忌搜索
[10]
、离散粒子群优化
[11]
等算
法。文献[12]提出了基于 Physarum的启发式算法,并与遗传
算法和离散粒子群优化算法进行比较,结果表明基于
Physarum
的启发式算法对于该问题能取得更好的效果。启发式算法可
以快速得到问题的可行解,但是无法保证所得解的质量。
针对现有算法的上述缺点,本文利用节点加权的
Steiner
第 37卷第 11期
2020年 11月
计 算 机 应 用 研 究
ApplicationResearchofComputers
Vol37No11
Nov.2020