PDA

Просмотр полной версии : Не тривиальная задачка


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

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

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

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

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

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


вспомнил вот.:v2_unsur: был у нас пуру лет назад препод, читал чужие лекции:v2_crazy:: задачки на "упаковку" (минимизацию площади) (http://www.math.nsc.ru/LBRT/k5/lec5.pdf) (698k - pdf), там как раз алгоритмы под твою проблему, делали ему кажется:v2_smile: даже какую-то лабу одним из методов (на пц... методом "имитации отжига", кажется)...

если интересует классический подход - теория самое оно будет:v2_wacko: (хоть и выглядит как бред сивой кобылы), во всяком случае будешь знать в каком направлении копать.:v2_conf2: на wikipedi'и, кстати, практически только "имитация отжига" коротенько описана, так что походу довольно классический метод..
diver
10.01.2008, 21:10
алгортима не знаю, но тут (http://www.smartmoney.com/marketmap/) ее точно решили :)
newart
10.01.2008, 22:42
тут
левак какой-то по ссылке.
diver
11.01.2008, 05:17
ну правильно :) карта фондового рынка. там объемы рынка у всех меняются (площади), а карта постоянно упакована в один прямоугольник.
psb
11.01.2008, 18:26
тупой перебор - долго, быстрее (но не оптимально!!!) - генетический алгоритм. точно не расскажу, но смысл в том, что сначала компонуешь случайно. потом _что-то_ меняешь, смотришь, получилось лучше или хуже. если лучше, то опять меняешь.. так оно улучшается, улучшается.. в итоге к чему-то придешь. можно модифицировать. например, заполняешь случайно 10 раз. среди всех ищешь лучший. делаешь в нем 10 разных замен, в лучшей еще 10, и т.д.
newart
11.01.2008, 19:05
тупой перебор
Даже для перебора нужен какой то алгоритм. Не представляю только какой.
Да и задачка усложнилась. Теперь прямоуголник в котором нужно распределить прямогольники стал квадратным и фиксированого размера.
diver
11.01.2008, 22:15
1) отсортировать прямоугольники по убыванию площади
2) в угол пустого квадрата помещается наибольший прямоугольник
3) пустое место после размещения ветвится на 2 прямоугольника - большой и маленький, запоминаем, сортируем тоже.
4) берем следующий прямоугольник размещаем его в наименьшее подходящее пустое место, нужно только понять в какой угол, для начала тупо в произвольный.
5) если прямоугольники или пустые места не кончились, go to 3.
newart
11.01.2008, 22:50
2) в угол пустого квадрата помещается наибольший прямоугольник
У меня похожая идея. Что то вроде тетриса, падают фигуры до упора и сдвигаются в угол и дальше падают если возможно, фигуры выбираются по убыванию размера (90% фигур прямоуголники с соотношением сторон 3 к 5).
pulsar
11.01.2008, 23:02
в продолжении моего первого поста в этой теме, нашел вот такое: "имитация отжига" (http://dl.filehoster.ru/files/baff2d9e4eb79aeacb65f93686b26e8767d5a692a69b4d/othzig.zip) (304 Кб - делфовый проект + exe'шник для ознакомления, чтоб делфу в пустую не устанавливать:v2_neutr:), по контексту как раз вроде что надо... разбираться, что к чему сейчас не когда да и не хочется:v2_conf2: пользуйся, если на что сгодится:v2_huh:

с усложнением задачки, правда, все сложнее:v2_rolley
newart
11.01.2008, 23:25
по контексту как раз вроде что надо.
Работает, вылетая время от времени. Жалко что в квадрат упаковывать не умеет.
diver
11.01.2008, 23:37
в продолжении моего первого поста в этой теме, нашел вот такое:

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

по-моему в общем случае оптимальнее всего - сортировка пустых мест и расположение наибольшего прямоугольника в наименьшее пустое место.
newart
12.01.2008, 00:00
как-то страшнО и неоптимально.
Там важна настройка, но для ленты можно и более простой алгоритм придумать.
А на наибольшем прямоуголнике ты зря зацикливаешься, допустим в моем случае разница между прямоугольниками не более 10-15%.
Да и фигур кстати больше чем влезает в один квадрат, что дает возможность для наибольшей оптимизации, но в месте с тем усложняет и алгоритм.
diver
12.01.2008, 00:12
я пишу про общий случай.
частные случаи могут изменить алгоритм до неузнаваемости. была бы точная постановка, возможно было бы решение.
ram_scan
12.01.2008, 21:50
Классическая "задача укладки рюкзака" или "задача раскроя листа". NP полная. С приемлимой точностью решается за разумное время. Гуглить по вышеназваным словам, материала в сети как говна :-)
newart
18.01.2008, 04:06
Гуглить по вышеназваным словам, материала в сети как говна
Ага, только толку то с него?

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

lection2.rar (http://zxpk.untergrund.net/downloads.php?id=64)
ram_scan
20.01.2008, 09:22
Никаких формул. Точно данная адача называется "задача двумерной упаковки".