华南理工大学学报(自然科学版) ›› 2019, Vol. 47 ›› Issue (12): 78-85.doi: 10.12141/j.issn.1000-565X.190370

• 土木建筑工程 • 上一篇    下一篇

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

王淼1,吴松涛1,李永哲2,武悦1   

  1. 1. 哈尔滨工业大学
    2. 代尔夫特理工大学
  • 收稿日期:2019-06-23 修回日期:2019-07-15 出版日期:2019-12-25 发布日期:2019-11-02
  • 通信作者: 王淼 E-mail:wangmiao88414@163.com
  • 基金资助:
    国家自然科学基金

A Greedy Heuristic-based Approach to Solving the Discrete Unit Disk Cover Problem

Miao WANGSong-Tao WU2,Yong-Zhe LI3, 2   

  • Received:2019-06-23 Revised:2019-07-15 Online:2019-12-25 Published:2019-11-02
  • Contact: Miao WANG E-mail:wangmiao88414@163.com

摘要: 共享经济所提出的城市综合体模式,具有有限服务半径的特点。城市综合体选址问题的基本数学模型为离散单位圆盘覆盖(DUDC)问题。该问题考虑用若干给定半径r的离散单位圆盘对平面中n个离散点进行覆盖。其研究目的是用最少数量的圆盘覆盖全部离散点。本文提出了一种基于贪心启发式的计算方法,可以在多项式时间复杂度内获得DUDC问题的近似最优解。首先生成了可替代二维平面的离散单元格,在每一单元格中心建立能够覆盖一定数量目标点的替代集,使用贪心算法确定替代集的最小组合方式,实现了对目标点的全覆盖。基于每个子集内所包含的点的具体位置,计算了其最小覆盖圆。最小覆盖圆的中心视为选址位置。基于具体案例证明了算法的有效性。讨论了该算法的影响因素,分析了时间复杂度以及近似度比率。

Abstract: The current urban complex model proposed by the sharing economy has a limited service radius. The basic mathematical model for selecting the location of a complex is a discrete unit disk coverage (DUDC) problem. Given n points in a plane and unit disks with radius r, the objective of the DUDC problem is to determine a minimum number of the disks to cover all points. This paper presented an approach, which makes use of a greedy heuristic-based algorithm, to get the approximate optimal solution for the DUDC problem within polynomial time. The presented approach generated discrete cells to represent the 2D plane. Then, unit disks can be placed at the center of cells. Target points covered by the disks can be used to generate basic sets. A greedy algorithm was articulated to find a minimal combination of the covering sets that facilitates the realization of full coverage of all target points. The center of the minimal covering circles regarding the points in the sets was calculated and considered as the positions of the disks. Based on a case study, the effectiveness of the proposed algorithm has been validated. The factors that influence the performance of the algorithm were also discussed.

中图分类号: