В рейтинге участвует:

групп:

каналов:

Виртуальный сервер на SSD - недорого!

Аренда выделенных и виртуальных серверов (VDS/VPS), хостинг, аренда IP-адресов, администрирование, круглосуточная поддержка

qwarta.ru подробнее

Резервное копирование с проверкой на вирусы!!!

Удобный сервис создания резервных копий на любой сервер сети интернет. Отслеживайте изменения, проверяйте на вирусы. Надежно защитите свой бизнес!

go.backupland.com

Выбираете сервер? Любая конфигурация на заказ!

Аренда физических серверов любых конфигураций под любые запросы - 1С бухгалтерия, игровые сервера, нагруженные проекты, интернет-магазины!

qwarta.ru подробнее

Size: a a a

pro.algorithms

1761 membersпожаловаться на группу
2020 October 25

EZ

Evgenii Zheltonozhsk... in pro.algorithms
Евгений Вознесенский
А можете посоветовать идейно, куда копать для задачи нахождения минимальной суммы площадей прямоугольников для покрытия n точек с ограничением на не более чем k прямоугольников?

Прямоугольники не могут пересекаться, паралельные осям координат

Выглядит устрашающе...
Динамика мб (какая конкретно не придумал)
источник
17:57пожаловаться#1

ЕВ

Евгений Вознесенский... in pro.algorithms
Точек кстати, не более 50. Может, перебор какой-то?
источник
17:58пожаловаться#2

GK

Gleb Koveshnikov in pro.algorithms
Евгений Вознесенский
Точек кстати, не более 50. Может, перебор какой-то?
По маскам будет очень долго
источник
17:58пожаловаться#3

ЕВ

Евгений Вознесенский... in pro.algorithms
Евгений Вознесенский
А можете посоветовать идейно, куда копать для задачи нахождения минимальной суммы площадей прямоугольников для покрытия n точек с ограничением на не более чем k прямоугольников?

Прямоугольники не могут пересекаться, паралельные осям координат

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

А изначальные k прямоугольников можно накинуть на точки перебором?🤔
источник
18:14пожаловаться#4

ЕВ

Евгений Вознесенский... in pro.algorithms
Хотя нет, даже изначальный перебор это оверкилл
источник
18:16пожаловаться#5

K

Kotomord_λapki in pro.algorithms
Стороны прямоугольников параллельны осям?
источник
18:16пожаловаться#6

ЕВ

Евгений Вознесенский... in pro.algorithms
+
источник
18:16пожаловаться#7

K

Kotomord_λapki in pro.algorithms
Интересно, есть ли разделяй-и-властвуй
источник
18:17пожаловаться#8

K

Kotomord_λapki in pro.algorithms
А есть, по углу
источник
18:19пожаловаться#9

K

Kotomord_λapki in pro.algorithms
Или нет, хз
источник
18:19пожаловаться#10

@N

@urandon Nikita Khom... in pro.algorithms
Евгений Вознесенский
А можете посоветовать идейно, куда копать для задачи нахождения минимальной суммы площадей прямоугольников для покрытия n точек с ограничением на не более чем k прямоугольников?

Прямоугольники не могут пересекаться, паралельные осям координат

Выглядит устрашающе...
Полигоны какие? Выпуклые / невыпуклые / с дырками / самопересечениями?

UPD. А, там прямоугольники
источник
18:23пожаловаться#11

ЕВ

Евгений Вознесенский... in pro.algorithms
По-идее, можно сначало накинуть по прямоугольнику на точку, а затем их объединять пока количество больше k.

Хотя нужно придумать, как их объеденять.

Вопрос ещё в том, что если мы на текущем шаге сделали оптимальное объедение по площади, то приведёт ли это нас к оптимальному решению в итоге.
источник
18:51пожаловаться#12

MK

Matwey Kornilov in pro.algorithms
Евгений Вознесенский
А можете посоветовать идейно, куда копать для задачи нахождения минимальной суммы площадей прямоугольников для покрытия n точек с ограничением на не более чем k прямоугольников?

Прямоугольники не могут пересекаться, паралельные осям координат

Выглядит устрашающе...
Что-то про деревья
источник
22:36пожаловаться#13

MK

Matwey Kornilov in pro.algorithms
Могу жадный алгоритм предложить
источник
22:50пожаловаться#14

MK

Matwey Kornilov in pro.algorithms
Не уверен, что точное решение не NP задача
источник
22:50пожаловаться#15

ЕВ

Евгений Вознесенский... in pro.algorithms
Matwey Kornilov
Могу жадный алгоритм предложить
Топ, предложи, пожалуйста
источник
23:35пожаловаться#16

MK

Matwey Kornilov in pro.algorithms
Евгений Вознесенский
Топ, предложи, пожалуйста
берешь большой прямоугольник min(x) min(y) max(x) max(y), он описывает все точки.
дальше ищешь как его поделить на два. таких способов будет 2(N-1), из них надо выбрать способ с минимальной суммой площадей.
потом каждый прямоугольник опять делишь пока не кончатся свободные прямоугольники
источник
23:37пожаловаться#17

MK

Matwey Kornilov in pro.algorithms
Еще можно посмотреть на алгоритмы кластеризации, типа разбить на k кластеров точки и каждый в свой прямоугольник вписать. Но это зависит от того как твои точки обычно выглядят
источник
23:43пожаловаться#18

ЕВ

Евгений Вознесенский... in pro.algorithms
Matwey Kornilov
Еще можно посмотреть на алгоритмы кластеризации, типа разбить на k кластеров точки и каждый в свой прямоугольник вписать. Но это зависит от того как твои точки обычно выглядят
Ну точки в 2д пространстве
источник
23:43пожаловаться#19

MK

Matwey Kornilov in pro.algorithms
Евгений Вознесенский
Ну точки в 2д пространстве
ну они могут быть насыпаны почти равномерно, а могут кучковаться
источник
23:43пожаловаться#20