Square CoCalc Logo
InfoShareSupport Sign InSign Up
Path: dkms14.ipynb
Views: 8
License: MIT
Visibility: Unlisted (only visible to those who know the link)
Image: ubuntu2004
Project: Packing a Knapsack of Unknown Capacity 2014 (Almost OK)
Raw | Embed | Download |
Kernel: Python 3

Упаковка рюкзака неизвестной вместимости

Видеопрезентация

Постановка задачи

Имеется набор из nn предметов I\mathcal{I}.

  • Каждый предмет iIi \in \mathcal{I} обладает неотрицательной стоимостью v(i)Q0v(i)\in \mathbb{Q}_{\geqslant 0} и строго положительным размером l(i)Q>0l(i)\in \mathbb{Q}_{>0}.

  • Задача — найти подмножество предметов SS, обладающее наибольшей суммарной стоимостью, помещающееся в рюкзак емкостью CC:

S:iSl(i)CS:\sum_{i\in S} l(i) \leqslant CiSv(i)max\sum_{i\in S}v(i) \to \max

Особенность задачи упаковки рюкзака неизвестной вместимости (oblivious knapsack problem) — при выборе подмножества предметов SS емкость рюкзака СС неизвестна. Все предметы рассматриваются по одному разу в некотором порядке, для каждого предмета возможен один из двух исходов:

  • Если рассматриваемый предмет помещается в рюкзак, он должен быть положен.

  • Если рассматриваемый предмет не помещается в рюкзак, он откладывается.

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

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

Если есть метафора лучше → предлагайте свою.

Решение задачи для заданного набора I\mathcal{I} — некоторая политика P\mathcal{P} выбора предметов, представимая в виде бинарного дерева решений, в вершинах которого стоят предметы, имеющие двух потомков, выбор которых зависит от того, был ли предмет помещен в рюкзак.

Любой путь от корня этого дерева к листьям содержит каждый предмет ровно один раз. P(C)I\mathcal{P}(C)\subseteq \mathcal{I} — упаковка политики для заданной вместимости CC.

b_tree.png

Универсальная политика Π\Pi для набора I\mathcal{I} — политика, при которой выбор следующего предмета не зависит от предыдущих исходов.

  • Все пути от корня к листьям в дереве решений такой политики совпадают.

  • Она может быть задана как фиксированная перестановка предметов Π=(Π1,Π2,,Πn)\Pi = (\Pi_1, \Pi_2, \cdots,\Pi_n).

Результат упаковки политики сравнивается с оптимальной упаковкой рюкзака заданной вместимости. Политика P\mathcal{P} для набора I\mathcal{I} называется α\alpha-устойчивой (α\alpha-robust) для вместимости CC, если v(Opt(I,C))αv(P(C)),v(Opt(\mathcal{I}, C)) \leqslant \alpha\cdot v(\mathcal{P(C)}),

где v()v(\cdot) — суммарная стоимость всех предметов в упаковке, Opt(I,C))Opt(\mathcal{I}, C)) — оптимальная упаковка рюкзака вместимости CC для набора I\mathcal{I}.

Политика P\mathcal{P} α\alpha-устойчива, если она α\alpha-устойчива для для любой вместимости. В таком случае α\alpha — множитель устойчивости (robustness factor) политики P\mathcal{P}.

In [108]:
from collections import namedtuple import numpy as np from random import randint

Класс для элемента рюкзака, со стоимостью и весом.

In [109]:
Item = namedtuple('Item', ['size', 'value']) class Item(Item): def __repr__(self): return "«$%d/%d⚖️»" % (self.value, self.size)

Класс для самого рюкзака, с функциями добавления, очистки, и перегрузки

In [110]:
class Knapsack: def __init__(self, capacity): self.capacity = capacity self.empty() def __repr__(self): ''' Выводим компактно все параметры рюкзака, не зависящие от длины''' return "«${total_value}°{total_size}⚖️/{capacity}⚖️#{leni} → {slice}…»".format(**vars(self), leni = len(self.items), slice=self.items[:10]) def add_item(self, item): if self.total_size + item.size > self.capacity: return False self.items.append(item) self.total_size += item.size self.total_value += item.value return True def empty(self): self.total_size = 0 self.total_value = 0 self.items = [] def fill(self, item_list): for item in item_list: self.add_item(item)
In [131]:
item1 = Item(1, 4) item2 = Item(3, 1) knapsack = Knapsack(2) res = knapsack.add_item(item1) res = knapsack.add_item(item2) knapsack
Out[131]:
«$4°1⚖️/2⚖️#1 → [«$4/1⚖️»]…»

Модифицированный жадный алгоритм

Рассматривается классический жадный алгоритм для задачи упаковки рюкзака с известной вместимостью.

  • Сначала отбрасываются предметы, размер которых превосходит емкость рюкзака,

  • затем остальные предметы сортируются в порядке уменьшения плотности d(i)=v(i)/l(i)d(i) = v(i)/l(i).

  • В рюкзак кладутся либо первые jj предметов в этом порядке, которые помещаются в рюкзак, но j+1j+1 уже не помещается,

    • либо, что является модификацией алгоритма, j+1j+1 предмет, если его стоимость превосходит суммарную стоимость всех предыдущих предметов.

mgreedy.png

In [132]:
def MGreedy(knapsack, items): filtered_items = filter(lambda x: x.size <= knapsack.capacity, items) sorted_items = sorted(filtered_items, key=lambda x: - x.value / x.size) s = None for item in sorted_items: item_added = knapsack.add_item(item) if not item_added: s = item break if s is not None and s.value > knapsack.total_value: knapsack.empty() knapsack.add_item(s)
In [133]:
items = (Item(1, 1), Item(1, 4), Item(1, 3), Item(1, 2), Item(4, 20)) knapsack = Knapsack(3) MGreedy(knapsack, items) knapsack
Out[133]:
«$9°3⚖️/3⚖️#3 → [«$4/1⚖️», «$3/1⚖️», «$2/1⚖️»]…»
In [134]:
items = (Item(1, 1), Item(1, 4), Item(1, 3), Item(1, 2), Item(3, 10)) knapsack = Knapsack(3) MGreedy(knapsack, items) knapsack
Out[134]:
«$10°3⚖️/3⚖️#1 → [«$10/3⚖️»]…»
In [135]:
items = (Item(1, 1), Item(1, 4), Item(1, 3), Item(1, 2)) knapsack = Knapsack(4) MGreedy(knapsack, items) knapsack
Out[135]:
«$10°4⚖️/4⚖️#4 → [«$4/1⚖️», «$3/1⚖️», «$2/1⚖️», «$1/1⚖️»]…»

Устойчивость модифицированного жадного алгоритма

Известное свойство модифицированного жадного алгоритма: для любого набора предметов I\mathcal{I} и любой вместимости рюкзака CC в задаче упаковки рюкзака с известной вместимостью v(Opt(I,C))2v(MGreedy(I,C))v(Opt(\mathcal{I}, C)) \leqslant 2\cdot v(MGreedy(\mathcal{I}, C)) Проверим это свойство в задаче упаковки рюкзака с целочисленными вместимостью рюкзака, размерами и стоимостями предметов.

В этой задаче оптимальное решение можно найти при помощи алгоритма динамического программирования.

In [0]:
def optimal_package_value(knapsack, items): assert (type(knapsack.capacity) == int) for item in items: assert (type(item.size) == int) total_sizes = np.zeros((len(items) + 1, knapsack.capacity + 1), dtype=int) for k, item in enumerate(items): k = k + 1 for size in range(1, knapsack.capacity + 1): if size >= item.size: total_sizes[k][size] = max(total_sizes[k - 1][size], total_sizes[k -1][size - item.size] + item.value) else: total_sizes[k][size] = total_sizes[k - 1][size] return total_sizes[len(items)][knapsack.capacity]

Stas: Опциональная задача (не в 2021 году) — ускорить поиск оптимального решения, используя ЦЛП решатель, доступный из Python, например, ortools.

In [136]:
from ortools.algorithms import pywrapknapsack_solver
In [142]:
def optimal_package_value_ortools(knapsack, items): solver = pywrapknapsack_solver.KnapsackSolver( pywrapknapsack_solver.KnapsackSolver. KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER, 'KnapsackBoolean') values = [it.value for it in items] weights = [[it.size for it in items]] capacities = [knapsack.capacity] solver.Init(values, weights, capacities) computed_value = solver.Solve() return computed_value

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

In [143]:
def search_worst_case(capacity, n_items, n_samples, algorithm, ud = False): capacity = capacity max_item_size = capacity max_item_value = capacity max_alpha = -1 for _ in range(n_samples): items = [] for _ in range(n_items): size = randint(1, max_item_size) value = size if ud else randint(1, max_item_value) items.append(Item(size, value)) knapsack = Knapsack(capacity) optimal_value = optimal_package_value(knapsack, items) optimal_value_or = optimal_package_value_ortools(knapsack, items) assert(optimal_value == optimal_value_or) algorithm(knapsack, items) alpha = optimal_value / knapsack.total_value if max_alpha == -1 or alpha > max_alpha: max_alpha = alpha worst_items = items return worst_items, max_alpha

Stas: Не совсем понятно, зачем искать наихудший набор для жадного среди случайных наборов — его же легко построить конструктивно.

In [144]:
SIZE = 200 N_ITEMS = 5 N_SAMPLES = 100000
In [145]:
worst_items, max_alpha = search_worst_case(SIZE, N_ITEMS, N_SAMPLES, MGreedy, ud=False) print('Наибольшее отклонение от оптимальной стоимости:', max_alpha) print('Набор предметов:', worst_items) knapsack = Knapsack(SIZE) MGreedy(knapsack, worst_items) knapsack
Out[145]:
Наибольшее отклонение от оптимальной стоимости: 1.9482758620689655 Набор предметов: [«$29/47⚖️», «$123/176⚖️», «$165/21⚖️», «$174/177⚖️», «$7/5⚖️»]
«$174°177⚖️/200⚖️#1 → [«$174/177⚖️»]…»

Можно заметить, что наибольшее отклонение суммарной стоимости предметов от оптимальной близко, но не превосходит 2.

Универсальная политика в задаче упаковки рюкзака неизвестной вместимости

Алгоритм имитирует поведение модифицированного жадного алгоритма.

  • Сначала определяются меняющие предметы (swap items) — предметы, которые при выполнении жадного алгоритма на рюкзаке соответствующим им вместимости выбирались из-за модификации: сумма стоимостей всех предметов, плотность которых превосходит плотность меняющего предмета, меньше стоимости этого предмета.

In [115]:
def swap_items(items): sorted_items = sorted(items, key=lambda x: - x.value/x.size) sum_value = 0 swap_items = [] for item in sorted_items: swap_items.append((item, item.value > sum_value)) sum_value += item.value return swap_items
In [116]:
swap_items([ Item(size=1, value=3), Item(size=1, value=2), Item(size=1, value=1), Item(size=3, value=6), ])
Out[116]:
[(«$3/1⚖️», True), («$2/1⚖️», False), («$6/3⚖️», True), («$1/1⚖️», False)]
  • Также задается строгий порядок между предметами по плотности, причем если плотность предметов совпадает, сравнение производится по индексу (tie-breaking index).

In [117]:
def comp_items(ext_item1, ext_item2): bi1, item1 = ext_item1 bi2, item2 = ext_item2 if item1.value / item1.size == item2.value / item2.size: return bi1 > bi2 return item1.value / item1.size > item2.value / item2.size
In [118]:
comp_items( (2, Item(2,1)), (1, Item(4,2)) )
Out[118]:
True
In [119]:
comp_items( (1, Item(2,1)), (2, Item(4,2)) )
Out[119]:
False
In [120]:
comp_items( (2, Item(2,1)), (1, Item(3,2)) )
Out[120]:
False

Универсальная политика формируется следующим образом: предметы обходятся в порядке неубывания размера. Если предмет является меняющим, он добавляется в начало политики. Иначе предмет вставляется в политику так, что все предметы до него имеют больший порядок.

universal.png

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

In [121]:
def Universal(items): items_swp = swap_items(items) sorted_items = sorted(items_swp, key=lambda x: x[0].size) packing_policy = [] total_value = 0 for breaking_index, (item, swap_item) in enumerate(sorted_items): ext_item = (breaking_index, item) if swap_item: packing_policy.insert(0, ext_item) else: j = 0 while (j < len(packing_policy) and comp_items(packing_policy[j], ext_item)): j += 1 packing_policy.insert(j, ext_item) total_value += item.value return [item for _, item in packing_policy]
In [122]:
def fill_universal(knapsack, items): knapsack.fill(Universal(items))
In [123]:
items = (Item(1, 1), Item(1, 4), Item(1, 3), Item(1, 2), Item(4, 20)) knapsack = Knapsack(3) fill_universal(knapsack, items) knapsack
Out[123]:
«$9°3⚖️/3⚖️#3 → [«$4/1⚖️», «$3/1⚖️», «$2/1⚖️»]…»
In [124]:
items = (Item(2.5, 1), Item(1, 4), Item(2.5, 3), Item(2.5, 2), Item(3, 10)) knapsack = Knapsack(3) fill_universal(knapsack, items) knapsack
Out[124]:
«$10°3⚖️/3⚖️#1 → [«$10/3⚖️»]…»
In [125]:
items = (Item(1, 1), Item(1, 4), Item(1, 3), Item(1, 2)) knapsack = Knapsack(4) fill_universal(knapsack, items) knapsack
Out[125]:
«$10°4⚖️/4⚖️#4 → [«$4/1⚖️», «$3/1⚖️», «$2/1⚖️», «$1/1⚖️»]…»

Устойчивость алгоритма Universal

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

In [126]:
worst_items, max_alpha = search_worst_case(SIZE, N_ITEMS, N_SAMPLES, fill_universal, ud=False) print('Наибольшее отклонение от оптимальной стоимости:', max_alpha) print('Набор предметов:', worst_items) knapsack = Knapsack(SIZE) fill_universal(knapsack, worst_items) knapsack
Out[126]:
Наибольшее отклонение от оптимальной стоимости: 1.8522727272727273 Набор предметов: [«$168/146⚖️», «$18/14⚖️», «$158/53⚖️», «$194/179⚖️», «$180/181⚖️»]
«$176°67⚖️/200⚖️#2 → [«$158/53⚖️», «$18/14⚖️»]…»

Наибольшее отклонение суммарной стоимости предметов от оптимальной близко, но не превосходит 2.

Универсальная политика при единичной плотности предметов

Если в задаче построения универсальной политики для рюкзака неизвестной вместимости все предметы имеют единичную плотность v(i)=l(i)v(i) = l(i), можно построить политику с меньшим коэффициентом устойчивости, равным золотому сечению φ1,618\varphi \approx 1,618.

Алгоритм работает следующим образом: сначала предметы сортируются в порядке возрастания стоимости, причем при равенстве задается строгий порядок по индексу. Далее предметы обходятся в полученном порядке. Каждый предмет вставляется в политику так, что все стоимости всех предметов до него в политике при умножении на φ\varphi превосходит стоимость этого предмета.

universalud.png

In [127]:
PHI = 1.618034 def comp_items_ud(ext_item1, ext_item2): bi1, item1 = ext_item1 bi2, item2 = ext_item2 if item1.value == item2.value: return bi1 > bi2 return item1.value > item2.value def UniversalUD(items): for item in items: assert (item.value == item.size) sorted_items = sorted(items, key=lambda x: x.value) packing_policy = [] for item in sorted_items: j = 0 while (j < len(packing_policy) and item.value < packing_policy[j].value * PHI): j += 1 packing_policy.insert(j, item) return packing_policy def fill_universal_ud(knapsack, items): knapsack.fill(UniversalUD(items))

Устойчивость алгоритма UniversalUD

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

In [128]:
worst_items, max_alpha = search_worst_case(SIZE, N_ITEMS, N_SAMPLES, MGreedy, ud=True) print('Наибольшее отклонение от оптимальной стоимости:', max_alpha) print('Набор предметов:', worst_items) knapsack = Knapsack(SIZE) MGreedy(knapsack, worst_items) knapsack
Out[128]:
Наибольшее отклонение от оптимальной стоимости: 1.9702970297029703 Набор предметов: [«$41/41⚖️», «$60/60⚖️», «$100/100⚖️», «$180/180⚖️», «$139/139⚖️»]
«$101°101⚖️/200⚖️#2 → [«$41/41⚖️», «$60/60⚖️»]…»
In [129]:
worst_items, max_alpha = search_worst_case(SIZE, N_ITEMS, N_SAMPLES, fill_universal, ud=True) print('Наибольшее отклонение от оптимальной стоимости:', max_alpha) print('Набор предметов:', worst_items) knapsack = Knapsack(SIZE) fill_universal(knapsack, worst_items) knapsack
Out[129]:
Наибольшее отклонение от оптимальной стоимости: 1.8181818181818181 Набор предметов: [«$3/3⚖️», «$106/106⚖️», «$102/102⚖️», «$98/98⚖️», «$107/107⚖️»]
«$110°110⚖️/200⚖️#2 → [«$107/107⚖️», «$3/3⚖️»]…»

Полученные значения близки к 2.

В статье приводится доказательство, что коэффициент устойчивости построенной универсальной политики в задаче с единичными плотностями предметов равен φ1,618\varphi \approx 1,618. Это следует из следующего отношения: 1+1φ=φ1 + \frac{1}{\varphi} = \varphi

In [130]:
worst_items, max_alpha = search_worst_case(SIZE, N_ITEMS, N_SAMPLES, fill_universal_ud, ud=True) print('Наибольшее отклонение от оптимальной стоимости:', max_alpha) print('Набор предметов:', worst_items) knapsack = Knapsack(SIZE) fill_universal_ud(knapsack, worst_items) knapsack
Out[130]:
Наибольшее отклонение от оптимальной стоимости: 1.6179775280898876 Набор предметов: [«$144/144⚖️», «$127/127⚖️», «$89/89⚖️», «$140/140⚖️», «$131/131⚖️»]
«$89°89⚖️/200⚖️#1 → [«$89/89⚖️»]…»

Полученное значение коэффициента устойчивости близко к теоретическому.

Stas:Потенциальная задача — рассмотреть из статьи алгоритм с O(nlogn)O(n \log n)

In [0]: