найти минимальную сумму матрицы (nxn), которая выбирает только одну в каждой строке и столбце

Question

это еще одна проблема алгоритмов, связанная с динамическим программированием

Вот проблема:

найдите минимальную сумму данной матрицы, такую, чтобы выбрать одну в каждой строке и столбце

Например:

3 4 2

8 9 1

7 9 5

минимальное значение: 4 + 1 + 7

Я думаю, что решение - это сетевой поток (максимальный поток / минимальное сокращение), но я думаю, что это не должно быть так сложно, как это

Мое решение: разделить список n [column], column1, column2... столбец n

, затем начальная точка (S) -> столбец1 -> столбец2 -> ... -> конечная точка столбца -> (E) и максимальный расход потока / минимальное сокращение

Answer 1

Это Задача присваивания , которую можно считать частным случаем идеального соответствия минимального веса на графиках. Классический способ решения проблемы назначения - использовать Венгерский алгоритм .