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

Abstract

A greedy heuristic-based algorithm was put forward to obtain the approximate optimal solution for the DUDC(discrete unit disk cover) problem within polynomial time. Firstly, discrete cells were generated to represent the 2D plane. Then, alternative sets which can cover certain amount of target points were built. A greedy algorithm was articulated to find a minimal combination of the alternative sets, and full coverage of all target points was realized. The minimal covering circles were calculated considering the position of each point in the sets. The center of the minimal covering circles was selected as the location. Based on a case study, the effectiveness of the proposed algorithm was validated. The factors of influence the performance of the algorithm were also discussed and ratio of time complexity and approximation was analyzed.