期刊文献+
共找到2篇文章
< 1 >
每页显示 20 50 100
奖励-收集Steiner树问题的精确算法
1
作者 曾宾 宁爱兵 +2 位作者 付振星 付馨懿 张惠珍 《系统管理学报》 CSSCI CSCD 北大核心 2024年第5期1242-1250,共9页
奖励-收集Steiner树问题是图的Steiner最小树问题的衍生,同时也是组合优化中的NP-hard问题。首先,提出该问题的数学性质并给出证明,利用数学性质能降低该问题的规模;其次,基于该问题的数学性质设计出上下界子算法、降阶子算法和回溯子算... 奖励-收集Steiner树问题是图的Steiner最小树问题的衍生,同时也是组合优化中的NP-hard问题。首先,提出该问题的数学性质并给出证明,利用数学性质能降低该问题的规模;其次,基于该问题的数学性质设计出上下界子算法、降阶子算法和回溯子算法,通过上下界子算法和降阶子算法可以降低该问题解空间的规模,从而缩短回溯子算法的搜索时间,进而降低求解该问题最优解的时间;最后,应用案例分析、算例分析以及算法分析与对比表明,所设计的算法不仅可以求出该问题的最优解,而且比没有考虑该问题数学性质的一般回溯算法的时间复杂度更低。 展开更多
关键词 奖励-收集Steiner树 上下界算法 降阶子算法 回溯算法
下载PDF
奖励-收集顶点覆盖问题的精确算法
2
作者 曾宾 宁爱兵 +2 位作者 付振星 徐江盼 张惠珍 《计算机时代》 2023年第5期51-56,共6页
奖励-收集顶点覆盖问题是顶点覆盖问题的衍生问题,同时也是组合优化NP-hard问题。本文提出该问题的数学性质并给出证明,利用数学性质能够确定某些顶点一定在或一定不在最优奖励-收集顶点覆盖集中,从而降低该问题的规模;基于该问题的数... 奖励-收集顶点覆盖问题是顶点覆盖问题的衍生问题,同时也是组合优化NP-hard问题。本文提出该问题的数学性质并给出证明,利用数学性质能够确定某些顶点一定在或一定不在最优奖励-收集顶点覆盖集中,从而降低该问题的规模;基于该问题的数学性质设计出上下界子算法、降阶子算法、回溯子算法,通过降阶子算法可以降低该问题的规模,从而缩短回溯子算法的搜索时间,进而降低求解该问题最优解的时间。通过应用和算法对比表明,所设计的算法比没有考虑该问题数学性质的一般精确算法的时间复杂度更低。 展开更多
关键词 奖励-收集顶点覆盖 上下界算法 降阶子算法 回溯算法
下载PDF
上一页 1 下一页 到第
使用帮助 返回顶部