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

допустим, у меня есть парабола. Теперь у меня тоже есть куча палочек, которые имеют одинаковую ширину (да, мои навыки рисования потрясающие!). Как я могу сложить эти палочки в параболу таким образом, что я минимизирую пространство, которое он использует, насколько это возможно? Я считаю, что это подпадает под категорию проблемы с рюкзаком, но эта страница Википедии, похоже, не приближает меня к решению реального мира. Это NP-трудная проблема?

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

7 60
algorithm np-hard

7 ответов:

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

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

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

Sorted insertion

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

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

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

23

упрощение

сначала я хочу упростить задачу, для этого:

  • я переключаю оси и добавляю их друг к другу, это приводит к росту 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] реального значения:

enter image description here

и части высот

15

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

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

12

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

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

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

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

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

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

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

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

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

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

2

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

1

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

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

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

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

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

1