Задача раскроя. Узнать есть ли решение не вычисляя его

Для начала сравнить сумму площадей маленьких с большим.

Это уже сделано. Гарантируется что общая сумма площадей мелких меньше или равна чем площадь области для размещения. Это конечно отсеивает приличное число задач, но их все равно слишком много.

Насыпать маленькие прямоугольники в большой и потрясти, пока они не уляжутся плотно. Если не помогло, перемешать и повторить.

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

Поворачивать на произвольный угол можно?

Нет, ориентация имеет значение, менять нельзя (как-то двусмысленно прозвучало)

Т.е. даже на 90° нельзя поворачивать? А изначально-то они прямо ориентированы? Если да, то:

Во-первых, можно выкинуть случаи, когда h > a || w > a, но это вроде очевидно.

Во-вторых, можно пробовать искать случаи, когда есть два прямоугольника, такие что h1+h2 > a && w1+w2 > a. Но не факт, что это эффективно.

// a = сторона кв-та; h/w - высота/ширина прям-в

это хорошо, но оно отбрасывает как раз самые простые случаи, и таких минимум. Но все равно спасибо :-) Обычно прямоугольников от 5 до 8 штук.

В порядке мозгового штурма:

1) Если устраивает false negative срабатывание алгоритма, то можно взять некий эмпирический коэффициент <1 на который умножать площадь большого прямоугольника. И уже с ним сравнивать сумму площадей.

2) Хитро разбить все варианты на некоторые множества так, что бы не получив решение для определенной задачи из множества можно было сказать что все остальное множество не имеет решений.

По первому - лечше false positive, к сожалению

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

Говоришь, есть миллионы задач. Во-первых, приведи их все к стандартной форме, например, масштабировав большой прямоугольник к квадрату 1×1. В каждой нерешаемой задаче выдели минимальное конфликтующее подмножество прямоугольников. Классифицируй все такие подмножества, с точностью до поворотов и зеркальных отражений.

Тогда задача сведётся к поиску в данном множестве подмножества ≥ имеющегося в списке, что намного легче перебора вариантов.

Хитрую формулу можно было бы получить, используя нейронные сети, скажем для 2-х, 3-х и т.д. прямоугольников. Расчет на то, что если есть какая-то закономерность, то персептрон или что-там вместо него, окажутся настолько гибкими, что сумеют схватить зависимость. Метод довольно тупой, но иногда работает.

https://en.wikipedia.org/wiki/Packing_problems

Нужно узнать если в принципе возможно разместить мелкие прямоугольники на этой области (без пересечений). Само решение (способ расстановки) не интересует.

Поиск ответа на вопрос «Есть ли решение?» тоже NP-полный.

Обычно прямоугольников от 5 до 8 штук.

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

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

Да с этим проблем нет, просто задач реально много - порядка нескольких миллионов. Поиск решений для всех, при использовании python/numpy в моем случае занимает от 10 до 30+ минут в зависимости от случая. В принципе это приемлемо, но хотелось бы быстрее.

Поиск ответа на вопрос «Есть ли решение?» тоже NP-полный.

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

Поиск решений для всех, при использовании python/numpy в моем случае занимает от 10 до 30+ минут в зависимости от случая.

Может быть, стоит реализовать на Си. И не простой перебор, а что-нибудь поумнее.

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

Ну это для общего случая. «Отфильтровать хоть что-то», может быть, всё-таки можно, но существующие алгоритмы решения должны это учитывать, поэтому придётся читать литературу.

А что хоть за предметная область?

В качестве дополнительного фильтра: все прямоугольники упорядочиваются по максимальной координате, далее начиная с самого большого проверяется вписываемость в область. Пусть W и H ширина и длина области, h1,w1,h2,w2,... - габариты прямоугольников. Для случая одного прямоугольника необходимый критерий уже описан: (h1<=H) && (w1<=W) Для двух самых больших: ((h1+h2)<=H) || ((w1+w2)<=W) Для трех уже сложнее, но, по идее, можно построить сам алгоритм заполнения таким образом, чтобы на каждом шаге по этому критерию отсеивались заведомо бесперспективные.

Автоматическая верстка газетных полос при помощи LaTeX. Есть статьи для каждой полосы, некоторые статьи (важные) имеют фиксированную позицию (это, кстати, упрощает задачу, уменьшая количество вариантов). Каждая из остальных статей может быть заверстана разными способами (на 1, 2, 3, 4 или 5 колонок, с фоткой сверху на всю ширину, сбоку на пару колонок, или внутри статьи) - это дает некоторую гибкость, так как у каждого варианта выходит разная площадь.

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

А надо ли тебе в таком общем виде задачу решать?

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

Гм, задача вполне стандартная, лет пять назад сам реализовывал такую на яваскрипте. Действительно, вы черезчур обобщаете и усложняете себе жизнь - рекламные блоки всегда имеют стандартные кратные размеры и явно миллионами не исчисляются. Алгоритм прост как две копейки - сперва в полосу ставятся самые большие блоки, а затем оставшееся пространство заполняется спичечными коробками. В итоге поиск решения занимает буквально миллисекунды даже на тормозном js

Пожалуй так и сделаю, спасибо

А разве поиски признаков (не)решаемости - это не вычисление? Подозреваю, что поиск таких признаков может оказаться намного сложнее перебора «в лоб».

В общем, спасибо всем, ребята. Благодаря вашим советам удалось сократить время перебора до приемлемых 15-30 секунд для 32 полос, так что можно считать что проблема решена

Поиск ответа на вопрос «Есть ли решение?» тоже NP-полный.

Таки уже NP-полный? Пруф будет?

Таки уже NP-полный? Пруф будет?

В статье, на которую я ссылался, есть пруф (задачу упаковки в контейнеры можно свести к задаче раскроя).

Нет, ты не прав в общем случае.

Был неправ, каюсь.