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

Skip quadtree: определение, время работы

2014-01-20T15:27:11Z

93.92.200.173:

{{ready}}
== Описание ==
[[Файл:Skip_quadtree.png | 500px | thumb | По картинке должно быть понятно]]
Skip quadtree {{---}} как skip list, только вместо list'а quadtree. Поэтому желательно знать, что такое [[Список с пропусками | skip list]], и необходимо знать, что такое [[Квадродеревья#Сжатое квадродерево | сжатое квадродерево]]. В данной статье будет рассматриваться только рандомизированая версия этой структуры, потому что больше и не нужно, кажется.

The randomized skip quadtree {{---}} последовательность сжатых квадродеревьев над последовательностью подмножеств некоторого исходного множества <tex>S</tex>. <tex>S_0 = S</tex>, в <tex>S_1</tex> каждый элемент из <tex>S_0</tex> входит с вероятностью <tex>p \in (0, 1)</tex> и так далее. The randomized skip quadtree состоит из последовательности <tex>\{Q_i\}</tex>, где <tex>Q_i</tex> {{---}} сжатое квадродерево над множеством <tex>S_i</tex>. Будем называть эти квадродеревья уровнями, при этом нулевой уровень содержит в точности точки из <tex>S</tex>.
Заметим, что если какой-то квадрат [[Квадродеревья и перечисление точек в произвольном прямоугольнике (статика)#interesting | интересный]] в <tex>Q_i</tex>, то он интересный и в <tex>Q_{i-1}</tex>.

== Операции над skip quadtree ==
Будем для каждого интересного квадрата на каждом уровне хранить указатели на тот же квадрат уровнем ниже и уровнем выше (если есть).

Локализация выполняется аналогично сжатому квадродереву. Под локализацией подразумевается, что мы хотим найти минимальный интересный квадрат, содержащий данную точку (содержит геометрически, в самом дереве её может не быть, тут, возможно, правильнее сказать «пересекает»). Сначала локализуемся в квадродереве наибольшего уровня, начиная с его корня. Затем локализуемся в квадродереве уровня ниже, начиная уже не с корня, а с того квадрата, который нашли на прошлом уровне. И так далее, пока не дойдём до дна.

Для добавления сначала надо локализоваться. При этом мы локализуемся сразу на всех уровнях (так уж устроен процесс). Дальше добавляемся в нулевой уровень, затем с вероятностью <tex>p</tex> добавляемся на уровень выше и так далее до первого недобавления. При этом количество уровней должно увеличиться максимум на 1, то есть, если появился новый уровень, то процесс точно заканчивается. Хотя не, давайте без последнего условия, вроде с ним только лучше, но без него проще доказывать.

Удаление совсем просто: локализуемся, удаляем со всех уровней, на которых есть. При этом какой-то уровень мог стать пустым, в таком случае выкинем его.

== Время работы и память ==

{{Лемма
|about=
О количестве шагов на одном уровне
|statement=
На каждом уровне в среднем совершается <tex>O(1)</tex> шагов поиска для любой точки <tex>x</tex>.
|proof=
Пусть в <tex>Q_i</tex> (то есть на <tex>i</tex>-ом уровне) поиск точки <tex>x</tex>, начинающийся с корня, проходит по квадратам <tex>p_0, p_1, \dots, p_m</tex>. Пусть случайная величина <tex>j</tex> {{---}} количество шагов поиска в <tex>Q_i</tex>, тогда <tex>p_{m - j}</tex> {{---}} последний квадрат из <tex>p_0, p_1, \dots, p_m</tex>, являющийся интересным в <tex>Q_{i + 1}</tex>.

Оценим вероятность того, что делается <tex>j</tex> шагов. Забьём на случай <tex>j = 0</tex>, так как он не важен при расчёте мат. ожидания. На пути <tex>p_{m - j + 1} \dots, p_m</tex> будет хотя бы <tex>j + 1</tex> непустых четвертинок. У первого квадрата на этом пути есть хотя бы 2 непустые четвертинки, одна из них {{---}} следующий квадрат на пути, в котором тоже хотя бы 2 непустые четвертинки, и так далее. В последнем квадрате просто хотя бы 2 непустые четвертинки. Чтобы
<tex>p_{m - j}</tex> был последним из <tex>p_0, p_1, \dots, p_m</tex> интересным квадратом в <tex>Q_{i + 1}</tex> небходимо, чтобы среди этих как минимум <tex>j + 1</tex> непустых четвертинок только одна (вероятность этого назовём <tex>Pr_1</tex>) или ноль (вероятность этого назовём <tex>Pr_0</tex>) были непустыми в <tex>Q_{i + 1}</tex>. Иначе, если будет хотя бы пара непустых четвертинок, то их наименьший общий предок в дереве будет интересным квадратом и будет находиться глубже <tex>p_{m - j}</tex>. Таким образом, искомая вероятность не превосходит <tex>Pr_0 + Pr_1</tex>.

''Лично мне утверждение из предыдущего абзаца далось с трудом, если у вас тоже всё очень плохо, попробуйте напрячь мозг и залипнуть в картинку, вдруг поможет. Хотя я постарался расписать поподробней, чем в статье.''

<tex>q = 1 - p</tex>

<tex>Pr_0 \leq q^{(j + 1)}</tex>, потому что это в сущности вероятность того, что ни одна точка из как минимум <tex>j + 1</tex> непустых четвертинок не попала на уровень выше.

<tex>Pr_1 \leq (j + 1) \cdot pq^j</tex>, потому что это в сущности вероятность того, что ровно одна точка из как минимум <tex>j + 1</tex> непустых четвертинок попала на уровень выше.

''В общем, если чуть подумать, оценки на <tex>Pr_0</tex> и <tex>Pr_1</tex> довольно ясны.''

<tex>E(j) = \sum\limits_{j = 1}^{m} j \cdot Pr(j) \leq \sum\limits_{j = 1}^{m} j \cdot (q^{(j + 1)} + (j + 1) \cdot pq^j) \leq \sum\limits_{j = 1}^{\infty} j \cdot (q^{(j + 1)} + (j + 1) \cdot pq^j)</tex>

Это почти геометрическая прогрессия, только на полином домножили, определяется всё экспоненциальным множителем, так что это <tex>O(1)</tex>. Можно совсем строго оценить, но и так понятно, что ряд сходится, а сойтись он может только к константе.
}}

{{Лемма
|about=
О количестве уровней
|statement=
Математическое ожидание количества уровней составляет <tex>O(\log(n))</tex>
|proof=
Для оценки мат. ожидания посчитаем вероятность того, что количество уровней <tex>h</tex> равно <tex>k</tex>. <tex>p(h = k) = p(h \leq k) \cdot p(h \geq k)</tex>.

<tex>p(h \leq k) = (1 - p^{k + 1})^n</tex>, потому что вероятность того, что точка дойдёт до уровня <tex>k + 1</tex>, равна <tex>p^{k + 1}</tex>.

<tex>p(h \geq k) = (1 - (1 - p^k)^n)</tex>, потому что вероятность того, что точка не дойдёт до уровня <tex>k</tex>, равна <tex>1 - p^k</tex>.

''А вот нифига не так, я тут понял. Там зависимые события, поэтому перемножать вероятности так нельзя, но всё не сильно портится. <tex>p(h = k) = 1 - p(h > k) - p(h < k) = 1 - (1 - (1 - p^{k + 1})^n) - (1 - p^{k})^n = (1 - p^{k + 1})^n - (1 - p^k)^n \leq 1 - (1 - p^k)^n \leq np^k</tex>, и дальше этой оценки достаточно.''

<tex>E(h) = \sum\limits_{k = 1}^{\infty} k \cdot p(h = k) = p(1) \cdot 1 + \dots + p(\log_{1/p} n) \cdot \log_{1/p} n + \sum\limits_{k = \log_{1/p} n + 1}^{\infty} k \cdot p(k)</tex>

Оценим первую сумму:

<tex>p(1) \cdot 1 + \dots + p(\log_{1/p} n) \cdot \log_{1/p} n \leq p(1) \cdot \log_{1/p} n + \dots + p(\log_{1/p} n) \cdot \log_{1/p} n = O(\log(n))</tex>, поскольку сумма этих вероятностей не превосходит единицу.

Оценим вторую сумму:

<tex>\sum\limits_{k = \log_{1/p} n + 1}^{\infty} k \cdot p(k) = \leq \sum\limits_{k = \log_{1/p} n}^{\infty} k \cdot n p^k = n \cdot \sum\limits_{k = \log_{1/p} n}^{\infty} k \cdot p^k</tex>

Рассмотрим эту сумму:

<tex>\sum\limits_{k = \log_{1/p} n}^{\infty} k \cdot p^k = p^{\log_{1/p} n} \cdot \sum\limits_{k = 0}^{\infty} (k + \log_{1/p} n) \cdot p^k = p^{\log_{1/p} n} \cdot (\sum\limits_{k = 0}^{\infty} (k p^k) + \log_{1/p} n \cdot \sum\limits_{k = 0}^{\infty} (p^k)) = p^{\log_{1/p} n} \cdot (O(1) + \log_{1/p} n \cdot O(1)) = 1/n \cdot O(\log(n))</tex>

Суммируя всё вышесказанное, получаем, что <tex>O(\log(n))</tex>.

''Для лучшего понимания можно представлять, что <tex>p = 1/2</tex>.''
}}

{{Теорема
|about=
О времени работы
|statement=
Поиск, добавление и удаление точки работают за <tex>O(\log(n))</tex> в среднем.
|proof=
Достаточно очевидно из предыдущих лемм.
}}

{{Теорема
|about=
О занимаемой памяти
|statement=
Математическое ожидание занимаемой памяти {{---}} <tex>O(n)</tex>.
|proof=
Сжатое квадродерево для <tex>n</tex> точек занимает <tex>O(n)</tex> памяти. На нулевом уровне <tex>n</tex> точек. На следующем уровне <tex>p \cdot n</tex> точек, дальше <tex>p^2 \cdot n</tex> и так далее. Получим геометрическую прогрессию, в итоге <tex>O(n)</tex> памяти.
}}

== В чём профит? ==
Как и [[Перечисление точек в произвольном прямоугольнике за n * log ^(d - 1) n (range tree) | range tree]], данная структура умеет выдавать точки, принадлежащие какому-то прямоугольнику, алгоритм очень похож на тот, который применяется в range tree. Только ответ на запрос происходит за <tex>O(\log n + k)</tex> (вроде бы независимо от размерности, хотя квадродерево подразумевает двумерное пространство, но для обобщения на больше размерности асимптотика будет та же, кажется). И памяти нужно <tex>O(n)</tex>. Этим skip quadtree круче.

=== Как отвечать на запрос ===
Сначала локализуем все четыре точки прямоугольника

''Я тут понял, что пока не знаю, как это делать, сейчас буду думать.''

''Всё очень плохо, я тупой, меня можно побить.''

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

== Источник ==
http://arxiv.org/pdf/cs.cg/0507049.pdf

[[Категория: Вычислительная геометрия]]

Разрешимые (рекурсивные) языки

2013-12-21T12:32:27Z

93.92.200.173: Добавил id к определению универсального языка, чтобы ссылаться на него из других конспектов

{{Определение
|definition=Язык <tex>L</tex> называется '''разрешимым''' ('''рекурсивным, recursive language'''), если существует такая программа <tex> p </tex>, что <tex> \forall w \in L: p(w) = 1</tex>, а <tex> \forall w \notin L: p(w) = 0</tex>. Класс всех разрешимых языков часто обозначается через <tex> \mathrm{R} </tex>.
}}

==Пример разрешимого множества==
{{Лемма
|id=st1
|statement=
Язык чётных чисел разрешим.
|proof=
Приведём программу, разрешающую язык чётных чисел:
<tex>p(i):</tex>
'''if''' <tex> i \ mod \ 2 == 0 </tex>
'''return''' <tex> 1 </tex>
'''else'''
'''return''' <tex> 0 </tex>
Заметим, что программа нигде не может зависнуть.
}}

==Пример неразрешимого множества==

{{Определение
|id=uni
|definition=Язык <tex>\ U = \{\langle p, x \rangle \ |\ p(x) = 1\} </tex> называется '''универсальным''' ('''universal language''').
}}

{{Лемма
|id=st1
|statement=
Универсальный язык неразрешим.
|proof=
Приведём доказательство от противного. <br/>
Пусть язык <tex> U </tex> разрешим. Тогда существует такая программа <tex> u </tex>, что <tex> \forall \langle p, x \rangle \in U: u(\langle p, x \rangle) = 1</tex>, а <tex> \forall \langle p, x \rangle \notin U: u(\langle p, x \rangle) = 0</tex>. <br/>
Составим следующую программу:

<tex>r(x):</tex>
'''if''' <tex> u(\langle x, x \rangle) == 1 </tex>
'''while''' <tex> true </tex>
'''else'''
'''return''' <tex> 1 </tex>

Теперь рассмотрим вызов <tex> r(r) </tex>:
* если <tex> u(\langle r, r \rangle) = 1 </tex>, то условие '''if''' выполнится и программа зависнет. Но так как программа <tex> u </tex> разрешает универсальный язык, <tex> u(\langle r, r \rangle) = 1 \Rightarrow r(r) = 1</tex>;
* если <tex> u(\langle r, r \rangle) = 0 </tex>, то условие '''if''' не выполнится и программа вернет <tex>1</tex>. Но так как программа <tex> u </tex> разрешает универсальный язык, <tex> u(\langle r, r \rangle) = 0 \Rightarrow r(r) \ne 1</tex>.

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

== Источники ==
* Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. — М.: МЦНМО, 1999. С. 134. ISBN 5-900916-36-7
* [http://en.wikipedia.org/wiki/Recursive_language Wikipedia — Recursive language]
* [http://ru.wikipedia.org/wiki/%D0%A0%D0%B5%D0%BA%D1%83%D1%80%D1%81%D0%B8%D0%B2%D0%BD%D1%8B%D0%B9_%D1%8F%D0%B7%D1%8B%D0%BA Википедия — Рекурсивный язык]

[[Категория: Теория формальных языков]]
[[Категория: Теория вычислимости]]

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

2013-06-11T18:34:13Z

93.92.200.173:

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

'''Декартово дерево''' {{---}} это структура данных, объединяющая в себе бинарное дерево поиска и бинарную кучу (отсюда и второе её название: 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>T_1</tex> и <tex>T_2</tex>, причем в <tex>T_1</tex>
находятся все ключи дерева <tex>T</tex>, не большие <tex>k</tex>, а в <tex>T_2</tex> {{---}} большие <tex>k</tex>.

<tex>\mathrm{Split}(T, k) \to \{T_1, T_2\}</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>.

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

Псевдокод:
<pre>
Split(Treap t, int k, Treap &t1, Treap &t2)
if t == NULL
t1 = t2 = NULL;
else if k > t.x
Split(t.right, k, t.right, t2);
t1 = t;
else
Split(t.left, k, t1, t.left);
t2 = t;
</pre>

Оценим время работы операции <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>.

Псевдокод:
<pre>
Merge(Treap &t, Treap t1, Treap t2)
if t1 == NULL or t2 == NULL
if t1 != NULL
t = t1;
else
t = t2;
else if t1.y > t2.y
Merge(t1.right, t1.right, t2);
t = t1;
else
Merge(t2.left, t1, t2.left);
t = t2;
</pre>

Рассуждая аналогично операции <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 \{T_1, T_2\}</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 \{T_1, T_2\}</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 \{T_1, T_2\}</tex>.
# Теперь отделяем от первого дерева элемент <tex>x</tex>, опять таки разбивая по ключу <tex>x</tex>, то есть <tex>\mathrm{Split }(T_1, k.x - \varepsilon) \to \{T_1, T_3\}</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>y_1 , y_2 , \ldots , y_n</tex> и выберем максимум среди них, пусть это будет <tex>y_k</tex>, и сделаем <tex>(x_k, y_k)</tex> корнем дерева (по свойству [[Двоичная куча|пирамиды]] в корне должен быть элемент с максимальным приоритетом). Проделав то же самое с <tex>y_1 , y_2 , \ldots , y_{k-1}</tex> и <tex>y_{k+1} , y_{k+2} , \ldots , y_n</tex>, получим соответственно левого и правого сына <tex>(x_k, y_k)</tex>.

Такой алгоритм работает за <tex>O(n^2)</tex>.

=== Алгоритм за O(n) ===
Будем строить дерево слева направо, то есть начиная с <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} \frac{1}{k - i + 1} &&, k \ > \ i\\
0 &&, k\ =\ i\\
\frac{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} \frac{1}{k - i + 1} + \sum\limits_{i = k + 1}^{n} \frac{1}{i - k + 1} \le \ln(k) + \ln(n-k) + 2</tex> (здесь мы использовали неравенство <tex>\sum\limits_{i = 1}^{n} \frac{1}{i} \le \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]

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

Алгоритм Эдмондса-Карпа

2013-06-01T19:12:27Z

93.92.200.173:

== Алгоритм ==

Для заданной сети <tex>G(V, E, c)</tex> алгоритм Эдмондса-Карпа находит поток максимальной величины из заданного истока <tex>s</tex> в заданный сток <tex>t</tex> за <tex>O(V E^2)</tex>.

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

'''Edmonds_Karp''' (G, s, t)
'''for''' (для) каждого ребра <tex>(u,v) \in E[G]</tex>
'''do''' <tex>f[u,v] \leftarrow 0</tex>
<tex>f[v,u] \leftarrow 0</tex>
'''while''' существует ''кратчайший'' путь <tex>p</tex> из <tex>s</tex> в <tex>t</tex> в остаточной сети <tex>G_f</tex>
'''do''' <tex>c_f(p) \leftarrow min\{c_f(u,v) : (u,v) \in p\}</tex>
'''for''' (для) каждого ребра <tex>(u,v) \in p</tex>
'''do''' <tex>f[u,v] \leftarrow f[u,v] + c_f(p)</tex>
<tex>f[v,u] \leftarrow -f[u,v]</tex>

== Корректность алгоритма Эдмондса-Карпа ==

Алгоритм Эдмондса-Карпа является реализацией метода [[Алгоритм Форда-Фалкерсона для поиска максимального паросочетания|Форда-Фалкерсона]]. На каждой итерации цикла '''while''' поток в графе <tex>G</tex> увеличивается вдоль одного из кратчайших путей в <tex>G_f</tex> из истока <tex>s</tex> в сток <tex>t</tex>. Этот процесс повторяется до тех пор пока существует кратчайший <tex>s \leadsto t</tex> путь в <tex>G_f</tex>. Если в <tex>G_f</tex> не существует кратчайшего пути из <tex>s</tex> в <tex>t</tex>, значит, не существует никакого вообще никакого <tex>s \leadsto t</tex> пути в <tex>G_f</tex> следовательно по [[Теорема Форда-Фалкерсона|теореме Форда-Фалкерсона]] найденный поток <tex>f</tex> максимальный.

== Оценка быстродействия ==

{{Лемма
|id=lemma1
|statement=
Если в сети <tex>G(V,E)</tex> с источником <tex>s</tex> и стоком <tex>t</tex> увеличение потока производится вдоль кратчайших <tex>s \leadsto t</tex> путей в <tex>G_f</tex>, то для всех вершин <tex>v \in V\backslash\{s,t\}</tex> длина кратчайшего пути <tex>\delta_f(s, v)</tex> в остаточной сети <tex>G_f</tex> не убывает после каждого увеличения потока.
|proof=
Предположим противное, пусть существует вершина <tex>v \in V \backslash\{s,t\}</tex>, что после какого-то увеличения потока длина кратчайшего пути из <tex>s</tex> в <tex>v</tex> уменьшилась. Обозначим потоки до и после увеличения соответственно за <tex>f</tex> и <tex>f'</tex>. Пусть <tex>v</tex> {{---}} вершина, расстояние <tex>\delta'_f(s,v)</tex> от <tex>s</tex> до которой минимально и уменьшилось с увеличением потока. Имеем <tex>\delta'_f(s,v) < \delta_f(s,v)</tex>. Рассмотрим путь <tex>p = s \leadsto u \rightarrow v</tex>, являющийся кратчайшим от <tex>s</tex> к <tex>v</tex> в <tex>G'_f</tex>. Тогда верно, что <tex>\delta'_f(s, u) = \delta'_f(s,v) - 1</tex>.

По выбору <tex>v</tex> и из предыдущего утверждения получаем, что <tex>\delta'_f (s, u) \ge \delta_f(s,u)</tex>.

Предположим <tex>(u, v) \in E_f</tex>, тогда <tex>\delta_f(s,v) \le \delta_f(s, u) + 1 \le \delta'_f(s,u) + 1 = \delta'_f(s, v)</tex>. Это противоречит <tex>\delta'_f(s,v) < \delta_f(s,v)</tex>.

Пусть <tex>(u,v) \notin E_f</tex>, но известно, что <tex>(u,v) \in E_f'</tex>. Появление ребра <tex>(u,v)</tex> после увеличения потока означает увеличение потока по обратному ребру <tex>(v, u)</tex>. Увеличение потока производится вдоль кратчайшего пути, поэтому кратчайший путь из <tex>s</tex> в <tex>u</tex> вдоль которого происходило увеличения выглядит как <tex>s \leadsto v \rightarrow u</tex>, из чего получаем <tex>\delta_f(s, v) = \delta_f(s, u) - 1 \le \delta'_f(s, u) - 1 = \delta'(s, v) - 2</tex>. Данное утверждение противоречит <tex>\delta'_f(s,v) < \delta_f(s,v)</tex>. Итак мы пришли к противоречию с существованием вершины <tex>v</tex>, кратчайшее расстояние до которой уменьшилось с увеличением потока.
}}

Опираясь на предшествующую лемму, докажем следующую теорему, которая ограничивает сверху число итераций цикла '''while''' в алгоритме Эдмондса-Карпа.

{{Теорема
|statement=Пусть для некоторой сети <tex>G(V,E)</tex> с источником <tex>s</tex> и стоком <tex>t</tex> выполняется алгоритм Эдмондса-Карпа, то общее число итераций цикла '''while''' составляет <tex>O(V E)</tex>.
|proof=
Рассмотрим множество ребер <tex>(u,v)</tex> остаточной сети <tex>G_f</tex>, принадлежащих увеличивающему пути <tex>p</tex>, таких что <tex>c_f(p) = c_f(u,v)</tex>. Назовем данные ребра критическими. Покажем, что каждое из <tex>|E|</tex> ребер может становиться критическим не более, чем <tex>|V| - 1</tex> раз. Заметим, что после увеличения потока вдоль пути <tex>p</tex> все критические ребра исчезают из остаточной сети, кроме того по определению остаточной пропускной способности пути хотя бы одно ребро увеличивающего пути {{---}} критическое.

Рассмотрим две вершины <tex>u</tex> и <tex>v</tex> принадлежащие <tex>V</tex>, соединенные некоторым ребром из <tex>E</tex>. Увеличение производится вдоль кратчайших путей, поэтому если ребро <tex>(u,v)</tex> становиться критическим в первый раз, верно, что <tex>\delta_f(s,v) = \delta_f(s,u) + 1</tex>. После увеличения потока ребро <tex>(u, v)</tex> исчезает из сети. Оно не появится в другом увеличивающем пути до тех, пор пока не будет уменьшен по обратному ребру <tex>(v, u)</tex>. Это может произойти только в том случае, если ребро <tex>(v, u)</tex> встретится на некотором увеличивающем пути. Пусть в момент перед увеличением поток в сети <tex>G</tex> составлял <tex>f'</tex>, то поскольку увеличение производиться вдоль кратчайших путей, верно: <tex>\delta'_f(s,u) = \delta'_f(s, v) + 1</tex>. Согласно [[#lemma1|лемме]] <tex>\delta_f(s,v) \le \delta'_f(s,v)</tex>, откуда <tex>\delta'_f(s,u) = \delta'(s,v) + 1 \ge \delta_f(s,v) + 1 = \delta_f(s,u) + 2</tex>.

Итак в промежуток времени между тем, когда ребро <tex>(u,v)</tex> становится критическим в первый раз, до момента, когда оно становится критическим в следующий раз, расстояние от <tex>s</tex> до <tex>u</tex> увеличивается минимум на <tex>2</tex>. Расстояние <tex>\delta(s,u)</tex> в начальный момент времени больше либо равно <tex>0</tex>. Среди промежуточных вершин на кратчайшем пути <tex>s \leadsto u</tex> не могут находиться <tex>s</tex>, <tex>u</tex> или <tex>t</tex>. Следовательно к тому моменту, когда вершина <tex>u</tex> станет недостижимой из источника расстояние до нее не превысит <tex>|V| - 2</tex>. Получаем, что ребро <tex>(u, v)</tex> могло стать критическим не более <tex>(|V| -2)/2 = |V|/2 - 1</tex> раз. Поскольку в графе не более <tex>O(E)</tex> пар вершин, между которыми могут существовать ребра в остаточной сети, то общее количество критических ребер в ходе выполнения алгоритма Эдмондса-Карпа равно <tex>O(V E)</tex>.

Так как каждый увеличивающий путь содержит по крайней мере одно критическое ребро, следовательно число кратчайших путей составляет <tex>O(V E)</tex>. На каждой итерации цикла '''while''' рассматривается ровно один увеличивающий путь, а поскольку в случае отсутствия такого пути выполнение цикла прерывается, то число итераций цикла '''while''' также составляет <tex>O(V E)</tex>.
}}

Если увеличивающий путь находить поиском в ширину, то каждую итерацию цикла '''while''' можно выполнить за время <tex>O(E)</tex>. Инициализация в процедуре '''Edmonds_Karp''' производится за <tex>O(E)</tex>, следовательно время работы алгоритма алгоритма Эдмондса-Карпа составляет <tex>O(V E^2)</tex>. Заметим также, что сущетсвует сеть [http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=maxFlowRevisited "грибок"] на которой нижняя граница времени работы алгоритмы Эдмондса-Карпа также составляет <tex>\Omega(V E^2)</tex>.

== Литература ==
* ''Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд'' '''Алгоритмы: построение и анализ''', 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Задача о максимальном потоке]]