4446
правок
Задача присваивания: различия между версиями
Материал из WEGA
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 42: | Строка 42: | ||
Стоит отметить следующее свойство данного алгоритма: | Стоит отметить следующее свойство данного алгоритма: | ||
<math>\bar{S} = X \backslash S \;</math>. | |||
<math>\bar{T} = Y \backslash T \;</math>. | |||
<math>|S| > |T| \;</math>. | |||
Поскольку метки в S уменьшаются, ребра (в графе G), ведущие из S в T, потенциально могут попасть в подграф равенства Gi. По мере увеличения значения A в какой-то момент ребро окажется в подграфе равенства. В этот момент процесс следует остановить и обновить венгерское дерево. Если вершина из T, добавленная к T, сопоставлена с вершиной из S, обе эти вершины перемещаются в S и T, что увеличивает размер венгерского дерева. Если вершина из T свободна, то дополняющий путь найден и данный этап завершен. Этап состоит из таких шагов, выполненных между приращениями размера паросочетания. Поскольку в G всего n вершин, у алгоритма будет не более n этапов, поскольку на каждом этапе размер паросочетания увеличивается на 1. В рамках каждого этапа размер венгерского дерева увеличивается не более n раз. Очевидно, что за время O( | Между S и <math>\bar{T}</math> не имеется ребер, поскольку в противном случае не было бы возможности полностью вырастить венгерские деревья. Поскольку венгерские деревья выращиваются в G^, альтернативные вершины в поиске помещаются в S и T. Для обновления меток следует взять метки из S и начать равномерно уменьшать их (скажем, на значение A), в то же время увеличивая метки в T на то же значение A. Этот подход гарантирует, что ребра, ведущие из S в T, не исчезнут из подграфа равенства (рис. 1). | ||
Поскольку метки в S уменьшаются, ребра (в графе G), ведущие из S в <math>\bar{T}</math>, потенциально могут попасть в подграф равенства Gi. По мере увеличения значения A в какой-то момент ребро окажется в подграфе равенства. В этот момент процесс следует остановить и обновить венгерское дерево. Если вершина из <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>. | |||
| Строка 67: | Строка 71: | ||
Интуитивно кажется, что вычисление Я требует O(n2) времени. Для каждой вершины y | Интуитивно кажется, что вычисление Я требует O(n2) времени. Для каждой вершины <math>y \in \bar{T} \;</math> отметим ребро с минимальным провисом, т.е. | ||
slack[y] = min slack(x; y): | slack[y] = min slack(x; y): | ||
x2S | x2S | ||
Вычисление slack[y] для всех y | Вычисление slack[y] для всех <math>y \in \bar{T} \;</math> требует <math>O(n^2) \;</math> времени в начале этапа. По мере продвижения по данному этапу все значения провисов легко обновляются за время O(n), поскольку все они изменяются на одну и ту же величину (метки вершин из S уменьшаются равномерным образом). При перемещении вершины u из <math>\bar{S}</math> в S необходимо перевычислить провисы вершин в <math>\bar{T}</math>, что требует O(n) времени. Однако перемещать вершину из <math>\bar{S}</math> в S можно не более n раз. | ||
