Какой смысл prime nulls в hungarian algorithm?

Question

[alex_agaphe]

https://en.wikipedia.org/wiki/Hungarian_algorithm
The zero on Row 3 is uncovered. We add to the path the first zero of Row 1, then the second zero of Row 1, then we are done.
Какой смысл здесь primed нулей?

Comments

[mayton2019]

Как тебе отвечать? Тоже на английком?

Чтоб не потерять контекст - лучше дай свой собственный перевод. Заодно и ты узнаешь
как сам понял. И тогда ответы пойдут быстрее. А пока - выглядит как ненужное квотирование.

Answer 1

[Wataru]

Почитайте вот тут описание алгоритма: e-maxx.ru/algo/assignment_hungary

По вашей ссылке звездочками отмечены нули, соответствующие ребрам в текущем паросочетании (потенциалы уже вычтены из всех значений в матрице, поэтому нули соответствуют жестким ребрам). "primed", т.е. отмеченные символом ' нули соответствуют ребрам, которые вы перебираете в удлинняющей цепи. Помеченные столбцы и строки - соответствуют обойденным вершинам.

Смысл в том, что ' нули вытесняют какие-то * нули и в итоге у вас получается на 1 ноль больше в паросочетании.