Задача "Круги"

[sasha-parazit]

Не могу найти алгоритм решения следующей задачи:

На плоскости заданы N кругов. Какое минимальное число кругов нужно переместить,
чтобы ни одна пара кругов не имела ни одной общей точки.
Ограничение времени – 2 секунды.

$1\leq N\leq 100$. Координаты и радиусы кругов натуральные числа меньшие 10000.

Замечание. Жадный алгоритм (удаляет круг с которым пересекается наибольшее число кругов и т.д.) не работает.

Подскажите, пожалуйста, идею.

[Zealint]

sasha-parazit в сообщении #484738 писал(а):

Не могу найти алгоритм решения следующей задачи

Мне кажется, вы несколько преувеличиваете проблему поиска алгоритма нахождения максимального паросочетания в двудольном графе.

[Sender]

Zealint в сообщении #484785 писал(а):

sasha-parazit в сообщении #484738 писал(а):

Не могу найти алгоритм решения следующей задачи

Мне кажется, вы несколько преувеличиваете проблему поиска алгоритма нахождения максимального паросочетания в двудольном графе.

По-моему, больше похоже на задачу нахождения вершинной связности графа.

[Klad33]

Смотря как круги разбросаны. Может быть такая ситуация, когда нужно перемещать N-1 кругов, например в таком случае:

[Zealint]

Sender в сообщении #484800 писал(а):

По-моему, больше похоже на задачу нахождения вершинной связности графа.

Если вы отыщите наименьшее число вершин, которые нужно удалить, чтобы граф перестал быть связным, то это не гарантирует, что какие-то два круга перестанут иметь общую точку.

Цитата:

Смотря как круги разбросаны.

В этом, собственно, и состоит задача. Ваш пример можно было изобразить проще - все круги совпадают.

[sasha-parazit]

Zealint в сообщении #484785 писал(а):

Мне кажется, вы несколько преувеличиваете проблему поиска алгоритма нахождения максимального паросочетания в двудольном графе.

но граф не обязательно двудольный. пример на рисунке Klad33

[Zealint]

sasha-parazit в сообщении #484882 писал(а):

Zealint в сообщении #484785 писал(а):

Мне кажется, вы несколько преувеличиваете проблему поиска алгоритма нахождения максимального паросочетания в двудольном графе.

но граф не обязательно двудольный. пример на рисунке Klad33

Ну так да, я же не сказал, что граф создается из кругов, взятых в качестве вершин. Каждую вершину нужно удвоить, одну часть - в левую долю, а вторую - в правую. Потом соединить левую долю с правой, попробуйте подумать, как.

PS. Я, кстати, ещё не доказал, является ли моя идея правильной, поэтому оставляю место для сомнения. Если докажите или опровергните, пните меня здесь, самому интересно стало.

[Sender]

Zealint в сообщении #484865 писал(а):

Если вы отыщите наименьшее число вершин, которые нужно удалить, чтобы граф перестал быть связным, то это не гарантирует, что какие-то два круга перестанут иметь общую точку.

Именно гарантирует, если в качестве вершин графа рассматривать круги, причём две вершины соединены ребром тогда и только тогда, когда соответствующие круги пересекаются.

[sasha-parazit]

Sender в сообщении #485122 писал(а):

Zealint в сообщении #484865 писал(а):

Если вы отыщите наименьшее число вершин, которые нужно удалить, чтобы граф перестал быть связным, то это не гарантирует, что какие-то два круга перестанут иметь общую точку.

Именно гарантирует, если в качестве вершин графа рассматривать круги, причём две вершины соединены ребром тогда и только тогда, когда соответствующие круги пересекаются.

Zealint прав. Несвязный граф может имееть ребера.

[Sender]

sasha-parazit в сообщении #485194 писал(а):

Zealint прав. Несвязный граф может имееть ребера.

Прошу прощения, и впрямь глупость написал. Тут задача поиска не вершинной связности графа, а максимального независимого множества. Только ведь она NP-полна, разве можно гарантированно уложиться в пару секунд на 100 вершинах?

[sasha-parazit]

А где можно посмотреть что она NP-полна?

[Sender]

sasha-parazit в сообщении #485202 писал(а):

А где можно посмотреть что она NP-полна?

Да вот хоть в википедии.

[sasha-parazit]

Да, действительно задача NP-полная. Sender, спасибо за ссылку.