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

摘要：

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

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

所属期刊栏目：47

分类号：TP312;TU984(计算技术、计算机技术)

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

在线出版日期：2020-03-26（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：78-85