4446
правок
Задача присваивания: различия между версиями
Материал из WEGA
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 30: | Строка 30: | ||
Вышеприведенная теорема служит основой алгоритма нахождения паросочетания с максимальным весом в полном двудольном графе. Начав с допустимой разметки, вычислим подграф равенства и затем найдем максимальное паросочетание в этом подграфе (на этом этапе веса ребер не учитываются). Если найденное паросочетание является совершенным, процесс на этом завершается. В противном случае к подграфу равенства добавляются ребра посредством пересмотра меток вершин. После добавления ребер к подграфу равенства либо увеличивается размер паросочетания (был найден дополняющий путь), либо продолжает расти венгерское дерево.1 В первом случае этот этап процесса завершается и начинается новый (поскольку размер паросочетания вырос). Во втором случае венгерское дерево растет за счет добавления к нему новых вершин, что, очевидно, не может произойти более n раз. | Вышеприведенная теорема служит основой алгоритма нахождения паросочетания с максимальным весом в полном двудольном графе. Начав с допустимой разметки, вычислим подграф равенства и затем найдем максимальное паросочетание в этом подграфе (на этом этапе веса ребер не учитываются). Если найденное паросочетание является совершенным, процесс на этом завершается. В противном случае к подграфу равенства добавляются ребра посредством пересмотра меток вершин. После добавления ребер к подграфу равенства либо увеличивается размер паросочетания (был найден дополняющий путь), либо продолжает расти венгерское дерево.1 В первом случае этот этап процесса завершается и начинается новый (поскольку размер паросочетания вырос). Во втором случае венгерское дерево растет за счет добавления к нему новых вершин, что, очевидно, не может произойти более n раз. | ||
1 Эта структура включает исследованные ребра при поиске базисного возможного решения одновременно из всех свободных вершин в S. Когда в T найдена вершина, сопоставленная какой-либо вершине из S, нужно исследовать только соответствующее ребро; однако в S исследуются все ребра, инцидентные этой вершине. | |||
| Строка 39: | Строка 42: | ||
T =YnT : | T =YnT : | ||
\S\>\T\. | \S\>\T\. | ||
Между S и T не имеется ребер, поскольку в противном случае не было бы возможности полностью вырастить венгерские деревья. Поскольку венгерские деревья выращиваются в G^, альтернативные вершины в поиске помещаются в S и T. Для обновления меток следует взять метки из S и начать равномерно уменьшать их (скажем, на значение A), в то же время увеличивая метки в T на то же значение A. Этот подход гарантирует, что ребра, ведущие из S в T, не исчезнут из подграфа равенства (рис. 1). | |||
Поскольку метки в S уменьшаются, ребра (в графе G), ведущие из S в T, потенциально могут попасть в подграф равенства Gi. По мере увеличения значения A в какой-то момент ребро окажется в подграфе равенства. В этот момент процесс следует остановить и обновить венгерское дерево. Если вершина из T, добавленная к T, сопоставлена с вершиной из S, обе эти вершины перемещаются в S и T, что увеличивает размер венгерского дерева. Если вершина из T свободна, то дополняющий путь найден и данный этап завершен. Этап состоит из таких шагов, выполненных между приращениями размера паросочетания. Поскольку в G всего n вершин, у алгоритма будет не более n этапов, поскольку на каждом этапе размер паросочетания увеличивается на 1. В рамках каждого этапа размер венгерского дерева увеличивается не более n раз. Очевидно, что за время O(n2) можно обнаружить, какое ребро, ведущее из S в T, первым войдет в подграф равенства (для этого нужно просто просмотреть все ребра). Общее время выполнения в таком случае составит O(n4). Теперь покажем, как реализовать это подход за время O(n3). | |||
Показаны только ребра в Gg | |||
Задача присваивания, рис. 1 | |||
Множества S и T, поддерживаемые алгоритмом | |||
Более эффективная реализация | |||
