Не тривиальная задачка

[newart]

Есть некоторое количество прямоугольников (60-100).

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

Вращать прямоугольники нельзя.
Скорость выполнения значения не имеет.

Может быть есть какое-нибудь классическое решение?

А то у меня вариантов кроме тупого перебора, что-то пока вообще нет.

[Advertiser]

[pulsar]

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

Вращать прямоугольники нельзя.
Скорость выполнения значения не имеет.

вспомнил вот. был у нас пуру лет назад препод, читал чужие лекции: задачки на "упаковку" (минимизацию площади) (698k - pdf), там как раз алгоритмы под твою проблему, делали ему кажется даже какую-то лабу одним из методов (на пц... методом "имитации отжига", кажется)...

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

[diver]

алгортима не знаю, но тут ее точно решили

[newart]

тут

левак какой-то по ссылке.

[diver]

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

[psb]

тупой перебор - долго, быстрее (но не оптимально!!!) - генетический алгоритм. точно не расскажу, но смысл в том, что сначала компонуешь случайно. потом _что-то_ меняешь, смотришь, получилось лучше или хуже. если лучше, то опять меняешь.. так оно улучшается, улучшается.. в итоге к чему-то придешь. можно модифицировать. например, заполняешь случайно 10 раз. среди всех ищешь лучший. делаешь в нем 10 разных замен, в лучшей еще 10, и т.д.

[newart]

тупой перебор

Даже для перебора нужен какой то алгоритм. Не представляю только какой.
Да и задачка усложнилась. Теперь прямоуголник в котором нужно распределить прямогольники стал квадратным и фиксированого размера.

[diver]

1) отсортировать прямоугольники по убыванию площади
2) в угол пустого квадрата помещается наибольший прямоугольник
3) пустое место после размещения ветвится на 2 прямоугольника - большой и маленький, запоминаем, сортируем тоже.
4) берем следующий прямоугольник размещаем его в наименьшее подходящее пустое место, нужно только понять в какой угол, для начала тупо в произвольный.
5) если прямоугольники или пустые места не кончились, go to 3.

[pulsar]

в продолжении моего первого поста в этой теме, нашел вот такое: "имитация отжига" (304 Кб - делфовый проект + exe'шник для ознакомления, чтоб делфу в пустую не устанавливать), по контексту как раз вроде что надо... разбираться, что к чему сейчас не когда да и не хочется пользуйся, если на что сгодится

с усложнением задачки, правда, все сложнее

[diver]

в продолжении моего первого поста в этой теме, нашел вот такое:

как-то страшнО и неоптимально.

по-моему в общем случае оптимальнее всего - сортировка пустых мест и расположение наибольшего прямоугольника в наименьшее пустое место.