|
|||||
|
|
| TST问题的降阶回溯算法 | |
| 引用本文： | 付振星,宁爱兵,曾宾,程志浩,张惠珍.TST问题的降阶回溯算法[J].计算机时代,2023(4):39-43. |
| 作者姓名： | 付振星 宁爱兵 曾宾 程志浩 张惠珍 |
| 作者单位： | 上海理工大学管理学院 |
| 基金项目： | 国家自然科学基金（71401106）； |
| 摘 要： | 考虑Terminal Steiner Tree(TST)问题中特殊结点及其关联边之间的关系、结点之间的权值比较、可行解的连通性等几个方面，提出该问题的相关数学性质，判断问题中结点与边是否一定在或一定不在最优解中；利用上下界子算法对降阶回溯算法的解空间进行剪枝，加快了算法求解问题的速率，最后通过算法复杂度分析证明算法的有效性。 |
| 关 键 词： | TST问题 数学性质 降阶 回溯 |