Как найти минимальное количество подразделов

Question

Представьте, что у вас есть холст, и на этом холсте уже есть некоторые объекты. Как вы можете найти минимальный способ покрыть «непокрытую» область квадратами, а не накладывать друг на друга, полностью заполняя холст.

В моем случае «холст» представляет собой контейнер html-div, а объекты представляют собой вложенные div-контейнеры. могли бы выглядеть следующим образом: http://www.encodechain.com/demo/200908_optimize.png Слева есть «Пуск», а справа есть на возможный первый «шаг» ...

Я знаю, что есть алгоритм для этого, но в настоящее время я не могу вспомнить имя.

Answer 1

Лучшее, что я смог найти в этой статье: Tiling a rectangle with the fewest squares. Статья интересна читателю, хотя временами она глубоко погружается в теорию с разговорами о «универсальных константах». Я не уверен, является ли NP-полным вопрос о том, может ли прямоугольник размером m на n быть разбит слоем k квадратов. Как отмечено в другом ответе, ваш вопрос напоминает проблемы упаковки, которые являются NP-полными. И, конечно, ваша проблема - это обобщение того, которое рассматривается в этой статье, поскольку вы имеете дело с непрямоугольными областями. Вы можете начать с разбивки своей области на минимальное количество прямоугольников, что еще одна интересная проблема сама по себе. И, наконец, даже если вы можете сделать это эффективно, я не уверен, что оптимальное разбиение этих прямоугольников приведет к общему оптимальному разбиению.

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

Answer 2

Packing Problem

Knapsack Problem

И article на решении 2d проблемы упаковки