Вопрос или проблема
//minval - это минимальное значение среди непокрытых элементов
if (row_covered_[i]) {
cost_matrix_(i, j) += minval;
}
if (!col_covered_[j]) {
cost_matrix_(i, j) -= minval;
}
Во многих реализациях алгоритма Куна-Мункрес есть несколько строк кода, подобных этому. Я понимаю, что вычитание наименьшего значения нужно для создания нового нуля.
Однако я не понимаю почему нам нужно добавлять минимальное значение к числу, для которого row_covered = 1 и col_covered = 1.
Вот диаграмма, объясняющая, как работает алгоритм.
На рисунке 12 мы нашли минимальное значение 1, а на рисунке 13 добавили это значение в верхний левый угол матрицы.
Почему нам нужно это делать, с моей точки зрения, код должен быть изменен на
//minval - это минимальное значение среди непокрытых элементов
if (!row_covered[i] && !col_covered_[j]) {
cost_matrix_(i, j) -= minval;
}
Ответ или решение
К сожалению, текущее понимание вашего вопроса может быть неверным, и я постараюсь пояснить, как работает алгоритм Куна-Мункреса и зачем нужно добавлять минимальное значение к элементам с закрашенными строками.
Алгоритм Куна-Мункреса (также известный как метод венгерского алгоритма) находит оптимальное соответствие в двудольном графе. Один из ключевых моментов алгоритма заключается в преобразовании матрицы стоимостей таким образом, чтобы все минимальные элементы были равны нулю и при этом сохранить оптимальность решения.
Когда мы говорим о строках и столбцах, которые уже были "закрыты" (то есть, на них уже было сделано соответствие), добавление минимального значения к элементам, которые находятся на закрашенных строках (row_covered), нужно по нескольким причинам:
-
Сохранение равновесия: При добавлении минимального значения к элементам с закрашенными строками мы сохраняем общий вес текущего соответствия. Это важно, потому что каждое соответствие должно оставаться оптимальным. Если бы мы не добавляли минимальное значение, стоимость соответствия могла бы увеличиться, а это повлияло бы на окончательный результат.
-
Обновление покрытий: Добавляя минимальное значение к элементам закрашенных строк, мы создаём новые пропуски (нули) в матрице. Это важно для поиска новых соответствий. Если бы вы просто уменьшали элементы без добавления минимального значения к уже закрашенным ячейкам, это могло бы привести к потере возможности найти новые соответствия.
-
Поддержка характеристик алгоритма: Алгоритм Куна-Мункрес работает с отобранными элементами. Закрытые линии обозначают, что соответствие было найдено, а мы должны быть уверены, что любой изменённый элемент (включая элементы, находящиеся в закрашенных строках) продолжает поддерживать свойства оптимальности.
Что касается вашего предложения изменить код на:
if (!row_covered[i] && !col_covered_[j]) {
cost_matrix_(i, j) -= minval;
}такая модификация будет неправильно трактовать, поскольку вы бы лишь уменьшали значения элементов, не учитывая, что те элементы, которые уже покрыты, также могут потребовать пересмотра в соответствии с текущим решением. Примерно так вы потеряете необходимую связь между строками и столбцами, что, в конечном счете, повлияет на результат.
Таким образом, добавление минимального значения к элементам с закрашенными строками необходимо для того, чтобы сохранять необходимость в поддержании следующих шагов алгоритма, позволяя сохранить структуру и оптимальность решений на протяжении всей работы алгоритма.