Изменения
→Алгоритм за O(n^3)
После того, как мы нашли дополняющую цепь, производим серию замен вдоль нее. Цепь состоит из элементов паросочетания и добавленных на текущей итерации нулей, причем для каждого элемента цепи (кроме, разумеется, последнего) известен следующий за ним. После того, как мы удалим из паросочетания все ребра цепи, принадлежащие ему и добавим не принадлежащие, суммарный размер паросочетания увеличится.
Краткий псевдокод данного алгоритма выглядит примерно так: '''HungarianAlgorithm'''(A) 1 '''for''' i = 0..height-1 2 '''do''' 3 создать в матрице A новый нулевой элемент 4 '''while''' новый элемент приводит к коллизии 5 изменить метки элементов вдоль найденной цепочки 6 '''return''' найденное паросочетание При добавлении строки с номером <tex> i </tex> на поиск дополняющей цепи требуется <tex> O(i) </tex> итераций, если каждая итерация требует <tex> O(m) </tex> действий, то общее время работы алгоритма составляет <tex> O(mn^2) </tex>. При наивной реализации <tex> m = O(n^2) </tex>. Но если запоминать минимальные значения можно не пересчитывать каждый раз все измененные элементы матрицы. Вместо них будем хранить и обновлять для каждой строки и каждого столбцаминимум по данной строке/столбцу. Текущее значение элемента в каждый момент можно восстановить, а также обновлять их, не пересчитывая используя эти вспомогательные массивы. При выполнении преобразования <tex> R\uparrow\downarrow C </tex> изменим соответствующие элементы самой матрицы, то массивов на <tex>d</tex>. Так можно выполнять все требуемые действия за <tex> O(n) </tex> операций, тогда на выполнение всего алгоритма потребуется <tex> O(n^3) </tex> действий.
== Ссылки ==
