Изучение жадного решения проблемы раскроя запасов
Содержание
- Мотивация проблемы раскроя запасов
- Краткий обзор задач NP-Hard
- Кодирование задачи раскроя в Python
- Жадный алгоритм
- Сравнение с полным перебором в малом n-пространстве
- Сравнение со случайным поиском в старшем n-пространстве
- Заключение
Мотивация проблемы сокращения запасов
По профессии я специалист по данным. Хотя мои навыки работы с данными очень важны на работе (по определению), я считаю, что концепции науки о данных помогают решать множество проблем и вне работы!
Один из способов, которым мои навыки DS пригодятся, — это мое хобби в качестве мастера / производителя. Распространенной проблемой является знание того, как планировать резку материала. У меня есть список вырезов, которые мне нужно сделать из нескольких кусков материала одинакового размера из магазина. Как спланировать разрезы таким образом, чтобы тратить как можно меньше? Эта задача известна как «Проблема раскроя». Как оказалось, решить ее может быть очень сложно, на самом деле NP-сложно!
В этой статье я рассмотрю «кратчайший путь» (каламбур) для решения этой проблемы и проанализирую, как этот метод сравнивается с длинным путем.
Краткий обзор проблем NP-Hard
Я не собираюсь вдаваться в подробности о задачах NP-Hard, но хочу дать некоторое представление об этом. Что делает задачу оптимизации сложной, так это обычно размер области ее решения. Имеется в виду, сколько возможных решений вам нужно изучить, чтобы найти лучшее? Сложность задачи обычно оценивается по тому, насколько быстро увеличивается пространство для решения по мере увеличения размера задачи.
В случае с «Проблемой раскроя» проблема становится больше, намного больше по мере того, как вы добавляете больше сокращений. Посмотрите, как быстро растет пространство решений ниже!
Пространство решений увеличивается факторно, а это означает, что общее количество решений, которые необходимо найти, чтобы быть уверенным в оптимальном ответе, равно n!, которое, как вы видите, становится очень, очень быстрым.
NP означает «недетерминированный полином», что означает, что проблема растет быстрее, чем любой…
