Найдите k прямоугольников, чтобы они покрывали максимальное количество точек
В двумерном пространстве, с учетом группы прямоугольников, каждый прямоугольник покрывает несколько точек, и может быть перекрытие между двумя произвольными прямоугольниками для заданного числа K, как я могу найти k прямоугольников, чтобы их объединение покрывало максимальное число точки? В этой задаче, если точка покрыта более чем двумя прямоугольниками, она считается только один раз, и мы предполагаем, что положения и размеры прямоугольников и положения точек фиксированы, как указано во входных данных.
Может кто-нибудь дать мне алгоритм, используемый для его решения? Или указать, что это может быть сведено к какой-то известной проблеме?
4 ответа
Это похоже на геометрическую версию проблемы максимального покрытия, которая тесно связана с проблемой покрытия покрытия, и эти два являются NP-Complete.
Из того, что я мог найти, похоже, что геометрическая версия Set Cover также является NP-Complete, и в статье приведен алгоритм быстрого приближения, который использует тот факт, что он является геометрическим: http://www.almaden.ibm.com/u/kclarkson/set_cover/p.pdf. Тот факт, что геометрическая версия Set Cover является NP-Complete, подразумевает, что геометрическая версия задачи "Максимальное покрытие" также является NP-Complete.
Конечно, ваш частный случай, когда множества являются прямоугольниками, все же может быть пригоден для алгоритмов точного полиномиального времени, но я сомневаюсь в этом. Возможно, ссылки в приведенной выше статье могут привести вас к хорошему решению.
Надеюсь, это поможет!
Я предполагаю, что у вас есть фиксированные прямоугольники (то есть вы не можете выбрать, насколько велики ваши прямоугольники и где они расположены). Если бы вы могли выбрать размер прямоугольников, проблема была бы тривиальной. Если бы вы могли выбрать, где расположить свои прямоугольники, это также было бы другой проблемой (решаемой другим жадным алгоритмом).
Для получения более подробной информации вы должны сообщить нам, как указываются ваши прямоугольники и точки и как они хранятся - или вам нужна помощь в выборе хорошей структуры данных с учетом вашего формата ввода.
Теперь жадное решение вашей проблемы заключается в следующем. Сначала начните со всех "прямоугольников", выбранных в качестве точек покрытия. Затем один за другим удалите прямоугольник, покрывающий наименьшее количество точек, пока в вашем наборе не останется только K прямоугольников. Сложность этого алгоритма является полиномиальной, а его эффективность зависит от того, как вы собираетесь реализовать запрос "выяснить, какой прямоугольник покрывает наименьшее количество точек". Используя кучу, вы можете сделать это в O(1), с фазой предварительной обработки, чтобы построить кучу (сложность которой будет зависеть от того, как хранятся ваши очки).
РЕДАКТИРОВАТЬ: проблема с этим решением заключается в том, что на каждом шаге ответ "сделает так, чтобы у меня было наименьшее количество непокрытых точек" не является уникальным, несколько прямоугольников могут на этом этапе заполнить критерий; в итоге может оказаться, что один выбор был бы лучше другого, и это не могло быть определено на этом этапе...
/---------\
|2 |
/-----\ /-------\
|1 | *| |* | 3|
\-----/ \-------/
| |
\---------/
Например, здесь все прямоугольники связаны: если вы удалите один прямоугольник, вы не обнаружите никаких точек. Однако очевидно, что наилучшее 1-решение состоит в том, чтобы прямоугольник 2 покрывал точки (обратите внимание, что прямоугольники 1 и 3 могут быть произвольно широкими, поэтому размер не является показательным фактором).
Если у вас есть n прямоугольников, k из которых вы должны выбрать, то есть (choose n k) разные комбинации, т.е. (/ (factorial n) (factorial k) (factorial (- n k))), В общем случае я подозреваю, что вам нужно перечислить эти комбинации и рассчитать их охват. Тем не менее, вы могли бы немного сократить это сокращение, упорядочив прямоугольники по покрытию (то есть по количеству точек, покрытых ими), начиная с комбинации самых больших прямоугольников и заканчивая, когда оставшиеся прямоугольники не могут превзойти вашу ранее лучшую комбинацию.
Я думаю, что вам нужен комбинаторный алгоритм оптимизации, который может выбирать значения / узлы (например, здесь прямоугольники), чтобы данная функция давала максимумы. Я не знаю это подробно, но вы можете попробовать оптимизацию в MATLAB