Русскоязычный IT клуб

Кто знает хороший алгоритм для решения задачи упаковки нескольких маленьких коробок в одну большую?

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

пока нашелся вот такой: https://github.com/yetzt/boxing" onclick="window.open(this.href);return false;

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

Кто знает более качественный Boxing-алгоритм?
Высшим пилотажем было-бы учитывать возможность положить длинный предмет в коробку по диагонали

T-80 писал(а): Кто знает более качественный Boxing-алгоритм?

THREE-DIMENSIONAL BIN PACKING по-научному

http://www.cs.ukzn.ac.za/publications/e ... 07-034.pdf" onclick="window.open(this.href);return false;

а вот тут польские друзья онлайн отрисовывают чего куда класть:
http://www.pakowacz.net/simulator" onclick="window.open(this.href);return false;

Чувак ты знаешь что такое Методы оптимизации?

serjserj писал(а):Чувак ты знаешь что такое Методы оптимизации?

Знаю, но тут речь скорее не о методах оптимизации, а об оптимизации метода ("эффективнее, а не быстрее").
так что в принципе, как раз то, что и искал.

из пэйпера:

Bin packing being an NP-Hard problem, suggests that an
exhaustive search for the optimal solution is in general
computationally intractable, and also that there is thus no
known real computationally feasible optimal solution
method for the problem. So other means to obtain a
solution have to be found.

T-80 писал(а):Кто знает хороший алгоритм для решения задачи упаковки нескольких маленьких коробок в одну большую?

Есть один хороший и быстрый алгоритм. Только комп нужен квантовый.

Для начала неплохо бы решить задачу об упаковки ранца...
http://ru.wikipedia.org/wiki/%D0%97%D0% ... 1%86%D0%B5

http://habrahabr.ru/post/136225/" onclick="window.open(this.href);return false;

Есть опыт с похожими оптимизациями - vehicle routing problem.

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

Работало значительно лучше, чем "красивые" генетические и муравьиные алгоритмы.

Гость писал(а):Есть опыт с похожими оптимизациями - vehicle routing problem.

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

Работало значительно лучше, чем "красивые" генетические и муравьиные алгоритмы.

Случайный перебор значительно лучше генетических алгоритмов?

Да и фраза "Сначала находим хоть какое-то решение" напоминает известную картинку: http://www.adberlin.com/qm/QM-Ameisen_klein.jpg" onclick="window.open(this.href);return false;