|
|||||
|
|
| 基于贪心算法的离散单位圆盘覆盖问题研究 | |
| 引用本文： | 王淼,吴松涛,李永哲,武悦.基于贪心算法的离散单位圆盘覆盖问题研究[J].华南理工大学学报(自然科学版),2019,47(12). |
| 作者姓名： | 王淼 吴松涛 李永哲 武悦 |
| 作者单位： | 哈尔滨工业大学 建筑学院 寒地城乡人居环境科学与技术工业和信息化部重点实验室,黑龙江 哈尔滨150001;代尔夫特理工大学 工业设计工程学院,荷兰 代尔夫特2628CE |
| 摘 要： | 提出了一种基于贪心启发式的计算方法,可以在多项式时间复杂度内获得DUDC问题的近似最优解.首先生成了可替代二维平面的离散单元格,在每一单元格中心建立能够覆盖一定数量目标点的替代集,使用贪心算法确定替代集的最小组合方式,实现了对目标点的全覆盖.基于每个子集内所包含的点的具体位置,计算了其最小覆盖圆.最小覆盖圆的中心视为选址位置.基于具体案例证明了算法的有效性.讨论了该算法的影响因素,分析了时间复杂度以及近似度比率. |
| 关 键 词： | 贪心算法 离散单位圆盘覆盖问题 选址问题 城市综合服务中心 |
| 本文献已被 CNKI 万方数据 等数据库收录！ | |