Bin Packing - Рекурсивное решение методом грубой силы - Как сделать это быстрее
У меня есть массив, который содержит список материалов разных размеров: {4,3,4,1,7,8}, Тем не менее, корзина может вместить материалы до размера 10. Мне нужно выяснить минимальное количество корзин, необходимое для упаковки всех элементов в массиве.
Для указанного выше массива вы можете упаковать 3 контейнера и разделить их следующим образом: {4,4,1}, {3,7}, {8}, Существуют и другие возможные варианты размещения, которые также подходят к трем запасным трубам, но это не может быть сделано с меньшим количеством
Я пытаюсь решить эту проблему с помощью рекурсии, чтобы лучше ее понять.
Я использую эту формулировку DP (страница 20 файла PDF)
Рассмотрим вход (n1;:::;nk) с n = ∑nj элементами
Определите набор k-кортежей (подмножеств входных данных), которые могут быть упакованы в один контейнер
То есть все кортежи (q1;:::;qk), для которых OPT(q1;:::;qk) = 1
Обозначим это множество через Q. Для каждого набора из q мы имеем OPT(q) = 1.
Вычислить оставшиеся значения с помощью повторения: OPT(i1;:::;ik) = 1 + minOPT(i1 - q1;:::;ik - qk)
Я сделал код, и он отлично работает для небольшого набора данных. Но если увеличить размер моего массива до более чем 6 элементов, он станет чрезвычайно медленным - потребуется около 25 секунд, чтобы решить массив, содержащий 8 элементов. Можете ли вы сказать мне, если что-то не так с алгоритмом? Мне не нужно альтернативное решение - просто нужно знать, почему это так медленно, и как его можно улучшить
Вот код, который я написал на C++:
void recCutStock(Vector<int> & requests, int numStocks)
{
if (requests.size() == 0)
{
if(numStocks <= minSize)
{
minSize = numStocks;
}
// cout<<"GOT A RESULT : "<<numStocks<<endl;
return ;
}
else
{
if(numStocks+1 < minSize) //minSize is a global variable initialized with a big val
{
Vector<int> temp ; Vector<Vector<int> > posBins;
getBins(requests, temp, 0 , posBins); // 2-d array(stored in posBins) containing all possible single bin formations
for(int i =0; i < posBins.size(); i++)
{
Vector<int> subResult;
reqMinusPos(requests, subResult, posBins[i]); // subtracts the initial request array from the subArray
//displayArr(subResult);
recCutStock(subResult, numStocks+1);
}
}
else return;
}
}
Функция getBins выглядит следующим образом:
void getBins(Vector<int> & requests, Vector<int> current, int index, Vector<Vector<int> > & bins)
{
if (index == requests.size())
{
if(sum(current,requests) <= stockLength && sum(current, requests)>0 )
{
bins.add(current);
// printBins(current,requests);
}
return ;
}
else
{
getBins(requests, current, index+1 , bins);
current.add(index);
getBins(requests, current, index+1 , bins);
}
}
5 ответов
Алгоритм динамического программирования - это O(n^{2k}), где k - количество различных элементов, а n - общее количество элементов. Это может быть очень медленным независимо от реализации. Как правило, при решении NP-сложной задачи эвристики требуются для скорости.
Я предлагаю вам рассмотреть возможность уменьшения высоты при следующей посадке (NFDH) и высоты уменьшения при первой посадке (FFDH) от Coffman et al. Они 2-оптимальны и 17/10-оптимальны соответственно и работают за O(n log n) времени.
Я рекомендую сначала попробовать NFDH: отсортировать в порядке убывания, сохранить результат в связанном списке, затем многократно пытаться вставлять элементы, начиная с начала (сначала самые большие значения), пока вы не заполните корзину или не останется больше элементов, которые могут быть вставленным. Затем перейдите к следующей корзине и так далее.
Рекомендации:
Оуэн Казер, Даниэль Лемир, Рисование в облаке тегов: алгоритмы визуализации в облаке, тегирование и метаданные для организации социальной информации (WWW 2007), 2007. (см. Раздел 5.1 для обсуждения по теме).
Э. Г. Коффман-младший, М. Р. Гарей, Д. С. Джонсон и Р. Э. Тарьян. Границы производительности для ориентированных на уровень двумерных алгоритмов упаковки. SIAM J. Comput., 9(4):808–826, 1980.
Но если увеличить размер моего массива до более чем 6 элементов, он станет чрезвычайно медленным - потребуется около 25 секунд, чтобы решить массив, содержащий 8 элементов. Можете ли вы сказать мне, если что-то не так с алгоритмом?
Это нормально с грубой силой. Грубая сила не масштабируется вообще.
В вашем случае: размер корзины = 30, общее количество элементов = 27, требуется как минимум 3 корзины. Вы можете попробовать сначала уменьшиться, и это работает!
Больше способов улучшить: с 3 мусорными ведрами и 27 единицами размера у вас останется 3 единицы пространства. Это означает, что вы можете игнорировать элемент размером 1; если вы поместите остальные в 3 лотка, они будут где-то помещаться. Это оставляет вам 26 единиц размера. Это означает, что в одной корзине будет по крайней мере два пустых блока. Если у вас есть предметы размером 2, вы также можете их игнорировать, потому что они подойдут. Если у вас было два предмета размером 2, вы также можете игнорировать предметы размером 3.
У вас есть два предмета размером 7 + 3, который точно соответствует размеру корзины. Всегда есть оптимальное решение, когда эти два находятся в одной корзине: если бы "7" были с другими предметами, их размер был бы 3 или меньше, так что вы могли бы поменять их местами с "3", если они находятся в другой корзине.
Другой метод: если у вас есть k элементов>= размер бина / 2 (на данный момент у вас не может быть двух элементов, равных размеру бина / 2), то вам нужно k бинов. Это может увеличить минимальное количество бинов, которое вы оценили изначально, что, в свою очередь, увеличивает гарантированное пустое пространство во всех бинах, что увеличивает минимальный размер оставшегося пространства в одном бине. Если для j = 1, 2, ..., k вы можете разместить все элементы с ними в j корзинах, которые могут поместиться в одну и ту же корзину, то это оптимально. Например, если у вас есть размеры 8, 1, 1, но нет размера 2, тогда 8+1+1 в корзине будет оптимальным. Так как у вас осталось 8 + 4 + 4, и с 8 ничего не подходит, только "8" в его корзине является оптимальным. (Если бы у вас были предметы размером 8, 8, 8, 2, 1, 1, 1 и ничего больше размера 2, оптимально было бы упаковать их в три корзины).
Больше вещей, которые можно попробовать, если у вас есть большие предметы: если у вас есть большой предмет, и самый большой предмет, который ему подходит, такой же большой или больше, чем любая комбинация предметов, которая подойдет, тогда объединение их является оптимальным. Если места больше, это можно повторить.
В общем, немного размышлений уменьшило проблему, поместив два элемента размером 4, 4 в одну или несколько корзин. С большими проблемами, каждый немного помогает.
После того, как вы сделаете все возможное, чтобы уменьшить проблему, у вас останется проблема: по возможности разместить n элементов в k бункерах, в k + 1 бинах или в k + 2 бинах и т. Д. Если сбой k бинов, то вы знаете, что у вас будет больше свободного места в оптимальном решении k + 1 корзин, что может позволить удалить больше мелких предметов, так что это первое, что нужно сделать.
Затем вы пробуете несколько простых методов: сначала подходит по убыванию, затем подходит по убыванию. Я попробовал достаточно быстрый вариант спуска по первому соответствию: пока подходят два самых больших элемента, добавьте самый большой элемент. В противном случае найдите один элемент или наибольшую комбинацию из двух подходящих элементов и добавьте один элемент или большее из этой комбинации. Если какой-либо из этих алгоритмов помещает ваши элементы в k корзин, вы решили проблему.
И в конце концов вам нужна грубая сила. Вы можете решить: вы пытаетесь уместить все в k корзин или вы пытаетесь доказать, что это невозможно? У вас будет свободное пространство для игры. Скажем, 10 корзин размером 100 и предметы общего размера 936, которые оставят вам 64 единицы пустого пространства. Если вы положите в свой первый ящик только предметы размером 80, то 20 из ваших 64 юнитов уже исчезнут, что затруднит поиск решения оттуда. Таким образом, вы не пробуете вещи в случайном порядке. Сначала вы пробуете комбинации для первого бина, которые заполняют его полностью или почти полностью. Поскольку мелкие предметы облегчают заполнение контейнеров полностью, вы стараетесь не использовать их в первых корзинах, а оставляете их на потом, когда у вас меньше выбора. И когда вы найдете предметы, которые нужно положить в корзину, попробуйте один из простых алгоритмов, чтобы увидеть, смогут ли они его закончить. Например, если при первом подходе по убыванию поместите 90 единиц в первый контейнер, и вам только что удалось поместить туда 99 единиц, вполне возможно, что этого улучшения достаточно, чтобы уместить все.
С другой стороны, если места очень мало (10 лотков, например, общий размер элемента 995), вы можете доказать, что подгонка элементов невозможна. Вам не нужно заботиться об оптимизации алгоритма, чтобы быстро найти решение, потому что вам нужно попробовать все комбинации, чтобы убедиться, что они не работают. Очевидно, что вам нужно с этими числами разместить не менее 95 единиц в первом бункере и т. Д.; это может помочь быстро исключить решения. Если вы доказали, что k бинов недостижимы, то k + 1 бинов должно быть намного более легкой целью.
Я написал решение для упаковки в мусорное ведро, и я могу порекомендовать наилучший вариант при случайном порядке