Как я могу уменьшить сетку квадратов одинакового размера до минимального набора прямоугольников?

Question

Если у меня есть сетка произвольного размера из квадратов одинакового размера (без промежутков между ними), мне нужно знать эффективный способ уменьшить их до минимальное количество прямоугольников, например, если каждая звездочка представляет квадрат, то это может быть уменьшено до одного большого прямоугольника:

*****
*****
*****

Хотя это можно уменьшить до двух прямоугольников:

  ***             ***
*****   =>  **(1) ***(2)
*****       **    ***
  ***             ***

Очевидное решение состоит в том, чтобы собрать соседние квадраты в каждом ряду, а затем собрать смежные ряды, которые идентичны. Для моего второго примера это будет три прямоугольника, что не оптимально.

  *** (1)

***** (2)
*****

  *** (3)

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

Answer 1

У меня есть ощущение, что эта проблема может быть сложной ... например, рассмотрим

   *
   ***
****
   ***
   *

Оптимальное решение - 4

   B
   BCC
AAAB
   BDD
   B

но я не нахожу простой способ предвидеть, исходя из местных соображений, что А должен остановиться перед последним квадратом. В оптимальном решении A, C и D являются немаксимальными прямоугольниками, и только B является максимальным. Вещи могут стать еще более сложными, например, с:

   *
   ***
****
   ***
   *
 *****
  * *
  * *

, где оптимальным решением является

   B
   BCC
AAAB
   BDD
   B
 EEEEE
  F G
  F G

, где только E является максимальным. Также выглядит, что на самом деле легко построить сколь угодно большие задачи, когда в оптимальном решении все, кроме одного, не максимальны. Конечно, это не означает, что в IMO не существует простого решения ... как я уже говорил, это интуитивное чувство, но у IMO у любого решателя, который рассуждает с максимальными прямоугольниками, будут проблемы, если необходим абсолютный минимум.

Для несколько схожей, но и другой проблемы (я искал минимальное покрытие с не обязательно непересекающимися дисками), я использовал медленный жадный подход, всегда добавляя к решению диск, который содержался, и покрывая большинство еще не покрытых квадраты. Для вашей проблемы я, вероятно, посмотрю, как это работает, добавляя самый большой прямоугольник каждый раз ... что, как показывают приведенные выше примеры, однако, в общем, это не будет оптимальным решением.

Answer 2

Из головы не знаю, есть ли алгоритм для этого, поэтому я придумал:

Найти (xmin, ymin) (xmax, ymax), то есть минимум и максимум координат x и y существующих квадратов. Это определяет один ограничивающий прямоугольник, охватывающий все ваши квадраты.

Найдите и соедините прямыми вогнутыми углами в пределах ограничительного прямоугольника.

Ответ на комментарии: хорошо, поэтому, если мы соединим все вогнутые углы периметра вдоль линий сетки, постепенно удаляя (маркируя) периферийные прямоугольники, мы получим следующее на вышеприведенном сложном примере:

   A
   XBB
CCCX
   XDD
   X
 EFFFG
  I J
  I J

, что, как справедливо отмечено, является неоптимальным. Есть некоторые решения, которые необходимо принять для того, чтобы попарно соединить вогнутости, когда возможно более одного пути. Выберите тот, который приведет к наименьшему количеству новых прямоугольников. (См. F под самым низким X).

Когда разделение закончено, мы добавляем еще один этап расширения (слияния) существующих прямоугольников. Важно, чтобы допускалось только такое слияние, которое не уменьшает ни одного из существующих прямоугольников. Изменение самого верхнего X на B было бы таким запрещенным изменением, потому что прямоугольник X был уменьшен. Это условие гарантирует, что изменения происходят только в направлении к минимальному количеству прямоугольников. Продолжая эту процедуру на приведенном выше примере, мы получим:

   X
   XBB
CCCX
   XDD
   X
 FFFFF
  I J
  I J

Что в данном примере оказывается оптимальным, но в целом вам может потребоваться выполнить поиск в пространстве состояний с использованием этих операций, чтобы найти глобальный минимум.