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