Вид для печати
Есть некоторое количество прямоугольников (60-100).
Задача - скомпоновать их так, что бы получился прямоугольник с максимально эффективно занятой площадью.
Вращать прямоугольники нельзя.
Скорость выполнения значения не имеет.
Может быть есть какое-нибудь классическое решение?
А то у меня вариантов кроме тупого перебора, что-то пока вообще нет.
вспомнил вот.:v2_unsur: был у нас пуру лет назад препод, читал чужие лекции:v2_crazy:: задачки на "упаковку" (минимизацию площади) (698k - pdf), там как раз алгоритмы под твою проблему, делали ему кажется:v2_smile: даже какую-то лабу одним из методов (на пц... методом "имитации отжига", кажется)...Цитата:
Сообщение от newart
если интересует классический подход - теория самое оно будет:v2_wacko: (хоть и выглядит как бред сивой кобылы), во всяком случае будешь знать в каком направлении копать.:v2_conf2: на wikipedi'и, кстати, практически только "имитация отжига" коротенько описана, так что походу довольно классический метод..
алгортима не знаю, но тут ее точно решили :)
левак какой-то по ссылке.Цитата:
Сообщение от diver
ну правильно :) карта фондового рынка. там объемы рынка у всех меняются (площади), а карта постоянно упакована в один прямоугольник.
тупой перебор - долго, быстрее (но не оптимально!!!) - генетический алгоритм. точно не расскажу, но смысл в том, что сначала компонуешь случайно. потом _что-то_ меняешь, смотришь, получилось лучше или хуже. если лучше, то опять меняешь.. так оно улучшается, улучшается.. в итоге к чему-то придешь. можно модифицировать. например, заполняешь случайно 10 раз. среди всех ищешь лучший. делаешь в нем 10 разных замен, в лучшей еще 10, и т.д.
Даже для перебора нужен какой то алгоритм. Не представляю только какой.Цитата:
Сообщение от psb
Да и задачка усложнилась. Теперь прямоуголник в котором нужно распределить прямогольники стал квадратным и фиксированого размера.
1) отсортировать прямоугольники по убыванию площади
2) в угол пустого квадрата помещается наибольший прямоугольник
3) пустое место после размещения ветвится на 2 прямоугольника - большой и маленький, запоминаем, сортируем тоже.
4) берем следующий прямоугольник размещаем его в наименьшее подходящее пустое место, нужно только понять в какой угол, для начала тупо в произвольный.
5) если прямоугольники или пустые места не кончились, go to 3.
У меня похожая идея. Что то вроде тетриса, падают фигуры до упора и сдвигаются в угол и дальше падают если возможно, фигуры выбираются по убыванию размера (90% фигур прямоуголники с соотношением сторон 3 к 5).Цитата:
Сообщение от diver
в продолжении моего первого поста в этой теме, нашел вот такое: "имитация отжига" (304 Кб - делфовый проект + exe'шник для ознакомления, чтоб делфу в пустую не устанавливать:v2_neutr:), по контексту как раз вроде что надо... разбираться, что к чему сейчас не когда да и не хочется:v2_conf2: пользуйся, если на что сгодится:v2_huh:
с усложнением задачки, правда, все сложнее:v2_rolley
Работает, вылетая время от времени. Жалко что в квадрат упаковывать не умеет.Цитата:
Сообщение от pulsar
как-то страшнО и неоптимально.Цитата:
Сообщение от pulsar
по-моему в общем случае оптимальнее всего - сортировка пустых мест и расположение наибольшего прямоугольника в наименьшее пустое место.
Там важна настройка, но для ленты можно и более простой алгоритм придумать.Цитата:
Сообщение от diver
А на наибольшем прямоуголнике ты зря зацикливаешься, допустим в моем случае разница между прямоугольниками не более 10-15%.
Да и фигур кстати больше чем влезает в один квадрат, что дает возможность для наибольшей оптимизации, но в месте с тем усложняет и алгоритм.
я пишу про общий случай.
частные случаи могут изменить алгоритм до неузнаваемости. была бы точная постановка, возможно было бы решение.
Классическая "задача укладки рюкзака" или "задача раскроя листа". NP полная. С приемлимой точностью решается за разумное время. Гуглить по вышеназваным словам, материала в сети как говна :-)
Ага, только толку то с него?Цитата:
Сообщение от ram_scan
Будь там псевдо код, я бы еще разобрался, а там тАкией формулы, что троечнику лучше и не соваться...
lection2.rar
Никаких формул. Точно данная адача называется "задача двумерной упаковки".