Викиконспекты - Вклад участника [ru]

Декартово дерево

2016-11-26T08:32:36Z

37.57.17.214: /* Другой алгоритм за O(n\log n) */ опечатка

''Эта статья про курево''

'''Декартово дерево или дерамида''' (англ. ''Treap'') {{---}} это структура данных, объединяющая в себе [[Дерево поиска, наивная реализация|бинарное дерево поиска]] и [[Двоичная куча|бинарную кучу]] (отсюда и второе её название: treap (tree + heap) и дерамида (дерево + пирамида), также существует название курево (куча + дерево).

Более строго, это бинарное дерево, в узлах которого хранится пары <tex> (x,y) </tex>, где <tex>x</tex> {{---}} это ключ, а <tex>y</tex> {{---}} это приоритет. Также оно является двоичным деревом поиска по <tex>x</tex> и пирамидой по <tex>y</tex>. Предполагая, что все <tex>x</tex> и все <tex>y</tex> являются различными, получаем, что если некоторый элемент дерева содержит <tex>(x_0,y_0)</tex>, то у всех элементов в левом поддереве <tex>x < x_0</tex>, у всех элементов в правом поддереве <tex> x > x_0</tex>, а также и в левом, и в правом поддереве имеем: <tex> y < y_0</tex>.

Дерамиды были предложены Сиделем (Siedel) и Арагоном (Aragon) в 1996 г.

== Операции в декартовом дереве ==
=== split ===
[[file:split.png|thumb|400px|Операция split]]

Операция <tex>\mathrm{split}</tex> (''разрезать'') позволяет сделать следующее, разрезать исходное дерево <tex>T</tex> по ключу <tex>k</tex>. Возвращать она будет такую пару деревьев <tex>\langle T_1, T_2\rangle </tex>, что в дереве <tex>T_1</tex> ключи меньше <tex>k</tex>, а в дереве <tex>T_2</tex> все остальные: <tex>\mathrm{split}(T, k) \to \langle T_1, T_2\rangle </tex>.

Эта операция устроена следующим образом.

Рассмотрим случай, в котором требуется разрезать дерево по ключу, большему ключа корня.
Посмотрим, как будут устроены результирующие деревья <tex>T_1</tex> и <tex>T_2</tex>:
* <tex>T_1</tex>: левое поддерево <tex>T_1</tex> совпадёт с левым поддеревом <tex>T</tex>. Для нахождения правого поддерева <tex>T_1</tex>, нужно разрезать правое поддерево <tex>T</tex> на <tex>T^R_1</tex> и <tex>T^R_2</tex> по ключу <tex>k</tex> и взять <tex>T^R_1</tex>.
* <tex>T_2</tex> совпадёт с <tex>T^R_2</tex>.

Случай, в котором требуется разрезать дерево по ключу, меньше либо равному ключа в корне, рассматривается симметрично.

=== Псевдокод ===

'''<tex>\langle</tex>Treap, Treap<tex>\rangle</tex>''' split(t: '''Treap''', k: '''int'''):
'''if''' t == <tex> \varnothing </tex>
'''return''' <tex>\langle</tex><tex> \varnothing </tex>, <tex> \varnothing </tex><tex>\rangle</tex>
'''else if''' k > t.x
<tex>\langle</tex>t1, t2<tex>\rangle</tex> = split(t.right, k)
t.right = t1
'''return''' <tex>\langle</tex>t, t2<tex>\rangle</tex>
'''else'''
<tex>\langle</tex>t1, t2<tex>\rangle</tex> = split(t.left, k)
t.left = t2
'''return''' <tex>\langle</tex>t1, t<tex>\rangle</tex>

=== Время работы ===

Оценим время работы операции <tex>\mathrm{split}</tex>. Во время выполнения вызывается одна операция <tex>\mathrm{split}</tex> для
дерева хотя бы на один меньшей высоты и делается ещё <tex>O(1)</tex> операций. Тогда итоговая трудоёмкость этой операции
равна <tex>O(h)</tex>, где <tex>h</tex> {{---}} высота дерева.

=== merge ===
[[file:merge.png|thumb|400px|Операция merge]]

Рассмотрим вторую операцию с декартовыми деревьями {{---}} <tex>\mathrm{merge}</tex> (''слить'').

С помощью этой операции можно слить два декартовых дерева в одно.
Причем, все ключи в первом(''левом'') дереве должны быть меньше, чем
ключи во втором(''правом''). В результате получается дерево, в котором есть все ключи из первого и второго деревьев: <tex>\mathrm{merge}(T_1, T_2) \to \{T\}</tex>

Рассмотрим принцип работы этой операции. Пусть нужно слить деревья <tex>T_1</tex> и <tex>T_2</tex>.
Тогда, очевидно, у результирующего дерева <tex>T</tex> есть корень.
Корнем станет вершина из <tex>T_1</tex> или <tex>T_2</tex> с наибольшим приоритетом <tex>y</tex>. Но вершина с самым большим <tex>y</tex> из всех вершин деревьев
<tex>T_1</tex> и <tex>T_2</tex> может быть только либо корнем <tex>T_1</tex>, либо корнем <tex>T_2</tex>.
Рассмотрим случай, в котором корень <tex>T_1</tex> имеет больший <tex>y</tex>, чем корень <tex>T_2</tex>.
Случай, в котором корень <tex>T_2</tex> имеет больший <tex>y</tex>, чем корень <tex>T_1</tex>, симметричен этому.

Если <tex>y</tex> корня <tex>T_1</tex> больше <tex>y</tex> корня <tex>T_2</tex>, то он и будет являться корнем. Тогда левое поддерево
<tex>T</tex> совпадёт с левым поддеревом <tex>T_1</tex>. Справа же нужно подвесить объединение правого поддерева
<tex>T_1</tex> и дерева <tex>T_2</tex>.

=== Псевдокод ===

'''Treap''' merge(t1: '''Treap''', t2: '''Treap'''):
'''if''' t2 == <tex> \varnothing </tex>
'''return''' t1
'''if''' t1 == <tex> \varnothing </tex>
'''return''' t2
'''else if''' t1.y > t2.y
t1.right = merge(t1.right, t2)
'''return''' t1
'''else'''
t2.left = merge(t1, t2.left)
'''return''' t2

=== Время работы ===

Рассуждая аналогично операции <tex>\mathrm{split}</tex> приходим к выводу, что трудоёмкость операции <tex>\mathrm{merge}</tex>
равна <tex>O(h)</tex>, где <tex>h</tex> {{---}} высота дерева.

=== insert ===
Операция <tex>\mathrm{insert}(T, k)</tex> добавляет в дерево <tex>T</tex> элемент <tex>k</tex>, где <tex>k.x</tex> {{---}} ключ, а <tex>k.y</tex>{{---}} приоритет.

Представим что элемент <tex>k</tex>, это декартово дерево из одного элемента, и для того чтобы его добавить в наше декартово дерево <tex>T</tex>, очевидно, нам нужно их слить. Но <tex>T</tex> может содержать ключи как меньше, так и больше ключа <tex>k.x</tex>, поэтому сначала нужно разрезать <tex>T</tex> по ключу <tex>k.x</tex>.

* Реализация №1
# Разобьём наше дерево по ключу, который мы хотим добавить, то есть <tex>\mathrm{split}(T, k.x) \to \langle T_1, T_2\rangle</tex>.
# Сливаем первое дерево с новым элементом, то есть <tex>\mathrm{merge}(T_1, k) \to T_1</tex>.
# Сливаем получившиеся дерево со вторым, то есть <tex>\mathrm{merge}(T_1, T_2) \to T</tex>.

* Реализация №2
# Сначала спускаемся по дереву (как в обычном бинарном дереве поиска по <tex>k.x</tex>), но останавливаемся на первом элементе, в котором значение приоритета оказалось меньше <tex>k.y</tex>.
# Теперь вызываем <tex>\mathrm{split}(T, k.x) \to \langle T_1, T_2\rangle</tex> от найденного элемента (от элемента вместе со всем его поддеревом)
# Полученные <tex>T_1</tex> и <tex>T_2</tex> записываем в качестве левого и правого сына добавляемого элемента.
# Полученное дерево ставим на место элемента, найденного в первом пункте.

В первой реализации два раза используется <tex>\mathrm{merge}</tex>, а во второй реализации слияние вообще не используется.

=== remove ===
Операция <tex>\mathrm{remove}(T, x)</tex> удаляет из дерева <tex>T</tex> элемент с ключом <tex>x</tex>.

* Реализация №1

# Разобьём наше дерево по ключу, который мы хотим удалить, то есть <tex>\mathrm{split }(T, k.x) \to \langle T_1, T_2\rangle</tex>.
# Теперь отделяем от первого дерева элемент <tex>x</tex>, то есть самого левого ребенка дерева <tex> T_2 </tex>.
# Сливаем первое дерево со вторым, то есть <tex>\mathrm{merge }(T_1, T_2) \to T</tex>.

* Реализация №2
# Спускаемся по дереву (как в обычном бинарном дереве поиска по <tex>x</tex>), и ищем удаляемый элемент.
# Найдя элемент, вызываем <tex>\mathrm{merge}</tex> его левого и правого сыновей
# Результат процедуры <tex>\mathrm{merge}</tex> ставим на место удаляемого элемента.

В первой реализации один раз используется <tex>\mathrm{split}</tex>, а во второй реализации разрезание вообще не используется.

== Построение декартова дерева ==
Пусть нам известно из каких пар <tex>(x_i, y_i)</tex> требуется построить декартово дерево, причем также известно, что <tex>x_1 < x_2 < \ldots < x_n</tex>.
=== Алгоритм за <tex>O(n\log n)</tex> ===
Отсортируем все приоритеты по убыванию за <tex> O(n\log n) </tex> и выберем первый из них, пусть это будет <tex>y_k</tex>. Сделаем <tex>(x_k, y_k)</tex> корнем дерева. Проделав то же самое с остальными вершинами получим левого и правого сына <tex>(x_k, y_k)</tex>. В среднем высота Декартова дерева <tex>\log n</tex> (см. далее) и на каждом уровне мы сделали <tex>O(n)</tex> операций. Значит такой алгоритм работает за <tex>O(n\log n)</tex>.

=== Другой алгоритм за <tex>O(n\log n)</tex> ===
Отсортируем парочки <tex>(x_i, y_i)</tex> по убыванию <tex>x_i</tex> и положим их в очередь. Сперва достанем из очереди первые <tex>2</tex> элемента и сольем их в дерево и положим в конец очереди, затем сделаем то же самое со следующими двумя и т.д. Таким образом, мы сольем сначала <tex>n</tex> деревьев размера <tex>1</tex>, затем <tex>\dfrac{n}{2}</tex> деревьев размера <tex>2</tex> и так далее. При этом на уменьшение размера очереди в два раза мы будем тратить суммарно <tex>O(n)</tex> время на слияния, а всего таких уменьшений будет <tex>\log n</tex>. Значит полное время работы алгоритма будет <tex>O(n\log n)</tex>.

=== Алгоритм за <tex>O(n)</tex> ===
Будем строить дерево слева направо, то есть начиная с <tex>(x_1, y_1)</tex> по <tex>(x_n, y_n)</tex>, при этом помнить последний добавленный элемент <tex>(x_k, y_k)</tex>. Он будет самым правым, так как у него будет максимальный ключ, а по ключам декартово дерево представляет собой [[Дерево поиска, наивная реализация|двоичное дерево поиска]]. При добавлении <tex>(x_{k+1}, y_{k+1})</tex>, пытаемся сделать его правым сыном <tex>(x_k, y_k)</tex>, это следует сделать если <tex>y_k > y_{k+1}</tex>, иначе делаем шаг к предку последнего элемента и смотрим его значение <tex>y</tex>. Поднимаемся до тех пор, пока приоритет в рассматриваемом элементе меньше приоритета в добавляемом, после чего делаем <tex>(x_{k+1}, y_{k+1})</tex> его правым сыном, а предыдущего правого сына делаем левым сыном <tex>(x_{k+1}, y_{k+1})</tex>.

Заметим, что каждую вершину мы посетим максимум дважды: при непосредственном добавлении и, поднимаясь вверх (ведь после этого вершина будет лежать в чьем-то левом поддереве, а мы поднимаемся только по правому). Из этого следует, что построение происходит за <tex>O(n)</tex>.

== Случайные приоритеты ==
Мы уже выяснили, что сложность операций с декартовым деревом линейно зависит от его высоты. В действительности высота декартова дерева может быть линейной относительно его размеров. Например, высота декартова дерева, построенного по набору ключей <tex>(1, 1), \ldots, (n, n)</tex>, будет равна <tex>n</tex>. Во избежание таких случаев, полезным оказывается выбирать приоритеты в ключах случайно.

== Высота в декартовом дереве с случайными приоритетами ==
{{Теорема
|statement = В декартовом дереве из <tex>n</tex> узлов, приоритеты <tex>y</tex> которого являются [[Дискретная случайная величина|случайными величинами]] c равномерным распределением, средняя глубина вершины <tex>O(\log n)</tex>.
|proof=

Будем считать, что все выбранные приоритеты <tex>y</tex> попарно различны.

Для начала введем несколько обозначений:
* <tex>x_k</tex> {{---}} вершина с <tex>k</tex>-ым по величине ключом;
* индикаторная величина <tex>A_{i, j} = \left\{\begin{array}{lllc} 1 ,&& x_i\ \text{is ancestor of} \ x_j\\
0 ,&& \text{otherwise}\\
\end{array}\right.
</tex>
* <tex>d(v)</tex> {{---}} глубина вершины <tex>v</tex>;

В силу обозначений глубину вершины можно записать как количество предков:
:<tex>d(x_k) = \sum\limits_{i = 1}^{n} A_{i,k} </tex>.

Теперь можно выразить [[Математическое ожидание случайной величины|математическое ожидание]] глубины конкретной вершины:
:<tex>E(d(x_k)) = \sum\limits_{i = 1}^{n} Pr[A_{i,k} = 1] </tex> {{---}} здесь мы использовали линейность математического ожидания, и то что <tex>E(X) = Pr[X = 1]</tex> для индикаторной величины <tex>X</tex> (<tex>Pr[A]</tex> {{---}} вероятность события <tex>A</tex>).
Для подсчёта средней глубины вершин нам нужно сосчитать вероятность того, что вершина <tex>x_i</tex> является предком вершины <tex>x_k</tex>, то есть <tex>Pr[A_{i,k} = 1]</tex>.

Введем новое обозначение:
* <tex>X_{i, k}</tex> {{---}} множество ключей <tex>\{x_i, \ldots, x_k\}</tex> или <tex>\{x_k, \ldots, x_i\}</tex>, в зависимости от <tex>i < k</tex> или <tex>i > k</tex>. <tex>X_{i, k}</tex> и <tex>X_{k, i}</tex> обозначают одно и тоже, их мощность равна <tex>|k - i| + 1</tex>.

{{Лемма
|statement=Для любых <tex>i \ne k</tex> , <tex>x_i</tex> является предком <tex>x_k</tex> тогда и только тогда, когда <tex>x_i</tex> имеет наибольший приоритет среди <tex>X_{i, k}</tex>.
|proof=Если <tex>x_i</tex> является корнем, то оно является предком <tex>x_k</tex> и по определению имеет максимальный приоритет среди всех вершин, следовательно, и среди <tex>X_{i, k}</tex>.

С другой стороны, если <tex>x_k</tex> {{---}} корень, то <tex>x_i</tex> {{---}} не предок <tex>x_k</tex>, и <tex>x_k</tex> имеет максимальный приоритет в декартовом дереве; следовательно, <tex>x_i</tex> не имеет наибольший приоритет среди <tex>X_{i, k}</tex>.

Теперь предположим, что какая-то другая вершина <tex>x_m</tex> {{---}} корень. Тогда, если <tex>x_i</tex> и <tex>x_k</tex> лежат в разных поддеревьях, то <tex>i < m < k</tex> или <tex>i > m > k</tex>, следовательно, <tex>x_m</tex> содержится в <tex>X_{i , k}</tex>. В этом случае <tex>x_i</tex> {{---}} не предок <tex>x_k</tex>, и наибольший приоритет среди <tex>X_{i, k}</tex> имеет вершина с номером <tex>m</tex>.

Наконец, если <tex>x_i</tex> и <tex>x_k</tex> лежат в одном поддереве, то доказательство применяется по индукции: пустое декартово дерево есть тривиальная база, а рассматриваемое поддерево является меньшим декартовым деревом.
}}

Так как распределение приоритетов равномерное, каждая вершина среди <tex>X_{i, k}</tex> может иметь максимальный приоритет, мы немедленно приходим к следующему равенству:
: <tex>Pr[A_{i, j} = 1] = \left\{\begin{array}{lllc} \dfrac{1}{k - i + 1} ,&& k \ > \ i\\
0 ,&& k\ =\ i\\
\dfrac{1}{i - k + 1} ,&& k \ < \ i\\
\end{array}\right.
</tex>

Подставив последнее в нашу формулу с математическим ожиданием получим:
:<tex>E(d(x_k)) = \sum\limits_{i = 1}^{n} Pr[A_{i,k} = 1] = \sum\limits_{i = 1}^{k - 1}\dfrac{1}{k - i + 1} + \sum\limits_{i = k + 1}^{n}\dfrac{1}{i - k + 1} \leqslant </tex>
<tex>\leqslant \ln(k) + \ln(n - k)+2</tex> (здесь мы использовали неравенство <tex>\sum\limits_{i = 1}^{n} \dfrac{1}{i} \leqslant \ln(n) + 1</tex>)
: <tex>\log(n)</tex> отличается от <tex>\ln(n)</tex> в константу раз, поэтому <tex>\log(n) = O(\ln(n))</tex>.

В итоге мы получили что <tex>E(d(x_k)) = O(\log(n))</tex>.
}}

Таким образом, среднее время работы операций <tex>\mathrm{split}</tex> и <tex>\mathrm{merge}</tex> будет <tex>O(\log(n))</tex>.

== См. также ==
* [[Декартово дерево по неявному ключу]]

== Источники информации ==
*[http://ru.wikipedia.org/wiki/Декартово_дерево Декартово дерево — Википедия]
*[http://rain.ifmo.ru/cat/data/theory/trees/treaps-2006/article.pdf Treaps и T-Treaps]

[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Деревья поиска]]

Двоичная куча

2016-10-15T03:45:39Z

37.57.17.214: /* Определение */ лишняя запятая

==Определение==
{{Определение
|definition=
'''Двоичная куча''' или '''пирамида''' (англ. ''Binary heap'') — такое двоичное [[Дерево, эквивалентные определения|подвешенное дерево]], для которого выполнены следующие три условия:

* Значение в любой вершине не меньше (если куча для максимума), чем значения её потомков.
* На <tex>i</tex>-ом слое <tex>2^i</tex> вершин, кроме последнего. Слои нумеруются с нуля.
* Последний слой заполнен слева направо (как показано на рисунке)
}}
[[Файл:Min_heap.png‎|thumb|325px|Пример кучи для минимума]]
[[Файл:Min_heap_array.png‎|thumb|325px|Хранение кучи в массиве, красная стрелка {{---}} левый сын, зеленая {{---}} правый]]
Удобнее всего двоичную кучу хранить в виде массива <tex>a[0..n-1]</tex>, у которого нулевой элемент, <tex>a[0]</tex> — элемент в корне, а потомками элемента <tex>a[i]</tex> являются <tex>a[2i+1]</tex> и <tex>a[2i+2]</tex>. Высота кучи определяется как высота двоичного дерева. То есть она равна количеству рёбер в самом длинном простом пути, соединяющем корень кучи с одним из её листьев. Высота кучи есть <tex>O(\log{n})</tex>, где <tex>n</tex> — количество узлов дерева.

Чаще всего используют кучи для минимума (когда предок не больше детей) и для максимума (когда предок не меньше детей).

Двоичные кучи используют, например, для того, чтобы извлекать минимум из набора чисел за <tex>O(\log{n})</tex>. Они являются частным случаем приоритетных очередей.

==Базовые процедуры==

===Восстановление свойств кучи===

Если в куче изменяется один из элементов, то она может перестать удовлетворять свойству упорядоченности. Для восстановления этого свойства служат процедуры <tex> \mathrm {siftDown} </tex> (просеивание вниз)
и <tex> \mathrm {siftUp} </tex> (просеивание вверх).
Если значение измененного элемента увеличивается, то свойства кучи восстанавливаются функцией <tex> \mathrm {siftDown} </tex>.
Работа процедуры: если <tex>i</tex>-й элемент меньше, чем его сыновья, всё поддерево уже является кучей, и делать ничего не надо. В противном случае меняем местами <tex>i</tex>-й элемент с наименьшим из его сыновей, после чего выполняем <tex> \mathrm {siftDown} </tex> для этого сына.
Процедура выполняется за время <tex>O(\log{n})</tex>.
====siftDown====
<code style="display:inline-block">
'''function''' siftDown(i : '''int'''):
'''while''' 2 * i + 1 <tex><</tex> a.heapSize // heapSize {{---}} количество элементов в куче
left = 2 * i + 1 // left {{---}} левый сын
right = 2 * i + 2 // right {{---}} правый сын
j = left
'''if''' right <tex><</tex> a.heapSize '''and''' a[right] <tex><</tex> a[left]
j = right
'''if''' a[i] <tex>\leqslant</tex> a[j]
'''break'''
swap(a[i], a[j])
i = j
</code>

====siftUp====
Если значение измененного элемента уменьшается, то свойства кучи восстанавливаются функцией <tex> \mathrm {siftUp} </tex>.

Работа процедуры: если элемент больше своего отца, условие 1 соблюдено для всего дерева, и больше ничего делать не нужно. Иначе, мы меняем местами его с отцом. После чего выполняем <tex> \mathrm {siftUp} </tex>
для этого отца. Иными словами, слишком маленький элемент всплывает наверх.
Процедура выполняется за время <tex>O(\log{n})</tex>.
<code style="display:inline-block">
'''function''' siftUp(i : '''int'''):
'''while''' a[i] <tex><</tex> a[(i - 1) / 2] // i <tex>==</tex> 0 {{---}} мы в корне
swap(a[i], a[(i - 1) / 2])
i = (i - 1) / 2
</code>

===Извлечение минимального элемента===

Выполняет извлечение минимального элемента из кучи за время <tex>O(\log{n})</tex>.
Извлечение выполняется в четыре этапа:
# Значение корневого элемента (он и является минимальным) сохраняется для последующего возврата.
# Последний элемент копируется в корень, после чего удаляется из кучи.
# Вызывается <math> \mathrm {siftDown} </math> для корня.
# Сохранённый элемент возвращается.

<code style="display:inline-block">
'''int''' extractMin():
'''int''' min = a[0]
a[0] = a[a.heapSize - 1]
a.heapSize = a.heapSize - 1
siftDown(0)
'''return''' min
</code>

===Добавление нового элемента===

Выполняет добавление элемента в кучу за время <tex>O(\log{n})</tex>.
Добавление произвольного элемента в конец кучи, и восстановление свойства упорядоченности с помощью процедуры <math> \mathrm {siftUp} </math>.

<code style="display:inline-block">
'''function''' insert(key : '''int'''):
a.heapSize = a.heapSize + 1
a[a.heapSize - 1] = key
siftUp(a.heapSize - 1)
</code>

===Построение кучи за O(n) ===
{{Определение | definition =
'''<tex>D</tex>-куча''' {{---}} это куча, в которой у каждого элемента, кроме, возможно, элементов на последнем уровне, ровно <tex>d</tex> потомков.
}}

Дан массив <tex>a[0.. n - 1].</tex> Требуется построить <tex>d</tex>-кучу с минимумом в корне. Наиболее очевидный способ построить такую кучу из неупорядоченного массива {{---}} сделать нулевой элемент массива корнем, а дальше по очереди добавить все его элементы в конец кучи и запускать от каждого добавленного элемента <math>\mathrm {siftUp}</math>. Временная оценка такого алгоритма <tex> O(n\log{n})</tex>. Однако можно построить кучу еще быстрее — за <tex> O(n) </tex>.

Представим, что в массиве хранится дерево (<tex>a[0] - </tex> корень, а потомками элемента <tex>a[i]</tex> являются <tex>a[di+1]...a[di+d]</tex>). Сделаем <tex> \mathrm {siftDown} </tex> для вершин, имеющих хотя бы одного потомка: от <tex dpi=140>\dfrac{n}{d}</tex> до <tex>0</tex>,{{---}} так как поддеревья, состоящие из одной вершины без потомков, уже упорядочены.
{{Лемма
|statement= На выходе получим искомую кучу.
|proof= При вызове <tex> \mathrm {siftDown} </tex> для вершины, ее поддеревья являются кучами. После выполнения <tex> \mathrm {siftDown} </tex> эта вершина с ее поддеревьями будут также являться кучей. Значит, после выполнения всех <tex> \mathrm {siftDown} </tex> получится куча.
}}
{{Лемма
|statement= Время работы этого алгоритма <tex> O(n) </tex>.
|proof= Число вершин на высоте <tex>h</tex> в куче из <tex>n</tex> элементов не превосходит <tex dpi = "160"> \left \lceil \frac{n}{d^h} \right \rceil </tex>. Высота кучи не превосходит <tex> \log_{d}n </tex>. Обозначим за <tex> H </tex> высоту дерева, тогда время построения не превосходит

<tex dpi = "160"> \sum_{h = 1}^H \limits\frac{n}{d^h} \cdot d </tex> <tex dpi = "150"> \cdot h </tex> <tex dpi = "160"> = n \cdot d \cdot {\sum_{h = 1}^H \limits}\frac{h}{d^h}. </tex>

Докажем вспомогательную лемму о сумме ряда.

{{Лемма
|statement= <tex dpi = "160"> {\sum_{h = 1}^\infty \limits}\frac{h}{d^h} = \frac{d}{(d - 1)^2} . </tex>
|proof=
Обозначим за <tex>s</tex> сумму ряда. Заметим, что
<tex dpi = "160"> \frac{n}{d^n} = \frac{1}{d} \cdot \frac{n - 1}{d ^{n - 1}} + \frac{1}{d^n}. </tex>

<tex dpi = "160">{\sum_{n = 1}^\infty \limits}\frac{1}{d^n}</tex> {{---}} это сумма бесконечной убывающей геометрической прогрессии, и она равна <tex dpi = "160">
\frac{\frac{1}{d}}{1 - \frac{1}{d}} = \frac{1}{d - 1}. </tex>

Получаем <tex>s</tex> <tex dpi = "160" >=\frac{1}{d}</tex> <tex>\cdot s +</tex> <tex dpi = "160" > \frac{1}{d - 1}. </tex> Откуда <tex>s</tex> <tex dpi = "160"> = \frac{d}{(d - 1)^2}. </tex>
}}

Подставляя в нашу формулу результат леммы, получаем <tex >n</tex> <tex dpi = "160">\cdot (\frac {d}{d - 1})^2 </tex> <tex> \leqslant 4 \cdot n </tex> <tex>=O(n).</tex>
}}

Псевдокод алгоритма:
<code style="display:inline-block">
'''function''' heapify():
'''for''' i = a.heapSize / 2 '''downto''' 0
siftDown(i)
</code>

===Слияние двух куч===
Даны две кучи <tex>a</tex> и <tex>b</tex>, размерами <tex>n</tex> и <tex>m</tex>, требуется объединить эти две кучи.
====Наивная реализация====
Поочередно добавим все элементы из <tex>b</tex> в <tex>a</tex>. Время работы {{---}} <tex>O(m \log(n+m))</tex>.
<code style="display:inline-block">
'''function''' merge(a, b : '''Heap'''):
'''while''' b.heapSize <tex>\neq</tex> 0
a.insert(b.extractMin())
</code>
====Реализация с помощью построения кучи====
Добавим все элементы кучи <tex>b</tex> в конец массива <tex>a</tex>, после чего вызовем функцию построения кучи. Процедура выполняется за время <tex>O(n + m)</tex>.

<code style="display:inline-block">
'''function''' merge(a, b : '''Heap'''):
'''for''' i = 0 '''to''' b.heapSize - 1
a.heapSize = a.heapSize + 1
a[a.heapSize - 1] = b[i]
a.heapify()
</code>

===Поиск k-ого элемента===
Требуется найти <tex>k</tex>-ый по величине элемент в куче.

# Создаем новую кучу, в которой будем хранить пару <tex>\langle \mathtt{value}, \mathtt{index} \rangle</tex>, где <tex>\mathtt{value}</tex> {{---}} значение элемента, а <tex>\mathtt{index}</tex> {{---}} индекс элемента в основном массиве, и добавляем в нее корень кучи.
# Возьмем корень новой кучи и добавим её детей из основной кучи, после чего удалим корень. Проделаем этот шаг <tex>k - 1</tex> раз.
# В корне новой кучи будет находиться ответ.

Время работы алгоритма {{---}} <tex>O(k \log k)</tex>.

При <tex>n \lessapprox k \log k </tex> выгоднее запускать [[поиск k-ой порядковой статистики]].
[[Файл:Min_heap_kth.png‎|thumb|center|650px|Пример при <tex>k = 5</tex>, красные {{---}} уже удаленные из кучи элементы, зеленые находятся в куче, а голубые {{---}} еще не рассмотрены.]]

== См. также ==
* [[Биномиальная куча]]
* [[Фибоначчиева куча]]
* [[Левосторонняя куча]]

== Источники информации ==
* [[wikipedia:ru:Двоичная куча|Википедия {{---}} Двоичная куча]]
* [[wikipedia:ru:Очередь с приоритетом|Википедия {{---}} Очередь с приоритетом]]
* [[wikipedia:en:Binary heap|Wikipedia {{---}} Binary heap]]
* [[wikipedia:en:Priority queue|Wikipedia {{---}} Priority queue]]

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Приоритетные очереди]]
[[Категория: Структуры данных]]

Персистентные структуры данных

2016-10-15T01:03:00Z

37.57.17.214: /* Получение полностью персистентных структур данных */ опечатка

{{Определение
|definition= '''Персистенные структуры данных''' (англ. ''persistent data structure'') — это структуры данных, которые при внесении в них каких-то изменений сохраняют все свои предыдущие состояния и доступ к этим состояния.}}

==Уровни персистентности==
Есть несколько уровней персистентности:
*частичная (англ. ''partial''),
*полная (англ. ''full''),
*конфлюэнтная (англ. ''confluent''),
*фунциональная (англ. ''functional'').

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

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

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

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

==Способы преобразования структур данных в персистентные==
Есть несколько способов сделать любую структуру персистентной:
*полное копирование (англ. ''full copy'') когда при любой операции изменения полностью копируется структура данных и в получившуюся новую копию вносятся изменения,
* копирование пути (англ. ''path copying''),

*метод «толстых» узлов (англ. ''fat node'').
Рассмотрим для начала частичную персистентность. Для наглядности занумеруем разные версии структур данных. История изменений структуры данных линейна, в любой момент времени можно обратиться к любой версии структуры данных, но поменять возможно только последнюю версию (на рисунке она выделена синим цветом).

[[Файл:Список версий.png]]

Сформулируем, что такое структура данных. В нашем понимании структурой данных будет называться набор узлов, в которых хранятся какие-то данные, и эти узлы связаны ссылками. Пример структуры данных — [[Дерево поиска, наивная реализация|дерево]]. Рассмотрим, как методом копирования пути превратить дерево в персистентное.

===Метод копирование пути===
Пусть есть [[АВЛ-дерево |сбалансированное дерево поиска]]. Все операции в нем делаются за <tex>O(h)</tex>, где <tex>h</tex> — высота дерева, а высота дерева <tex>O</tex> <tex>(\log n)</tex>, где <tex>n</tex> — количество вершин. Пусть необходимо сделать какое-то обновление в этом сбалансированном дереве, например, добавить очередной элемент, но при этом нужно не потерять старое дерево. Возьмем узел, в который нужно добавить нового ребенка. Вместо того чтобы добавлять нового ребенка, скопируем этот узел, к копии добавим нового ребенка, также скопируем все узлы вплоть до корня, из которых достижим первый скопированный узел вместе со всеми указателями. Все вершины, из которых измененный узел не достижим, мы не трогаем. Количество новых узлов всегда будет порядка логарифма. В результате имеем доступ к обоим версиям дерева.

[[Файл:Копирование пути.png]]

Так как рассматривается сбалансированное дерево поиска, то поднимая вершину вверх при балансировке, нужно делать копии всех вершин, участвующих во вращениях, у которых изменились ссылки на детей. Таких всегда не более трех, поэтому ассимптотика <tex>O</tex> <tex>( \log n)</tex> не пострадает. Когда балансировка закончится, нужно дойти вверх до корня, делая копии вершин на пути.

Этот метод хорошо работает на [[Стек|стеке]], двоичных ([[Декартово дерево |декартовых]], [[Красно- черное дерево | красно-черных]]) деревьях. Но в случае преобразования [[Очередь| очереди]] в персистентную операция добавления будет очень дорогой, так как элемент добавляется в хвост очереди, который достижим из всех остальных элементов. Также не выгодно применять этот метод и в случае, когда в структуре данных имеются ссылки на родителя.

==== Реализация на основе дерева отрезков ====

На основе дерева отрезков можно построить полностью персистентную структуру данных.

Для реализации персистентного дерева отрезков удобно несколько изменить структуру дерева. Для этого будем использовать явные указатели <tex>L</tex> и <tex>R</tex> для дочерних элементов. Кроме того, заведем массив <tex>roots[]</tex>, в котором <tex>roots[i]</tex> указывает на корень дерева отрезков версии <tex>i</tex>

Для построения персистентного дерева отрезков из <tex>n</tex> элементов необходимо применить <tex>n</tex> раз операцию добавления элемента к последней версии дерева. Для того, чтобы добавить новый элемент к <tex>k</tex>-ой версии дерева, необходимо проверить, является ли оно полным бинарным. Если да, то создадим новый корень, левым сыном сделаем <tex>roots[k]</tex>. Иначе, сделаем копию корня исходной версии. Добавим корень в конец массива корней. Далее, спускаясь от корня к первому свободному листу, будем создавать несуществующие узлы и клонировать существующие. После этого в новой ветке необходимо обновить значение функции и некоторые указатели дочерних элементов. Поэтому, возвращаясь из рекурсии, будем менять один указатель на только что созданную или скопированную вершину, а также обновим значение функции, для которой строилось дерево. После этой операции в дереве появится новая версия, содержащая вставленный элемент.

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

[[Файл:persist.png]]

Здесь изображено персистентное дерево отрезков с операцией минимум, в котором изначально было 3 вершины. Сперва к нему была добавлена вершина со значением 2, а потом изменена вершина со значением 7. Цвет ребер и вершин соответствует времени их появления. Синий цвет элементов означает, что они были изначально, зеленый - что они появились после добавления, а оранжевый - что они появились после изменения элемента.

===Метод «толстых» узлов===
Пусть в структуре данных есть узел, в котором нужно сделать изменения (например, на рисунке ниже в первой версии структуры данных в узле <tex>X</tex> есть поле <tex>a=3</tex>, а во второй версии это поле должно быть равно <tex>4</tex>), но при этом нужно сохранить доступ к старой версии узла <tex>X</tex> и не нужно экономить время. В таком случае можно хранить обе версии узла <tex>X</tex> в большом комбинированном узле.

[[Файл:Метод толстых узлов.png|600px|центр]] ‎

В примере выше в этом «толстом» узле будет храниться первая версия <tex>V_1</tex>, у которой <tex>a=3</tex> и вторая версия <tex>V_2</tex>, у которой <tex>a=4</tex>. Если далее последуют еще какие-то изменения (например, поле <tex>b</tex> узла <tex>X</tex> станет равно <tex>5</tex>) добавим в толстый узел <tex>X</tex> еще одну версию — <tex>V_3</tex>.

[[Файл:Список версий1.png|500px|центр]]

Пусть нужно сделать запрос ко второй версии структуры данных (на рисунке выше это запрос <tex>X.a-?)</tex>. Чтобы сделать этот запрос, нужно зайти в узел <tex>X</tex> и найти в списке версий максимальную версию, которая меньше или равна версии запроса (в примере на рисунке это версия <tex>2</tex>), и в этой версии узла найти значение поля <tex>a</tex> (в примере <tex>a=4</tex>).
Чтобы быстро найти нужную версию в списке версий, хранящихся в «толстом» узле, нужно хранить их в виде дерева. Тогда мы сможем за логарифм найти нужную версию и к ней обратиться. Значит, все операции, которые будут производиться на этой структуре данных, будут домножаться на логарифм от числа версий.

Структура толстого узла может быть и другой: к каждой вершине можно хранить лог ее изменений, в который записывается версия, в которой произошло изменение, а также само изменение. Такая структура толстого узла рассмотрена ниже, в разделах об общих методах получения частично и полностью персистентных структур данных. Лог может быть организован по-разному. Обычно делают отдельный лог для каждого поля вершины. Когда что-то меняется в вершине, то в лог соответствующего поля записывается это изменение и номер версии, с которой данное изменение произошло. Когда нужно обратиться к старой версии, то двоичным поиском ищут в логе последнее изменение до этой версии и находят нужное значение.
Метод ''fat node'' дает замедление <tex> \log t</tex>, где <tex>t</tex> — число изменений структуры данных; памяти требуется <tex>n+t</tex>, где <tex>n</tex> — число вершин в структуре данных.

==Преобразование списка в персистентный за O(1)==
Если скомбинировать методы ''path copiyng'' и ''fat node'', то получим универсальный метод, который позволит преобразовывать структуры данных в частично персистентные без дополнительного логарифма памяти и времени.
Пусть мы имеем [[Список| двусвязный список]] и хотим внести в него какое-то изменение, например, добавить узел <tex>Z</tex> между узлами <tex>X</tex> и <tex>Y</tex>, то есть при переходе из версии <tex>1</tex> в версию <tex>2</tex> добавим в двусвязный список узел <tex>Z</tex>.
Применим метод «толстых» узлов. Для этого в узлы <tex>X</tex> и <tex>Y</tex> добавим вторую версию и изменим ссылку, следующую из <tex>X</tex>, и предыдущую перед <tex>Y</tex>, как показано на рисунке.
Этот алгоритм работает следующим образом. Например, текущая первая версия. Идем по списку слева направо от первого узла к узлу <tex>X</tex>, а затем нужно перейти к следующему узлу. В «толстом» узле <tex>X</tex> выбираем нужную (первую) версию и далее следуем по ссылкам.

[[Файл:Список1.png|600px]]

Пусть мы хотим добавить еще один элемент между узлами <tex>X</tex> и <tex>Y</tex>, но проблема в том, что у <tex>X</tex> и <tex>Y</tex> уже есть вторая версия, если будем добавлять еще новые версии, то получим дополнительный логарифм времени при обращении к узлу, как в рассмотренном выше методе "толстых" узлов. Поэтому более двух версий добавлять не будем. Используем метод копирования пути. Скопируем узлы <tex>X</tex> и <tex>Y</tex>, начиная с их третьей версии, и свяжем новые узлы с исходным списком. Для этого добавим вторые версии предыдущему перед <tex>X</tex> и последующему после <tex>Y</tex> узлам и свяжем эти узлы соответствующими ссылками. Так все версии остаются доступными.

[[Файл:Список2.png|700px]]

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

[[Файл:Аморанализ.png|700px]]

Оценим амортизационное время работы такого алгоритма. У нас частично персистентная структура данных, изменять можно только ее последнюю версию. Примем функцию потенциала <tex>\Phi</tex> равной числу полных узлов в последней версии.
# Амортизационная стоимость операции добавления:
#* <tex>a_{empty} = t + \Delta\Phi = O(1) + 2 = O(1), </tex> так как если добавление узла не задевает полных узлов, то узел добавляется за константное время, а количество полных узлов увеличивается на <tex> 2 </tex>.
#* <tex>a_{fat} = t + \Delta\Phi = O(1) + k - k + 2 = O(1), </tex> так как если узел влечёт изменения полных узлов, то сначала потратится <tex> k </tex> времени на копирование этих полных узлов, и в то же время потенциал уменьшится на <tex> k </tex>, а потом увеличится максимум на <tex> 2 </tex>.
# Для любого <tex>i: \Phi_i = O(n),</tex> так как полных узлов не больше общего количества узлов в списке.

Таким образом, [[Амортизационный анализ#Метод потенциалов|по теореме о методе потенциалов]], амортизационное время работы по добавлению элемента будет <tex>O(1)</tex>.

==Общий метод построения частично персистентных структур данных==
[[Файл:Частичная персистентность.png|мини|справа|500x300px| Пунктирные линии — обратные ссылки, <tex>X</tex> — исходный узел, актуальный до версии <tex>10</tex>, 
<tex>X'</tex> — склонированный узел, актуальный с версии <tex>11</tex>, с пустым списком изменений]]
Применим методы, описанные выше, в общем случае для абстрактной структуры данных.

Пусть есть структура данных, у каждого узла которой количество указателей на этот узел не больше некоторой константы <tex>P</tex>. При клонировании узла важно знать, откуда на этот узел идут указатели, чтобы затем их переставить. Поэтому необходимо в каждом узле хранить обратные ссылки на те узлы, которые ссылаются на клонируемый узел.
Все узлы будут храниться в виде «толстых» узлов, в которых содержится начальная версия этого узла и список внесенных в него изменений (англ. ''change log'') длиной не больше <tex>2P</tex>.

Пусть нужно внести изменение в структуру данных в узел <tex>X</tex>. Если есть место в списке изменений, просто вносим туда изменение: записываем номер версии, с которой начинается это изменение, в какое поле узла вносится изменение и какое именно. Если ''change log'' заполнен, то клонируем узел <tex>X</tex>: берем стартовую версию узла, производим в ней все изменения, записанные в ''change log'', добавляем последнее изменение и делаем версию со свободным списком изменений. Затем пройдем по обратным ссылкам от <tex>X</tex> и в ''change log'' каждого узла, ссылающегося на <tex>X</tex>, добавим изменение указателя начиная с этой версии структуры данных с <tex>X</tex> на <tex>X'</tex>.

Оценим время работы этого алгоритма. Введем функцию потенциала, которая будет равна суммарному размеру всех списков изменений в последней версии. Посмотрим, как меняется суммарный размер списков изменений, когда мы совершаем одно изменение. Если ''change log'' был не полный, то мы просто добавляем туда один элемент, потенциал увеличится на единицу.
Если ''change log'' был полный, то потенциал уменьшается на его размер, так как мы склонировали узел с пустым списком изменений. После этого мы пошли по обратным ссылкам (их было <tex>P</tex> штук) и добавили в <tex>P</tex> узлов по одному значению. Таким образом амортизированное время работы будет <tex>O(1)</tex>.

==Получение полностью персистентных структур данных==
Для полностью персистентных структур данных применить описанный выше метод преобразования не получится, так как история создания версий не линейна и нельзя отсортировать изменения по версиям, как в частично персистентных структурах данных.
Пусть мы храним историю изменения версий в виде дерева. Сделаем[[Обход в глубину, цвета вершин| обход этого дерева в глубину]]. В порядке этого обхода запишем, когда мы входим, а когда выходим из каждой версии. Эта последовательность действий полностью задает дерево, сделаем из нее список. Когда после какой-то версии (на рисунке ниже это версия <tex>6</tex>) добавляется новая версия структуры данных (на рисунке версия <tex>8</tex>), мы вставляем два элемента в список (на рисунке это <tex>+8</tex> и <tex>-8</tex>) после входа, но до выхода из той версии, когда произошло изменение (то есть между
элементами <tex>+6</tex> и <tex>-6</tex>). Первый элемент вносит изменение, а второй будет возвращать обратно значение предыдущей версии. Таким образом, каждая операция разбивается на две: первая делает изменение, а вторая его откатывает.

[[Файл:Полная персистентность.png‎]]

Для реализации описанного в предыдущем пункте метода преобразования структур данных в полностью персистентные нам нужен такой список, который поддерживает операции <tex>\mathrm{insert After(p,q})</tex> (вставить <tex>q</tex> после <tex>p</tex>) и <tex>\mathrm{order(p,q)}</tex> (должен уметь отвечать на запросы вида "<tex>p</tex> лежит в этом списке до <tex>q</tex>"). <tex>\mathrm{order(p,q)}</tex> возвращает <tex>1</tex>, если <tex>p</tex> лежит до <tex>q</tex> и <tex>0</tex> иначе. Это список с поддержкой запроса о порядке [[List order maintenance|''List Order Maintenance'']], который обе эти операции делает за <tex>O(1)</tex>.

В ''change log'' «толстого» узла теперь будем добавлять два события: одно указывает на изменение, произошедшее в соответствующей версии, а другое на его отмену. События будут добавляться в ''change log'' не по номерам версий, а по их порядку в списке версий ''List Order Maintenance''.

Когда есть запрос к какой-то версии, то нужно найти в списке версий такую, после входа в которую, но до выхода из которой лежит версия запроса, а среди таких максимальную. Например, если приходит запрос к версии <tex>6</tex> на рисунке выше, то мы видим, что она в списке версий лежит после входа, но до выхода в версии <tex>1</tex>, <tex>2</tex> и <tex>4</tex>. Необходимо найти наибольшую из них. Список ''List Order Maintenance'' позволяет делать это за <tex>O(1)</tex> с помощью операции <tex>\mathrm{order(p,q)}</tex>. В примере это версия <tex>4</tex>. Так как ''change log'' каждого узла имеет константный размер, то поиск нужной версии в нем происходит за <tex>O(1)</tex>.

В какой-то момент ''change log'' «толстого» узла переполнится. Тогда нужно клонировать этот узел и нижнюю половину изменений перенести в ''change log'' склонированного узла. Первую половину изменений применяем к исходной версии узла и сохраняем в качестве исходной в склонированном узле.

[[Файл:Полностью персистентные сд.png|900x700px]]

Получится два узла: первый отвечает за отрезок версий до операции последнего изменения, а второй {{---}} после нее. Дальнейший порядок действий аналогичен тому, который использовался в общем методе построения частично персистентных структур данных.

Оценим амортизационное время работы этого алгоритма. Введем функцию потенциала, равную числу полных узлов. Когда узел раздваивается, функция потенциала уменьшается на единицу, затем мы переставляем <tex>P</tex> ссылок, потенциал увеличивается на <tex>P</tex>, значит, амортизационное время работы — <tex>O(1)</tex>.

==Использование персистентных структур данных для решения геометрических задач==

Персистентные структуры данных используются при решении геометрических задач. Примером может служить [[Локализация в ППЛГ методом полос (персистентные деревья)|Point location problem]] — задача о местоположении точки. Задачи такого рода решаются в ''offline'' и ''online''. В ''offline''-задачах все запросы даны заранее и можно обрабатывать их одновременно. В ''online''-задачах следующий запрос можно узнать только после того, как найден ответ на предыдущий.

При решении ''offline''-задачи данный планарный граф разбивается на полосы вертикальными прямыми, проходящими через вершины многоугольников. Затем в этих полосах при помощи техники заметающей прямой ''(scane line)'' ищется местоположение точки-запроса. При переходе из одной полосы в другую изменяется [[Дерево поиска, наивная реализация|сбалансированное дерево поиска]]. Если использовать частично персистентную структуру данных, то для каждой полосы будет своя версия дерева и сохранится возможность делать к ней запросы. Тогда ''Point location problem'' может быть решена в ''online''.

== См. также ==
* [[Персистентный стек]]
* [[Персистентная очередь]]
* [[Персистентный дек]]
* [[List order maintance]]

== Источники информации ==
*[https://www.lektorium.tv/lecture/14321/ Дополнительные главы алгоритмов. Лекции Андрея Станкевича]
*[http://logic.pdmi.ras.ru/csclub/node/2734/ Персистентные структуры данных. Лекции Павла Маврина]

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Персистентные структуры данных]]

Задача о рюкзаке

2016-10-08T03:32:22Z

37.57.17.214: /* Задача о суммах подмножеств */ опечатка

'''Задача о рюкзаке'''(''англ. Knapsack problem'') — дано <tex>N</tex> предметов, <tex>n_i</tex> предмет имеет массу <tex> w_i > 0</tex> и стоимость <tex> p_i > 0</tex>. Необходимо выбрать из этих предметов такой набор, чтобы суммарная масса не превосходила заданной величины <tex>W</tex> (вместимость рюкзака), а суммарная стоимость была максимальна.

== Формулировка задачи ==

Дано <tex>N</tex> предметов, <tex>W</tex> - вместимость рюкзака, <tex>w=\{w_{1},w_{2},...,w_{N}\}</tex> — соответствующий ему набор положительных целых весов, <tex>p=\{p_{1},p_{2},...,p_{N}\}</tex> — соответствующий ему набор положительных целых стоимостей. Нужно найти набор бинарных величин <tex>B=\{b_{1},b_{2},...,b_{N}\}</tex>, где <tex>b_{i} = 1 </tex>, если предмет <tex>n_i</tex> включен в набор, <tex> b_{i} = 0 </tex>, если предмет <tex>n_i</tex> не включен, и такой что:

#<tex>b_{1} w_{1}+ ... + b_{N} w_{N} \le W</tex>
#<tex>b_{1} p_{1}+ ... + b_{N} p_{N} </tex> максимальна.

== Варианты решения ==

Задачу о рюкзаке можно решить несколькими способами:

* Перебирать все подмножества набора из N предметов. Сложность такого решения <tex>O({2^{N}})</tex>.

* Методом [[Meet-in-the-middle|Meet-in-the-middle]]. Сложность решения <tex> O({2^{N/2}}\times{N}) </tex>

* Метод динамического программирования. Сложность - <tex>O(N \times W)</tex>.

== Метод динамического программирования ==

Пусть <tex>A(k, s)</tex> есть максимальная стоимости предметов, которые можно уложить в рюкзак вместимости <tex>s</tex>, если можно использовать только первые <tex>k</tex> предметов, то есть <tex>\{n_1,n_2,...,n_k\}</tex>, назовем этот набор допустимых предметов для <tex>A(k,s)</tex>.

<tex>A(k, 0) = 0</tex>

<tex>A(0, s) = 0</tex>

Найдем <tex>A(k, s)</tex>. Возможны 2 варианта:

#Если предмет <tex>k</tex> не попал в рюкзак. Тогда <tex>A(k, s)</tex> равно максимальной стоимости рюкзака с такой же вместимостью и набором допустимых предметов <tex>\{n_1,n_2,...,n_{k-1}\}</tex>, то есть <tex>A(k,s) = A(k-1, s)</tex>
# Если <tex>k</tex> попал в рюкзак. Тогда <tex>A(k, s)</tex> равно максимальной стоимости рюкзака, где вес <tex>s</tex> уменьшаем на вес <tex>k</tex> -ого предмета и набор допустимых предметов <tex>\{n_1,n_2,...,n_{k-1}\}</tex> плюс стоимость <tex>k</tex>, то есть <tex>A(k-1, s-w_k) + p_k</tex>

То есть:
<tex>A(k,s) = max(A(k-1,s), A(k-1,s-w_{k}) + p_{k})</tex>

Стоимость искомого набора равна <tex>A(N,W)</tex>, так как нужно найти максимальную стоимость рюкзака, где все предметы допустимы и вместимость рюкзака <tex>W</tex>.

'''Восстановим набор предметов, входящих в рюкзак'''

Будем определять, входит ли <tex>n_i</tex> предмет в искомый набор. Начинаем с элемента <tex>A(i,w)</tex>, где <tex>i = N</tex>, <tex>w = W</tex>. Для этого сравниваем <tex>A(i,w)</tex> со следующими значениями:

#Максимальная стоимость рюкзака с такой же вместимостью и набором допустимых предметов <tex>\{n_1,n_2,...,n_{i-1}\}</tex>, то есть <tex>A(i-1, w)</tex>
#Максимальная стоимость рюкзака с вместимостью на <tex>w_i</tex> меньше и набором допустимых предметов <tex>\{n_1,n_2,...,n_{i-1}\}</tex> плюс стоимость <tex>p_i</tex>, то есть <tex>A(i-1, w-w_i)+p_i</tex>

Заметим, что при построении <tex>A</tex> мы выбирали максимум из этих значений и записывали в <tex>A(i, w)</tex>. Тогда будем сравнивать <tex>A(i, w)</tex> c <tex>A(i-1, w)</tex>, если равны, тогда <tex>n_i</tex> не входит в искомый набор, иначе входит.

== Реализация ==
Сначала генерируем <tex>A</tex>.

for i = 0..W
A[0][i] = 0;
for i = 0..N
A[i][0] = 0; //Первые элементы приравниваем к 0
for k = 1..N
for s = 1..W //Перебираем для каждого k все вместимости
if s >= w[k] //Если текущий предмет вмещается в рюкзак
A[k][s] = max(A[k-1][s], A[k-1][s-w[k]]+p[k]); //выбираем класть его или нет
else
A[k][s] = A[k-1][s]; //иначе, не кладем

Затем найдем набор <tex>ans</tex> предметов, входящих в рюкзак, рекурсивной функцией:

findAns(k, s)
if A[k][s] == 0
return;
if A[k-1][s] == A[k][s]
findAns(k-1, s);
else
findAns(k-1, s - w[k]);
ans.push(k);

Сложность алгоритма <tex>O(N \times W)</tex>

== Пример ==

<tex>W = 13, N = 5</tex>

<tex>w_{1} = 3, p_{1} = 1 </tex>

<tex>w_{2} = 4, p_{2} = 6 </tex>

<tex>w_{3} = 5, p_{3} = 4 </tex>

<tex>w_{4} = 8, p_{4} = 7 </tex>

<tex>w_{5} = 9, p_{5} = 6 </tex>

[[Файл:Knapsack problem0.png]]

Числа от 0 до 13 в первой строчке обозначают вместимость рюкзака.

В первой строке как только вместимость рюкзака <tex>n \ge 3</tex>, добавляем в рюкзак 1 предмет.

Рассмотрим <tex>k = 3</tex>, при каждом <tex>s \ge 5 (</tex>так как <tex>w_3 = 5)</tex> сравниваем <tex>A[k-1][s]</tex> и <tex>A[k-1][s-w_3]+p_3</tex> и записываем в <tex>A[k][s]</tex> стоимость либо рюкзака без третьего предмета, но с таким же весом, либо с третьим предметом, тогда стоимость равна стоимости третьего предмета плюс стоимость рюкзака с вместимостью на <tex>w_3</tex> меньше.

Максимальная стоимость рюкзака находится в <tex>A(5, 13)</tex>.

'''Восстановление набора предметов, из которых состоит максимально дорогой рюкзак.'''

Начиная с <tex>A(5, 13)</tex> восстанавливаем ответ.

[[Файл:Задача о рюкзаке3.png]]

Таким образом, в набор входит <tex>2</tex> и <tex>4</tex> предмет.

Стоимость рюкзака <tex>= 6 + 7 = 13</tex>

Вес рюкзака <tex>= 4 + 8 = 12</tex>

=Другие задачи семейства=
==Ограниченный рюкзак ==
'''Ограниченный рюкзак''' (англ. ''Bounded Knapsack Problem'') - обобщение классической задачи, когда любой предмет может быть взят некоторое количество раз.

'''Пример:''' Вор грабит склад. Он может унести ограниченный вес, каждый товар на складе содержится в определенном ограниченном количестве. Нужно унести предметов на максимальную сумму.
===Формулировка Задачи===
Каждый предмет может быть выбран ограниченное <tex>b_i</tex> число раз.
Задача выбрать число <tex>x_i</tex> предметов каждого типа так, чтобы

* максимизировать общую стоимость: <tex>\sum_{i=1}^N p_ix_i</tex>;

* выполнялось условие совместности: <tex>\sum_{i=1}^N w_ix_i \le W</tex>;

где <tex> x_i \in (0,1,...,b_i)</tex> для всех <tex> i= 1,2,...,N</tex>.

===Варианты решения===
При небольших <tex>b_i</tex> решается сведением к классической задаче о рюкзаке. В иных случаях:
* Методом ветвей и границ.
* Методом динамического программирования.

===Метод динамического программирования===
Пусть <tex>d(i,c)</tex> максимальная стоимость любого возможного числа предметов типов от 1 до <tex>i</tex>, суммарным весом до <tex>c</tex>.

Заполним <tex>d(0,c)</tex> нулями.

Тогда меняя i от 1 до <tex>N</tex>, рассчитаем на каждом шаге <tex>d(i,c)</tex>, для <tex>c</tex> от 1 до <tex>W</tex>, по рекуррентной формуле:

<tex>d(i,c) = max(d(i - 1, c - lw_i) + lp_i) </tex> по всем целым <tex> l </tex> из промежутка <tex> 0 \le l \le min(b_i,\lfloor c/w_i \rfloor)</tex>.

Если не нужно восстанавливать ответ, то можно использовать одномерный массив <tex>d(c)</tex> вместо двумерного.

После выполнения в <tex> d(N,W) </tex> будет лежать максимальная стоимость предметов, помещающихся в рюкзак.

=== Реализация ===
for i = 0..W // база
d[0][i] = 0;
for i = 1..N
for c = 1..W //Перебираем для каждого i, все вместимости
d[i][c] = d[i - 1][c];
for l = min(b[i], c / w[i]) .. 1 // ищем l для которого выполняется максимум
d[i][c] = max(d[i][c], d[i - 1][c - l * w[i]] + p[i] * l);

Сложность алгоритма <tex>O(NW^2)</tex>.

==Неограниченный рюкзак==
'''Неограниченный рюкзак''' (англ.''Unbounded Knapsack Problem'') - обобщение ограниченного рюкзака, в котором любой предмет может быть выбран любое количество раз.

'''Пример:''' Перекупщик закупается на оптовой базе. Он может увезти ограниченное количество товара, количество товара каждого типа на базе не ограниченно. Нужно увезти товар на максимальную сумму.
===Формулировка Задачи===
Каждый предмет может быть выбран любое число раз.
Задача выбрать количество <tex>x_i</tex> предметов каждого типа так, чтобы

*максимизировать общую стоимость: <tex>\sum_{i=1}^N p_ix_i</tex>;

*выполнялось условие совместности: <tex>\sum_{i=1}^N w_ix_i \le W</tex>;

где <tex> x_i \ge 0 </tex> целое, для всех <tex> i= 1,2,...,N</tex>.

===Варианты решения===
Самые распространенные методы точного решения это:
* Метод ветвей и границ.
* Метод динамического программирования.

===Метод динамического программирования===
Пусть <tex>d(i,c)</tex> максимальная стоимость любого количества вещей типов от 1 до <tex>i</tex>, суммарным весом до <tex>c</tex> включительно.

Заполним <tex>d(0,c)</tex> нулями.

Тогда меняя i от 1 до <tex>N</tex>, рассчитаем на каждом шаге <tex>d(i,c)</tex>, для <tex>c</tex> от 0 до <tex>W</tex>, по рекуррентной формуле:

<tex>
d(i,c) =
\begin{cases}
d(i - 1, c) & for\ c = 0, ..., w_i - 1; \\
max(d(i - 1, c), d(i, c - w_i) + p_i) & for\ c = w_i, ..., W;
\end{cases}
</tex>

После выполнения в <tex> d(N,W) </tex> будет лежать максимальная стоимость предметов, помещающихся в рюкзак.

Если не нужно восстанавливать ответ, то можно использовать одномерный массив <tex>d(c)</tex> вместо двумерного и использовать формулу:

<tex> d(c) = max(d(c), d(c - w_i) + p_i) </tex>;

Сложность алгоритма <tex>O(NW)</tex>.

==Непрерывный рюкзак==
'''Непрерывный рюкзак''' (англ. ''Continuous knapsack problem'') - вариант задачи, в котором возможно брать любою дробную часть от предмета, при этом удельная стоимость сохраняется.

'''Пример:''' Вор грабит мясника. Суммарно он может унести ограниченный вес товаров. Вор может резать товары без ущерба к удельной стоимости. Нужно унести товара на максимальную сумму.
===Формулировка Задачи===
Задача выбрать часть <tex>x_i</tex> каждого предмета так, чтобы

*максимизировать общую стоимость: <tex>\sum_{i=1}^N p_ix_i</tex>;

*выполнялось условие совместности: <tex>\sum_{i=1}^N w_ix_i \le W</tex>;

где <tex> 0 \le x_i \le 1</tex> дробное, для всех <tex> i= 1,2,...,N</tex>.

===Варианты решения===
Возможность брать любую часть от предмета сильно упрощает задачу. Жадный алгоритм дает оптимальное решение в данном случае.

=== Реализация ===
sort(); // сортируем в порядке убывания удельной стоимости.
for i = 1..N // идем по предметам
if W >= w[i] //если помещается - берем
sum += p[i];
W -= w[i];
else
sum += W / w[i] * p[i];// иначе берем сколько можно и выходим
break;

==Задача о суммах подмножеств==
'''Задача о суммах подмножеств''' (англ. ''Subset-sum problem, Value Independent Knapsack Problem'') - задача из семейства, в которой стоимость предмета совпадает с его весом.

'''Пример:''' Машина может увезти определенное количество груза. Нужно увезти как можно больше крупного неделимого мусора за раз.
===Формулировка Задачи===
Нужно выбрать подмножество так, чтобы сумма ближе всего к <tex>W</tex>, но не превысила его. Формально, нужно найти набор бинарных величин <tex>x_i</tex>, так чтобы

*максимизировать общую стоимость: <tex>\sum_{i=1}^N w_ix_i</tex>;

*выполнялось условие совместности: <tex>\sum_{i=1}^N w_ix_i \le W</tex>;

<tex> x_j = 1 </tex> если <tex> j</tex> предмет назначен рюкзаку, иначе <tex> x_{ij} = 0 </tex>, для всех <tex> i= 1,2,...,N</tex>.

===Варианты решения===
Для решения пригодны любые методы применяемые для классической задачи, однако специализированые алгоритмы обычно более оптимальны по параметрам. Используются:
* Метод динамического программирования.
* Гибридный метод на основе динамического программирования и поиска по дереву. В худшем случае, работает за <tex> O(n) </tex>.

===Метод динамического программирования===
Пусть <tex>d(i,c)</tex> максимальная сумма <tex>\le c</tex>, подмножества взятого из <tex> 1, ...,\ i</tex> элементов.

Заполним <tex>d(0,c)</tex> нулями.

Тогда меняя i от 1 до <tex>N</tex>, рассчитаем на каждом шаге <tex>d(i,c)</tex>, для <tex>c</tex> от 0 до <tex>W</tex>, по рекуррентной формуле:

<tex>
d(i,c) =
\begin{cases}
d(i - 1, c) & for\ c = 0, ..., w_i - 1; \\
max(d(i - 1, c), d(i - 1, c - w_i) + w_i) & for\ c = w_i, ..., W;
\end{cases}
</tex>

После выполнения в <tex> d(N,W) </tex> будет лежать максимальная сумма подмножества, не превышающая заданное значение.

Сложность алгоритма <tex>O(NW)</tex>.

==Задача о размене==
'''Задача о размене''' (англ. ''Change-Making problem'') - имеются <tex> N </tex> неисчерпаемых типов предметов с весами <tex>w_i</tex>. Нужно наполнить рюкзак предметами с суммарным весом <tex>W</tex>.

Часто задачу ставят как, дать сдачу наименьшим количеством монет.
===Формулировка Задачи===
Каждый предмет может быть выбран любое число раз.
Задача выбрать количество <tex>x_i</tex> предметов каждого типа так, чтобы

*минимизировать количество взятых предметов: <tex>\sum_{i=1}^N x_i</tex>;

*сумма весов выбранных предметов равнялась вместимости рюкзака: <tex>\sum_{i=1}^N w_ix_i = W</tex>;

Где <tex> x_i \ge 0 </tex> целое, для всех <tex> i= 1,2,...,N</tex>.
===Варианты решения===
Самые распространенные методы точного решения это:
* Метод ветвей и границ.
* Метод динамического программирования.

===Метод динамического программирования===
Пусть <tex>d(i,c)</tex> минимальное число предметов, типов от 1 до <tex>i</tex>, необходимое, чтобы заполнить рюкзак вместимостью <tex>c</tex>.

Пусть <tex>d(0,0) = 0</tex>, а <tex>d(0,c) = \inf</tex> для всех <tex>c > 0</tex>.

Тогда меняя i от 1 до <tex>N</tex>, рассчитаем на каждом шаге <tex>d(i,c)</tex>, для <tex>c</tex> от 0 до <tex>W</tex>, по рекуррентной формуле:

<tex>
d(i,c) =
\begin{cases}
d(i - 1, c) & for\ c = 0, ..., w_i - 1; \\
min(d(i - 1, c), d(i, c - w_i) + 1) & for\ c = w_i, ..., W;
\end{cases}
</tex>

После выполнения в <tex> d(N,W) </tex> будет лежать максимальная стоимость предметов, помещающихся в рюкзак.

Если не нужно восстанавливать ответ, то можно использовать одномерный массив <tex>d(c)</tex> вместо двумерного и использовать формулу:

<tex> d(c) = min(d(c), d(c - w_i) + 1) \qquad for\ c = w_i, ..., W</tex>.

Сложность алгоритма <tex>O(NW)</tex>.

==Задача об упаковке==
'''Задача об упаковке''' (англ. ''Bin Packing Problem'') - имеются <tex> N </tex> рюкзаков вместимости <tex> W </tex> и столько же предметов с весами <tex>w_i</tex>. Нужно распределить все предметы, задействовав минимальное количество рюкзаков.

'''Пример:''' Нужно вывезти из шахты все куски руды, используя наименьшее число вагонеток.
===Формулировка Задачи===
Математически задачу можно представить так:

*минимизировать количество рюкзаков: <tex>\sum_{i=1}^N y_i</tex>;

*так чтобы выполнялось условие на совместность: <tex>\sum_{i=1}^N w_ix_{ij} \le Wy_j \qquad j \in {1, ..., N}</tex>;

<tex> x_{ij} = 1 </tex> если <tex> j</tex> предмет назначен <tex>i </tex> рюкзаку. Иначе <tex> x_{ij} = 0 </tex>.

<tex> y_i = 1 </tex> если <tex> i</tex> рюкзак используется. Иначе <tex> y_i = 0 </tex>.

===Варианты решения===
Применение динамического программирования нецелесообразно. Обычно применяют аппроксимационные алгоритмы, либо используют метод ветвей и границ.

==Мультипликативный рюкзак==
'''Мультипликативный рюкзак''' (англ. ''Multiple Knapsack Problem'') - есть <tex>N</tex> предметов и <tex>M</tex> рюкзаков (<tex>M\le N</tex>). У каждого рюкзака своя вместимость <tex>W_i</tex>. Задача: выбрать <tex>M</tex> не пересекающихся множеств, назначить соответствие рюкзакам так, чтобы суммарная стоимость была максимальна, а вес предметов в каждом рюкзаке не превышал его вместимость.

'''Пример:''' У транспортной компании есть парк машин разной грузоподъемности. Нужно перевезти товара на максимальную сумму с одного склада на другой единовременно.
===Формулировка Задачи===
Максимизировать <tex>\sum_{i=1}^M \sum_{j=1}^{N} p_jx_{ij}</tex>

так, чтобы <tex>\sum_{i=1}^N w_jx_{ij} \le W_i</tex> выполнялось для всех <tex> i= 1,2,...,N</tex>.

<tex>\sum_{j=1}^{M}x_{ij}=1</tex> для всех <tex> i= 1,2,...,N</tex>.

<tex> x_{ij} = 1 </tex> если <tex> j</tex> предмет назначен <tex>i </tex> рюкзаку. Иначе <tex> x_{ij} = 0 </tex>.

===Варианты решения===
Применение динамического программирования, для задач данного типа нецелесообразно. Используются вариации метода ветвей и границ.

==Задача о назначении==
'''Задача о назначении''' (англ. ''Generalized Assignment Problem'') - Наиболее общая задача семейства. Отличается от мультипликативного рюкзака тем, что каждый предмет имеет различные характеристики в зависимости от рюкзака, куда его помещают. Есть <tex>N</tex> предметов и <tex>M</tex> рюкзаков (<tex>M\le N</tex>). У каждого рюкзака своя вместимость <tex>W_i</tex>, у <tex> j </tex> предмета <tex> p_{ij} </tex> стоимость и вес, при помещении его в <tex> i </tex> рюкзак, равны <tex> p_{ij} </tex> и <tex> w_{ij} </tex> соответственно. Задача: выбрать <tex>M</tex> не пересекающихся множеств, назначить соответствие рюкзакам так, чтобы суммарная стоимость была максимальна, а вес предметов в каждом рюкзаке не превышал его вместимость.
Весьма важная задача, так как она моделирует оптимальное распределение различных задач между вычислительными блоками.
===Формулировка Задачи===

Максимизировать стоимость выбранных предметов <tex>\sum_{i=1}^M\sum_{j=1}^N p_{ij} x_{ij}</tex>,

при выполнении условия совместности <tex>\sum_{j=1}^N w_{ij} x_{ij} \le W_i \qquad i=1, \ldots, M</tex>.

<tex> \sum_{i=1}^M x_{ij} \leq 1 \qquad j=1, \ldots, N</tex>.

<tex> x_{ij} \in \{0,1\} \qquad i=1, \ldots, N, \quad j=1, \ldots, N</tex>.

===Варианты решения===
Применение динамического программирования нецелесообразно. Наиболее используем метод ветвей и границ.

= Литература =
*[http://informatics.mccme.ru/moodle/mod/book/view.php?id=815&chapterid=60 Дистанционная подготовка по информатике]
*[http://rosettacode.org/wiki/Knapsack_Problem Код для нескольких задач семейства на всевозможных языках]
*[http://www.diku.dk/users/pisinger/95-1.pdf David Pisinger Knapsack problems. — 1995]
*Silvano Martello, Paolo Toth. Knapsack Problems: Algorithms and Computer Implementations — 1990 г. — ISBN 0-471-92420-2

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Динамическое программирование]]

Задача о рюкзаке

2016-10-08T03:28:58Z

37.57.17.214: Отмена правки 55473 участника 37.57.17.214 (обсуждение)

'''Задача о рюкзаке'''(''англ. Knapsack problem'') — дано <tex>N</tex> предметов, <tex>n_i</tex> предмет имеет массу <tex> w_i > 0</tex> и стоимость <tex> p_i > 0</tex>. Необходимо выбрать из этих предметов такой набор, чтобы суммарная масса не превосходила заданной величины <tex>W</tex> (вместимость рюкзака), а суммарная стоимость была максимальна.

== Формулировка задачи ==

Дано <tex>N</tex> предметов, <tex>W</tex> - вместимость рюкзака, <tex>w=\{w_{1},w_{2},...,w_{N}\}</tex> — соответствующий ему набор положительных целых весов, <tex>p=\{p_{1},p_{2},...,p_{N}\}</tex> — соответствующий ему набор положительных целых стоимостей. Нужно найти набор бинарных величин <tex>B=\{b_{1},b_{2},...,b_{N}\}</tex>, где <tex>b_{i} = 1 </tex>, если предмет <tex>n_i</tex> включен в набор, <tex> b_{i} = 0 </tex>, если предмет <tex>n_i</tex> не включен, и такой что:

#<tex>b_{1} w_{1}+ ... + b_{N} w_{N} \le W</tex>
#<tex>b_{1} p_{1}+ ... + b_{N} p_{N} </tex> максимальна.

== Варианты решения ==

Задачу о рюкзаке можно решить несколькими способами:

* Перебирать все подмножества набора из N предметов. Сложность такого решения <tex>O({2^{N}})</tex>.

* Методом [[Meet-in-the-middle|Meet-in-the-middle]]. Сложность решения <tex> O({2^{N/2}}\times{N}) </tex>

* Метод динамического программирования. Сложность - <tex>O(N \times W)</tex>.

== Метод динамического программирования ==

Пусть <tex>A(k, s)</tex> есть максимальная стоимости предметов, которые можно уложить в рюкзак вместимости <tex>s</tex>, если можно использовать только первые <tex>k</tex> предметов, то есть <tex>\{n_1,n_2,...,n_k\}</tex>, назовем этот набор допустимых предметов для <tex>A(k,s)</tex>.

<tex>A(k, 0) = 0</tex>

<tex>A(0, s) = 0</tex>

Найдем <tex>A(k, s)</tex>. Возможны 2 варианта:

#Если предмет <tex>k</tex> не попал в рюкзак. Тогда <tex>A(k, s)</tex> равно максимальной стоимости рюкзака с такой же вместимостью и набором допустимых предметов <tex>\{n_1,n_2,...,n_{k-1}\}</tex>, то есть <tex>A(k,s) = A(k-1, s)</tex>
# Если <tex>k</tex> попал в рюкзак. Тогда <tex>A(k, s)</tex> равно максимальной стоимости рюкзака, где вес <tex>s</tex> уменьшаем на вес <tex>k</tex> -ого предмета и набор допустимых предметов <tex>\{n_1,n_2,...,n_{k-1}\}</tex> плюс стоимость <tex>k</tex>, то есть <tex>A(k-1, s-w_k) + p_k</tex>

То есть:
<tex>A(k,s) = max(A(k-1,s), A(k-1,s-w_{k}) + p_{k})</tex>

Стоимость искомого набора равна <tex>A(N,W)</tex>, так как нужно найти максимальную стоимость рюкзака, где все предметы допустимы и вместимость рюкзака <tex>W</tex>.

'''Восстановим набор предметов, входящих в рюкзак'''

Будем определять, входит ли <tex>n_i</tex> предмет в искомый набор. Начинаем с элемента <tex>A(i,w)</tex>, где <tex>i = N</tex>, <tex>w = W</tex>. Для этого сравниваем <tex>A(i,w)</tex> со следующими значениями:

#Максимальная стоимость рюкзака с такой же вместимостью и набором допустимых предметов <tex>\{n_1,n_2,...,n_{i-1}\}</tex>, то есть <tex>A(i-1, w)</tex>
#Максимальная стоимость рюкзака с вместимостью на <tex>w_i</tex> меньше и набором допустимых предметов <tex>\{n_1,n_2,...,n_{i-1}\}</tex> плюс стоимость <tex>p_i</tex>, то есть <tex>A(i-1, w-w_i)+p_i</tex>

Заметим, что при построении <tex>A</tex> мы выбирали максимум из этих значений и записывали в <tex>A(i, w)</tex>. Тогда будем сравнивать <tex>A(i, w)</tex> c <tex>A(i-1, w)</tex>, если равны, тогда <tex>n_i</tex> не входит в искомый набор, иначе входит.

== Реализация ==
Сначала генерируем <tex>A</tex>.

for i = 0..W
A[0][i] = 0;
for i = 0..N
A[i][0] = 0; //Первые элементы приравниваем к 0
for k = 1..N
for s = 1..W //Перебираем для каждого k все вместимости
if s >= w[k] //Если текущий предмет вмещается в рюкзак
A[k][s] = max(A[k-1][s], A[k-1][s-w[k]]+p[k]); //выбираем класть его или нет
else
A[k][s] = A[k-1][s]; //иначе, не кладем

Затем найдем набор <tex>ans</tex> предметов, входящих в рюкзак, рекурсивной функцией:

findAns(k, s)
if A[k][s] == 0
return;
if A[k-1][s] == A[k][s]
findAns(k-1, s);
else
findAns(k-1, s - w[k]);
ans.push(k);

Сложность алгоритма <tex>O(N \times W)</tex>

== Пример ==

<tex>W = 13, N = 5</tex>

<tex>w_{1} = 3, p_{1} = 1 </tex>

<tex>w_{2} = 4, p_{2} = 6 </tex>

<tex>w_{3} = 5, p_{3} = 4 </tex>

<tex>w_{4} = 8, p_{4} = 7 </tex>

<tex>w_{5} = 9, p_{5} = 6 </tex>

[[Файл:Knapsack problem0.png]]

Числа от 0 до 13 в первой строчке обозначают вместимость рюкзака.

В первой строке как только вместимость рюкзака <tex>n \ge 3</tex>, добавляем в рюкзак 1 предмет.

Рассмотрим <tex>k = 3</tex>, при каждом <tex>s \ge 5 (</tex>так как <tex>w_3 = 5)</tex> сравниваем <tex>A[k-1][s]</tex> и <tex>A[k-1][s-w_3]+p_3</tex> и записываем в <tex>A[k][s]</tex> стоимость либо рюкзака без третьего предмета, но с таким же весом, либо с третьим предметом, тогда стоимость равна стоимости третьего предмета плюс стоимость рюкзака с вместимостью на <tex>w_3</tex> меньше.

Максимальная стоимость рюкзака находится в <tex>A(5, 13)</tex>.

'''Восстановление набора предметов, из которых состоит максимально дорогой рюкзак.'''

Начиная с <tex>A(5, 13)</tex> восстанавливаем ответ.

[[Файл:Задача о рюкзаке3.png]]

Таким образом, в набор входит <tex>2</tex> и <tex>4</tex> предмет.

Стоимость рюкзака <tex>= 6 + 7 = 13</tex>

Вес рюкзака <tex>= 4 + 8 = 12</tex>

=Другие задачи семейства=
==Ограниченный рюкзак ==
'''Ограниченный рюкзак''' (англ. ''Bounded Knapsack Problem'') - обобщение классической задачи, когда любой предмет может быть взят некоторое количество раз.

'''Пример:''' Вор грабит склад. Он может унести ограниченный вес, каждый товар на складе содержится в определенном ограниченном количестве. Нужно унести предметов на максимальную сумму.
===Формулировка Задачи===
Каждый предмет может быть выбран ограниченное <tex>b_i</tex> число раз.
Задача выбрать число <tex>x_i</tex> предметов каждого типа так, чтобы

* максимизировать общую стоимость: <tex>\sum_{i=1}^N p_ix_i</tex>;

* выполнялось условие совместности: <tex>\sum_{i=1}^N w_ix_i \le W</tex>;

где <tex> x_i \in (0,1,...,b_i)</tex> для всех <tex> i= 1,2,...,N</tex>.

===Варианты решения===
При небольших <tex>b_i</tex> решается сведением к классической задаче о рюкзаке. В иных случаях:
* Методом ветвей и границ.
* Методом динамического программирования.

===Метод динамического программирования===
Пусть <tex>d(i,c)</tex> максимальная стоимость любого возможного числа предметов типов от 1 до <tex>i</tex>, суммарным весом до <tex>c</tex>.

Заполним <tex>d(0,c)</tex> нулями.

Тогда меняя i от 1 до <tex>N</tex>, рассчитаем на каждом шаге <tex>d(i,c)</tex>, для <tex>c</tex> от 1 до <tex>W</tex>, по рекуррентной формуле:

<tex>d(i,c) = max(d(i - 1, c - lw_i) + lp_i) </tex> по всем целым <tex> l </tex> из промежутка <tex> 0 \le l \le min(b_i,\lfloor c/w_i \rfloor)</tex>.

Если не нужно восстанавливать ответ, то можно использовать одномерный массив <tex>d(c)</tex> вместо двумерного.

После выполнения в <tex> d(N,W) </tex> будет лежать максимальная стоимость предметов, помещающихся в рюкзак.

=== Реализация ===
for i = 0..W // база
d[0][i] = 0;
for i = 1..N
for c = 1..W //Перебираем для каждого i, все вместимости
d[i][c] = d[i - 1][c];
for l = min(b[i], c / w[i]) .. 1 // ищем l для которого выполняется максимум
d[i][c] = max(d[i][c], d[i - 1][c - l * w[i]] + p[i] * l);

Сложность алгоритма <tex>O(NW^2)</tex>.

==Неограниченный рюкзак==
'''Неограниченный рюкзак''' (англ.''Unbounded Knapsack Problem'') - обобщение ограниченного рюкзака, в котором любой предмет может быть выбран любое количество раз.

'''Пример:''' Перекупщик закупается на оптовой базе. Он может увезти ограниченное количество товара, количество товара каждого типа на базе не ограниченно. Нужно увезти товар на максимальную сумму.
===Формулировка Задачи===
Каждый предмет может быть выбран любое число раз.
Задача выбрать количество <tex>x_i</tex> предметов каждого типа так, чтобы

*максимизировать общую стоимость: <tex>\sum_{i=1}^N p_ix_i</tex>;

*выполнялось условие совместности: <tex>\sum_{i=1}^N w_ix_i \le W</tex>;

где <tex> x_i \ge 0 </tex> целое, для всех <tex> i= 1,2,...,N</tex>.

===Варианты решения===
Самые распространенные методы точного решения это:
* Метод ветвей и границ.
* Метод динамического программирования.

===Метод динамического программирования===
Пусть <tex>d(i,c)</tex> максимальная стоимость любого количества вещей типов от 1 до <tex>i</tex>, суммарным весом до <tex>c</tex> включительно.

Заполним <tex>d(0,c)</tex> нулями.

Тогда меняя i от 1 до <tex>N</tex>, рассчитаем на каждом шаге <tex>d(i,c)</tex>, для <tex>c</tex> от 0 до <tex>W</tex>, по рекуррентной формуле:

<tex>
d(i,c) =
\begin{cases}
d(i - 1, c) & for\ c = 0, ..., w_i - 1; \\
max(d(i - 1, c), d(i, c - w_i) + p_i) & for\ c = w_i, ..., W;
\end{cases}
</tex>

После выполнения в <tex> d(N,W) </tex> будет лежать максимальная стоимость предметов, помещающихся в рюкзак.

Если не нужно восстанавливать ответ, то можно использовать одномерный массив <tex>d(c)</tex> вместо двумерного и использовать формулу:

<tex> d(c) = max(d(c), d(c - w_i) + p_i) </tex>;

Сложность алгоритма <tex>O(NW)</tex>.

==Непрерывный рюкзак==
'''Непрерывный рюкзак''' (англ. ''Continuous knapsack problem'') - вариант задачи, в котором возможно брать любою дробную часть от предмета, при этом удельная стоимость сохраняется.

'''Пример:''' Вор грабит мясника. Суммарно он может унести ограниченный вес товаров. Вор может резать товары без ущерба к удельной стоимости. Нужно унести товара на максимальную сумму.
===Формулировка Задачи===
Задача выбрать часть <tex>x_i</tex> каждого предмета так, чтобы

*максимизировать общую стоимость: <tex>\sum_{i=1}^N p_ix_i</tex>;

*выполнялось условие совместности: <tex>\sum_{i=1}^N w_ix_i \le W</tex>;

где <tex> 0 \le x_i \le 1</tex> дробное, для всех <tex> i= 1,2,...,N</tex>.

===Варианты решения===
Возможность брать любую часть от предмета сильно упрощает задачу. Жадный алгоритм дает оптимальное решение в данном случае.

=== Реализация ===
sort(); // сортируем в порядке убывания удельной стоимости.
for i = 1..N // идем по предметам
if W >= w[i] //если помещается - берем
sum += p[i];
W -= w[i];
else
sum += W / w[i] * p[i];// иначе берем сколько можно и выходим
break;

==Задача о суммах подмножеств==
'''Задача о суммах подмножеств''' (англ. ''Subset-sum problem, Value Independent Knapsack Problem'') - задача из семейства, в которой стоимость предмета совпадает с его весом.

'''Пример:''' В машина может увезти определенное количество груза. Нужно увезти как можно больше крупного неделимого мусора за раз.
===Формулировка Задачи===
Нужно выбрать подмножество так, чтобы сумма ближе всего к <tex>W</tex>, но не превысила его. Формально, нужно найти набор бинарных величин <tex>x_i</tex>, так чтобы

*максимизировать общую стоимость: <tex>\sum_{i=1}^N w_ix_i</tex>;

*выполнялось условие совместности: <tex>\sum_{i=1}^N w_ix_i \le W</tex>;

<tex> x_j = 1 </tex> если <tex> j</tex> предмет назначен рюкзаку, иначе <tex> x_{ij} = 0 </tex>, для всех <tex> i= 1,2,...,N</tex>.

===Варианты решения===
Для решения пригодны любые методы применяемые для классической задачи, однако специализированые алгоритмы обычно более оптимальны по параметрам. Используются:
* Метод динамического программирования.
* Гибридный метод на основе динамического программирования и поиска по дереву. В худшем случае, работает за <tex> O(n) </tex>.

===Метод динамического программирования===
Пусть <tex>d(i,c)</tex> максимальная сумма <tex>\le c</tex>, подмножества взятого из <tex> 1, ...,\ i</tex> элементов.

Заполним <tex>d(0,c)</tex> нулями.

Тогда меняя i от 1 до <tex>N</tex>, рассчитаем на каждом шаге <tex>d(i,c)</tex>, для <tex>c</tex> от 0 до <tex>W</tex>, по рекуррентной формуле:

<tex>
d(i,c) =
\begin{cases}
d(i - 1, c) & for\ c = 0, ..., w_i - 1; \\
max(d(i - 1, c), d(i - 1, c - w_i) + w_i) & for\ c = w_i, ..., W;
\end{cases}
</tex>

После выполнения в <tex> d(N,W) </tex> будет лежать максимальная сумма подмножества, не превышающая заданное значение.

Сложность алгоритма <tex>O(NW)</tex>.

==Задача о размене==
'''Задача о размене''' (англ. ''Change-Making problem'') - имеются <tex> N </tex> неисчерпаемых типов предметов с весами <tex>w_i</tex>. Нужно наполнить рюкзак предметами с суммарным весом <tex>W</tex>.

Часто задачу ставят как, дать сдачу наименьшим количеством монет.
===Формулировка Задачи===
Каждый предмет может быть выбран любое число раз.
Задача выбрать количество <tex>x_i</tex> предметов каждого типа так, чтобы

*минимизировать количество взятых предметов: <tex>\sum_{i=1}^N x_i</tex>;

*сумма весов выбранных предметов равнялась вместимости рюкзака: <tex>\sum_{i=1}^N w_ix_i = W</tex>;

Где <tex> x_i \ge 0 </tex> целое, для всех <tex> i= 1,2,...,N</tex>.
===Варианты решения===
Самые распространенные методы точного решения это:
* Метод ветвей и границ.
* Метод динамического программирования.

===Метод динамического программирования===
Пусть <tex>d(i,c)</tex> минимальное число предметов, типов от 1 до <tex>i</tex>, необходимое, чтобы заполнить рюкзак вместимостью <tex>c</tex>.

Пусть <tex>d(0,0) = 0</tex>, а <tex>d(0,c) = \inf</tex> для всех <tex>c > 0</tex>.

Тогда меняя i от 1 до <tex>N</tex>, рассчитаем на каждом шаге <tex>d(i,c)</tex>, для <tex>c</tex> от 0 до <tex>W</tex>, по рекуррентной формуле:

<tex>
d(i,c) =
\begin{cases}
d(i - 1, c) & for\ c = 0, ..., w_i - 1; \\
min(d(i - 1, c), d(i, c - w_i) + 1) & for\ c = w_i, ..., W;
\end{cases}
</tex>

После выполнения в <tex> d(N,W) </tex> будет лежать максимальная стоимость предметов, помещающихся в рюкзак.

Если не нужно восстанавливать ответ, то можно использовать одномерный массив <tex>d(c)</tex> вместо двумерного и использовать формулу:

<tex> d(c) = min(d(c), d(c - w_i) + 1) \qquad for\ c = w_i, ..., W</tex>.

Сложность алгоритма <tex>O(NW)</tex>.

==Задача об упаковке==
'''Задача об упаковке''' (англ. ''Bin Packing Problem'') - имеются <tex> N </tex> рюкзаков вместимости <tex> W </tex> и столько же предметов с весами <tex>w_i</tex>. Нужно распределить все предметы, задействовав минимальное количество рюкзаков.

'''Пример:''' Нужно вывезти из шахты все куски руды, используя наименьшее число вагонеток.
===Формулировка Задачи===
Математически задачу можно представить так:

*минимизировать количество рюкзаков: <tex>\sum_{i=1}^N y_i</tex>;

*так чтобы выполнялось условие на совместность: <tex>\sum_{i=1}^N w_ix_{ij} \le Wy_j \qquad j \in {1, ..., N}</tex>;

<tex> x_{ij} = 1 </tex> если <tex> j</tex> предмет назначен <tex>i </tex> рюкзаку. Иначе <tex> x_{ij} = 0 </tex>.

<tex> y_i = 1 </tex> если <tex> i</tex> рюкзак используется. Иначе <tex> y_i = 0 </tex>.

===Варианты решения===
Применение динамического программирования нецелесообразно. Обычно применяют аппроксимационные алгоритмы, либо используют метод ветвей и границ.

==Мультипликативный рюкзак==
'''Мультипликативный рюкзак''' (англ. ''Multiple Knapsack Problem'') - есть <tex>N</tex> предметов и <tex>M</tex> рюкзаков (<tex>M\le N</tex>). У каждого рюкзака своя вместимость <tex>W_i</tex>. Задача: выбрать <tex>M</tex> не пересекающихся множеств, назначить соответствие рюкзакам так, чтобы суммарная стоимость была максимальна, а вес предметов в каждом рюкзаке не превышал его вместимость.

'''Пример:''' У транспортной компании есть парк машин разной грузоподъемности. Нужно перевезти товара на максимальную сумму с одного склада на другой единовременно.
===Формулировка Задачи===
Максимизировать <tex>\sum_{i=1}^M \sum_{j=1}^{N} p_jx_{ij}</tex>

так, чтобы <tex>\sum_{i=1}^N w_jx_{ij} \le W_i</tex> выполнялось для всех <tex> i= 1,2,...,N</tex>.

<tex>\sum_{j=1}^{M}x_{ij}=1</tex> для всех <tex> i= 1,2,...,N</tex>.

<tex> x_{ij} = 1 </tex> если <tex> j</tex> предмет назначен <tex>i </tex> рюкзаку. Иначе <tex> x_{ij} = 0 </tex>.

===Варианты решения===
Применение динамического программирования, для задач данного типа нецелесообразно. Используются вариации метода ветвей и границ.

==Задача о назначении==
'''Задача о назначении''' (англ. ''Generalized Assignment Problem'') - Наиболее общая задача семейства. Отличается от мультипликативного рюкзака тем, что каждый предмет имеет различные характеристики в зависимости от рюкзака, куда его помещают. Есть <tex>N</tex> предметов и <tex>M</tex> рюкзаков (<tex>M\le N</tex>). У каждого рюкзака своя вместимость <tex>W_i</tex>, у <tex> j </tex> предмета <tex> p_{ij} </tex> стоимость и вес, при помещении его в <tex> i </tex> рюкзак, равны <tex> p_{ij} </tex> и <tex> w_{ij} </tex> соответственно. Задача: выбрать <tex>M</tex> не пересекающихся множеств, назначить соответствие рюкзакам так, чтобы суммарная стоимость была максимальна, а вес предметов в каждом рюкзаке не превышал его вместимость.
Весьма важная задача, так как она моделирует оптимальное распределение различных задач между вычислительными блоками.
===Формулировка Задачи===

Максимизировать стоимость выбранных предметов <tex>\sum_{i=1}^M\sum_{j=1}^N p_{ij} x_{ij}</tex>,

при выполнении условия совместности <tex>\sum_{j=1}^N w_{ij} x_{ij} \le W_i \qquad i=1, \ldots, M</tex>.

<tex> \sum_{i=1}^M x_{ij} \leq 1 \qquad j=1, \ldots, N</tex>.

<tex> x_{ij} \in \{0,1\} \qquad i=1, \ldots, N, \quad j=1, \ldots, N</tex>.

===Варианты решения===
Применение динамического программирования нецелесообразно. Наиболее используем метод ветвей и границ.

= Литература =
*[http://informatics.mccme.ru/moodle/mod/book/view.php?id=815&chapterid=60 Дистанционная подготовка по информатике]
*[http://rosettacode.org/wiki/Knapsack_Problem Код для нескольких задач семейства на всевозможных языках]
*[http://www.diku.dk/users/pisinger/95-1.pdf David Pisinger Knapsack problems. — 1995]
*Silvano Martello, Paolo Toth. Knapsack Problems: Algorithms and Computer Implementations — 1990 г. — ISBN 0-471-92420-2

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Динамическое программирование]]

Задача о рюкзаке

2016-10-08T03:22:50Z

37.57.17.214: /* Метод динамического программирования */ разве здесь не квадрат?

'''Задача о рюкзаке'''(''англ. Knapsack problem'') — дано <tex>N</tex> предметов, <tex>n_i</tex> предмет имеет массу <tex> w_i > 0</tex> и стоимость <tex> p_i > 0</tex>. Необходимо выбрать из этих предметов такой набор, чтобы суммарная масса не превосходила заданной величины <tex>W</tex> (вместимость рюкзака), а суммарная стоимость была максимальна.

== Формулировка задачи ==

Дано <tex>N</tex> предметов, <tex>W</tex> - вместимость рюкзака, <tex>w=\{w_{1},w_{2},...,w_{N}\}</tex> — соответствующий ему набор положительных целых весов, <tex>p=\{p_{1},p_{2},...,p_{N}\}</tex> — соответствующий ему набор положительных целых стоимостей. Нужно найти набор бинарных величин <tex>B=\{b_{1},b_{2},...,b_{N}\}</tex>, где <tex>b_{i} = 1 </tex>, если предмет <tex>n_i</tex> включен в набор, <tex> b_{i} = 0 </tex>, если предмет <tex>n_i</tex> не включен, и такой что:

#<tex>b_{1} w_{1}+ ... + b_{N} w_{N} \le W</tex>
#<tex>b_{1} p_{1}+ ... + b_{N} p_{N} </tex> максимальна.

== Варианты решения ==

Задачу о рюкзаке можно решить несколькими способами:

* Перебирать все подмножества набора из N предметов. Сложность такого решения <tex>O({2^{N}})</tex>.

* Методом [[Meet-in-the-middle|Meet-in-the-middle]]. Сложность решения <tex> O({2^{N/2}}\times{N}) </tex>

* Метод динамического программирования. Сложность - <tex>O(N \times W)</tex>.

== Метод динамического программирования ==

Пусть <tex>A(k, s)</tex> есть максимальная стоимости предметов, которые можно уложить в рюкзак вместимости <tex>s</tex>, если можно использовать только первые <tex>k</tex> предметов, то есть <tex>\{n_1,n_2,...,n_k\}</tex>, назовем этот набор допустимых предметов для <tex>A(k,s)</tex>.

<tex>A(k, 0) = 0</tex>

<tex>A(0, s) = 0</tex>

Найдем <tex>A(k, s)</tex>. Возможны 2 варианта:

#Если предмет <tex>k</tex> не попал в рюкзак. Тогда <tex>A(k, s)</tex> равно максимальной стоимости рюкзака с такой же вместимостью и набором допустимых предметов <tex>\{n_1,n_2,...,n_{k-1}\}</tex>, то есть <tex>A(k,s) = A(k-1, s)</tex>
# Если <tex>k</tex> попал в рюкзак. Тогда <tex>A(k, s)</tex> равно максимальной стоимости рюкзака, где вес <tex>s</tex> уменьшаем на вес <tex>k</tex> -ого предмета и набор допустимых предметов <tex>\{n_1,n_2,...,n_{k-1}\}</tex> плюс стоимость <tex>k</tex>, то есть <tex>A(k-1, s-w_k) + p_k</tex>

То есть:
<tex>A(k,s) = max(A(k-1,s), A(k-1,s-w_{k}) + p_{k})</tex>

Стоимость искомого набора равна <tex>A(N,W)</tex>, так как нужно найти максимальную стоимость рюкзака, где все предметы допустимы и вместимость рюкзака <tex>W</tex>.

'''Восстановим набор предметов, входящих в рюкзак'''

Будем определять, входит ли <tex>n_i</tex> предмет в искомый набор. Начинаем с элемента <tex>A(i,w)</tex>, где <tex>i = N</tex>, <tex>w = W</tex>. Для этого сравниваем <tex>A(i,w)</tex> со следующими значениями:

#Максимальная стоимость рюкзака с такой же вместимостью и набором допустимых предметов <tex>\{n_1,n_2,...,n_{i-1}\}</tex>, то есть <tex>A(i-1, w)</tex>
#Максимальная стоимость рюкзака с вместимостью на <tex>w_i</tex> меньше и набором допустимых предметов <tex>\{n_1,n_2,...,n_{i-1}\}</tex> плюс стоимость <tex>p_i</tex>, то есть <tex>A(i-1, w-w_i)+p_i</tex>

Заметим, что при построении <tex>A</tex> мы выбирали максимум из этих значений и записывали в <tex>A(i, w)</tex>. Тогда будем сравнивать <tex>A(i, w)</tex> c <tex>A(i-1, w)</tex>, если равны, тогда <tex>n_i</tex> не входит в искомый набор, иначе входит.

== Реализация ==
Сначала генерируем <tex>A</tex>.

for i = 0..W
A[0][i] = 0;
for i = 0..N
A[i][0] = 0; //Первые элементы приравниваем к 0
for k = 1..N
for s = 1..W //Перебираем для каждого k все вместимости
if s >= w[k] //Если текущий предмет вмещается в рюкзак
A[k][s] = max(A[k-1][s], A[k-1][s-w[k]]+p[k]); //выбираем класть его или нет
else
A[k][s] = A[k-1][s]; //иначе, не кладем

Затем найдем набор <tex>ans</tex> предметов, входящих в рюкзак, рекурсивной функцией:

findAns(k, s)
if A[k][s] == 0
return;
if A[k-1][s] == A[k][s]
findAns(k-1, s);
else
findAns(k-1, s - w[k]);
ans.push(k);

Сложность алгоритма <tex>O(N \times W)</tex>

== Пример ==

<tex>W = 13, N = 5</tex>

<tex>w_{1} = 3, p_{1} = 1 </tex>

<tex>w_{2} = 4, p_{2} = 6 </tex>

<tex>w_{3} = 5, p_{3} = 4 </tex>

<tex>w_{4} = 8, p_{4} = 7 </tex>

<tex>w_{5} = 9, p_{5} = 6 </tex>

[[Файл:Knapsack problem0.png]]

Числа от 0 до 13 в первой строчке обозначают вместимость рюкзака.

В первой строке как только вместимость рюкзака <tex>n \ge 3</tex>, добавляем в рюкзак 1 предмет.

Рассмотрим <tex>k = 3</tex>, при каждом <tex>s \ge 5 (</tex>так как <tex>w_3 = 5)</tex> сравниваем <tex>A[k-1][s]</tex> и <tex>A[k-1][s-w_3]+p_3</tex> и записываем в <tex>A[k][s]</tex> стоимость либо рюкзака без третьего предмета, но с таким же весом, либо с третьим предметом, тогда стоимость равна стоимости третьего предмета плюс стоимость рюкзака с вместимостью на <tex>w_3</tex> меньше.

Максимальная стоимость рюкзака находится в <tex>A(5, 13)</tex>.

'''Восстановление набора предметов, из которых состоит максимально дорогой рюкзак.'''

Начиная с <tex>A(5, 13)</tex> восстанавливаем ответ.

[[Файл:Задача о рюкзаке3.png]]

Таким образом, в набор входит <tex>2</tex> и <tex>4</tex> предмет.

Стоимость рюкзака <tex>= 6 + 7 = 13</tex>

Вес рюкзака <tex>= 4 + 8 = 12</tex>

=Другие задачи семейства=
==Ограниченный рюкзак ==
'''Ограниченный рюкзак''' (англ. ''Bounded Knapsack Problem'') - обобщение классической задачи, когда любой предмет может быть взят некоторое количество раз.

'''Пример:''' Вор грабит склад. Он может унести ограниченный вес, каждый товар на складе содержится в определенном ограниченном количестве. Нужно унести предметов на максимальную сумму.
===Формулировка Задачи===
Каждый предмет может быть выбран ограниченное <tex>b_i</tex> число раз.
Задача выбрать число <tex>x_i</tex> предметов каждого типа так, чтобы

* максимизировать общую стоимость: <tex>\sum_{i=1}^N p_ix_i</tex>;

* выполнялось условие совместности: <tex>\sum_{i=1}^N w_ix_i \le W</tex>;

где <tex> x_i \in (0,1,...,b_i)</tex> для всех <tex> i= 1,2,...,N</tex>.

===Варианты решения===
При небольших <tex>b_i</tex> решается сведением к классической задаче о рюкзаке. В иных случаях:
* Методом ветвей и границ.
* Методом динамического программирования.

===Метод динамического программирования===
Пусть <tex>d(i,c)</tex> максимальная стоимость любого возможного числа предметов типов от 1 до <tex>i</tex>, суммарным весом до <tex>c</tex>.

Заполним <tex>d(0,c)</tex> нулями.

Тогда меняя i от 1 до <tex>N</tex>, рассчитаем на каждом шаге <tex>d(i,c)</tex>, для <tex>c</tex> от 1 до <tex>W</tex>, по рекуррентной формуле:

<tex>d(i,c) = max(d(i - 1, c - lw_i) + lp_i) </tex> по всем целым <tex> l </tex> из промежутка <tex> 0 \le l \le min(b_i,\lfloor c/w_i \rfloor)</tex>.

Если не нужно восстанавливать ответ, то можно использовать одномерный массив <tex>d(c)</tex> вместо двумерного.

После выполнения в <tex> d(N,W) </tex> будет лежать максимальная стоимость предметов, помещающихся в рюкзак.

=== Реализация ===
for i = 0..W // база
d[0][i] = 0;
for i = 1..N
for c = 1..W //Перебираем для каждого i, все вместимости
d[i][c] = d[i - 1][c];
for l = min(b[i], c / w[i]) .. 1 // ищем l для которого выполняется максимум
d[i][c] = max(d[i][c], d[i - 1][c - l * w[i]] + p[i] * l);

Сложность алгоритма <tex>O(NW^2)</tex>.

==Неограниченный рюкзак==
'''Неограниченный рюкзак''' (англ.''Unbounded Knapsack Problem'') - обобщение ограниченного рюкзака, в котором любой предмет может быть выбран любое количество раз.

'''Пример:''' Перекупщик закупается на оптовой базе. Он может увезти ограниченное количество товара, количество товара каждого типа на базе не ограниченно. Нужно увезти товар на максимальную сумму.
===Формулировка Задачи===
Каждый предмет может быть выбран любое число раз.
Задача выбрать количество <tex>x_i</tex> предметов каждого типа так, чтобы

*максимизировать общую стоимость: <tex>\sum_{i=1}^N p_ix_i</tex>;

*выполнялось условие совместности: <tex>\sum_{i=1}^N w_ix_i \le W</tex>;

где <tex> x_i \ge 0 </tex> целое, для всех <tex> i= 1,2,...,N</tex>.

===Варианты решения===
Самые распространенные методы точного решения это:
* Метод ветвей и границ.
* Метод динамического программирования.

===Метод динамического программирования===
Пусть <tex>d(i,c)</tex> максимальная стоимость любого количества вещей типов от 1 до <tex>i</tex>, суммарным весом до <tex>c</tex> включительно.

Заполним <tex>d(0,c)</tex> нулями.

Тогда меняя i от 1 до <tex>N</tex>, рассчитаем на каждом шаге <tex>d(i,c)</tex>, для <tex>c</tex> от 0 до <tex>W</tex>, по рекуррентной формуле:

<tex>
d(i,c) =
\begin{cases}
d(i - 1, c) & for\ c = 0, ..., w_i - 1; \\
max(d(i - 1, c), d(i, c - w_i) + p_i) & for\ c = w_i, ..., W;
\end{cases}
</tex>

После выполнения в <tex> d(N,W) </tex> будет лежать максимальная стоимость предметов, помещающихся в рюкзак.

Если не нужно восстанавливать ответ, то можно использовать одномерный массив <tex>d(c)</tex> вместо двумерного и использовать формулу:

<tex> d(c) = max(d(c), d(c - w_i) + p_i) </tex>;

Сложность алгоритма <tex>O(NW^2)</tex>.

==Непрерывный рюкзак==
'''Непрерывный рюкзак''' (англ. ''Continuous knapsack problem'') - вариант задачи, в котором возможно брать любою дробную часть от предмета, при этом удельная стоимость сохраняется.

'''Пример:''' Вор грабит мясника. Суммарно он может унести ограниченный вес товаров. Вор может резать товары без ущерба к удельной стоимости. Нужно унести товара на максимальную сумму.
===Формулировка Задачи===
Задача выбрать часть <tex>x_i</tex> каждого предмета так, чтобы

*максимизировать общую стоимость: <tex>\sum_{i=1}^N p_ix_i</tex>;

*выполнялось условие совместности: <tex>\sum_{i=1}^N w_ix_i \le W</tex>;

где <tex> 0 \le x_i \le 1</tex> дробное, для всех <tex> i= 1,2,...,N</tex>.

===Варианты решения===
Возможность брать любую часть от предмета сильно упрощает задачу. Жадный алгоритм дает оптимальное решение в данном случае.

=== Реализация ===
sort(); // сортируем в порядке убывания удельной стоимости.
for i = 1..N // идем по предметам
if W >= w[i] //если помещается - берем
sum += p[i];
W -= w[i];
else
sum += W / w[i] * p[i];// иначе берем сколько можно и выходим
break;

==Задача о суммах подмножеств==
'''Задача о суммах подмножеств''' (англ. ''Subset-sum problem, Value Independent Knapsack Problem'') - задача из семейства, в которой стоимость предмета совпадает с его весом.

'''Пример:''' В машина может увезти определенное количество груза. Нужно увезти как можно больше крупного неделимого мусора за раз.
===Формулировка Задачи===
Нужно выбрать подмножество так, чтобы сумма ближе всего к <tex>W</tex>, но не превысила его. Формально, нужно найти набор бинарных величин <tex>x_i</tex>, так чтобы

*максимизировать общую стоимость: <tex>\sum_{i=1}^N w_ix_i</tex>;

*выполнялось условие совместности: <tex>\sum_{i=1}^N w_ix_i \le W</tex>;

<tex> x_j = 1 </tex> если <tex> j</tex> предмет назначен рюкзаку, иначе <tex> x_{ij} = 0 </tex>, для всех <tex> i= 1,2,...,N</tex>.

===Варианты решения===
Для решения пригодны любые методы применяемые для классической задачи, однако специализированые алгоритмы обычно более оптимальны по параметрам. Используются:
* Метод динамического программирования.
* Гибридный метод на основе динамического программирования и поиска по дереву. В худшем случае, работает за <tex> O(n) </tex>.

===Метод динамического программирования===
Пусть <tex>d(i,c)</tex> максимальная сумма <tex>\le c</tex>, подмножества взятого из <tex> 1, ...,\ i</tex> элементов.

Заполним <tex>d(0,c)</tex> нулями.

Тогда меняя i от 1 до <tex>N</tex>, рассчитаем на каждом шаге <tex>d(i,c)</tex>, для <tex>c</tex> от 0 до <tex>W</tex>, по рекуррентной формуле:

<tex>
d(i,c) =
\begin{cases}
d(i - 1, c) & for\ c = 0, ..., w_i - 1; \\
max(d(i - 1, c), d(i - 1, c - w_i) + w_i) & for\ c = w_i, ..., W;
\end{cases}
</tex>

После выполнения в <tex> d(N,W) </tex> будет лежать максимальная сумма подмножества, не превышающая заданное значение.

Сложность алгоритма <tex>O(NW)</tex>.

==Задача о размене==
'''Задача о размене''' (англ. ''Change-Making problem'') - имеются <tex> N </tex> неисчерпаемых типов предметов с весами <tex>w_i</tex>. Нужно наполнить рюкзак предметами с суммарным весом <tex>W</tex>.

Часто задачу ставят как, дать сдачу наименьшим количеством монет.
===Формулировка Задачи===
Каждый предмет может быть выбран любое число раз.
Задача выбрать количество <tex>x_i</tex> предметов каждого типа так, чтобы

*минимизировать количество взятых предметов: <tex>\sum_{i=1}^N x_i</tex>;

*сумма весов выбранных предметов равнялась вместимости рюкзака: <tex>\sum_{i=1}^N w_ix_i = W</tex>;

Где <tex> x_i \ge 0 </tex> целое, для всех <tex> i= 1,2,...,N</tex>.
===Варианты решения===
Самые распространенные методы точного решения это:
* Метод ветвей и границ.
* Метод динамического программирования.

===Метод динамического программирования===
Пусть <tex>d(i,c)</tex> минимальное число предметов, типов от 1 до <tex>i</tex>, необходимое, чтобы заполнить рюкзак вместимостью <tex>c</tex>.

Пусть <tex>d(0,0) = 0</tex>, а <tex>d(0,c) = \inf</tex> для всех <tex>c > 0</tex>.

Тогда меняя i от 1 до <tex>N</tex>, рассчитаем на каждом шаге <tex>d(i,c)</tex>, для <tex>c</tex> от 0 до <tex>W</tex>, по рекуррентной формуле:

<tex>
d(i,c) =
\begin{cases}
d(i - 1, c) & for\ c = 0, ..., w_i - 1; \\
min(d(i - 1, c), d(i, c - w_i) + 1) & for\ c = w_i, ..., W;
\end{cases}
</tex>

После выполнения в <tex> d(N,W) </tex> будет лежать максимальная стоимость предметов, помещающихся в рюкзак.

Если не нужно восстанавливать ответ, то можно использовать одномерный массив <tex>d(c)</tex> вместо двумерного и использовать формулу:

<tex> d(c) = min(d(c), d(c - w_i) + 1) \qquad for\ c = w_i, ..., W</tex>.

Сложность алгоритма <tex>O(NW)</tex>.

==Задача об упаковке==
'''Задача об упаковке''' (англ. ''Bin Packing Problem'') - имеются <tex> N </tex> рюкзаков вместимости <tex> W </tex> и столько же предметов с весами <tex>w_i</tex>. Нужно распределить все предметы, задействовав минимальное количество рюкзаков.

'''Пример:''' Нужно вывезти из шахты все куски руды, используя наименьшее число вагонеток.
===Формулировка Задачи===
Математически задачу можно представить так:

*минимизировать количество рюкзаков: <tex>\sum_{i=1}^N y_i</tex>;

*так чтобы выполнялось условие на совместность: <tex>\sum_{i=1}^N w_ix_{ij} \le Wy_j \qquad j \in {1, ..., N}</tex>;

<tex> x_{ij} = 1 </tex> если <tex> j</tex> предмет назначен <tex>i </tex> рюкзаку. Иначе <tex> x_{ij} = 0 </tex>.

<tex> y_i = 1 </tex> если <tex> i</tex> рюкзак используется. Иначе <tex> y_i = 0 </tex>.

===Варианты решения===
Применение динамического программирования нецелесообразно. Обычно применяют аппроксимационные алгоритмы, либо используют метод ветвей и границ.

==Мультипликативный рюкзак==
'''Мультипликативный рюкзак''' (англ. ''Multiple Knapsack Problem'') - есть <tex>N</tex> предметов и <tex>M</tex> рюкзаков (<tex>M\le N</tex>). У каждого рюкзака своя вместимость <tex>W_i</tex>. Задача: выбрать <tex>M</tex> не пересекающихся множеств, назначить соответствие рюкзакам так, чтобы суммарная стоимость была максимальна, а вес предметов в каждом рюкзаке не превышал его вместимость.

'''Пример:''' У транспортной компании есть парк машин разной грузоподъемности. Нужно перевезти товара на максимальную сумму с одного склада на другой единовременно.
===Формулировка Задачи===
Максимизировать <tex>\sum_{i=1}^M \sum_{j=1}^{N} p_jx_{ij}</tex>

так, чтобы <tex>\sum_{i=1}^N w_jx_{ij} \le W_i</tex> выполнялось для всех <tex> i= 1,2,...,N</tex>.

<tex>\sum_{j=1}^{M}x_{ij}=1</tex> для всех <tex> i= 1,2,...,N</tex>.

<tex> x_{ij} = 1 </tex> если <tex> j</tex> предмет назначен <tex>i </tex> рюкзаку. Иначе <tex> x_{ij} = 0 </tex>.

===Варианты решения===
Применение динамического программирования, для задач данного типа нецелесообразно. Используются вариации метода ветвей и границ.

==Задача о назначении==
'''Задача о назначении''' (англ. ''Generalized Assignment Problem'') - Наиболее общая задача семейства. Отличается от мультипликативного рюкзака тем, что каждый предмет имеет различные характеристики в зависимости от рюкзака, куда его помещают. Есть <tex>N</tex> предметов и <tex>M</tex> рюкзаков (<tex>M\le N</tex>). У каждого рюкзака своя вместимость <tex>W_i</tex>, у <tex> j </tex> предмета <tex> p_{ij} </tex> стоимость и вес, при помещении его в <tex> i </tex> рюкзак, равны <tex> p_{ij} </tex> и <tex> w_{ij} </tex> соответственно. Задача: выбрать <tex>M</tex> не пересекающихся множеств, назначить соответствие рюкзакам так, чтобы суммарная стоимость была максимальна, а вес предметов в каждом рюкзаке не превышал его вместимость.
Весьма важная задача, так как она моделирует оптимальное распределение различных задач между вычислительными блоками.
===Формулировка Задачи===

Максимизировать стоимость выбранных предметов <tex>\sum_{i=1}^M\sum_{j=1}^N p_{ij} x_{ij}</tex>,

при выполнении условия совместности <tex>\sum_{j=1}^N w_{ij} x_{ij} \le W_i \qquad i=1, \ldots, M</tex>.

<tex> \sum_{i=1}^M x_{ij} \leq 1 \qquad j=1, \ldots, N</tex>.

<tex> x_{ij} \in \{0,1\} \qquad i=1, \ldots, N, \quad j=1, \ldots, N</tex>.

===Варианты решения===
Применение динамического программирования нецелесообразно. Наиболее используем метод ветвей и границ.

= Литература =
*[http://informatics.mccme.ru/moodle/mod/book/view.php?id=815&chapterid=60 Дистанционная подготовка по информатике]
*[http://rosettacode.org/wiki/Knapsack_Problem Код для нескольких задач семейства на всевозможных языках]
*[http://www.diku.dk/users/pisinger/95-1.pdf David Pisinger Knapsack problems. — 1995]
*Silvano Martello, Paolo Toth. Knapsack Problems: Algorithms and Computer Implementations — 1990 г. — ISBN 0-471-92420-2

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Динамическое программирование]]

Meet-in-the-middle

2016-10-07T19:49:25Z

37.57.17.214: /* Реализация */ опечатка

{{Определение
|definition=
'''Meet-in-the-middle''' (Встреча в середине) — это метод решения уравнения вида <tex> f({x}) = g({y}) </tex>, где <tex> x \in {X} </tex> и <tex> y \in {Y} </tex>, который работает за время <tex> O(F(X) + Y \cdot G_X(y))</tex>, где <tex> F(X) </tex> {{---}} время построения множества <tex> X </tex>, <tex> G_X(y) </tex> {{---}} время поиска элемента <tex> x </tex> в множестве <tex> X </tex>, удовлетворяющее решению при заданном <tex> y </tex>, или проверка, что такого <tex> x </tex> не существует.
}}
'''Meet-in-the-middle''' разбивает задачу пополам и решает всю задачу через частичный расчет половинок. Он работает следующим образом: переберем все возможные значения <tex> {x} </tex> и запишем пару значений <tex> ({x},{f({x})}) </tex> в множество. Затем будем перебирать всевозможные значения <tex> y </tex>, для каждого из них будем вычислять <tex> g(y) </tex>, которое мы будем искать в нашем множестве. Если в качестве множества использовать отсортированный массив, а в качестве функции поиска {{---}} [[Целочисленный двоичный поиск | бинарный поиск]], то время работы нашего алгоритма составляет <tex> {O(X\log{X})} </tex> на сортировку, и <tex> {O(Y\log{X})} </tex> на двоичный поиск, что дает в сумме <tex>{O((X + Y)\log{X}})</tex>.

== Задача о нахождении четырех чисел с суммой равной нулю ==
Дан массив целых чисел <tex>{A}</tex>. Требуется найти любые <tex> 4 </tex> числа, сумма которых равна <tex> 0 </tex> (одинаковые элементы могут быть использованы несколько раз).

Например : <tex> {A} = ({2,3,1,0,-4,-1}) </tex>. Решением данной задачи является, например, четверка чисел <tex> 3 + 1 + 0 - 4 = 0</tex> или <tex> 0 + 0 + 0 + 0 = 0</tex>.

Наивный алгоритм заключается в переборе всевозможных комбинаций чисел. Это решение работает за <tex> {O(N^4)}</tex>. Теперь, с помощью '''Meet-in-the-middle''' мы можем сократить время работы до <tex> {O(N^2\log{N}}) </tex>.

Для этого заметим, что сумму <tex> a + b + c + d = 0 </tex> можно записать как <tex> a + b = -(c + d)</tex>. Мы будем хранить все <tex> {N^2} </tex> пар сумм <tex> a + b </tex> в массиве <tex> sum </tex>, который мы отсортируем. Далее перебираем все <tex> {N^2} </tex> пар сумм <tex> c + d </tex> и проверяем [[Целочисленный двоичный поиск|бинарным поиском]], есть ли сумма <tex> -(c + d) </tex> в массиве <tex> sum </tex>.

=== Реализация ===
// sum - массив сумм a + b, cnt - счетчик массива sum
'''findsum'''():
'''for''' a = 0..N - 1
'''for''' b = 0..N - 1
sum[cnt].res = A[a] + B[b]
sum[cnt].a = a
sum[cnt].b = b
cnt++
sort(sum, key = "res") // сортируем sum по полю res
'''for''' c = 0..N - 1
'''for''' d = 0..N - 1
'''if''' сумма -(A[c] + A[d]) есть в массив sum
index = индекс суммы -(A[c] + A[d])
'''return''' (sum[index].a, sum[index].b, A[c], A[d])
'''return''' "No solution"
Итоговое время работы <tex> {O(N^2\log{N}}) </tex>.

Если вместо отсортированного массива использовать [[Хеш-таблица | хэш-таблицу]], то задачу можно будет решить за время <tex> O(N^2) </tex>.

== Задача о рюкзаке ==
Классической задачей является задача о наиболее эффективной упаковке рюкзака. Каждый предмет характеризуется весом (<tex> {w_{i} \leqslant 10^{9}} </tex> ) и ценностью (<tex>{cost_{i} \leqslant 10^{9}} </tex>). В рюкзак, ограниченный по весу, необходимо набрать вещей с максимальной суммарной стоимостью. Для ее решения изначальное множество вещей N разбивается на два равных(или примерно равных) подмножества, для которых за приемлемое время можно перебрать все варианты и подсчитать суммарный вес и стоимость, а затем для каждого из них найти группу вещей из первого подмножества с максимальной стоимостью, укладывающуюся в ограничение по весу рюкзака. Сложность алгоритма <tex>O({2^{N/2}}\cdot{N})</tex>. Память <tex> O({2^{N/2}})</tex>.

=== Реализация ===
Разделим наше множество на две части. Подсчитаем все подмножества из первой части и будем хранить их в массиве <tex> first </tex>. Отсортируем массив <tex> first </tex> по весу. Далее пройдемся по этому массиву и оставим только те подмножества, для которых не существует другого подмножества с меньшим весом и большей стоимостью. Очевидно, что подмножества, для которых существует другое, более легкое и одновременно более ценное подмножество, можно удалять.
Таким образом в массиве <tex> first </tex> мы имеем подмножества, отсортированные не только по весу, но и по стоимости. Тогда начнем перебирать все возможные комбинации вещей из второй половины и находить бинарным поиском удовлетворяющие нам подмножества из первой половины, хранящиеся в массиве <tex> first </tex>.

Реализуем данный алгоритм:
// N - количество всех вещей, w[] - массив весов всех вещей, cost[] - массив стоимостей всех вещей, R - ограничение по весу рюкзака.
'''knapsack'''():
sn = N / 2
fn = N - sn
'''for''' mask = 0..2 ** sn - 1
'''for''' j = 0..sn
'''if''' j-ый бит mask == 1
first[i].w += w[j];
first[i].c += cost[j]
сортируем first по весу
'''for''' i = 0..2 ** sn - 1
'''if''' существует такое подмножество с индексом j, что first[j].w <tex> \leqslant </tex> first[i].w '''and''' first[j].c <tex> \geqslant </tex> first[i].c
удалим множество с индексом i из массива first

'''for''' mask = 0..2 ** fn - 1
'''for''' j = 0..fn
'''if''' j-ый бит mask == 1
curw += w[j + sn]
curcost += cost[j + sn]

index = позиция, найденная бинарным поиском в массиве first, подмножества с максимальным весом, не превыщающим R - curv
'''if''' first[index].w <tex> \leqslant </tex> R - curw '''and''' first[index].c + curcost <tex> > </tex> ans
ans = first[index].c + curcost
'''return''' ans

Итоговое время работы <tex> {O({2^{N/2}}\cdot({N}+\log{2^{N/2}}))} = O({2^{N/2}}\cdot{N}) </tex>.

== Задача о нахождении кратчайшего расстояния между двумя вершинами в графе ==
[[Файл:bfs.png|600px|thumb|right|Нахождение кратчайшего расстояния между двумя вершинами]]
Еще одна задача, решаемая '''Meet-in-the-middle''' — это нахождение кратчайшего расстояния между двумя вершинами, зная начальное состояние, конечное состояние и то, что длина оптимального пути не превышает <tex> N </tex>.
Стандартным подходом для решения данной задачи, является применение алгоритма [[Обход в ширину|обхода в ширину]]. Пусть из каждого состояния у нас есть <tex> K </tex> переходов, тогда бы мы сгенерировали <tex> {K^{N}} </tex> состояний. Асимптотика данного решения составила бы <tex> {O({K^{N}})} </tex>. '''Meet-in-the-middle''' помогает снизить асимптотику до <tex> {O({K^{N/2}})} </tex>. 
=== Алгоритм решения ===

1. Сгенерируем '''bfs'''-ом все состояния, доступные из начала и конца за <tex> {N/2} </tex> или меньше ходов.

2. Найдем состояния, которые достижимы из начала и из конца.

3. Найдем среди них наилучшее по сумме длин путей.

Таким образом, '''bfs-ом''' из двух концов, мы сгенерируем максимум <tex> {O({K^{N/2}})} </tex> состояний.

== См. также ==
* [[Обход в ширину]]
* [[Целочисленный двоичный поиск]]

==Cсылки==
*[http://infoarena.ro/blog/meet-in-the-middle Meet-in-the-middle]
*[http://g6prog.narod.ru/dpl.ps Лекции по информатике (36 страница)]

[[Категория: Дискретная математика и алгоритмы]]

[[Категория: Динамическое программирование ]]

Задача о редакционном расстоянии, алгоритм Вагнера-Фишера

2016-10-07T18:10:29Z

37.57.17.214: /* Память */ опечатки

{{Определение
|id=levenstain_dist
|definition=
'''Расстояние Левенштейна''' (англ. ''Levenshtein distance'') (также '''редакционное расстояние''' или '''дистанция редактирования''') между двумя строками в теории информации и компьютерной лингвистике — это минимальное количество операций вставки одного символа, удаления одного символа и замены одного символа на другой, необходимых для превращения одной строки в другую.}}

== Свойства ==

Для расстояния Левенштейна справедливы следующие утверждения:
* <tex>\rm{d}(S_1,S_2) \geqslant | |S_1| - |S_2| |</tex>
* <tex>\rm{d}(S_1,S_2) \leqslant max( |S_1| , |S_2| )</tex>
* <tex>\rm{d}(S_1,S_2) = 0 \Leftrightarrow S_1 = S_2</tex>
где <tex>\rm{d}(S_1,S_2)</tex> — расстояние Левенштейна между строками <tex>S_1</tex> и <tex>S_2</tex>, а <tex>|S|</tex> — длина строки <tex>S</tex>.

Расстояние Левенштейна является [[Метрическое пространство|метрикой]].
Для того чтобы доказать это достаточно доказать что выполняется неравенство треугольника:
* <tex>\rm{d}(S_1,S_3) \leqslant \rm{d}(S_1,S_2) + \rm{d}(S_2,S_3)</tex>

Пусть <tex>\rm{d}(S_1,S_3) = x</tex>, <tex>\rm{d}(S_1,S_2) = y</tex>, <tex>\rm{d}(S_2,S_3) = z</tex>. <tex>x</tex> — кратчайшее редакционное расстояние от <tex>S_1</tex> до <tex>S_3</tex>, <tex>y</tex> — кратчайшее редакционное расстояние от <tex>S_1</tex> до <tex>S_2</tex>, а <tex>z</tex> — кратчайшее редакционное расстояние от <tex>S_2</tex> до <tex>S_3</tex>. <tex>y + z</tex> — какое-то расстояние от <tex>S_1</tex> до <tex>S_3</tex>. В других случаях <tex>\rm{d}(S_1,S_3) < \rm{d}(S_1,S_2) + \rm{d}(S_2,S_3)</tex>. Следовательно, выполняется неравенство треугольника.

== Разные цены операций ==

Цены операций могут зависеть от вида операции (вставка, удаление, замена) и/или от участвующих в ней символов, отражая разную вероятность разных ошибок при вводе текста, и т. п. В общем случае:
* <tex>w(a, b)</tex> — цена замены символа <tex>a</tex> на символ <tex>b</tex>
* <tex>w(\varepsilon, b)</tex> — цена вставки символа <tex>b</tex>
* <tex>w(a, \varepsilon)</tex> — цена удаления символа <tex>a</tex>

Для решения задачи о редакционном расстоянии, необходимо найти последовательность замен, минимизирующую суммарную цену. Расстояние Левенштейна является частным случаем этой задачи при
* <tex>w(a, a) = 0</tex>
* <tex>w(a, b) = 1</tex> при <tex>a\ne b</tex>
* <tex>w(\varepsilon, b) = 1</tex>
* <tex>w(a, \varepsilon) = 1</tex>

<tex>\varepsilon</tex> — пустая последовательность.

Как частный случай, так и задачу для произвольных <tex>w</tex>, решает алгоритм Вагнера-Фишера, приведённый ниже. Здесь и ниже мы считаем, что все <tex>w</tex> неотрицательны, и действует правило треугольника: если две последовательные операции можно заменить одной, это не ухудшает общую цену (например, заменить символ <tex>x</tex> на <tex>y</tex>, а потом с <tex>y</tex> на <tex>z</tex> не лучше, чем сразу <tex>x</tex> на <tex>z</tex>).

== Формула ==

Будем считать, что элементы строк нумеруются с первого, как принято в математике, а не нулевого.

Пусть <tex>S_1</tex> и <tex>S_2</tex> — две строки (длиной <tex>M</tex> и <tex>N</tex> соответственно) над некоторым алфавитом, тогда редакционное расстояние <tex>\rm{d}(S_1, S_2)</tex> можно подсчитать по следующей рекуррентной формуле:

<tex>\ \rm{d}(S_1, S_2) = \rm{D}(M,N)</tex> , где

<tex>
D(i, j) = \left\{\begin{array}{llcl}
0&;\ i = 0,\ j = 0\\
i&;\ j = 0,\ i > 0\\
j&;\ i = 0,\ j > 0\\
D(i - 1, j - 1)&;\ S_1[i] = S_2[j]\\
\min{(}\\
\begin{array}{llcl}
&D(i, j - 1) + insertCost\\
&D(i - 1, j) + deleteCost&&\\
&D(i - 1, j - 1) + replaceCost\\
\end{array}&;\ j > 0,\ i > 0,\ S_1[i] \ne S_2[j]\\
)
\end{array}\right.
</tex>

<tex>\min(a, b, c)</tex> возвращает наименьший из аргументов.

=== Доказательство ===

Рассмотрим формулу более подробно. Здесь <tex>D(i, j)</tex> — расстояние между префиксами строк: первыми <tex>i</tex> символами строки <tex>S_1</tex> и первыми <tex>j</tex> символами строки <tex>S_2</tex>. Для нашей динамики должен выполняться [[Динамическое программирование|принцип оптимальности на префиксе]]. Очевидно, что редакционное расстояние между двумя пустыми строками равно нулю. Так же очевидно то, что чтобы получить пустую строку из строки длиной <tex>i</tex>, нужно совершить <tex>i</tex> операций удаления, а чтобы получить строку длиной <tex>j</tex> из пустой, нужно произвести <tex>j</tex> операций вставки. Осталось рассмотреть нетривиальный случай, когда обе строки непусты.

Для начала заметим, что в оптимальной последовательности операций, их можно произвольно менять местами. В самом деле, рассмотрим две последовательные операции:
* Две замены одного и того же символа — неоптимально (если мы заменили <tex>x</tex> на <tex>y</tex>, потом <tex>y</tex> на <tex>z</tex>, выгоднее было сразу заменить <tex>x</tex> на <tex>z</tex>).
* Две замены разных символов можно менять местами
* Два стирания или две вставки можно менять местами
* Вставка символа с его последующим стиранием — неоптимально (можно их обе отменить)
* Стирание и вставку разных символов можно менять местами
* Вставка символа с его последующей заменой — неоптимально (излишняя замена)
* Вставка символа и замена другого символа меняются местами
* Замена символа с его последующим стиранием — неоптимально (излишняя замена)
* Стирание символа и замена другого символа меняются местами

Пускай <tex>S_1</tex> кончается на символ <tex>a</tex>, <tex>S_2</tex> кончается на символ <tex>b</tex>. Есть три варианта:
# Символ «а», на который кончается <tex>S_1</tex>, в какой-то момент был стёрт. Сделаем это стирание первой операцией. Тогда мы стёрли символ <tex>a</tex>, после чего превратили первые <tex>i-1</tex> символов <tex>S_1</tex> в <tex>S_2</tex> (на что потребовалось <tex>D(i-1,\ j)</tex> операций), значит, всего потребовалось <tex>D(i-1,\ j)+1</tex> операций
# Символ <tex>b</tex>, на который кончается <tex>S_2</tex>, в какой-то момент был добавлен. Сделаем это добавление последней операцией. Мы превратили <tex>S_1</tex> в первые <tex>j-1</tex> символов <tex>S_2</tex>, после чего добавили <tex>b</tex>. Аналогично предыдущему случаю, потребовалось <tex>D(i,\ j-1)+1</tex> операций.
# Оба предыдущих утверждения неверны. Если мы добавляли символы справа от финального <tex>a</tex>, то чтобы сделать последним символом <tex>b</tex>, мы должны были или в какой-то момент добавить его (но тогда утверждение 2 было бы верно), либо заменить на него один из этих добавленных символов (что тоже невозможно, потому что добавление символа с его последующей заменой неоптимально). Значит, символов справа от финального <tex>a</tex> мы не добавляли. Самого финального <tex>a</tex> мы не стирали, поскольку утверждение 1 неверно. Значит, единственный способ изменения последнего символа — его замена. Заменять его 2 или больше раз неоптимально. Значит,
## Если <tex>a=b</tex>, мы последний символ не меняли. Поскольку мы его также не стирали и не приписывали ничего справа от него, он не влиял на наши действия, и, значит, мы выполнили <tex>D(i-1,\ j-1)</tex> операций.
## Если <tex>a\ne b</tex>, мы последний символ меняли один раз. Сделаем эту замену первой. В дальнейшем, аналогично предыдущему случаю, мы должны выполнить <tex>D(i-1,\ j-1)</tex> операций, значит, всего потребуется <tex>D(i-1,\ j-1)+1</tex> операций.

== Алгоритм Вагнера — Фишера ==

Для нахождения кратчайшего расстояния необходимо вычислить матрицу <tex>D</tex>, используя [[#Формула|вышеприведённую формулу]]. Её можно вычислять как по строкам, так и по столбцам.
Псевдокод алгоритма, написанный при произвольных ценах замен, вставок и удалений (важно помнить, что элементы нумеруются с <tex>1</tex>):

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

<code>
'''int''' '''levensteinInstruction'''('''String''' s1, '''String''' s2, '''int''' InsertCost, '''int''' DeleteCost, '''int''' ReplaceCost):
D[0][0] = 0
'''fo'''r j = 1 '''to''' N
D[0][j] = D[0][j - 1] + InsertCost
'''for''' i = 1 '''to''' M
D[i][0] = D[i - 1][0] + DeleteCost
'''for''' j = 1 '''to''' N
'''if''' S1[i] != S2[j]
D[i][j] = min(D[i - 1][j] + DeleteCost,
D[i][j - 1] + InsertCost,
D[i - 1][j - 1] + ReplaceCost)
'''else'''
D[i][j] = D[i - 1][j - 1]
'''return''' D[M][N]
</code>

=== Память ===

Алгоритм в виде, описанном выше, требует <tex>\Theta(M \cdot N)</tex> операций и такую же память, однако, если требуется только расстояние, легко уменьшить требуемую память до <tex>\Theta(N)</tex>. Заметим, что для вычисления <tex>D[i]</tex> нам нужно только <tex>D[i - 1]</tex>, поэтому будем вычислять <tex>D[i]</tex> в <tex>D[1]</tex>, а <tex>D[i - 1]</tex> в <tex>D[0]</tex>. Осталось только поменять местами <tex>D[1]</tex> и <tex>D[0]</tex>.

<code>
'''int''' '''levensteinInstruction'''('''int[]''' D):
'''for''' i = 0 '''to''' M
'''for''' j = 0 '''to''' N
вычислить D[1][j]
swap(D[0], D[1])
'''return''' D[0][N]
</code>

== Рекурсивный алгоритм ==
Для того, чтобы обеспечить время <tex>\Theta(M \cdot N)</tex> при памяти <tex>\Theta(\min(M,N))</tex>, определим матрицу <tex> E </tex> минимальных расстояний между ''суффиксами'' строк, то есть <tex> E(i, j) </tex> {{---}} расстояние между последними <tex> i </tex> символами <tex>S_1</tex> и последними <tex> j </tex> символами <tex>S_2</tex>. Очевидно, матрицу <tex> E </tex> можно вычислить аналогично матрице <tex> D </tex>, и так же быстро.

Теперь опишем алгоритм, считая, что <tex>S_2</tex> — кратчайшая из двух строк.

* Если длина одной из строк (или обеих) не больше <tex> 1 </tex>, задача тривиальна. Если нет, выполним следующие шаги.
* Разделим строку <tex>S_1</tex> на две подстроки длиной <tex>M/2</tex>. (Если <tex>M</tex> нечётно, то длины подстрок будут <tex>(M-1)/2</tex> и <tex>(M+1)/2</tex>.) Обозначим подстроки <tex>S_1^-</tex> и <tex>S_1^+</tex>.
* Для вычислим последнюю строку матрицы <tex> D </tex> для строк <tex>S_1^-</tex> и <tex>S_2</tex>, последнюю строку матрицы <tex> E </tex> для строк <tex>S_1^+</tex> и <tex>S_2</tex>.
* Найдём <tex> i </tex> такое, что <tex>D(|S_1^-|, i) + E(|S_1^+|, N-i)</tex> минимально. Здесь <tex> D </tex> и <tex> E </tex> {{---}} матрицы из предыдущего шага, но мы используем только их последние строки. Таким образом, мы нашли разбиение <tex>S_2</tex> на две подстроки, минимизирующее сумму расстояния левой половины <tex>S_1</tex> до левой части <tex>S_2</tex> и расстояния правой половины <tex>S_1</tex> до правой части <tex>S_2</tex>. Следовательно, левая подстрока <tex>S_2</tex> соответствует левой половине <tex>S_1</tex>, а правая {{---}} правой.
* Рекурсивно ищем редакционное предписание, превращающее <tex>S_1^-</tex> в левую часть <tex>S_2</tex> (то есть в подстроку <tex>S_2[1...i]</tex>)
* Рекурсивно ищем редакционное предписание, превращающее <tex>S_1^+</tex> в правую часть <tex>S_2</tex> (то есть в подстроку <tex>S_2[i+1...N]</tex>).
* Объединяем оба редакционных предписания.

===Псевдокод===

<code>
'''int''' '''levensteinInstruction'''('''String''' s1, '''String''' s2):
'''if''' s1.length <= 1 || s2.length <= 1
Решаем тривиально, возвращаем редакционное предписание
'''else'''
String s1l, s1r, s2l, s2r
'''if''' s2.length < s1.length
s1l = s1.substring(0, s1.length / 2) // S1-
s1r = s1.substring(s1.length / 2, s1.length) // S1+
 // d, e - массивы
d = '''calcD'''(s1l, s2) // Вычисляем последнюю строку матрицы D для S1- и S2
e = '''calcE'''(s1r, s2) // Вычисляем последнюю строку матрицы E для S1+ и S2
k = 0
'''for''' i = 1 '''to''' s2.length
'''if''' d[i] + e[s2.length - i] < d[k] + e[s2.length - k]
k = i
s2l = s2.substring(0, k)
s2r = s2.substring(k, s2.length)
'''else'''
 // s1 - меньшая строка
s2l = s2.substring(0, s2.length / 2) // S2-
s2r = s2.substring(s2.length / 2, s2.length) // S2+
d = '''calcD'''(s2l, s1) // Вычисляем последнюю строку матрицы D для S2- и S1
e = '''calcE'''(s2r, s1) // Вычисляем последнюю строку матрицы E для S2+ и S1
k = 0
'''for''' i = 1 '''to''' s1.length
'''if''' d[i] + e[s1.length - i] < d[k] + e[s1.length - k]
k = i
s1l = s1.substring(0, k)
s1r = s1.substring(k, s1.length)
'''return''' '''levensteinInstruction'''(s1l, s2l) + '''levensteinInstruction'''(s1r, s2r)

</code>

Время выполнения удовлетворяет (с точностью до умножения на константу) условию
: <tex>T(M,N)=MN+T(M/2,N')+T(M/2,N-N'),\ 0\leqslant N'\leqslant N</tex>,
Докажем:
: <tex>T(M,N) \leqslant 2MN</tex>
База индукции очевидна
: <tex>T(1,N) = N \leqslant 2N</tex>
Пусть для всех <tex>M' < M</tex> выполнено <tex>T(M',N') \leqslant 2M'N'</tex>.
Тогда учитывая <tex>T(M/2,N') \leqslant 2(M/2)N'</tex>, <tex>T(M/2,N-N') \leqslant 2(M/2)(N-N')</tex>, получим:
: <tex>T(M,N)=MN+T(M/2,N')+T(M/2,N-N') \leqslant</tex> <tex> MN+2(M/2)N'+2(M/2)(N-N')=2MN</tex>
следовательно
: <tex>T(M,N) = \Theta(M \cdot N)</tex>

Для вычисления последних строк матриц <tex> D, ~E </tex> можно использовать два глобальных двумерных массива размера <tex>2 \times (\min(M, N)+1)</tex>.

Т.к. мы вычисляем функцию рекурсивно, требуемый размер стека тоже следует учесть. На стек вызовов потребуется <tex>\Theta(\log(\max(M,N))</tex> памяти, потому общая оценка использования памяти будет <tex> \Theta(\min(M,N)) </tex>

== Редакционное предписание ==

'''Редакционное предписание''' (англ. ''Editorial prescription'') — последовательность действий, необходимых для получения из первой строки второй кратчайшим образом. Обычно действия обозначаются так: '''D''' (англ. delete) — удалить, '''I''' (англ. insert) — вставить, '''R''' (англ. replace) — заменить, '''M''' (англ. match) — совпадение.

Например, для 2-х строк «hell123» и «hello214» можно построить следующую таблицу преобразований:
{| class="wikitable"
!'''M''' ||'''M''' ||'''M''' ||'''M''' ||'''R''' ||'''M''' ||'''R''' ||'''I'''
|-
|h ||e ||l ||l ||1 ||2||3 ||
|-
|h ||e||l ||l ||o ||2 ||1 ||4
|}

==См. также==
*[[Задача о расстоянии Дамерау-Левенштейна]]

== Источники информации ==
*[http://en.wikipedia.org/wiki/Levenshtein_distance Wikipedia {{---}} Levenshtein distance]

*[http://pastie.org/5574488 Реализация рекурсивного алгоритма поиска редакционного предписания на языке Java]

*Романовский И.В. "Дискретный анализ". Третье издание. Стр. 103 - 105

[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Динамическое программирование]]