Упаковка кусков данных разного размера в несколько корзин

РЕДАКТИРОВАТЬ: Кажется, что эта проблема называется "проблема резки заготовки"

Мне нужен алгоритм, который дает мне (пространство) оптимальное расположение кусков в бункерах. Одним из способов было бы поместить большие куски в первую очередь. Но посмотрите, как этот алгоритм терпит неудачу в этом примере:

Chunks        Bins
-----------------------------
AAA BBB CC DD (       ) (   )

Algorithm     Result
-----------------------------
biggest first (AAABBB ) (CC )
optimal       (AAACCDD) (BBB)

"Самый большой первый" не может вписаться в ДД. Может быть, это поможет построить таблицу следующим образом:

Size 1: ---
Size 2: CC, DD
Size 3: AAA, BBB

Size 4: CCDD
Size 5: AAACC, AAADD, BBBCC, BBBDD
Size 6: AAABBB

Size 7: AAACCDD, BBBCCDD
Size 8: AAABBBCC, AAABBBDD
Size 10: AAABBBCCDD
Источник

4 ответа

Решение

Это в основном вариант проблемы упаковки в мусорное ведро. Эта проблема, как известно, является NP-сложной, поэтому не ожидайте найти эффективный оптимальный алгоритм для сложных случаев (т. Е. Со многими объектами и бинами).

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

Это довольно легко реализовать: просто возьмите первый объект, а затем рекурсивно перезапустите алгоритм с первым объектом, размещенным в каждом из бинов по очереди (т. Е. Вычтите размер объекта из доступного пространства бинов). Наконец, вам просто нужно отследить лучшее из найденных "решений" и вернуть его в качестве окончательного ответа, как только вы попробуете все комбинации.

Вы также можете ускорить выполнение этого алгоритма:

  • Считая все объекты одинакового размера эквивалентными
  • Обрезка дерева поиска (т.е. ранний возврат из ветви), если вы не можете превзойти текущее лучшее решение, например, когда вы уже нашли идеальное соответствие

Обновлено на основе комментариев о размере проблемы

Учитывая, что, похоже, у вас есть очень большое количество блоков, вы можете попробовать следующее:

  • Установите самые большие 10-20 кусков, используя исчерпывающий поиск, как указано выше.
  • Выделите остаток, используя метод наибольшего соответствия
Источник

Микера прав: эта множественная задача о ранце (вариант проблемы с упаковкой в ​​мусорное ведро) трудна для NP.

Вот несколько ваших вариантов (скопировано из моего ответа на похожий вопрос):

  • Грубая сила, или еще лучше, ветвь и связка. Не масштабируется (вообще!), Но найдет вам оптимальное решение (хотя, вероятно, не в наших жизнях).

  • Детерминистический алгоритм: сортируйте куски по наибольшему размеру, просматривайте этот список один за другим и назначайте ему лучшее оставшееся место. Это закончится очень быстро, но решение может быть далеко от оптимального (или выполнимого). Вот хорошая картинка, показывающая пример того, что может пойти не так. Но если вы хотите, чтобы все было просто, это путь.

  • Метаэвристика, начиная с результата детерминированного алгоритма. Это даст вам очень хороший результат в разумные сроки, лучше, чем люди придумали. В зависимости от того, сколько времени вы уделяете этому и сложности проблемы, это может быть или не быть оптимальным решением. Есть несколько библиотек, таких как Drools Planner (Java с открытым исходным кодом).

Источник

Общий лучший алгоритм для этой проблемы еще не существует (см. Проблему упаковки бина). Вы можете найти несколько разных подходов в википедии и / или прибегнуть к помощи "проблемы с упаковкой в ​​мусорное ведро", и, возможно, "проблема с рюкзаком" также поможет.

Источник

Алгоритм " Танцующие связи" Дональда Кнута быстр в поиске решений проблем "точного покрытия".

Источник
Другие вопросы по тегам