半径r可以覆盖n个点的最小圆数 [英] Minimum number of circles with radius r to cover n points

问题描述

要覆盖所有n个点，半径为r的最小圆数是多少?将给出r和n作为输入，然后是代表n个点的x-y坐标的n对整数.r为实数且大于0.n为＜.20.

如果一个点位于圆内，则该圆将覆盖该点.如果点与圆心之间的距离小于或等于r，则该点位于圆内.

解决方案

这可能不是最佳解决方案，但尝试对其进行优化.

算法基于随机抽样:

1. 在地图上生成N个圆圈
2. 删除所有未覆盖任何点的圆
3. 按覆盖点数降序排列圆圈
4. Foreach圆(已排序)-将圆所覆盖的点标记为已覆盖.如果圆圈没有覆盖任何新点，则从列表中删除.

以下是您可以实时预览的代码:

编辑2(最终算法)

最后:

1. 每个点在距点小于R的随机距离内生成N = 10个圆(圆的半径，因此我们可以确定每个圆至少有一个点属于该圆，并且每个点至少属于一个圆)
2. 重复直到所有要点都包括在内:
   • 获取覆盖最大未发现点数的圆圈.将点标记为已覆盖.

以下是为我带来最佳结果的版本，您可以在此处进行检查 http://jsfiddle.net/nwvao72r/4/每30点平均12圈.

What is the minimum number of circles with radius r needed to cover all n points? r and n will be given as input, followed by n pairs of integers representing the x-y co-ordinates of the n points. r is a real number and greater than 0. n is < 20.

A circle covers a point if the point lies inside the circle. A point lies inside a circle if the distance between the point and the center of the circle is less than or equal to r.

解决方案

This is not the best solution probably but and attempt to optimize it.

Algorithm is based on random sampling:

1. Generate N circles on the map
2. Remove all circles that are not covering any point
3. Sort circles descending by number of covered points
4. Foreach circle (sorted) - mark points that are covered by circle as covered. If circle is not covering any new points remove from the list.

Here is code you can preview it live: http://jsfiddle.net/rpr8qq4t/ example result (13 circles per 30 points):

Parametrizations:

  var POINTS_NUMBER = 30;
  var RADIUS = 50;
  var SAMPLE_COUNT = 400;

Some optimizations may be added to it (for example some circles can be excluded from the list too early)

Edit:

1. Change in step 1 brings better results: Generate N circles for each point (circles that covers at least on point) New version: http://jsfiddle.net/nwvao72r/3/

Edit 2 (final algorithm)

Finally:

1. Foreach point generate N=10 circles in random distance less than R from point (radius of circle so we are sure that for each circle at least one point belongs to it and each point belongs to at least one circle)
2. Repeat until all points are covered:
   • get circle covering max number of uncovered points. Mark points as covered.

Here is the version that brings best results for me, you can check it here http://jsfiddle.net/nwvao72r/4/ on average 12 circles per 30 points here.

这篇关于半径r可以覆盖n个点的最小圆数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！