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

Question

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

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

Answer 1

Я создал решение на JavaScript, используя processing.js и HTML5 canvas.

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

В зависимости от типа ввода алгоритм сортировки может дать хорошие результаты в 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

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

Answer 2

Упрощение

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

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

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

Пример Max'ed для 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-Упаковка проблема , с частичнойy заполненная корзина.

Поиск b

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

1. нижний предел: если сумма высот сегмента = сумма высот палки
2. верхний предел: количество сегментов =количество палочек самая длинная палка <самая длинная высота сегмента </li>

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

---

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

Например:

• сортировать палку по длине: от наибольшей к наименьшей
• начинать «помещать наибольшие предметы» в первую ячейку - 1081 *

Answer 3

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

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

Answer 4

Я очень уверен, что это эквивалентно упаковке в мусорное ведро:

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

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

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

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

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

Answer 5

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

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

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

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

.

Answer 6

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

Можно, конечно, расширить методологию «упаковки в несколько бинов» и протестировать сколь угодно малые приращения.(Пример: запустить методологию множественного бинпэкинга с уровнями, начинающимися с 0,0, 0,1, 0,2, ... 0,9), а затем выбрать лучший результат, но кажется, что вы застряли в расчетах на бесконечное количество времени, если у вас не было методологиичтобы убедиться, что вы поняли это «правильно» (или точнее, что у вас были все «строки» правильно относительно того, что они содержали, и в этот момент вы могли сдвинуть их вниз, пока они не встретились с краем параболы)

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

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

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

Answer 7

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