encontrar la suma mínima de matriz (n x n) que seleccione solamente uno en cada fila y columna

Question

Este es otro problema relacionado con algoritmos de programación dinámica

Aquí está el problema:

encontrar la suma mínima de la matriz dada de tal manera que seleccione uno en cada fila y columna

Por ejemplo:

3 4 2

8 9 1

7 9 5

el mínimo uno: 4 + 1 + 7

Creo que la solución es de flujo de red (max flujo / min corte) pero creo que no debería ser tan duro como es

Mi solución: separada a la lista n [columna], columna 1, ... columna2 columna n

A continuación, el punto inicial (S) -> column1 -> columna2 -> ... -> columna n -> (E) punto final y aplicar max flujo / min corte

Answer 1

Este es el Asignación Problema que puede considerarse un caso especial de peso mínimo en perfecta coincidencia gráficos. La forma clásica de resolver el problema de la asignación es utilizar la húngaro Algoritmo .