期刊导航
期刊开放获取
河南省图书馆
退出
期刊文献
+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息
检索
高级检索
期刊导航
共找到
1
篇文章
<
1
>
每页显示
20
50
100
已选择
0
条
导出题录
引用分析
参考文献
引证文献
统计分析
检索结果
已选文献
显示方式:
文摘
详细
列表
相关度排序
被引量排序
时效性排序
奖励-收集顶点覆盖问题的精确算法
1
作者
曾宾
宁爱兵
+2 位作者
付振星
徐江盼
张惠珍
《计算机时代》
2023年第5期51-56,共6页
奖励-收集顶点覆盖问题是顶点覆盖问题的衍生问题,同时也是组合优化NP-hard问题。本文提出该问题的数学性质并给出证明,利用数学性质能够确定某些顶点一定在或一定不在最优奖励-收集顶点覆盖集中,从而降低该问题的规模;基于该问题的数...
奖励-收集顶点覆盖问题是顶点覆盖问题的衍生问题,同时也是组合优化NP-hard问题。本文提出该问题的数学性质并给出证明,利用数学性质能够确定某些顶点一定在或一定不在最优奖励-收集顶点覆盖集中,从而降低该问题的规模;基于该问题的数学性质设计出上下界子算法、降阶子算法、回溯子算法,通过降阶子算法可以降低该问题的规模,从而缩短回溯子算法的搜索时间,进而降低求解该问题最优解的时间。通过应用和算法对比表明,所设计的算法比没有考虑该问题数学性质的一般精确算法的时间复杂度更低。
展开更多
关键词
奖励-收集顶点覆盖
上下界子算法
降阶子算法
回溯子算法
下载PDF
职称材料
题名
奖励-收集顶点覆盖问题的精确算法
1
作者
曾宾
宁爱兵
付振星
徐江盼
张惠珍
机构
上海理工大学管理学院
出处
《计算机时代》
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 [理学—运筹学与控制论]
下载PDF
职称材料
题名
作者
出处
发文年
被引量
操作
1
奖励-收集顶点覆盖问题的精确算法
曾宾
宁爱兵
付振星
徐江盼
张惠珍
《计算机时代》
2023
0
下载PDF
职称材料
已选择
0
条
导出题录
引用分析
参考文献
引证文献
统计分析
检索结果
已选文献
上一页
1
下一页
到第
页
确定
用户登录
登录
IP登录
使用帮助
返回顶部