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

作     者：王淼 吴松涛 李永哲 武悦 WANG Miao;WU Songtao;LI Yongzhe;WU Yue

作者机构：哈尔滨工业大学建筑学院寒地城乡人居环境科学与技术工业和信息化部重点实验室黑龙江哈尔滨150001 代尔夫特理工大学工业设计工程学院荷兰代尔夫特2628CE 

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

出 版 物：《华南理工大学学报（自然科学版）》 (Journal of South China University of Technology(Natural Science Edition))

年 卷 期：2019年第47卷第12期

页      码：78-85页

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

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

学科分类：12[管理学] 1204[管理学-公共管理类] 08[工学] 081303[081303] 0835[0835] 0813[工学-化工与制药类] 0833[0833] 081202[081202] 083302[083302] 0812[工学-测绘类] 

核心收录：

D　O　I：10.12141/j.issn.1000-565X.190370

馆 藏 号：203880130...