Параболический рюкзак

Ответ 1

Я приготовил решение в JavaScript с помощью processing.js и холста HTML5.

Этот проект должен стать хорошей отправной точкой, если вы хотите создать собственное решение. Я добавил два алгоритма. Один, который сортирует входные блоки от самых больших до самых маленьких, а другой - случайным образом перетасовывает список. Затем каждый предмет помещается в ковш, начиная со дна (наименьшее ведро) и перемещаясь вверх, пока не будет достаточно места для установки.

В зависимости от типа ввода алгоритм сортировки может давать хорошие результаты в O (n ^ 2). Здесь приведен пример отсортированного вывода.

Здесь вставка в алгоритм порядка.

function solve(buckets, input) {
  var buckets_length = buckets.length,
      results = [];

  for (var b = 0; b < buckets_length; b++) {
    results[b] = [];
  }

  input.sort(function(a, b) {return b - a});

  input.forEach(function(blockSize) {
    var b = buckets_length - 1;
    while (b > 0) {
      if (blockSize <= buckets[b]) {
        results[b].push(blockSize);
        buckets[b] -= blockSize;
        break;
      }
      b--;
    }
  });

  return results;
}

Проект на github - https://github.com/gradbot/Parabolic-Knapsack

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

Ответ 2

Упрощение

Сначала я хочу упростить проблему, чтобы сделать это:

• Я переключаю оси и добавляю их друг к другу, это приводит к росту x2.
• Я предполагаю, что это парабола на закрытом интервале [a, b], where a = 0 и для этого примера b = 3

Допустим, вам дана b (вторая часть интервала) и w (ширина сегмента), тогда вы можете найти общее количество сегментов n=Floor[b/w]. В этом случае существует тривиальный случай максимизации суммы и функции Римана, чтобы получить высоту сегмента i: f(b-(b*i)/(n+1))). На самом деле это предположение, и я не уверен на 100%.

Максимальный пример для 17 сегментов на закрытом интервале [0, 3] для функции Sqrt[x] действительных значений:

И функция сегмента высота в этом случае равна Re[Sqrt[3-3*Range[1,17]/18]], а значения:

• Точная форма:

{Sqrt [17/6], 2 Sqrt [2/3], Sqrt [5/2], Sqrt [7/3], Sqrt [13/6], Sqrt [2], Sqrt [11/6], Sqrt [5/3], Sqrt [3/2], 2/Sqrt [3], Sqrt [7/6], 1, Sqrt [5/6], Sqrt [2/3], 1/Sqrt [2], 1/Sqrt [3], 1/Sqrt [6]}

• Приблизительная форма:

{+1,6832508230603465, 1,632993161855452, +1,5811388300841898, +1,5275252316519468, +1,4719601443879744, +1,4142135623730951, +1,35400640077266, +1,2909944487358056, 1,224744871391589, +1,1547005383792517, +1,0801234497346435, 1, +0,9128709291752769, 0,816496580927726, +0,7071067811865475, +0,5773502691896258, 0,4082482904638631}

Что вы заархивировали, это проблема Bin-Packing, с частично заполненным ящиком.

Поиск b

Если b неизвестно или наша задача состоит в том, чтобы найти наименьшее возможное b, под которым все палочки образуют начальную связку. Тогда мы можем ограничить не менее b значениями:

• нижний предел: если сумма высоты сегмента = сумма высоты палок
• верхний предел: количество сегментов = количество палочек самая длинная палочка < максимальная высота сегмента

Один из простейших способов найти b - взять ось в (higher limit-lower limit)/2 найти, если решение существует. Затем он становится новым верхним или нижним пределом, и вы повторяете процесс до тех пор, пока не будет достигнута требуемая точность.

Когда вы ищете b, вам не нужен точный результат, но субоптимальный, и он будет намного быстрее, если вы используете эффективный алгоритм для нахождения относительно близкой точки поворота к фактическому b.

Например:

• сортировать палку по длине: от наибольшего до наименьшего
• начните "вставлять наибольшие предметы" в первый бит, подходящий вам.

Ответ 3

Это эквивалентно наличию нескольких рюкзаков (при условии, что эти блоки имеют одинаковую "высоту", это означает, что есть один рюкзак для каждой "линии" ) и, таким образом, является примером проблемы упаковки корзины.

См. http://en.wikipedia.org/wiki/Bin_packing

Ответ 4

Как я могу складывать эти палочки в параболе, так что я минимизирую (вертикальное) пространство, которое он использует как можно больше?

Просто справляйтесь с ним, как и с любой другой проблемой Bin Packing. Я бы бросил на него метаэвристику (например, поиск табу, имитированный отжиг,...), поскольку эти алгоритмы не являются специфичными для проблемы.

Например, если бы я начал с моей проблемы с облачным балансом (= форма Bin Packing) в Drools Planner. Если все палки имеют одинаковую высоту и нет вертикального пространства между двумя палочками друг на друга, мне нечего изменить:

• Переименуйте Computer в ParabolicRow. Удалите его свойства (процессор, память, полоса пропускания). Дайте ему уникальный level (где 0 - нижняя строка). Создайте несколько ParabolicRows.
• Переименуйте Process в Stick
• Переименуйте ProcessAssignement в StickAssignment
• Перепишите жесткие ограничения, чтобы проверить, хватит ли места для суммы всех Sticks, назначенных ParabolicRow.
• Перепишите мягкие ограничения, чтобы свести к минимуму наивысший level всех ParabolicRows.

Ответ 5

Я очень уверен, что это эквивалентно бин-упаковке:

неформальное сокращение

Будь x шириной самой широкой строки, сделайте бункеры 2x большими и создайте для каждой строки элемент-заполнитель, который является 2x-rowWidth большим. Таким образом, два элемента-заполнителя не могут быть упакованы в один ящик.

Чтобы уменьшить упаковку бинов на параболическом рюкзаке, вы просто создаете элементы-заполнители для всех строк, которые больше, чем требуемый бинзинг с размером width-binsize. Кроме того, добавьте заполнители для всех строк, которые меньше, чем binsize, которые заполняют всю строку.

Это, очевидно, означает, что ваша проблема NP-hard.

Для других идей смотрите здесь, возможно: http://en.wikipedia.org/wiki/Cutting_stock_problem

Ответ 6

Скорее всего, это 1-0 Рюкзак или проблема упаковки бутылок. Это сложная проблема с NP, и, скорее всего, эту проблему я не понимаю, и я не могу вам объяснить, но вы можете оптимизировать с помощью жадных алгоритмов. Вот полезная статья об этом http://www.developerfusion.com/article/5540/bin-packing, которую я использую, чтобы сделать мою упаковку bin php на phpclasses.org.

Ответ 7

Репутация для тех, кто упомянул о том, что уровни могут быть на разных высотах (например: если палки 1 'толщиной', уровень 1 идет от 0,1 единицы до 1,1 единицы или может составлять от 0,2 до 1,2 единицы вместо)

Разумеется, вы можете расширить методологию "множественной упаковки в банке" и протестировать произвольно малые приращения. (Пример: выполните множественную методологию binpacking с уровнями, начинающимися с 0.0, 0.1, 0.2,... 0.9), а затем выберите лучший результат, но похоже, что вы застряли бы в течение бесконечного промежутка времени, если у вас не было какой-либо методологии чтобы убедиться, что вы получили это "право" (точнее, что у вас были все "ряды" правильные относительно того, что они содержали, и в этот момент вы могли сдвинуть их вниз, пока они не достигли края параболы)

Кроме того, ОП не указывал, что палки должны были укладываться горизонтально - хотя, возможно, OP подразумевал это с этими милыми рисунками.

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

Я говорю, просто бросайте их туда и встряхивайте их;)