Каково минимальное количество окружностей с радиусом r, необходимым для покрытия всех n точек? r и n будут представлены как входные данные, за которыми следуют n пар целых чисел, представляющих координаты x-y n точек. r является действительным числом и больше, чем 0. n представляет собой < 20.
Круг охватывает точку, если точка лежит внутри круга. Точка лежит внутри круга, если расстояние между точкой и центром круга меньше или равно r.
Это не лучшее решение, возможно, но и попытка его оптимизации.
Алгоритм основан на случайной выборке:
Вот код, который вы можете просмотреть в прямом эфире: http://jsfiddle.net/rpr8qq4t/ пример результата (13 кругов на 30 очков):
Параметризации:
var POINTS_NUMBER = 30;
var RADIUS = 50;
var SAMPLE_COUNT = 400;
Некоторые оптимизации могут быть добавлены к нему (например, некоторые круги могут быть исключены из списка слишком рано)
Edit
Изменить 2 (окончательный алгоритм)
Наконец:
Вот версия, которая приносит мне лучшие результаты, вы можете проверить ее здесь http://jsfiddle.net/nwvao72r/4/ в среднем на 12 кругов на 30 пунктов.
Я уверен, что эта проблема NP-hard, хотя я не собираюсь это доказывать здесь.
Если это NP-жесткий, то для поиска гарантированного оптимального решения я рекомендую следующий подход:
При любых двух точках, меньших 2r друг от друга, ровно две окружности радиуса r, проходящие через эти точки:
[EDIT: мое первоначальное описание "наилучших возможных" кругов было неправильным, хотя это не приводит к проблемам - благодаря комментатору Джорджу, чтобы описать правильный способ подумать об этом.]
Если круг покрывает максимальное множество точек (это означает, что круг не может быть перемещен, чтобы покрыть один и тот же набор точек плюс не менее 1), то этот круг можно скользить, пока его граница не коснется ровно двух точек он охватывает, скажем, сдвигая его до тех пор, пока он не коснется уже покрытой точки, а затем повернет его по часовой стрелке вокруг этой касательной точки, пока не коснется другой уже покрытой точки. Этот перемещенный круг будет охватывать ровно множество точек, покрытых оригинальным кругом. Более того, нам не нужно рассматривать круги, которые охватывают немаксимальные множества точек, потому что максимальная окружность, покрывающая эти точки и более, по крайней мере так же полезна и не стоит больше. Это означает, что нам нужно только рассмотреть круги, которые касаются двух точек. При условии, что мы генерируем оба круга для каждой достаточно близкой пары точек на входе, мы будем генерировать все круги, которые потенциально могут понадобиться.
Таким образом, наш пул потенциальных кругов содержит не более 2 кругов на пару точек, для максимума n * (n-1) потенциальных кругов в целом. (Обычно их будет меньше, потому что некоторые пары точек будут, как правило, более чем на 2r друг от друга и, следовательно, не могут быть покрыты одним кругом радиуса r.) Кроме того, нам нужен дополнительный круг для каждой точки, которая больше 2r из любого другая точка - эти круги также могут быть сосредоточены на этих отдаленных точках.
Все, на что мы действительно заботимся, - это набор точек, охватываемых каждым потенциальным кругом. Поэтому для каждого потенциального круга найдите точки, которые он охватывает. Это можно сделать во время O (n ^ 3) в целом, используя проход O (n) для каждого потенциального круга. Чтобы немного ускорить работу, если мы обнаружим, что два разных круга покрывают ровно один и тот же набор точек, нам нужно только сохранить один из этих кругов (множество покрытых точек). Также мы можем отбросить любое покрытое множество точек, которое является подмножеством некоторого другого покрытого набора точек - всегда предпочтительнее выбирать более крупное покрытое множество точек в этом случае.
Наконец, у нас есть набор покрытых точечных множеств, и мы хотим найти минимальное подмножество этих множеств, которое охватывает каждую точку. Это установить проблему покрытия. Я не знаю конкретного алгоритма для решения этой проблемы, но ветвь и привязка является стандартным подходом к таким проблемам - она часто намного быстрее, чем более простой исчерпывающий поиск в обратном направлении. Сначала я бы попробовал поиск, сначала найдя одно (или более) эвристические решения, надеясь, что получим хорошую верхнюю границу, которая уменьшит время поиска ветвей и границ. Я думаю, что даже лучшие алгоритмы для этого берут экспоненциальное время в худшем случае, хотя я думаю, что это будет управляемо для n < 20, так как там не более 19 * 18 = 342 разных наборов точек.
Я понимаю, что круги не должны центрироваться в точках и поэтому вычислять все круги, проходящие через любую комбинацию из двух точек, включая круги, центрированные в каждой точке. Затем я нахожу, какие точки каждый круг покрывает и использует жадный алгоритм, чтобы найти минимальный набор кругов, чтобы покрыть все точки, но опять же, это может быть не минимальное множество кругов, но довольно легко вычислить.
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)}]]
Плитка, затем нажмите
Шаг 2, черепица может быть оптимизирована путем шага по каждой точке и вычисления/сохранения только тех кругов, которые будут содержать точку, если черепица будет очень скудной.
Из статьи "Проблема дискретного дискового накопителя" Гаутама К. Даса и др. Al:.
Минимальная геометрическая крышка диска. В задаче минимального геометрического покрытия диска вход состоит из набора точек на плоскости, и задача состоит в том, чтобы найти набор единичных дисков минимальной мощности, объединение которых покрывает точки. В отличие от DUDC, дисковые центры не могут быть выбраны из заданного дискретного набора, но могут быть центрированы в произвольных точках плоскости. Опять же, эта проблема NP-hard [9] и имеет решение PTAS [11, 12].
Литература:
- R. Фаулер, М. Патерсон и С. Танимото, Оптимальная упаковка и покрытие в плоскости являются NP-полными, Information Processing Letters, vol 12, pp. 133-137, 1981.
- G. Фредериксон, Быстрые алгоритмы для кратчайших путей в планарных графах, с приложениями, SIAM J. on Computing, vol. 16, pp. 1004-1022, 1987.
- Т. Gonzalez, Покрытие набора точек в многомерном пространстве, Обработка информации, том 40, стр. 181-188, 1991.
- D. Хохбаум и В. Маасс, Схемы приближения для задач покрытия и упаковки при обработке изображений и СБИС, J. ACM, том 32, стр. 130-136, 1985.
Это мой первый ответ, который я оставлю, поскольку на него ссылается другой ответ. Но см. мой более поздний ответ, который рассматривает круги между двумя точками, а не этим. Вот жадный алгоритм, закодированный в 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
Примечание: данные ввода-вывода рудиментарны, но алгоритм должен быть четким.
Если круг с центром C(cx, cy) охватывает точку P(px, py), тогда расстояние |CP| < r (r - радиус).
Таким образом, область, где центр круга может быть таким, что охватывает точку P, представляет собой круг с центром в P и радиусом r. Теперь давайте рисуем все круги с центрами в заданных точках и радиусе r. Если некоторые круги пересекаются, мы можем нарисовать новый круг с центром в таком пересечении, который покрывает соответствующие точки.
Поэтому для каждой пары входных точек мы проверяем, пересекаются ли круги.
Предположим, что входные точки - это вершины, а пересечение - между ними.
Теперь у нас есть минимальное краевое задание с ограниченным графом, охватывающее http://en.wikipedia.org/wiki/Edge_cover, которое может быть разрешено за многочленное время (хотя с ограничением n < 20 грубая сила, вероятно, быть приемлемым)
UPDATE. Это не край. Моя ошибка.
Я не уверен, что это правильно, но если нам не нужны точные местоположения кругов решений, мне кажется, что мы сможем решить это, посмотрев на кластеры точек: в любом из окружности решения, расстояние между любыми двумя точками должно быть меньше или равно 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)]])
Код Haskell:
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
Если вы поместите n круги (радиус r), центрированные в каждой точке, области поиска/точки максимального перекрытия и поместите новые круги (радиус r), центрированные в этой области. Я не уверен, что это лучший способ решения решения (если это способ решить эту проблему, кроме грубой силы), я уверен, что вы можете реализовать ее с довольно приличным количеством математики и таким образом снижая сложность выполнения вашего решения во время выполнения. Надеюсь это поможет. Пожалуйста, сообщите нам.