计算机时代2023，Issue(4) ：39-43.DOI:10.16644/j.cnki.cn33-1094/tp.2023.04.008

TST问题的降阶回溯算法

A backtracking algorithm with reduction for TST

付振星 宁爱兵 曾宾 程志浩 张惠珍
计算机时代2023，Issue(4) ：39-43.DOI:10.16644/j.cnki.cn33-1094/tp.2023.04.008
✕
  • NETL
  • NSTL
  • 维普
  • 万方数据

TST问题的降阶回溯算法

A backtracking algorithm with reduction for TST

付振星 1宁爱兵 1曾宾 1程志浩 1张惠珍1
扫码查看

作者信息

  • 1. 上海理工大学管理学院,上海 200093
  • 折叠

摘要

考虑Terminal Steiner Tree(TST)问题中特殊结点及其关联边之间的关系、结点之间的权值比较、可行解的连通性等几个方面,提出该问题的相关数学性质,判断问题中结点与边是否一定在或一定不在最优解中;利用上下界子算法对降阶回溯算法的解空间进行剪枝,加快了算法求解问题的速率,最后通过算法复杂度分析证明算法的有效性.

关键词

TST问题/数学性质/降阶/回溯

引用本文复制引用

基金项目

国家自然科学基金(71401106)

上海市"管理科学与工程"高原学科建设项目()

出版年

2023
计算机时代
浙江省计算技术研究所　浙江省计算机学会

计算机时代

影响因子：0.411
ISSN：1006-8228
参考文献量5
段落导航相关论文