基于贪心算法的离散单位圆盘覆盖问题研究

论文摘要

提出了一种基于贪心启发式的计算方法,可以在多项式时间复杂度内获得DUDC问题的近似最优解.首先生成了可替代二维平面的离散单元格,在每一单元格中心建立能够覆盖一定数量目标点的替代集,使用贪心算法确定替代集的最小组合方式,实现了对目标点的全覆盖.基于每个子集内所包含的点的具体位置,计算了其最小覆盖圆.最小覆盖圆的中心视为选址位置.基于具体案例证明了算法的有效性.讨论了该算法的影响因素,分析了时间复杂度以及近似度比率.

论文目录

• 1 DUDC问题的研究
•   1.1 基本模型
•   1.2 优化准则
•   1.3 最小集合覆盖问题
• 2 基于贪心算法求解DUDC问题
• 3 实例研究
•   3.1 案例提出
•   3.2 网格尺寸的影响
•   3.3 算法有效性验证
•   3.4 算法适应性讨论
•   3.5 算法时间复杂度分析
•   3.6 算法近似度分析
• 4 结论

文章来源

类型: 期刊论文

作者: 王淼,吴松涛,李永哲,武悦

关键词: 贪心算法,离散单位圆盘覆盖问题,选址问题,城市综合服务中心

来源: 华南理工大学学报(自然科学版) 2019年12期

年度: 2019

分类: 工程科技Ⅱ辑,信息科技

专业: 建筑科学与工程,计算机软件及计算机应用

单位: 哈尔滨工业大学建筑学院寒地城乡人居环境科学与技术工业和信息化部重点实验室,代尔夫特理工大学工业设计工程学院

基金: 国家自然科学基金资助项目(51808160)~~

分类号: TU984;TP301.6

页码: 78-85

总页数: 8

文件大小: 2146K

下载量: 129