Задача алгоритма оптимальной упаковки

vingur

Задача:
в 3D в прямоугольный параллилепипед оптимально (т.е. как можно больше) положить маленьких прямоугольных паралл-дов всяких разных размеров.
чтоб более-менее оптимальный алгоритм был.
Кто нибудь знает такое?

lera__m

Динамическое программирование?

lera__m

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

vingur

не криво класть нельзя.
Перебором - очень долго.

lera__m

динамика: знаем как оптимально разложить n-ящиков, добавляем один, и получаем оптимальную укладку n+1 ящика и т. д.
получим полиномиальную сложность типа n^3

lera__m

нумеруем ящики 1...n
на шаге n:
запоминаем в массиве результаты оптимальной укладки n ящиков (на 0 шаге инициализируем пустой комнатой в i-й укладке последним уложен i-й ящик. для этого перебираем все оптимальные укладки в прошлом массиве (в которых iй ящик отсутствует) и добавляем (оптимально) iй ящик.
итого: ~n^3

locker

а жадность точно не покатит?

RZ3ARO

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

lera__m

а как в данном случае понимать более оптимальную укладку?
мне в голову приходит такая жадность: отсортировать ящики (например по диаметру ) каждый ящик уложить в первый подходящий угол
как сортировать ящики хз

Dr_Jones

по обьёму ?

lera__m

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

locker

есть ощущение, что по "близости" соотношения их сторон к соотношению сторон исходного

Dr_Jones

может для 2 мерного случая сначала ?
для 1 мерного вроде тривиально все

locker

ага
для 1-мерного неинтересно %)
ща буду думать над двумерным

msk80

Вот здесь за такую программку просят 9000р. Причём алгоритм там используется, скорее всего, не самый оптимальный.

locker

так
любопытно
речь идёт о ящиках ведь?
значит тут ещё надо учитывать, свалится один с другого или нет что ли?
тогда я не берусь это решать

Dr_Jones

всмысле свалится ?

locker

ну смотри
есть ящик 2 на 2
в углу его ящик 0.1 на 0.1
а на нём уже -- тоже впритык к стенке -- ящик 1 на 1
конструкция нежизнеспособна

locker

а вот если сверху ещё поставить ящик 0.9 на 0.9 -- то вполне
жопа, одним словом

Dr_Jones

ну преставвь, что это мазайка, а не ящики.

lera__m

в двумерном случае не надо
а почему нет?
пусть свалятся, получится какая-то укладка

locker

тогда начинаю думать %)

zuzaka

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

Dr_Jones

в смысле не надо ?
надо сначало понять простой случай.
от простого к сложному.
нет , потому, что со сваливаниями задача усложняется до нерешаемой ИМХО

locker

дано такие варианты всё равно надо было бы как-то рассматривать и отбрасывать
ладно
проехали

Dr_Jones

короче.
помните рассказ про философа с камешками, горохом, песком и пивом ?
так вот имхо(в стиле американской логики) надо начинать укладывать с самых больших прямоугольников.

lera__m

вот я и хочу у тебя узнать что значит самый большой прямоугольник, или точнее что значит что A > B

Dr_Jones

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

lera__m

квадраты по стороне тривиально упорядочиваются

Sander

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

locker

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

zuzaka

Квадраты - да. А кубы? Мне лениво думать, может, подскажете?

lera__m

ни какой разницы

Dr_Jones

у кубы наверно тоже упорядочиваются

zuzaka

Да, реально. Торможу.

electricbird

>не криво класть нельзя.
почему нельзя?
мне вот кажется, что можно(и, вероятно, даже нужно, дабы сделать задачу сколь-нибудь обозримой) обойтись исключительно "прямыми" укладками

locker

мне почему-то показалось, что там запятая была пропущена
глюки, наверное

natunchik

Я спросил у гугла, и гугл мне ответил.
Задача о нахождении прямоугольника минимальной площади, в который можно упаковать без самопересечений данные n ориентированных прямоугольников, является NP-полной, так что всем можно расслабиццо. У меня есть текстик, в котором чуваки достаточно быстро (хотя и NP) упаковывают в данный прямоугольник квадраты 1х1, 2х2, ... NxN.
ftp://fj.local/Texts/ICAPS04KorfR.pdf

locker

задача, конечно, похожа, но не совсем та
хотя и тут НП пахнет за версту, конечно

natunchik

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

Xephon

может я чего-то не понимаю, но если у нас есть параллелепипеды размеров 1x1xN_i, то как решать эту задачу полиномиально?

natunchik

Дык я и говорю, что она NP!

locker

Павлик, ты что, настолько незауряден, что не видишь, что из возможности решить оригинальную задачу за полиномиальное время следует возможность решения этой задачи за полиномиальное время?
скажем так
я это _чувствую_
а вот строго показать что-то не могу

natunchik

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

locker

Очевидно, что если мы умеем проверять возможность замощения данного ящика, то мы половинным делением находим ящик минимальной площади
чего?
какое нах половинное деление?
а как же иррациональные числа и всё такое?

RZ3ARO

Ну а если в пределе?

natunchik

Они ориентированы! Соответственно количество возможных шырин ящика, при котором сдвинуть его стороны невозможно, потому что существует последовательность ящиков, которые касаются друг-друга и стенок попарно боковыми сторонами, конечно, и даже не очень велико! И можно оценить минимальную разницу между ними!
Оставить комментарий
Имя или ник:
Комментарий: