求解区间图上的罗马控制数的动态规划算法

• 作者: 吴璞 张修军 李宏 杨洪
• 来源期刊: 计算机应用研究
• 关键词: 区间图 罗马控制函数 罗马控制数 权重 动态规划算法
• 年，卷（期）: 2018,（7）
• 所属期刊栏目: 算法研究探讨
• 页码范围: 1986-1988
• 页数: 3页
• 分类号: TP301.6
• 语种: 中文
• DOI: 10.3969/j.issn.1001-3695.2018.07.014

摘要

针对区间图的最小罗马控制函数和罗马控制数求解的困难性,提出了一种动态规划算法.从区间图的顶点排序开始,结合区间图的某些性质,采用逐步搜索的方法,不断扩大搜索的顶点集合范围,最终求出最优的罗马控制集和罗马控制数.为保证算法的正确性和科学性,对算法进行了严格的数学推理和证明.最后还给出了一个典型的区间图求解过程的演示示例,增强了算法的可读性和可操作性.结果表明该算法不仅运算速度快,而且简单易行.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	李宏	成都大学信息科学与工程学院	9	24	3.0	4.0
2	张修军	成都大学信息科学与工程学院	26	32	3.0	4.0
3	杨洪	成都大学信息科学与工程学院	9	30	3.0	5.0
4	吴璞	成都大学信息科学与工程学院	1	1	1.0	1.0