Maximizar la suma de los números "no superpuestos" de la matriz

Question

Solo buscando un poco de dirección, me doy cuenta de que el ejemplo dado es posible de resolver usando la iteración de fuerza bruta, pero estoy buscando una más elegante (es decir, matemática?) solución que potencialmente podría resolver ejemplos significativamente más grandes (digamos 20x20 o 30x30). Es muy posible que esto no se pueda hacer, y he tenido muy poco éxito en encontrar un enfoque que no dependa de la fuerza bruta ...

Tengo una matriz (llámala A) que es nxn. Deseo seleccionar un subconjunto (llamarlo B) de puntos de la matriz A. El subconjunto consistirá en n elementos, donde uno y solo un elemento se tomará de cada fila y de cada columna de A. La salida debería proporcionar una solución (B) tal que la suma de los elementos que forman B es el valor máximo posible, dadas estas restricciones (por ejemplo, 25 en el ejemplo a continuación). Si se encuentran múltiples instancias de B (es decir, diferentes soluciones que dan la misma suma máxima), debe seleccionarse la solución para B que tiene el elemento mínimo más grande.

B también podría ser una matriz de selección que es nxn, pero donde solo los n elementos deseados son distintos de cero.

Por ejemplo: si A =

|5 4 3 2 1| 
|4 3 2 1 5| 
|3 2 1 5 4| 
|2 1 5 4 3| 
|1 5 4 3 2| 

=> B sería

|5 5 5 5 5| 

Sin embargo, si A =

|5 4 3| 
|4 3 2| 
|3 2 1| 

B =

|3 3 3| 

Como el elemento mínimo de B es 3 que es mayor que para

|5 3 1| 

o

|4 4 1| 

que también tanto suma a 9

Answer 1

Su problema es casi idéntico al Assignment problem, que puede p. ser resuelto por el Hungarian algorithm en tiempo polinomial.

Tenga en cuenta que el problema de asignación suele ser un problema de minimización, pero la multiplicación de su matriz por -1 y la adición de una constante deben hacer que el método sea aplicable. Además, no existe una condición formal de frenado de enlace, para el caso de múltiples soluciones óptimas. Sin embargo, el método produce una solución con la suma óptima. Deje m ser el summand mínimo. Modifique su matriz estableciendo todas las entradas menores o iguales a m en cero y resuelva nuevamente. O obtienes una solución con la misma suma que es mejor que la anterior. Si no, la solución anterior ya era óptima.

Answer 2

Esto está relacionado con la n Queens problem, excepto que no te importa la diagonal y tienes soluciones ponderadas. Como el problema de Queens, puedes resolverlo mediante retroalimentación (múltiple).

Es decir, una vez que encuentre una solución, recuerde su peso, marque la supresión como no válida y comience nuevamente. La (a) solución con el mayor peso gana.

Answer 3

Ouch. This algorithm is wrong; there is no proof because it's wrong and therefore it's impossible to prove that it's correct.;) Lo dejo aquí porque estoy demasiado apegado para eliminarlo por completo, y es una buena demostración de por qué debería probar formalmente los algoritmos en lugar de decir "¡esto parece correcto! ¡No hay forma posible de que esto no funcione! "

---

Estoy dando esta solución sin pruebas, por el momento. Tengo un boceto a prueba, pero estoy teniendo problemas para probar la subestructura óptima para este problema. De todos modos ...

Problema

Dada una matriz cuadrada de números, seleccione tantos números "que no se superponen" como sea posible para que se maximiza la suma de los números seleccionados. "No superpuesto" significa que no pueden haber dos números de la misma fila o la misma columna.

Algoritmo

• Let A ser una matriz cuadrada de n by n números.
• Deje Aij denotar el elemento de A en la 0ª fila i y la columna j.
• Vamos S(i1:i2, j1:j2) denotan la suma óptima de números que no se superponen para una submatriz cuadrada de A que contiene la intersección de filas i1 a i2 y columnas j1-j2.

entonces la suma óptima de números que no se solapan se denota S(1:n , 1:n) y se da como sigue:

S(1:n , 1:n) = max { [ S( 2:n , 2:n ) + A11 ] 
         [ S( 2:n , 1:n-1) + A1n ] 
         [ S(1:n-1 , 2:n ) + An1 ] 
         [ S(1:n-1 , 1:n-1) + Ann ] } 
(recursively) 

Note that S(i:i, j:j) is simply Aij. 

Esto es, la suma óptima para una matriz cuadrada de tamaño n se puede determinar calculando por separado la suma óptima para cada una de las cuatro sub-matrices de tamaño n-1, y luego maximizar la suma de la sub-matriz y el elemento que se "dejó afuera".

S for |# # # #| 
     |# # # #| 
     |# # # #| 
     |# # # #| 

Is the best of the sums S for: 

|#  |  |  #|  |# # # |  | # # #| 
| # # #|  |# # # |  |# # # |  | # # #| 
| # # #|  |# # # |  |# # # |  | # # #| 
| # # #|  |# # # |  |  #|  |#  | 

Implementación

El algoritmo recursivo anterior sugiere una solución recursiva:

def S(A,i1,i2,j1,j2): 
    if (i1 == i2) and (j1==j2): 
     return A[i1][j1] 
    else: 
     return max (S(A, i1+1, i2, j1+1, j2) + A[i1][j1] ], 
        S(A, i1+1, i2, j1, j2-1) + A[i1][j2] ], 
        S(A, i1, i2-1, j1+1, j2) + A[i2][j1] ], 
        S(A, i1, i2-1, j1, j2-1) + A[i2][j2] ],) 

Tenga en cuenta que esto hará que las llamadas a O(4^n)S() !! Esto es mucho mejor que el factorial O(n!) complejidad de tiempo de la solución de "fuerza bruta", pero aún un rendimiento horrible.

Lo importante a tener en cuenta aquí es que muchas de las llamadas son repetidas con los mismos parámetros. Por ejemplo, al resolver una matriz 3 * 3, cada matriz 2 * 2 se resuelve muchas veces.

Esto sugiere dos soluciones posibles para un aumento de velocidad:

• hacer que la función recursiva S() resultados de caché para que sólo necesita S(A,i1,i2,j1,j2) una vez por cada i1,i2,j1,j2. Esto significa que S() solo necesita calcular O(n^3) resultados - todas las demás solicitudes se completarán desde la memoria caché. (Esto se llama memoising.)
• En lugar de comenzar en la parte superior, con la gran n*n matriz, y trabajando a través de subproblemas cada vez más pequeños, a empezar por la parte inferior con los más pequeños subproblemas posibles y construir hasta al caso n*n. Esto se llama programación dinámica . También es O(n^3), pero es mucho más rápido O(n^3) porque no tiene que presionar un caché todo el tiempo.

La solución de programación dinámica procede algo así como:

• encontrar soluciones óptimas a todos los sub-matrices 1x1. (Trivial.)
• Encuentra soluciones óptimas para todos los sub-arreglos 2x2.
• Encuentra soluciones óptimas para todas las sub-matrices 3x3.
• ...
• Encuentre soluciones óptimas para todas las sub-matrices n-1 * n-1.
• Encuentra soluciones óptimas para la sub-matriz n * n completa.

Notas sobre esta solución:

• No hay pruebas todavía. Estoy trabajando en ello.
• Notarás que el algoritmo anterior solo te da S(), la suma óptima suma. No te dice qué números realmente componen esa suma. Puedes agregar tu propio método de retroceder en tu camino a la solución.
• El algoritmo anterior no garantiza la propiedad que une como 2,2 vs 1,3 se romperá a favor de tener todos los números individuales sean tan grandes como sea posible (de modo que 2,2 victorias.) Creo que se puede definir para romper max() está a favor del mayor número posible, y eso hará lo que quiera, pero no puedo probarlo.

Notas generales:

Dynamic programming es una poderosa técnica para la elaboración de algoritmos rápidos para cualquier problema que presenta dos propiedades:

1. subestructura óptima: Un problema puede ser dividido en un poco más pequeña partes, cada una de las cuales se puede usar como parte de la solución al problema original.
2. La superposición de subproblemas significa que hay pocos subproblemas reales que resolver, y las soluciones a los subproblemas se vuelven a usar muchas veces.

Si el problema tiene subestructura óptima, y ​​el problema se descompone en ligeramente problemas más pequeños - por ejemplo un problema de tamaño n se descompone en subproblemas de tamaño n-1 - entonces el problema puede ser resuelto por programación dinámica .

Si se puede dividir el problema en mucho trozos más pequeños - por ejemplo cortando un problema de tamaño n en dos mitades, cada una de tamaño n/2 - que es divide y vencerás, no de programación dinámica. Las soluciones de dividir y conquistar generalmente son muy muy rápidas; por ejemplo, la búsqueda binaria encontrará un elemento en una matriz ordenada en el tiempo O(log n).

Answer 4

Como Matthias indicó que debe usar retroceder.

1. Encuentre una solución razonable. Seleccione los valores máximos de cada fila y vea si no se superponen. De lo contrario, perturbe parte de la solución para que el resultado no se solape.
2. Define el estado físico de una solución parcial.Digamos que está recogiendo valor para cada fila de forma iterativa y que ya ha elegido valores de las primeras k filas. La idoneidad de esta solución es igual a la suma de los valores ya recogidos + valores máximos de las filas restantes y las columnas no seleccionadas
3. Ahora recursivamente comience la búsqueda de soluciones. Seleccione los valores de la primera fila, calcule su estado físico e insértelos en una cola de prioridad. Elimine todas las soluciones cuya idoneidad sea menor que la solución óptima actual (inicializada en el paso 1). Elija la solución al principio de la cola, calcule el siguiente nivel de soluciones e insértelo nuevamente en la cola de prioridad. Una vez que haya seleccionado los valores de todas las columnas y filas, calcule la suma, y ​​si es más alta que la óptima actual, reemplácela.