Comments 9
Вы — герой. Но мне интересно — а какой там объем входных данных, что NP-полнота имеет значение? Поставили бы какой-нибудь Blue Gene (условно говоря) для этой задачи.
когда-то решалось что-то подобное для автоматизации ячеистого склада… 20000 мест, 5000 номенклатуры… В итоге ограничились «типоразмерами» номенклатуры и «псевдовместимости» мест, ибо на минитестах подобное допущение давало погрешность менее 3%
Одна коммерческая библиотека, стоимостью $1K, которую припрягли для аналогичной задачи мы, имеет ограничения порядка 30 объектов и 10 типов коробок.
По словам автора библиотеки, при превышении этих параметров результаты выходят либо до непрактичности неточные, либо до непрактичности времязатратные.
В частности, я представляю себе случаи, когда жадный алгоритм скосячит: например, когда длинный узкий объект нужно поставить «торчком» в оставленные под его размеры «дырки» в предыдущих слоях.
По словам автора библиотеки, при превышении этих параметров результаты выходят либо до непрактичности неточные, либо до непрактичности времязатратные.
В частности, я представляю себе случаи, когда жадный алгоритм скосячит: например, когда длинный узкий объект нужно поставить «торчком» в оставленные под его размеры «дырки» в предыдущих слоях.
«Программка» совершенно нормально работает и с 20 типами коробок и со 100 объектами. Но все же это переборный метод, его время работы прямо пропорционально площади дна коробки, числу типов коробок и числу объектов. Еще одним ограничением является «дискретизация» положения упаковок на дне коробки. Например, если дискретизация — 1 см, а размеры коробок заданы в миллиметрах, то между упаковками будет оставаться расстояние.
Жадный алгоритм может делать неудачные ходы, согласен. Например, на рисунке в статье можно увидеть, что Classic Jenga была положена сначала на 6-м шаге выше, а на 7-м ниже и не плоско, а ребром. Это произошло из-за минимизации закрываемой пустоты. На шестом шаге была возможность положить Jenga без пустоты под ней, а на седьмом шаге она длиннее Фермера на 2 см и пустота под Jenga образовалась. Чтобы она оказалась меньше, программа положила 7-ю коробку на ребро.
Интересно, что буквально сегодня провели «натурный» эксперимент. Так вот, программка уложила упаковки лучше, чем два стажера, которым дали эту задачу, что было совершенно неожиданно для меня. Будем еще перепроверять этот результат.
Жадный алгоритм может делать неудачные ходы, согласен. Например, на рисунке в статье можно увидеть, что Classic Jenga была положена сначала на 6-м шаге выше, а на 7-м ниже и не плоско, а ребром. Это произошло из-за минимизации закрываемой пустоты. На шестом шаге была возможность положить Jenga без пустоты под ней, а на седьмом шаге она длиннее Фермера на 2 см и пустота под Jenga образовалась. Чтобы она оказалась меньше, программа положила 7-ю коробку на ребро.
Интересно, что буквально сегодня провели «натурный» эксперимент. Так вот, программка уложила упаковки лучше, чем два стажера, которым дали эту задачу, что было совершенно неожиданно для меня. Будем еще перепроверять этот результат.
Наверное, нет смысла в получении точной статистики по заказам данного клиента (хотя такая возможность имеется) — число строк в заказе (это будет число типов коробок) и число мест. Ориентировочно в заказе было 10 -15 строк и порядка 100 упаковок.
Когда я говорил, что эта задача NP-полная, я имел ввиду задачу получения глобально-оптимального решения, минимизирующего неиспользуемое пространство в коробе. Применяя «жадный» алгоритм, мы получаем субоптимальное решение. То есть мы не делаем «возвратов», если обнаружили неудачно расположенную на предыдущем шаге коробку, как, например, в методе ветвей и границ. Трудоемкость использованного алгоритма легко оценить. Она пропорциональна произведению ширины, глубины коробки, числу типов коробок и общему числу коробок.
Не вполне сейчас уверен, но вроде бы, в просмотренных мною работах на тему «container loading», давалась оценка эффективности жадного алгоритма как 77%. Есть стандартный набор тестов, на которых проверяются разные алгоритмы. Интересно, что гораздо более сложные алгоритмы могут давать 84, 86%. То есть их эффективность не настолько выше. Возможно, при загрузке морских контейнеров и вагонов и стоит бороться за эти 7-13%. В нашем случае в этом не было смысла.
Когда я говорил, что эта задача NP-полная, я имел ввиду задачу получения глобально-оптимального решения, минимизирующего неиспользуемое пространство в коробе. Применяя «жадный» алгоритм, мы получаем субоптимальное решение. То есть мы не делаем «возвратов», если обнаружили неудачно расположенную на предыдущем шаге коробку, как, например, в методе ветвей и границ. Трудоемкость использованного алгоритма легко оценить. Она пропорциональна произведению ширины, глубины коробки, числу типов коробок и общему числу коробок.
Не вполне сейчас уверен, но вроде бы, в просмотренных мною работах на тему «container loading», давалась оценка эффективности жадного алгоритма как 77%. Есть стандартный набор тестов, на которых проверяются разные алгоритмы. Интересно, что гораздо более сложные алгоритмы могут давать 84, 86%. То есть их эффективность не настолько выше. Возможно, при загрузке морских контейнеров и вагонов и стоит бороться за эти 7-13%. В нашем случае в этом не было смысла.
Кто-нибудь, объясните анекдот…
«Фреймворк, с которым мы работаем, основан на скриптовом языке» — Тот-Который-Нельзя-Называть
Sign up to leave a comment.
Будни автоматизации или «мне нужна программка для 3D упаковки»