首页> 外文期刊>Journal of algorithms & computational technology >A Steiner point candidate-based heuristic framework for the Steiner tree problem in graphs
【24h】

A Steiner point candidate-based heuristic framework for the Steiner tree problem in graphs

机译:图中Steiner树问题的基于Steiner候选点的启发式框架

获取原文
获取原文并翻译 | 示例

摘要

The underlying models of many practical problems in various engineering fields are equivalent to the Steiner tree problem in graphs, which is a typical NP-hard combinatorial optimization problem. Thus, developing a fast and effective heuristic for the Steiner tree problem in graphs is of universal significance. By analyzing the advantages and disadvantages of the fast classic heuristics, we find that the shortest paths and Steiner points play important roles in solving the Steiner tree problem in graphs. Based on the analyses, we propose a Steiner point candidate-based heuristic algorithm framework (SPCF) for solving the Steiner tree problem in graphs. SPCF consists of four stages: marking SPC_Ⅰ points, constructing the Steiner tree, eliminating the detour paths, and SPC_Ⅱ-based refining stage. For each procedure of SPCF, we present several alternative strategies to make the trade-off between the effectiveness and efficiency of the algorithm. By finding the shortest path clusters between vertex sets, several methods are proposed to mark the first type of Steiner point candidates SPC_Ⅰ. The solution qualities of the classic heuristics are effectively improved by looking SPC_Ⅰ points as terminals. By constructing a Voronoi diagram, a series of methods are suggested to mark the second type of Steiner point candidates SPC_Ⅱ. The feasible solution quality is efficiently improved by employing the SPC_Ⅱ points as the insertable key-vertices in key-vertex insertion local search method. Numerical experiments show that the proposed strategies are all effective for improving the solution quality. Compared with other effective algorithms, the proposed algorithms can achieve better solution quality and speed performance.
机译:各个工程领域中许多实际问题的基础模型等同于图中的Steiner树问题,这是一个典型的NP-hard组合优化问题。因此,为图中的Steiner树问题开发一种快速有效的启发式方法具有普遍意义。通过分析快速经典启发式算法的优缺点,我们发现最短路径和Steiner点在解决图中的Steiner树问题中起着重要作用。在此基础上,我们提出了一种基于斯坦纳点候选的启发式算法框架(SPCF)来解决图中的斯坦纳树问题。 SPCF包括四个阶段:标记SPC_Ⅰ点,构造Steiner树,消除绕道和基于SPC_Ⅱ的精炼阶段。对于SPCF的每个过程,我们提出几种替代策略,以在算法的有效性和效率之间进行权衡。通过找到顶点集之间的最短路径簇,提出了几种方法来标记第一种Steiner点候选SPC_Ⅰ。通过将SPC_Ⅰ点作为终端,有效地提高了经典启发式算法的求解质量。通过构造Voronoi图,建议了一系列方法来标记第二种斯坦纳点候选SPC_Ⅱ。通过将SPC_Ⅱ点作为键顶点插入局部搜索方法中的可插入键顶点,有效地提高了可行解的质量。数值实验表明,所提出的策略对于提高求解质量都是有效的。与其他有效算法相比,所提出的算法可以获得更好的解决方案质量和速度性能。

著录项

  • 来源
  • 作者单位

    Center for Discrete Mathematics and Theoretical Computer Science, Fuzhou University, FuZhou, PR China,College of Mathematics and Computer Science, Fuzhou University, FuZhou, PR China,Center for Discrete Mathematics and Theoretical Computer Science, Fuzhou University, No. 2 Xueyuan Road, District of Universities, FuZhou 350108, China;

    Center for Discrete Mathematics and Theoretical Computer Science, Fuzhou University, FuZhou, PR China,College of Mathematics and Computer Science, Fuzhou University, FuZhou, PR China;

    College of Mathematics and Computer Science, Fuzhou University, FuZhou, PR China;

  • 收录信息
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类
  • 关键词

    NP-hard; Steiner tree problem in graphs; Steiner points; Voronoi diagram;

    机译:NP-hard;图中的斯坦纳树问题;施泰纳分;Voronoi图;

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号