Изменения

Выделим в множествах <tex>X</tex> и <tex>Y</tex> подмножества <tex>X', Y'</tex>. Пусть <tex>d = \min \{c(xy)|\ x \in X \setminus X', y \in Y'\}</tex>. Прибавим <tex> d </tex> ко всем весам ребер, инцидентных вершинам из <tex>X'</tex>. Затем отнимем <tex> d </tex> от всех весов ребер, инцидентных вершинам из <tex>Y'</tex>(далее для краткости будем обозначать эту операцию как <tex> X' \uparrow\downarrow Y' </tex>). Тогда:

<td> <tex> XY' </tex> </td> <td> <tex> X Y \backslash XY' </tex> </td>

<td> <tex> YX' </tex> </td>

<td> <tex> B - C + d </tex> </td>

<td> <tex> Y X \backslash YX' </tex> </td> <td> <tex> C + B - d </tex> </td>

#* В противном случае, покроем нули матрицы весов минимальным количеством строк и столбцов (это не что иное, как [[Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах|нахождение минимального вершинного покрытия в двудольном графе]]). Теперь применим преобразование из леммы 2. Пусть множества вершин минимального вершинного покрытия из левой и правой долей — <tex> X_c \uparrow\downarrow Y \setminus Y_c </tex> и , где <tex> Y_c X_c </tex> соответственно, тогда берем и <tex> X' = X_c, Y' = Y \setminus Y_c </tex>— множества вершин минимального вершинного покрытия из левой и правой долей соответственно. Для этого преобразования <tex> d </tex> будет минимумом по всем ребрам между <tex> X \setminus X_c </tex> и <tex> Y \setminus Y_c </tex>, то есть, ребер нулевого веса здесь нет, поэтому, после его выполнения в матрице весов появится новый нуль. После этого перейдем к шагу 1.

Поиск максимального паросочетания или минимального контролирующего множества в двудольном графе совершается за <tex> O(n^3) </tex> операций. При каждом повторении шагов 1-3 в матрице весов появляется новый нуль, который увеличивает размер максимального паросочетания хотя бы на 1, поэтому всего будет совершено <tex> O(n) </tex> итераций внешнего цикла. Поэтому, суммарная асимптотика работы данной версии венгерского алгоритма — <tex> O(n^4) </tex>. В книге Асанова == Алгоритм за O(n^3) == Предложенный метод корректен, но не является оптимальным по времени работы, оно может быть улучшено до <tex> O(n^3) </tex>. Заметим, что искать максимальное паросочетание каждый раз заново необязательно, можно просто постепенно изменять его, получая новые нулевые ребра и строя [[Теорема_о_максимальном_паросочетании_и_дополняющих_цепях|дополняющие цепи]] на них (примерно так же, как и в [[Алгоритм_Куна_для_поиска_максимального_паросочетания|алгоритме Куна]], но здесь мы фактически строим целое дерево возможных дополняющих цепей). Для каждого столбца, если в нем есть элемент из текущего паросочетания, будем хранить номер строки этого элемента. Также, при построении дополняющей цепи, будем для каждого элемента паросочетания хранить, на какой элемент его нужно заменить, если цепь будет проходить через него. Будем рассматривать строки матрицы последовательно. Пусть в данный момент мы рассматриваем <tex> i </tex>-ую строку, а также в реализации первых <tex> i - 1 </tex> строках максимальное паросочетание уже найдено. Множество строк <tex> C </tex>, из которых мы будем вычитать минимумы, вначале состоит только из строки <tex> i </tex>, множество <tex> R </tex> пусто. Применим к матрице операцию <tex> C\uparrow\downarrow R </tex>. Если новый ноль с координатами <tex> xy </tex> появился в столбце, не занятом паросочетанием, то удлинняющая цепь найдена, <tex> xy </tex> — ее последнее ребро. Если нет, то существует элемент <tex> x'y </tex> из паросочетания. Тогда добавим строку <tex> x' </tex> и столбец <tex> y </tex> в множества <tex> C </tex> и <tex> R </tex> соответственно и отметим <tex> xy </tex> как замену для <tex> x'y </tex>. После того, как мы нашли дополняющую цепь, производим серию замен вдоль нее. При этом размер найденного нами паросочетания увеличится. При добавлении строки с номером <tex> i </tex> на C++ по ссылке ниже предложена оптимизацияпоиск дополняющей цепи требуется <tex> O(i) </tex> итераций, если каждая итерация требует <tex> O(m) </tex> действий, которая позволяет улучшить то общее время работы до алгоритма составляет <tex> O(mn^2) </tex>. При наивной реализации <tex> m = O(n^2) </tex>. Но если запоминать минимальные значения для каждой строки и столбца, а также обновлять их, не пересчитывая элементы самой матрицы, то можно выполнять все требуемые действия за <tex> O(n) </tex> операций, тогда на выполнение всего алгоритма потребуется <tex> O(n^3) </tex>действий.