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