覆盖所有 n 个点所需的半径为 r 的最小圆数是多少？r 和 n 将作为输入给出，然后是 n 对整数，表示 n 个点的 xy 坐标。r 是一个实数，大于 0。n < 20。
如果该点位于圆内，则圆覆盖该点。如果该点与圆心之间的距离小于或等于 r，则该点位于圆内。
问问题
10721 次
9 回答
12
这可能不是最好的解决方案，但并尝试对其进行优化。
算法基于随机抽样：
- 在地图上生成 N 个圆圈
- 删除所有不覆盖任何点的圆圈
- 按覆盖点数降序排列圆
- Foreach circle (sorted) - 将圆圈覆盖的点标记为已覆盖。如果圆圈没有覆盖任何新点，则从列表中删除。
这是您可以实时预览的代码：http: //jsfiddle.net/rpr8qq4t/示例结果（每 30 个点 13 个圆圈）：
参数化：
var POINTS_NUMBER = 30;
var RADIUS = 50;
var SAMPLE_COUNT = 400;
可能会添加一些优化（例如某些圆圈可能会过早地从列表中排除）
编辑：
- 步骤 1 中的更改带来更好的结果：为每个点生成 N 个圆圈（至少覆盖一个点的圆圈）新版本：http: //jsfiddle.net/nwvao72r/3/
编辑 2（最终算法）
最后：
- Foreach 点在距点小于 R 的随机距离内生成 N=10 个圆（圆的半径，因此我们确信对于每个圆至少有一个点属于它，并且每个点至少属于一个圆）
- 重复直到覆盖所有点：
- 获得覆盖最大未覆盖点数的圆圈。将点标记为已覆盖。
这是给我带来最好结果的版本，你可以在这里查看 http://jsfiddle.net/nwvao72r/4/这里 平均每 30 点 12 圈。
于 2014-08-21T10:44:22.347 回答
10
我确定这个问题是 NP 难的，尽管我不打算在这里尝试证明这一点。
如果它是 NP 难的，那么为了找到一个有保证的最优解决方案，我推荐以下方法：
- 找到所有“好”的潜在圆圈位置，并为每个记录其中包含哪些点。
- 用这些点集解决集合覆盖问题。（这个问题是 NP 难的。）
良好的圈子位置
给定距离小于 2r 的任意 2 个点，正好有两个半径为 r 的圆穿过这些点：
[编辑：我最初对“最佳”圈子的描述是错误的，尽管这不会导致问题——感谢评论者乔治描述了思考这个问题的正确方法。]
如果一个圆覆盖了最大的一组点（意味着该圆不能重新定位以覆盖相同的一组点加上至少 1 个以上），那么该圆可以滑动直到其边界恰好接触它所覆盖的两个点 - - 比如说，将它向左滑动直到它接触到一个已经覆盖的点，然后围绕这个接触点顺时针旋转它直到它接触到另一个已经覆盖的点。这个移动的圆圈将完全覆盖原始圆圈所覆盖的点集。此外，我们永远不需要考虑覆盖非最大点集的圆，因为覆盖这些点和更多点的最大圆至少是有用的并且不会花费更多。这意味着我们只需要考虑接触两点的圆。
所以我们的潜在圈子池每对点最多包含 2 个圈子，总共最多 n*(n-1) 个潜在圈子。（通常会更少，因为一些点对通常相距超过 2r，因此不能被半径为 r 的单个圆所覆盖。）此外，我们需要一个额外的圆来处理距离任何点超过 2r 的每个点另一点——这些圆圈也可能以这些远程点为中心。
设置封面
我们真正关心的是每个潜在圆圈所涵盖的点集。因此，对于每个潜在的圆圈，找到它所覆盖的点。这可以在 O(n^3) 时间内完成，对每个潜在的圆圈使用 O(n) 次。为了稍微加快速度，如果我们发现两个不同的圆圈覆盖完全相同的一组点，我们只需要保留其中一个圆圈（一组覆盖的点）。我们也可以丢弃任何作为其他覆盖点集子集的覆盖点集——在这种情况下，总是最好选择更大的覆盖点集。
最后，我们有一个覆盖点集的集合，我们想要找到覆盖每个点的这些集合的最小子集。这就是套套问题。我不知道解决这个问题的具体算法，但分支定界是此类问题的标准方法——它通常比简单的穷举回溯搜索快得多。我首先会通过首先找到一个（或多个）启发式解决方案来启动搜索，希望能产生一个好的上限，从而减少分支和边界搜索时间。我认为即使是最好的算法在最坏的情况下也需要指数时间，尽管我认为这对于 n < 20 是可以管理的，因为最多有 19*18 = 342 个不同的点集。
于 2013-04-08T21:24:24.313 回答
7
来自 Gautam K. Das 等人的论文“关于离散单元磁盘盖问题”。人：
最小几何圆盘盖。在最小几何圆盘覆盖问题中，输入由平面上的一组点组成，问题是找到一组最小基数的单位圆盘，其并集覆盖这些点。与 DUDC 不同，磁盘中心不限于从给定的离散集中选择，而是可以以平面中的任意点为中心。同样，这个问题是 NP-hard [9] 并且有一个 PTAS 解决方案 [11, 12]。
参考：
- R. Fowler、M. Paterson 和 S. Tanimoto，平面中的最佳包装和覆盖是 NP 完全的，信息处理快报，第 12 卷，第 133-137 页，1981。
- G. Frederickson，平面图中最短路径的快速算法及其应用，SIAM J. on Computing，第 16 卷，第 1004-1022 页，1987 年。
- T. Gonzalez，涵盖多维空间中的一组点，信息处理快报，第 40 卷，第 181-188 页，1991 年。
- D. Hochbaum 和 W. Maass，图像处理和 VLSI 中覆盖和打包问题的近似方案，J. ACM，第 32 卷，第 130-136 页，1985 年。
于 2015-04-23T06:44:43.170 回答
4
我意识到圆不必以点为中心，因此计算通过两个点的任意组合的所有圆，包括以每个点为中心的圆。然后我找到每个圆圈覆盖的点，并使用贪心算法找到一个最小的圆圈集来覆盖所有点，但同样，它可能不是最小的圆圈集，但很容易计算。
from collections import namedtuple
from itertools import product
from math import sqrt
from pprint import pprint as pp
Pt = namedtuple('Pt', 'x, y')
Cir = namedtuple('Cir', 'x, y, r')
def circles_from_p1p2r(p1, p2, r):
'Following explanation at http://mathforum.org/library/drmath/view/53027.html'
(x1, y1), (x2, y2) = p1, p2
if p1 == p2:
#raise ValueError('coincident points gives infinite number of Circles')
return None, None
# delta x, delta y between points
dx, dy = x2 - x1, y2 - y1
# dist between points
q = sqrt(dx**2 + dy**2)
if q > 2.0*r:
#raise ValueError('separation of points > diameter')
return None, None
# halfway point
x3, y3 = (x1+x2)/2, (y1+y2)/2
# distance along the mirror line
d = sqrt(r**2-(q/2)**2)
# One answer
c1 = Cir(x = x3 - d*dy/q,
y = y3 + d*dx/q,
r = abs(r))
# The other answer
c2 = Cir(x = x3 + d*dy/q,
y = y3 - d*dx/q,
r = abs(r))
return c1, c2
def covers(c, pt):
return (c.x - pt.x)**2 + (c.y - pt.y)**2 <= c.r**2
if __name__ == '__main__':
for r, points in [(3, [Pt(*i) for i in [(1, 3), (0, 2), (4, 5), (2, 4), (0, 3)]]),
(2, [Pt(*i) for i in [(1, 3), (0, 2), (4, 5), (2, 4), (0, 3)]]),
(3, [Pt(*i) for i in [(-5, 5), (-4, 4), (3, 2), (1, -1), (-3, 2), (4, -2), (6, -6)]])]:
n, p = len(points), points
# All circles between two points (which can both be the same point)
circles = set(sum([[c1, c2]
for c1, c2 in [circles_from_p1p2r(p1, p2, r) for p1, p2 in product(p, p)]
if c1 is not None], []))
# points covered by each circle
coverage = {c: {pt for pt in points if covers(c, pt)}
for c in circles}
# Ignore all but one of circles covering points covered in whole by other circles
#print('\nwas considering %i circles' % len(coverage))
items = sorted(coverage.items(), key=lambda keyval:len(keyval[1]))
for i, (ci, coveri) in enumerate(items):
for j in range(i+1, len(items)):
cj, coverj = items[j]
if not coverj - coveri:
coverage[cj] = {}
coverage = {key: val for key, val in coverage.items() if val}
#print('Reduced to %i circles for consideration' % len(coverage))
# Greedy coverage choice
chosen, covered = [], set()
while len(covered) < n:
_, nxt_circle, nxt_cov = max((len(pts - covered), c, pts)
for c, pts in coverage.items())
delta = nxt_cov - covered
covered |= nxt_cov
chosen.append([nxt_circle, delta])
# Output
print('\n%i points' % n)
pp(points)
print('A minimum of circles of radius %g to cover the points (And the extra points they covered)' % r)
pp(chosen)
显示三个运行的输出是：
5 points
[Pt(x=1, y=3), Pt(x=0, y=2), Pt(x=4, y=5), Pt(x=2, y=4), Pt(x=0, y=3)]
A minimum of circles of radius 3 to cover the points (And the extra points they covered)
[[Cir(x=2.958039891549808, y=2.5, r=3),
{Pt(x=4, y=5), Pt(x=0, y=3), Pt(x=1, y=3), Pt(x=0, y=2), Pt(x=2, y=4)}]]
5 points
[Pt(x=1, y=3), Pt(x=0, y=2), Pt(x=4, y=5), Pt(x=2, y=4), Pt(x=0, y=3)]
A minimum of circles of radius 2 to cover the points (And the extra points they covered)
[[Cir(x=1.9364916731037085, y=2.5, r=2),
{Pt(x=0, y=3), Pt(x=1, y=3), Pt(x=0, y=2), Pt(x=2, y=4)}],
[Cir(x=4, y=5, r=2), {Pt(x=4, y=5)}]]
7 points
[Pt(x=-5, y=5),
Pt(x=-4, y=4),
Pt(x=3, y=2),
Pt(x=1, y=-1),
Pt(x=-3, y=2),
Pt(x=4, y=-2),
Pt(x=6, y=-6)]
A minimum of circles of radius 3 to cover the points (And the extra points they covered)
[[Cir(x=3.9951865152835286, y=-0.8301243435223524, r=3),
{Pt(x=3, y=2), Pt(x=1, y=-1), Pt(x=4, y=-2)}],
[Cir(x=-2.0048134847164714, y=4.830124343522352, r=3),
{Pt(x=-4, y=4), Pt(x=-3, y=2), Pt(x=-5, y=5)}],
[Cir(x=6.7888543819998315, y=-3.1055728090000843, r=3), {Pt(x=6, y=-6)}]]
于 2013-04-09T19:39:35.003 回答
3
平铺然后摇晃
- TILE：找到包围所有点的矩形
- 用间隔为 r * sqrt(2) 的圆圈平铺矩形区域。
- 对于每个点，计算它们是哪些圆圈以及每个圆圈中有哪些点。
- 删除任何没有点的圆圈。
- 删除仅包含多个圆中包含的点的任何圆。
- 重复5，直到没有更多。
- 摇晃：对于每个圆圈：尝试移动它以查看它是否可以覆盖其原始点以及最大的新点，然后这样做。
- 再做4和5。
- 重复 7 直到摇晃不改变哪些圆点在或时间耗尽。
第 2 步，如果平铺非常稀疏，则可以通过遍历每个点并仅计算/保留那些包含一个点的圆来优化平铺。
于 2014-08-21T16:14:31.133 回答
2
我不确定这是否正确，但如果我们不需要解圈的确切位置，在我看来，我们可以通过查看点簇来解决这个问题：在任何解决方案中 -圆，任意两点之间的距离应小于或等于 2*r。
算法：
1. j_random_hacker indicated that any solution-circle could be shifted so that
two of its covered-points lay on its circumference without changing the
original covered-points. Since the solution-circle radius is given, for each
point: (a) calculate potential circle-centers using the point, radius, and
each other point that is at a distance of 2*r or less, (b) for each circle,
list the cluster of points that it could cover. Sort each cluster and, for
each point, remove duplicate clusters.
2. For each cluster group in 1., choose the cluster that has the greatest point-
count, that is, the cluster that is most shared.
3. Remove duplicates and clusters that are sub-sequences of other clusters
from 2., and present the resulting size of 2. (perhaps together with the
chosen clusters) as the solution.
等边三角形的输出，r=3，[(0,0),(5.196152422706632,3),(5.196152422706632,-3)]
*Main> solve
(2,[[(0.0,0.0),(5.196152422706632,3.0)],[(0.0,0.0),(5.196152422706632,-3.0)]])
Paddy3118 示例的输出，r=3, [(1,3),(0,2),(4,5),(2,4),(0,3)]：
*Main> solve
(1,[[(0.0,2.0),(0.0,3.0),(1.0,3.0),(2.0,4.0),(4.0,5.0)]])
r=3, [(-5,5),(-4,4),(3,2),(1,-1),(-3,2),(4,-2),(6 的输出,-6)]:
*Main> solve
(3,[[(-5.0,5.0),(-4.0,4.0),(-3.0,2.0)],[(1.0,-1.0),(3.0,2.0),(4.0,-2.0)],
[(4.0,-2.0),(6.0,-6.0)]])
哈斯克尔代码：
import Data.List (delete, nub, nubBy, isInfixOf, sort, sortBy, maximumBy)
points = [(0,0),(5.196152422706632,3),(5.196152422706632,-3)]--[(1,3),(0,2),(4,5),(2,4),(0,3)]--[(-5,5),(-4,4),(3,2),(1,-1),(-3,2),(4,-2),(6,-6)]
r = 3
twoR = 2*r
circleCenters (x1,y1) (x2,y2) =
let q = sqrt $ (x2-x1)^2 + (y2-y1)^2
(x3, y3) = ((x1+x2)/2,(y1+y2)/2)
first = (x3 + sqrt(r^2-(q/2)^2)*(y1-y2)/q, y3 + sqrt(r^2-(q/2)^2)*(x2-x1)/q)
second = (x3 - sqrt(r^2-(q/2)^2)*(y1-y2)/q, y3 - sqrt(r^2-(q/2)^2)*(x2-x1)/q)
in [first,second]
isInCircle (center_x,center_y) (x,y) = (x-center_x)^2 + (y - center_y)^2 <= r^2
findClusters (px,py) =
nub [sort $ [(px,py)] ++ filter (isInCircle a) potentialPoints | a <- potentialCircleCenters]
where
potentialPoints = filter (\(x,y) -> (x-px)^2 + (y-py)^2 <= twoR^2) (delete (px,py) points)
potentialCircleCenters = concatMap (circleCenters (px,py)) potentialPoints
solve = (length bestClusters, bestClusters) where
clusters = map findClusters points
uniqueClusters = nub . concat $ clusters
bestClusterForEachPoint = map (maximumBy (\a b -> compare (length a) (length b))) clusters
bestClusters = nub . nubBy (\a b -> isInfixOf a b) . sortBy (\a b -> compare (length b) (length a))
$ bestClusterForEachPoint
于 2013-04-09T15:01:54.800 回答
1
这是我的第一个答案，因为另一个答案提到了它，所以我将保留它。但是请参阅我稍后的答案，该答案考虑了两点之间的圆圈，而不是这个。 这是一个用 Python 编码的贪心算法，它会找到一个最小值，但我不知道它是否是最小的解决方案。
dbg = False
if not dbg:
r, n = (int(s) for s in input('r n: ').split())
points = p = [ tuple(int(s) for s in input('x%i y%i: ' % (i, i)).split())
for i in range(n) ]
else:
r, n, points = 3, 5, [(1, 3), (0, 2), (4, 5), (2, 4), (0, 3)]; p = points
# What a circle at each point can cover
coverage = { i: frozenset(j
for j in range(i, n)
if (p[i][0] - p[j][0])**2 + (p[i][1] - p[j][1])**2 <= r**2)
for i in range(n)}
# Greedy coverage choice
chosen, covered = [], set()
while len(covered) < n:
# Choose the circle at the point that can cover the most ADDITIONAL points.
_, nxt_point, nxt_cov = max((len(pts - covered), i, pts)
for i, pts in coverage.items())
covered |= nxt_cov
chosen.append(nxt_point)
print('Cover these points:\n %s' % '\n '.join('%s, %s' % p[i] for i in chosen))
这是一个示例运行：
r n: 3 5
x0 y0: 1 3
x1 y1: 0 2
x2 y2: 4 5
x3 y3: 2 4
x4 y4: 0 3
Cover these points:
1, 3
4, 5
注意：数据 i/o 是初级的，但算法应该清楚
于 2013-04-08T18:31:00.393 回答
1
如果中心圆C(cx, cy)覆盖点，P(px, py)则距离|CP| < r（r-半径）。因此，圆心可能是覆盖点的区域P是圆心 inP和 radius r。现在让我们以给定的点和半径绘制所有圆心r。如果一些圆相交，那么我们可以在覆盖相应点的交叉点上绘制以中心为中心的新圆。因此，对于每一对输入点，我们检查圆是否相交。
假设输入点是顶点，并且它们之间的交点是边缘。现在我们有一个已知的图问题最小边覆盖http://en.wikipedia.org/wiki/Edge_cover可以在多项式时间内解决（尽管有限的n < 20蛮力可能是可以接受的）
更新。那不是边缘覆盖。我的错。
于 2013-04-08T21:22:06.283 回答
0
If you place n circles (of radius r) all centered at each point, the find regions/points of maximum overlap and place new circles (of radius r) centered in that region. I'm not sure if this is the best way of solving the solution (if this is a way to solve it, besides the brute force way), I'm sure you can implement it with a quite a decent amount of math, and thus lowering the run-time complexity of your solution. Hope this helps. Please give feedback.
于 2013-04-08T18:15:06.260 回答