4446
правок
Задача присваивания: различия между версиями
Материал из WEGA
м
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| (не показана 1 промежуточная версия этого же участника) | |||
| Строка 12: | Строка 12: | ||
<math>\forall y \in Y \; \; \; \ell(y) = 0</math> | <math>\forall y \in Y \; \; \; \ell(y) = 0</math> | ||
<math>\forall x \in X \; \; \; \ell(x) = max_{y \in Y} \; w(x, y).</math> | <math>\forall x \in X \; \; \; \ell(x) = max_{y \in Y} \; w(x, y).</math> | ||
| Строка 27: | Строка 25: | ||
Действительно, заметим, что сумма меток является верхней границей веса совершенного паросочетания с максимальным весом. Алгоритм последовательно находит паросочетание и допустимую разметку, такие, что вес паросочетания оказывается равен сумме всех меток. | |||
| Строка 41: | Строка 39: | ||
Стоит отметить | Стоит отметить следующие свойства данного алгоритма: | ||
<math>\bar{S} = X \backslash S \;</math>. | <math>\bar{S} = X \backslash S \;</math>. | ||
| Строка 53: | Строка 51: | ||
Поскольку метки в S уменьшаются, ребра (в графе G), ведущие из S в <math>\bar{T}</math>, потенциально могут попасть в подграф равенства <math>G_{ \ell}\;</math>. По мере увеличения значения <math>\lambda \;</math> в какой-то момент ребро окажется в подграфе равенства. В этот момент процесс следует остановить и обновить венгерское дерево. Если вершина из <math>\bar{T}</math>, добавленная к T, сопоставлена с вершиной из <math>\bar{S}</math>, обе эти вершины перемещаются в S и T, что увеличивает размер венгерского дерева. Если вершина из <math>\bar{T}</math> свободна, то дополняющий путь найден и данный этап завершен. Этап состоит из таких шагов, выполненных между приращениями размера паросочетания. Поскольку в G всего n вершин, у алгоритма будет не более n этапов, | Поскольку метки в S уменьшаются, ребра (в графе G), ведущие из S в <math>\bar{T}</math>, потенциально могут попасть в подграф равенства <math>G_{ \ell}\;</math>. По мере увеличения значения <math>\lambda \;</math> в какой-то момент ребро окажется в подграфе равенства. В этот момент процесс следует остановить и обновить венгерское дерево. Если вершина из <math>\bar{T}</math>, добавленная к T, сопоставлена с вершиной из <math>\bar{S}</math>, обе эти вершины перемещаются в S и T, что увеличивает размер венгерского дерева. Если вершина из <math>\bar{T}</math> свободна, то дополняющий путь найден и данный этап завершен. Этап состоит из таких шагов, выполненных между приращениями размера паросочетания. Поскольку в G всего n вершин, у алгоритма будет не более n этапов, так как на каждом этапе размер паросочетания увеличивается на 1. В рамках каждого этапа размер венгерского дерева увеличивается не более n раз. Очевидно, что за время <math>O(n^2) \;</math> можно обнаружить, какое ребро, ведущее из S в <math>\bar{T}</math>, первым войдет в подграф равенства (для этого нужно просто просмотреть все ребра). Общее время выполнения в таком случае составит <math>O(n^4) \;</math>. Теперь покажем, как реализовать этот подход за время <math>O(n^3) \;</math>. | ||
