华南理工大学学报(自然科学版) ›› 2019, Vol. 47 ›› Issue (12): 78-85.doi: 10.12141/j.issn.1000-565X.190370
王淼1,吴松涛1,李永哲2,武悦1
Miao WANGSong-Tao WU2,Yong-Zhe LI3, 2
摘要: 共享经济所提出的城市综合体模式,具有有限服务半径的特点。城市综合体选址问题的基本数学模型为离散单位圆盘覆盖(DUDC)问题。该问题考虑用若干给定半径r的离散单位圆盘对平面中n个离散点进行覆盖。其研究目的是用最少数量的圆盘覆盖全部离散点。本文提出了一种基于贪心启发式的计算方法,可以在多项式时间复杂度内获得DUDC问题的近似最优解。首先生成了可替代二维平面的离散单元格,在每一单元格中心建立能够覆盖一定数量目标点的替代集,使用贪心算法确定替代集的最小组合方式,实现了对目标点的全覆盖。基于每个子集内所包含的点的具体位置,计算了其最小覆盖圆。最小覆盖圆的中心视为选址位置。基于具体案例证明了算法的有效性。讨论了该算法的影响因素,分析了时间复杂度以及近似度比率。
中图分类号: