Вопрос

Эффективно находите все комбинации назначения меньших бинов большим бинам

Автор вопроса: Matt K27.08.2015Ответов: 2

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

var smallBins = [1, 5, 10, 20, 30, 4, 10];

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

var largeBins = [40, 50];

Я хочу найти ЛЮБУЮ комбинацию того, как маленькие контейнеры могут быть распределены по большим контейнерам без превышения вместимости (например, поместите маленькие контейнеры № 4, № 5 в большой контейнер № 2, остальные в № 1).

Ограничения:

Каждая маленькая ячейка должна быть назначена большой ячейке.
Большой бак можно оставить пустым

Эту проблему легко решить за ~~O(n^m)~~ O(2^n) времени (см. ниже): просто попробуйте каждую комбинацию и, если емкость не превышена, сохраните решение. Я хотел бы что-то более быстрое, что может обрабатывать переменное количество бункеров. Какой неясный алгоритм теории графов я могу использовать для уменьшения пространства поиска?

//Brute force
var smallBins = [1, 5, 10, 20, 30, 4, 10];
var largeBins = [40, 50];

function getLegitCombos(smallBins, largeBins) {
  var legitCombos = [];
  var assignmentArr = new Uint32Array(smallBins.length);
  var i = smallBins.length-1;
  while (true) {
    var isValid = validate(assignmentArr, smallBins, largeBins);
    if (isValid) legitCombos.push(new Uint32Array(assignmentArr));
    var allDone = increment(assignmentArr, largeBins.length,i);
    if (allDone === true) break;
  }
  return legitCombos;
}

function increment(assignmentArr, max, i) {
  while (i >= 0) {
    if (++assignmentArr[i] >= max) {
      assignmentArr[i] = 0;
      i--;
    } else {
      return i;
    }
  }
  return true;
}

function validate(assignmentArr, smallBins, largeBins) {
  var totals = new Uint32Array(largeBins.length);
  for (var i = 0; i < smallBins.length; i++) {
    var assignedBin = assignmentArr[i];
    totals[assignedBin] += smallBins[i];
    if (totals[assignedBin] > largeBins[assignedBin]) {
      return false;
    }
  }
  return true;
}
getLegitCombos(smallBins, largeBins);

вы уверены, что ваш код O (n ^ m)? Потому что существует 2 ^ n комбинаций, и в худшем случае алгоритм должен вернуть их все. FuzzyTree 28.08.2015
Я могу ошибаться в этом... проверьте мои рассуждения: каждому маленькому бину m можно присвоить каждый большой бин n, всего n^m. Matt K 28.08.2015
Вы слышали о так называемой проблеме упаковки в корзину? Удачи в поиске более эффективного решения - вы можете выиграть много денег :-) Bergi 28.08.2015
К счастью, это намного проще, чем задача упаковки в мусорное ведро. Я мог бы использовать некоторые из тех же принципов (например, отсортировать ячейки от наибольшего к наименьшему, если емкость превышена, пропустить попытку добавить к ней меньшие значения), но я думаю, что существует что-то, что сбивает его на порядок, вроде как венгерский алгоритм задачи о назначениях. Matt K 28.08.2015
Извини, Мэтт, это действительно O(2^n) просто найти решение для одной из больших корзин (даже если ты оставишь другую пустой). На самом деле это немного сложнее, а не проще, чем упаковка в мусорное ведро. По сути, вы решаете проблему для обоих больших бинов по отдельности (считая другой бин пустым, как указано вторым ограничением), затем вы можете объединить результаты в O(n*(a + b)) = O(2^N), где a и b - количество комбинаций для каждого из двух больших бинов. Nuclearman 28.08.2015
это имеет смысл, я ужасен во временных сложностях. Спасибо, что прояснили! Matt K 28.08.2015

javascript algorithm math graph-theory mathematical-optimization

Ответы

Ответ 1 · рейтинг 2 · גלעד ברקן

Вот моя громоздкая рекурсивная попытка избежать дубликатов и выйти раньше из слишком больших сумм. Функция предполагает, что повторяющиеся элементы, а также размеры ячеек представлены сгруппированными и подсчитанными во входных данных. Вместо того, чтобы помещать каждый элемент в каждую корзину, каждый элемент помещается только в одну из повторяющихся ячеек; и каждый элемент с дубликатами разделяется отчетливо.

Например, в моих результатах комбинация [[[1,10,20]],[[4,5,10,30]]] появляется один раз; в то время как в примере SAS в ответе Лео дважды: один раз как IN[1]={1,3,4} IN[2]={2,5,6,7} и снова как IN[1]={1,4,7} IN[2]={2,3,5,6}.

Однако не могу ручаться за эффективность или плавность работы, так как она почти не тестировалась. Возможно, стекирование вызовов, а не рекурсия, может снизить нагрузку на браузер.

Код JavaScript:

function f (as,bs){

  // i is the current element index, c its count;
  // l is the lower-bound index of partitioned element
  function _f(i,c,l,sums,res){

    for (var j=l; j<sums.length; j++){
      // find next available duplicate bin to place the element in
      var k=0;
      while (sums[j][k] + as[i][0] > bs[j][0]){
        k++;
      }

      // a place for the element was found
      if (sums[j][k] !== undefined){
        var temp = JSON.stringify(sums),
            _sums = JSON.parse(temp);
        _sums[j][k] += as[i][0];

        temp = JSON.stringify(res);
        var _res = JSON.parse(temp);

        _res[j][k].push(as[i][0]);

        // all elements were placed
        if (i == as.length - 1 && c == 1){
          result.push(_res);
          return;

        // duplicate elements were partitioned, continue to next element
        } else if (c == 1){
          _f(i + 1,as[i + 1][1],0,_sums,_res);

        // otherwise, continue partitioning the same element with duplicates
        } else {
          _f(i,c - 1,j,_sums,_res);
        }
      }
    }
  }

  // initiate variables for the recursion
  var sums = [],
      res = []
      result = [];

  for (var i=0; i<bs.length; i++){
    sums[i] = [];
    res[i] = [];
    for (var j=0; j<bs[i][1]; j++){
      sums[i][j] = 0;
      res[i][j] = [];
    }
  }

  _f(0,as[0][1],0,sums,res);
  return result;
}

Выход:

console.log(JSON.stringify(f([[1,1],[4,1],[5,1],[10,2],[20,1],[30,1]], [[40,1],[50,1]])));

/*
[[[[1,4,5,10,10]],[[20,30]]],[[[1,4,5,10,20]],[[10,30]]],[[[1,4,5,20]],[[10,10,30]]]
,[[[1,4,5,30]],[[10,10,20]]],[[[1,4,10,20]],[[5,10,30]]],[[[1,4,30]],[[5,10,10,20]]]
,[[[1,5,10,20]],[[4,10,30]]],[[[1,5,30]],[[4,10,10,20]]],[[[1,10,20]],[[4,5,10,30]]]
,[[[1,30]],[[4,5,10,10,20]]],[[[4,5,10,20]],[[1,10,30]]],[[[4,5,30]],[[1,10,10,20]]]
,[[[4,10,20]],[[1,5,10,30]]],[[[4,30]],[[1,5,10,10,20]]],[[[5,10,20]],[[1,4,10,30]]]
,[[[5,30]],[[1,4,10,10,20]]],[[[10,10,20]],[[1,4,5,30]]],[[[10,20]],[[1,4,5,10,30]]]
,[[[10,30]],[[1,4,5,10,20]]],[[[30]],[[1,4,5,10,10,20]]]]
*/

console.log(JSON.stringify(f([[1,1],[4,1],[5,1],[10,2],[20,1],[30,1]], [[20,2],[50,1]])));

/*
[[[[1,4,5,10],[10]],[[20,30]]],[[[1,4,5,10],[20]],[[10,30]]],[[[1,4,5],[20]],[[10,10,30]]]
,[[[1,4,10],[20]],[[5,10,30]]],[[[1,5,10],[20]],[[4,10,30]]],[[[1,10],[20]],[[4,5,10,30]]]
,[[[4,5,10],[20]],[[1,10,30]]],[[[4,10],[20]],[[1,5,10,30]]],[[[5,10],[20]],[[1,4,10,30]]]
,[[[10,10],[20]],[[1,4,5,30]]],[[[10],[20]],[[1,4,5,10,30]]]]
*/

Вот вторая, более простая версия, которая пытается завершить поток только тогда, когда элемент не может быть размещен:

function f (as,bs){

  var stack = [],
      sums = [],
      res = []
      result = [];

  for (var i=0; i<bs.length; i++){
    res[i] = [];
    sums[i] = 0;
  }

  stack.push([0,sums,res]);

  while (stack[0] !== undefined){
    var params = stack.pop(),
        i = params[0],
        sums = params[1],
        res = params[2];

    for (var j=0; j<sums.length; j++){
      if (sums[j] + as[i] <= bs[j]){
        var _sums = sums.slice();
        _sums[j] += as[i];

        var temp = JSON.stringify(res);
        var _res = JSON.parse(temp);

        _res[j].push(i);

        if (i == as.length - 1){
          result.push(_res);

        } else {
          stack.push([i + 1,_sums,_res]);
        }
      }
    }
  }

  return result;
}

Выход:

var r = f([1,5,10,20,30,4,10,3,4,5,1,1,2],[40,50,30]);
console.log(r.length)

console.log(JSON.stringify(f([1,4,5,10,10,20,30], [40,50])));

162137

[[[30],[1,4,5,10,10,20]],[[10,30],[1,4,5,10,20]],[[10,20],[1,4,5,10,30]]
,[[10,30],[1,4,5,10,20]],[[10,20],[1,4,5,10,30]],[[10,10,20],[1,4,5,30]]
,[[5,30],[1,4,10,10,20]],[[5,10,20],[1,4,10,30]],[[5,10,20],[1,4,10,30]]
,[[4,30],[1,5,10,10,20]],[[4,10,20],[1,5,10,30]],[[4,10,20],[1,5,10,30]]
,[[4,5,30],[1,10,10,20]],[[4,5,10,20],[1,10,30]],[[4,5,10,20],[1,10,30]]
,[[1,30],[4,5,10,10,20]],[[1,10,20],[4,5,10,30]],[[1,10,20],[4,5,10,30]]
,[[1,5,30],[4,10,10,20]],[[1,5,10,20],[4,10,30]],[[1,5,10,20],[4,10,30]]
,[[1,4,30],[5,10,10,20]],[[1,4,10,20],[5,10,30]],[[1,4,10,20],[5,10,30]]
,[[1,4,5,30],[10,10,20]],[[1,4,5,20],[10,10,30]],[[1,4,5,10,20],[10,30]]
,[[1,4,5,10,20],[10,30]],[[1,4,5,10,10],[20,30]]]

Ответ 2 · рейтинг 2 · Leo

Эта проблема встречается достаточно часто, поэтому большинство систем логического программирования с ограничениями включают предикат для ее явного моделирования. В OPTMODEL и CLP мы называем это упаковать:

proc optmodel;
    set SMALL init 1 .. 7, LARGE init 1 .. 2;
    num size    {SMALL} init [1 5 10 20 30 4 10];
    num capacity{LARGE} init [40 50];

    var WhichBin {i in SMALL} integer >= 1 <= card(LARGE);
    var SpaceUsed{i in LARGE} integer >= 0 <= capacity[i];

    con pack( WhichBin, size, SpaceUsed );

    solve with clp / findall;

    num soli;
    set IN{li in LARGE} = {si in SMALL: WhichBin[si].sol[soli] = li};
    do soli = 1 .. _nsol_;
        put IN[*]=;
    end;
quit;

Этот код выдает все решения за 0,06 секунды на моем ноутбуке:

IN[1]={1,2,3,4,6} IN[2]={5,7}
IN[1]={1,2,3,4} IN[2]={5,6,7}
IN[1]={1,2,3,6,7} IN[2]={4,5}
IN[1]={1,2,5,6} IN[2]={3,4,7}
IN[1]={1,2,5} IN[2]={3,4,6,7}
IN[1]={1,2,4,6,7} IN[2]={3,5}
IN[1]={1,2,4,7} IN[2]={3,5,6}
IN[1]={1,2,4,6} IN[2]={3,5,7}
IN[1]={1,3,4,6} IN[2]={2,5,7}
IN[1]={1,3,4} IN[2]={2,5,6,7}
IN[1]={1,5,6} IN[2]={2,3,4,7}
IN[1]={1,5} IN[2]={2,3,4,6,7}
IN[1]={1,4,6,7} IN[2]={2,3,5}
IN[1]={1,4,7} IN[2]={2,3,5,6}
IN[1]={2,3,4,6} IN[2]={1,5,7}
IN[1]={2,3,4} IN[2]={1,5,6,7}
IN[1]={2,5,6} IN[2]={1,3,4,7}
IN[1]={2,5} IN[2]={1,3,4,6,7}
IN[1]={2,4,6,7} IN[2]={1,3,5}
IN[1]={2,4,7} IN[2]={1,3,5,6}
IN[1]={3,5} IN[2]={1,2,4,6,7}
IN[1]={3,4,7} IN[2]={1,2,5,6}
IN[1]={3,4,6} IN[2]={1,2,5,7}
IN[1]={3,4} IN[2]={1,2,5,6,7}
IN[1]={5,7} IN[2]={1,2,3,4,6}
IN[1]={5,6} IN[2]={1,2,3,4,7}
IN[1]={5} IN[2]={1,2,3,4,6,7}
IN[1]={4,6,7} IN[2]={1,2,3,5}
IN[1]={4,7} IN[2]={1,2,3,5,6}

Просто измените первые 3 строки, чтобы решить для других экземпляров. Однако, как указывали другие, эта проблема NP-Hard. Таким образом, он может внезапно переключаться с очень быстрого на очень медленное. Вы также можете решить вариант, в котором не каждый мелкий предмет нужно помещать в большую корзину, создав фиктивную большую корзину с достаточной вместимостью, чтобы вместить всю коллекцию мелких предметов.

Как видно из раздела "Подробности" руководства, алгоритмы, которые быстро решают практические задачи, непросты, и детали их реализации имеют большое значение. Мне неизвестны какие-либо библиотеки CLP, написанные на Javascript. Лучше всего обернуть CLP в веб-службу и вызвать эту службу из кода Javascript.

Перевод вопроса и ответов сообщества Stack Overflow, лицензия CC BY-SA. Оригинал на Stack Overflow.

Эффективно находите все комбинации назначения меньших бинов большим бинам

Ответы

Ответ 1 · рейтинг 2 · גלעד ברקן

Ответ 2 · рейтинг 2 · Leo

Похожие материалы