В венгерском методе, который используется для решения задачи о назначениях, добавление потенциалов (или модификация весов) происходит в процессе улучшения текущего сопоставления. Потенциалы помогают скорректировать веса рёбер графа таким образом, чтобы гарантировать отсутствие отрицательных циклов.
### Этап, когда \(u[i] = v[j] = 0\) для всех \(i\) и \(j\)
На начальном этапе алгоритма для всех вершин возможного назначения и операций (векторов \(u\) и \(v\)) устанавливаются равные нулю значения. Это необходимо для того, чтобы задать начальные условия для итераций алгоритма, когда оптимизация только начинается. Таким образом все рёбра имеют свои начальные веса, что позволяет приступить к выступлению алгоритма.
### Пустое множество \(H\)
Если после некоторого шага алгоритма множество \(H\) оказывается пустым, это может означать, что текущая конфигурация рёбер не позволяет продолжить дальнейшие итерации улучшения сопоставлений. В таком случае необходимо пересчитать потенциалы. Это достигается путём поиска нового пути в графе.
### Как добавляются потенциалы
Когда множество \(H\) становится пустым, происходит следующее:
1. **Поиск минимального произведенного веса**: Находим минимальный вес среди рёбер, которые накрывают доступные вершины, и \(u[i]+\v[j]-c[i][j]\), где \(c[i][j]\) — изначальная стоимость выполнения задачи.
2. **Обновление потенциалов**: Обновляем веса рёбер: для всех \(i\) и \(j\) увеличиваем \(u[i]\) на найденный минимум, а \(v[j]\) уменьшаем на тот же самый минимум. Это обеспечивает, что новый набор рёбер поддерживает свойства оптимальности.
3. **Повторение итераций**: После обновления потенциалов алгоритм продолжает итерации до тех пор, пока не будет найдено оптимальное сопоставление.
Таким образом, после того как множество \(H\) становится пустым, корректировка потенциалов через нахождение минимального значения и обновления каждого потенциала позволяет продолжить процесс улучшения сопоставления и достичь окончательного решения задачи о назначениях.