encontrar la suma mínima de matriz (n x n) que seleccione solamente uno en cada fila y columna
-
11-10-2019 - |
Pregunta
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
Solución
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 .