Алгоритм компоновки блоков - программирование

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

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

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

Существуют ли какие-либо эвристики или алгоритмы аппроксимации, которые могут мне помочь?

Результаты выглядят примерно так:

Кроме того, возможно, мой Грататар отдает, что это Mega Man, связанный...

Ответ 1

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

http://gp.home.xs4all.nl/Site/Polyomino_Solver.html.

http://gp.home.xs4all.nl/PolyominoSolver/downloadsolver.htm

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

http://www.math.missouri.edu/~stephen/software/

Я не уверен, что любое из этих программ приблизит наилучшее соответствие полиоминосов, допускающих отверстия. Но это определенно "разрешимо" таким образом, в том смысле, что вы, конечно же, могли бы добавить в ваше решение дополнительные 1-миллиметровые полиоминозы и посмотреть, сможет ли он найти конкретный результат, который подходит, а затем удалить 1x1 штук, чтобы получить результат.

Для вашего приложения может быть более эффективным работать в обратном направлении. Все эти алгоритмы имеют сложность в количестве единичных ячеек в каждом блоке. Хорошим способом выложить ваши блоки было бы думать о них как о "подразделениях" в больших ячейках, так что квадрат 3x3 в вашем блоке соответствует квадрату 1x1 в масштабированной версии. Затем проложите блоки с пустым пространством, чтобы они состояли из более крупных блоков, запускали алгоритм и отбрасывали лишнее пространство. Мало того, что это будет намного быстрее выполнять, но также создаст пространство между требуемыми блоками.