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

1) В постановке есть противоречия. Если пустых мест не должно быть, то задача должна накладывать ограничения на кратность длин сторон прямоугольников {A}. В противном случае, можно сразу констатировать ОТСУТСТВИЕ РЕШЕНИЯ ДЛЯ ОБЩЕГО СЛУЧАЯ.

2) Читаем далее - и еще больше удивляемся. "...прямоугольники могут перекыватся...". Это как? Есть ли критерий? Или можно перекрыть как угодно. В таком случае я беру самый крупный прямоугольник A1, последовательно укладываю в него все остальные A2...An (не нарушая условий) и объявляю A1 искомым прямоугольником B. В данном случае РЕШЕНИЕ ТРИВИАЛЬНО!

3) Ну и, конечно-же как правильно подметил коллега, следует искать не максимальный а минимальный прямоугольник, потому-как поиск маскимального лишён смысла.

Вообще складывается впечатление, что автор озвучил задачу "своими словами", потеряв в процессе смысл оригинально постановки. А посему... я вопрошая - а хде собсно исходная?

Задачка мне очень напоминает покрытие пола линолеумом из кусочков.

Я бы предложил следующий подход:

1. Выделить множество крупных прямоугольников {A big} (критерий выборки - нечёткий. Это может быть либо площадь, либо минимальная сторона). Выложить из них периметр прямоугольника B. Здесь задача еще решается конечным количеством шагов и можно применить строгие проверки на отсутствие дырок в периметре.

2. Оставшееся пространство (в середине комнаты), можно заполнить случайным образом из оставшихся прямоугольников {A small}, руководтсвуясь нечёткими критериями. (Наложить сетку, использовать какие - нибудь ГА, для выбора координат и ориентации и т.п.) Здесь вариантов реализации будет масса и все они - одинаково правильны.

3. Если {A small} не хватит, то можно вернутся на шаг 1 и уменьшить периметр B (скажем на 5%) и повторить шаг 2, до тех пор, пока сетка не будет содержать дырок.

P.S. Сетка необходима для "квантизации" площади и упрощения процесса поиска дырок. В принципе, можно обойтись и без неё, но тогда методы поска дырок во времени вырастают экспоненциально.

Привожу картинку для (1) шага алгоритма.

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

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

2. Площадь "внутренней дырки" при этом оказывается сравнимой с площадью оставшихся "маленьких прямоугольников".


Я понял вашу мысль. Вас интересует принципиальная возможность заполнения дырки в этом бублике. Думаю, что этот вопрос решается введением итераций в предложный мной алгоритм с учетом нехватки "сеточного" пространства для оставшихся {A small}.

По поводу периметра.

С учетом отсутствия явных ограничений на перекрытие, я утверждаю, что выложить периметр можно ВСЕГДА с количеством прямоугольников, начиная от четырёх (как я привёл на рисунке).
Другое дело, насколько близко мы прибизимся к рекорду площади минимального прямоугольника B.

Кстати, предлагаю рассмотреть максимально возможную площадь Smax=Sum {Ai}, и площадь прямоугольника B равную Sb. Сравнение этих двух площадей будет хорошим критерием близости к наилучшему (гипотетическому решению). В алгоритм-же следует ввести некий критерий sEpsilon.


Кстати, можно придумать еще одно утвердение для шагов алгоритма.


Если вдруг на (1) шаге мы получили Sb > Smax то изначально очевидно, что дырка в нашем бублике не заполнится.

softwarerНе только. Меня интересует еще и отсутствие варианта "кучу маленьких прямоугольников заведомо будет некуда класть".

Я тоже думал об этом. Сейчас появилась мысль о принципиальной решабельности задачи в некоторых условиях. Мне удалось создать набор прямоугольником для которого не удаётся найти максимальный вложенный прямоугольник B без дырок. Это необходимо ввести в дополнительное условие задачи.

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

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

2 Палестинец

Попробуйте решить задачу Слоняры для данного набора прямоугольников.

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

2 Slonyara

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

С уважением
Mayton

Slonyaraпо какому принципу определять длину каждой из сторон прямоугольника В? ведь может выйти так что я выложу только одну сторону а на остальные не хватит выбранных прямоугольников.
хотя... можно просчитать по площади прямоугольника В...

Может быть и такое. Повторяйте алгоритм, уменьшая пропорции периметра (например на 5-15%).

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

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

Начните хотя-бы с самого первого.

Не пытайтесь искать наилучшее решение для общего случая! Его ИМХО невозможно найти за реальное (не бесконечное) время. Ищите оптимальное. Особенно в условиях "непрерывности" размеров {A}, что сводит на нет усилия по применению "комбинаторных" решений.

Хорошей практикой будет следующее - запустить алгоритм в фоновом потоке, дав ему лимит времени 1-2 минуты, и собрав набор решений, остановить поток, и выдать в результаты, отсортировав по критерию качества в убывающием порядке (площадь прямоугольника B). Для введения возможности "рыскания" алгоритма по различным оптимальным раскладам, в него можно ввести некий "случайный фактор" и запускать многократно. Например, из прямогуольников периметра формировать различные наборы покрытий, меняя в зависимости от "фактора" порядок и ориентацию прямоугольников {A}.


нельзя резать. но не исключено, что слишком длинные прямоуголники "мешающие" решению в некоторых случаях придется удалять... незаметно от препода :)

Я думаю, не стоит этого делать. Препод может специально задать "краевые" начальные данные, чтобы подёргать алгоритм на прочность.

Для упрощенной проверки сделайте в начале алгоритма ряд тестов типа


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

На этом я закругляюсь, и желаю вам успехов.