Заполнение объёма....

Дан объём x*y*z (или хотя бы x*x*x). В него кидают кубики, размер ребра у каждого кубика разный. Составить алгоритм укладывания этих кубиков в данном объёме наиболее оптимально. Разумеется, перекрываться кубы не могут....

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

Кто может, плиз, помогите! Желательно поскорее....

Сообщение отредактировано: 7in - 30.06.02, 16:33

Погляди тут http://pascal.sources.ru/cgi-bin/forum/YaBB.cgi?board=algorithm;action=display;num=1017321962
Может, натолкнет на идею.

Это работает только с первым вариантом (и то остаются пустоты, которые могли бы быть заполнены другими кубиками), а такую подачу кубиков реализовать сложно, вернее, даже будет не совсем то....

Ещё желательно бы такой вариант сделать (дополнительно): чтобы новые кубики не могли попадать туда, куда он не сможет "пролезть" (в замкнутое пространство, например)....

Может, хотя бы подскажете, какие методы мне почитать?

Плииииииз, ну ооооочень надо....
Времени мало уже остаётся!!! :-/

Сообщение отредактировано: 7in - 15.06.02, 17:14

это, ничего лучше полного перебора чегой-то не придумывается....

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

А как ты себе представляешь полный перебор?
Все размеры - не целые числа!!!

я просто представлял себе задачу так:
есть некийц набор кубиков разных размеров.
например кубики с ребром 1
с ребром 1.5 ...
нужно используя эти кубики заполнить максимально плотно твой обьем.
немного напоминает задачу о разбиении некой суммы N  на монеты по 1,5, 10,25 коп.

перечитал еще раз условие... скоеее всего я ошибался сори:?)

Если на самом деле размеры всех кубов не известны, укладывать придеться большие в одну сторону, а мелкие по другую. Тем более, что должно существовать ограничение на размер кубика. ;D ;D ;D

Есть размеры 1,2,3,4,5...10 + 0,01 (допустим) кубиков, а размер области, куда они бросаются может быть любым....
А что значит большие и мелкие? И в одну или другую сторону? Так их целых 8, сторон этих!
И надо алгоритм, как их укладывать!!!

Нет ты давай конкретно.
Еслди есть размеры кубиков. И если известно, что каждый следующий больше предыдущего в определенное количество раз, то существует алгоритм (довольно старенький) укладывания их в прямоугольный стакан. ;D ;D ;D

Нет! Каждый следующий не больше предыдущего!
Короче, задача такая....
Есть функция распределения объёмов кубиков (к примеру, Гаусса, они меняться будут, т.к. нужно решить несколько задач, отличающихся именно функциями распределения). Стороны кубиков - числа от N₁ до N₂ с определённым шагом. К этому размеру прибавляется случайное число от e₁ до e₂. Кстати, у этого случайного числа тоже есть функция распределения
Но это всё фигня....
Главное - это то, что нужно кидать эти кубики в резервуар размером X*Y*Z, причём укладывать их как можно плотнее. Для чего это нужно: надо найти объём свободного пространства после укладки!!! Вот и всё задача.... Короче, завтра вечером мне это уже нужно будет, иначе (если в инете не найду и ничего не придумаю) я сделаю какую-нибудь фигню... :'(

может пациент еще жив ???

вариант1:

@@кидаем объект:
    кидаем_объект_не_больший_чем_есть_свободного_места
    mov счетчик_падений,(от фонаря)
@@уплотняем:
    dec счетчик_падений
    jz @@заколебало
случайным_образом_выбираем_направление_падения
    Все_роняем_на_выбранную_строну
    вписалось в границы?
    jnz @@уплотняем
    свободного места больше чем минимальный объект?
    jz @@кидаем объект
    jmp @@Exit
@@заколебало:  
    убираем последний добавленный объект
    последний добавленный объект был наименьшим из возможных?
    jnz @@кидаем объект
Exit:

вариант 2 (геморойный): Типа Броуновское движение, т.е. кидаем в стакан объекты, и все они находятся в постоянном движении, постепенно стакан сжимается (стремится сжаться),
    mov счетчик добавлений,(от фонаря)
@@Еще_объект:
    есть место?
    jnz @@Exit:
    Раздвинуть границы стакана
    Добавляем_объект
@@Время:
    mov время, (от фонаря)
@@встряхиваем:
    Встряхиваем_стакан
    Сжимаем_стакан
    упорядочилось?
    jz @@Еще_объект:
    dec время
    jnz @@встряхиваем
    убираем наименьший объект
    dec счетчик добавлений
    jnz @@Время
     
@@Exit: ;могло быть и лучше, но не будет
   

как насчет задачи о рюкзаке (ранце)

имеется ранец объема V и неограниченное кол-во каждого из Л' различных предметов. Для каждого предмета 1-го типа при (-1,2,..., N известны его объем Vi и ценность т/. В ранец можно положить целое число предметов разного типа. При этом цель состоит в том, чтобы суммарная стоимость всех находящихся в ранце предметов была максимальна, а их объем не превышал величины У. 3. о р. может также решаться Гомори методом, методами программирования дин. и др. К 3. о р. может быть сведена задача макс, использования грузоподъемности подвижного состава, грузовместимости судна и т.п.

Примерно об этом я и говорил
Если надо алгоритмом поделюсь

Сообщение отредактировано: GrAnd - 19.06.02, 12:12

2 fog: Первый вариант весьма неоптимальный, к тому же медленный (из-за счётчика), а по поводу второго.... Мне размеры резервуара менять нельзя! И что значит "встряхиваем"?

2 Mamochka & GrAnd: Блин! Точно.... я помню, у нас было что-то такое, но я в суть не вникал.... Если можно, опишите метод (попонятнее). Я сам тоже поищу в нете....

---

А теперь мой способ.... Может, он и не самый оптимальный, но ИМХО довольно-таки неплохой и не шибко сложный

Объясняю суть: создаётся фукция z=F(x,y) , которая изначально является прямой (z=0). При опускании кубика ищем минимум (z_min) функции, такой, чтобы в этот минимум кубик умещался по ширине и длине и был прижат к левому краю⁽¹⁾, и находим координаты x1 и y1 (для первого кубика, эти координаты, разумеется, будут (x=0;y=0)). После этого в функцию добавляется правило, что при x1<x<x2 и y1<y<y2 функция принимает значение z_min+ВысотаКубика (где x1, y1 - найденные координаты; x2=x1+ШиринаКубика, y2=y1+ДлинаКубика). Затем процесс повторяется до тех пор, пока минимум (удовлетворяющий условиям ⁽¹⁾) не перестанет существовать (например, после 10 попыток, т.к. не исключается вероятность того, что для кубика с другими размерами этот минимум будет найден).
[center]Вот иллюстрация двухмерного варианта:
[/center]Здесь на графике эта функция изображена синей линией, кубик - голубым цветом. Серым цветом обозначено заполненное пространство, желтым - свободное, но уже не используемое.

Но!.... есть некоторые сложности:
1. Как найти этот минимум? Вернее, как найти минимум, удовлетворяющий условиям ⁽¹⁾? Можно перебирать все точки по x и по y с шагом, равным ширине и длине кубика соответственно, но тогда можно попасть в яму, которая будет Уже, но будет находиться внутри той ямы, которая нам подходит
2. Как определить, можно ли удалить то или иное правило (для ускорения вычисления функции)? Можно, конечно, попробовать сравнить значение для этого парвила со значением функции F на концах отрезка, принадлежащего этому правилу, но ведь не исключено, что в середине отрезка значение правила будет совпадать с функцией F, поэтому его удалять нельзя.... Для иллюстрации сказанного (а то, возможно, я не очень понятно объяснил) некоторые отрезки, принадлежащие разным правилам я выделил красным цветом.

Я ещё сам подумаю, как ответить на эти вопросы, но может, Вы найдёте более оптимальное и быстрое решение?

Плиз, времени уже нет!!!

- Заранее Спасибо! ;D

Сообщение отредактировано: 7in - 19.06.02, 15:10

>Мне размеры резервуара менять нельзя! И что значит "встряхиваем"?

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