Алгоритм оптимального трехмерного заполнения

Здесь Вы можете найти или обсудить множество различных алгоритмов, их описаний, реализаций на VB и других языках.
Ronin
Постоялец
Постоялец
Аватара пользователя
 
Сообщения: 635
Зарегистрирован: 13.02.2002 (Ср) 14:16
Откуда: Россия, Москва

Алгоритм оптимального трехмерного заполнения

Сообщение Ronin » 08.07.2009 (Ср) 14:03

Доброго времени суток!

Задача такова: Имеется ячейка (коробка, называйте как хотите). Имееются ее габариты. Также имеются коробки поменьше, тоже с габаритами (коробки одинаковые). Коробочки можно крутить как угодно.
Задача - компактно разместить коробочки в ячейку.
Ищу алгоритм, который решает подобную задачу (алгоритм трехмерного размещения).
Я нашел кое-что но очень мало и не понятно. Если кто-нибудь сталкивался с такой задачей, поделитесь пожалуйста.

Заранее спасибо
С уважением,
Игорь Шувалов aka Ronin

alibek
Большой Человек
Большой Человек
 
Сообщения: 14111
Зарегистрирован: 19.04.2002 (Пт) 11:40
Откуда: Russia

Re: Алгоритм оптимального трехмерного заполнения

Сообщение alibek » 08.07.2009 (Ср) 14:10

Насколько я помню, решения такой задачи не существует. Только перебор.
Хотя может и путаю с чем-то.
Lasciate ogni speranza, voi ch'entrate.

Ronin
Постоялец
Постоялец
Аватара пользователя
 
Сообщения: 635
Зарегистрирован: 13.02.2002 (Ср) 14:16
Откуда: Россия, Москва

Re: Алгоритм оптимального трехмерного заполнения

Сообщение Ronin » 08.07.2009 (Ср) 14:14

Решения существуют. То что коробочки одинаковые сильно упрощают задачу. т.к. всю информацию по проблеме размещения я нашел как раз для случая когда габариты коробочек разные..
А какой алгоритм перебора предложите?
С уважением,
Игорь Шувалов aka Ronin

alibek
Большой Человек
Большой Человек
 
Сообщения: 14111
Зарегистрирован: 19.04.2002 (Пт) 11:40
Откуда: Russia

Re: Алгоритм оптимального трехмерного заполнения

Сообщение alibek » 08.07.2009 (Ср) 15:32

Если коробки одинаковые, тогда да, решение упрощается.
Можно искать НОД и если он будет найден, то соответственно, контейнер можно заполнить полностью.
Lasciate ogni speranza, voi ch'entrate.

Ronin
Постоялец
Постоялец
Аватара пользователя
 
Сообщения: 635
Зарегистрирован: 13.02.2002 (Ср) 14:16
Откуда: Россия, Москва

Re: Алгоритм оптимального трехмерного заполнения

Сообщение Ronin » 08.07.2009 (Ср) 16:57

Вопрос не в том можно ли заполнить. Вопрос в том как..
В конечном итоге я хочу получить количество коробок которые поместятся в ячейку, при оптимальном заполнении. При этом я сразу получу данные о координатах и повороте коробок. То есть виртуально заполнить смогу и даже визулизировать
С уважением,
Игорь Шувалов aka Ronin

alibek
Большой Человек
Большой Человек
 
Сообщения: 14111
Зарегистрирован: 19.04.2002 (Пт) 11:40
Откуда: Russia

Re: Алгоритм оптимального трехмерного заполнения

Сообщение alibek » 08.07.2009 (Ср) 21:27

Если контейнер может быть заполнен полностью, то совершенно не важно, как именно заполнять, количество коробок будет всегда одинаковым.
Разные результаты могут быть только в том случае, когда полностью заполнить контейнер невозможно, тогда нужно минимизировать незанятый объем. А значит нужно находить НОД и по остатку от деления считать незанятый объем.
Lasciate ogni speranza, voi ch'entrate.

Ronin
Постоялец
Постоялец
Аватара пользователя
 
Сообщения: 635
Зарегистрирован: 13.02.2002 (Ср) 14:16
Откуда: Россия, Москва

Re: Алгоритм оптимального трехмерного заполнения

Сообщение Ronin » 09.07.2009 (Чт) 15:35

Кто нибудь может скомпилить (см. вложение) и сделать импорт в .net? =) А то я не умею =)
Вложения
3dbpp.zip
(35.93 Кб) Скачиваний: 231
С уважением,
Игорь Шувалов aka Ronin


Вернуться в Алгоритмы

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 2

    TopList