科研之友
微信
新浪微博
Facebook
分享链接
摘要
k-CARD树问题(k-Cardinality Tree Problem)是组合优化中一个典型的NP-Hard问题,可描述为在一个给定的无向图G中寻找一棵含k条边的子树,使得该子树权值之和最小。首先研究该问题的数学性质,其中包括可以单个减小问题规模和成批减小问题规模的数学性质;然后提出其上下界子算法;最后根据这些性质和子算法设计了一个可以大幅缩减问题搜索解空间,且保证获得全局最优解的降阶回溯算法。通过一个示例阐述该算法的执行过程,并通过数值实验说明算法的可行性与有效性。
- 出版日期2021
- 单位上海理工大学
