Основные параметры задачи:
Есть некое количество объектов со следующими свойствами:
1)Форма объекта (Параллелепипед, рулон, конус, шар и т.п.).
2)Размеры объекта (Длинна ребер объекта, к примеру для параллелепипед это высота, ширина и длина).
3)Вес объекта.
4)Прочность объекта.
5)Возможные варианты положения объекта (Пример: рулон не может быть поставлен на свое основание, но может быть положен. Конус может быть поставлен только на свое основание)
6)Важность загрузки (при плотной упаковке определяется стоимость, к примеру есть большая кабина и её желательно загрузить в первую очередь, нежели кучу болтов)

Объекты должны быть уложены в минимальное количество контейнеров с параметрами:
1)Размеры контейнера (Предполагается что контейнеры изначально имеют форму параллелепипеда).
2)Варианты загрузки в контейнер (Различное расположение дверей накладывают свое ограничение, так-же есть понятие разгрузки в нескольких точках)

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

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

Прошу добавить если чего пропустил.

Совсем забыл про равномерную загрузку в контейнере..

P.S. По мотивам: http://www.forum.mista.ru/topic.php?&id=292718#F

пипетц. ты хоть книжки то открывал?

(3) Ты о чем? намек не понятен..

о том что эту задачу уже много веков как решили
http://ru.wikipedia.org/wiki/Задача_о_рюкзаке

на вот еще почитай
http://ru.wikipedia.org/wiki/Задача_об_упаковке_в_контейнеры

(5), (6) Какой по вашему мнению программный продукт необходимо было бы выпустить

Вот тут вот указывается что программного продукта, совместимого с 1с под условия в (0) и (1) - нету..
Итого решение для 1с нет - значит нужно его выпустить.

Из ссылок, что ты привел:
Задача об упаковке в контейнеры:
"В теории сложности вычислений или Теории комплексности задача об упаковке в контейнеры — NP-трудная комбинаторная задача"

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

Внимательно прочитай Википедию. В ней сказано что это не такая уж и простая задача. Интересует именно оптимальный алгоритм, заточенный под специфику рынка!!!

Вообще задача сводиться к написанию исскуственного интеллекта для ПК. Если честно..

Мдя... Товарищ в (5) и (6) немного погорячилсо.
(0) А не много параметров учитываешь?

(9) От малого к великому:

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

(9) Я тоже вот думаю, что погорячился, но раз кто-то сделал, то можно и мне. Хотя бы минимум :)

(10) Правильно, однако имей ввиду, что добавление сложность перебора растет экспоненциально от числа параметров. То есть добавишь один параметр - и твой метод может стать неэффективным. Лучше сразу все учитывать с этой позиции :)

решать простым перебором нельзя.

ИМХО, на 1С приемлемого решения не сделаешь. Даже двумерная упаковка для нее слишком тяжела.
PS постоянные вопли в ответ на замечания о медлительности интерпретатора 1С - "для учетной системы не нужно быстродействие", таки нужно иногда

(14) Для хорошего алгоритма быстродействие - не принципиально. Тока придумать такой алгоритм - не два палца об асфальт

(12)

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

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

(14) Буду на .Net ваять.. Сначала отдельную прогу. Если успехов добьюсь, то и ВК сваяю..

(16) перебором? ну-ну

объясните мне как человеку далёкому от этих вещей - как перебирать варианты, если они не дискретны.
Например одну коробку сверху другой можно положить бесконечным количеством вариантов, сдвигая по миллиметру

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

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

Это перебор, просто оптимизированный.. как метод называется - не помню, давно уже ВМ сдавал :)

(18) Сделать эти варианты дискретными

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

(0) Обычно проблема состоит не в том, как запихать, а как запихать так, что бы последовательно выгружать. Т.е. берем 40 кубов и нам нужно заполнить товаром таким  образом, что бы учитывать, что первым на разгрузку пойдет этот товар, потом этот, потом этот. Сложность то вот в чем...

PS. К примеру вагон идет через 5 городов, выгрузка через один проем, разгрузка во всех городах своя, но в определенной последовательности.

(22) перебор даст - просто к моменту решения уже ничего не будет нужно ;) :)

(23) Это в условии есть..

предлагаю способ задать дискретность: не координатно а правилом:
Положим мы укладываем товар слой за слоем, от дальнего борта слева на право
тогда перебор станет тривиален

единственое только... а что значит "слой за слоем"
Если скажем у нас ящики одной высоты - всё ясно
а если высоты X, X*1.5, X*2 - это какой слой, первый или второй ?  И не помешает ли ящик X*2 укладывать следующий слой за ним ?

(25) сортировать по высоте пойдет? Сначала более высокие, потом более низкие..

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

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

(28) Есть такое..
(27) Поэтому в (0) указаны многие максимальные параметры..

(27) ну вообще-то прога которую тут приводили - это всё делает

(24) "Цель, растянутая в бесконечность, бессмысленна" (с) вроде бы А.Азимов
(25) к "тривиальному" перебору - вот, тривиальным перебором уложили все, а вот последнее, мля, не умещается.. и чо делаем? опять тривиальный перебор, и опять последнее не уместилось.. а теперь считаем полное количество "тривиальных переборов", охреневаем от количества, и сматываем удочки с форума)))

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

т.е. достаточно будет изначально отсортировать грузы по габаритам по убыванию, а дальше подобрать эвристический алгоритм перестановок

хотя тут же возникает вопрос: а какой груз больше - тонкий и длинный или толстый и короткий ? :))

короче меньше слов - больше дела..

(32) Что то как то не очевидно...

Мало того, что груз можно сдвигать на бесконечно малые величины... его ж еще можно и вращать в любых плоскостях... даже параллепипед можно на ребро там поставить, или вообще на вершину :) Еще некоторые можно деформировать... например подушку, если в нормально состоянии не влазит, можно и «заархивировать» :)

чувствую скоро все это потянет на какую нить как минимум математическую премию

(36) Даешь нобелевскую премию участникам Мисты!!!

(36) Чувствую, что ничего не получится :)

(5) и (6) к этой задаче отношения не имеют - никакой это не рюкзак и в википендии пишут неаккуратно. А нейронные сети - чистая спекуляция.
Не пытайтесь задачу решать алгоритмически - ничего не получится. Даже перебора не сделаете.

помоему для каждого груза придется описывать набор критериев. Как он правильно лежит.
И после каждого изменения положения проверять для каждого из грузов все критерии. Так же можно будет описать куда и как может перемещаться груз.
При этом еще до погрузки придется сортировать груз на очередность загрузки и начинать с самых важных. При этом полюбому нужно будет в итоге выдавать несколько вариантов которые оптимальны по разным критериям и уже потом выбирать самый оптимальный.

А еще может получать такая глупость типа - везти груз надо по 4 точкам, но програма загрузила в машину только груз для первой точки, потому что так больше всего влезло. В итоге на 3 остальных точки машина едет пустая.

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

Полунедобэтта - http://transportlogistik.narod.ru/

Очень сырая и т.п. - но можно уже поюзать - посмотреть что и как там. Пояснение - открываеться журнал документов. Кликаем по 1-му документу, в документе есть кнопка "Расчитать". Откроется окно расчета, там кнопка "Поместить". Топаем по кнопке до полной загрузке. 3Д вьювер можно покрутить - колесиком изменяться масштаб..

В данный момент только позволяет загрузить кубики.

Алгоритм неоптимален - буду делать..

zcxvb, выйди на связь!!!

up