-
题名奖励-收集Steiner树问题的精确算法
- 1
-
-
作者
曾宾
宁爱兵
付振星
付馨懿
张惠珍
-
机构
上海理工大学管理学院
-
出处
《系统管理学报》
CSSCI
CSCD
北大核心
2024年第5期1242-1250,共9页
-
基金
国家自然科学基金资助项目(71401106)
上海市“管理科学与工程”高原学科建设项目。
-
文摘
奖励-收集Steiner树问题是图的Steiner最小树问题的衍生,同时也是组合优化中的NP-hard问题。首先,提出该问题的数学性质并给出证明,利用数学性质能降低该问题的规模;其次,基于该问题的数学性质设计出上下界子算法、降阶子算法和回溯子算法,通过上下界子算法和降阶子算法可以降低该问题解空间的规模,从而缩短回溯子算法的搜索时间,进而降低求解该问题最优解的时间;最后,应用案例分析、算例分析以及算法分析与对比表明,所设计的算法不仅可以求出该问题的最优解,而且比没有考虑该问题数学性质的一般回溯算法的时间复杂度更低。
-
关键词
奖励-收集Steiner树
上下界子算法
降阶子算法
回溯子算法
-
Keywords
prize-collection Steiner tree
upper and lower bound sub algorithm
reduced order sub algorithm
backtracking sub algorithm
-
分类号
O223
[理学—运筹学与控制论]
-
-
题名最小连通顶点覆盖问题的降阶回溯算法
- 2
-
-
作者
曾宾
宁爱兵
付振星
李之桥
张惠珍
-
机构
上海理工大学管理学院
-
出处
《运筹与管理》
CSSCI
CSCD
北大核心
2024年第3期28-34,共7页
-
基金
国家自然科学基金资助项目(71401106)。
-
文摘
本文从最小连通顶点覆盖问题的求解算法出发,提出一种基于该问题本身的数学性质的降阶回溯算法来求解。通过基于问题的数学性质来设计精确算法,不仅能够克服使用启发式算法求解该问题在一般情形下都无法求得最优解的缺点,也改善了该问题使用传统精确算法时最坏时间复杂度高的缺点。本文首先研究该问题的数学性质,部分数学性质可成批确定某些顶点在或不在最小连通顶点覆盖集中,从而降低该问题的规模,提高精确算法的求解速度。其次,在数学性质的基础上,设计出上下界子算法、降阶子算法、回溯子算法来求解该问题的最优解。最后,时间复杂度分析以及无线网络设计的实例分析表明,该算法不仅能求得该问题的最优解,且相对一般精确算法,本文算法的时间复杂度更低。
-
关键词
最小连通顶点覆盖
上界子算法
下界子算法
回溯子算法
-
Keywords
minimum connected vertex cover
upper bound sub algorithm
lower bound sub algorithm
backtracking sub algorithm
-
分类号
O223
[理学—运筹学与控制论]
-
-
题名TST问题的降阶回溯算法
- 3
-
-
作者
付振星
宁爱兵
曾宾
程志浩
张惠珍
-
机构
上海理工大学管理学院
-
出处
《计算机时代》
2023年第4期39-43,共5页
-
基金
国家自然科学基金(71401106)
上海市“管理科学与工程”高原学科建设项目。
-
文摘
考虑Terminal Steiner Tree(TST)问题中特殊结点及其关联边之间的关系、结点之间的权值比较、可行解的连通性等几个方面,提出该问题的相关数学性质,判断问题中结点与边是否一定在或一定不在最优解中;利用上下界子算法对降阶回溯算法的解空间进行剪枝,加快了算法求解问题的速率,最后通过算法复杂度分析证明算法的有效性。
-
关键词
TST问题
数学性质
降阶
回溯
-
Keywords
TST problem
mathematical properties
reduction
backtracking
-
分类号
TP301.6
[自动化与计算机技术—计算机系统结构]
-
-
题名奖励-收集顶点覆盖问题的精确算法
- 4
-
-
作者
曾宾
宁爱兵
付振星
徐江盼
张惠珍
-
机构
上海理工大学管理学院
-
出处
《计算机时代》
2023年第5期51-56,共6页
-
基金
国家自然科学基金(71401106)
上海市“管理科学与工程”高原学科建设项目。
-
文摘
奖励-收集顶点覆盖问题是顶点覆盖问题的衍生问题,同时也是组合优化NP-hard问题。本文提出该问题的数学性质并给出证明,利用数学性质能够确定某些顶点一定在或一定不在最优奖励-收集顶点覆盖集中,从而降低该问题的规模;基于该问题的数学性质设计出上下界子算法、降阶子算法、回溯子算法,通过降阶子算法可以降低该问题的规模,从而缩短回溯子算法的搜索时间,进而降低求解该问题最优解的时间。通过应用和算法对比表明,所设计的算法比没有考虑该问题数学性质的一般精确算法的时间复杂度更低。
-
关键词
奖励-收集顶点覆盖
上下界子算法
降阶子算法
回溯子算法
-
Keywords
prize-collecting vertex cover
upper and lower bound sub-algorithm
reduced-order sub-algorithm
backtracking subalgorithm
-
分类号
O223
[理学—运筹学与控制论]
-
