algorithm - seleccionar - De una entrevista: Eliminar filas y columnas en una matriz n × n para maximizar la suma de los valores restantes

suma de elementos de una matriz matlab (16)

Bueno, el método de la fuerza bruta es algo como esto:

Para n filas hay 2 ⁿ subconjuntos.
Para n columnas hay 2 ⁿ subconjuntos.
Para una matriz nxn hay 2 ²ⁿ subconjuntos.

0 elementos es un subconjunto válido pero, obviamente, si tiene 0 filas o 0 columnas, el total es 0, por lo que realmente hay 2 ^2n-2 + 1 subconjuntos, pero eso no es diferente.

Así que puedes trabajar cada combinación por fuerza bruta como un algoritmo O (a ⁿ ). Rápido. :)

Sería más rápido averiguar cuál es el valor máximo posible y lo hace sumando todos los números positivos en la cuadrícula. Si esos números forman una sub-matriz válida (lo que significa que puede crear ese conjunto eliminando filas y / o columnas), está su respuesta.

Implícito en esto es que si ninguno de los números es negativo, entonces la matriz completa es, por definición, la respuesta.

Además, saber cuál es el máximo más alto posible posiblemente te permita atajar la evaluación de fuerza bruta, ya que si obtienes una combinación igual a ese máximo, esa es tu respuesta y puedes dejar de verificar.

Además, si todos los números no son positivos, la respuesta es el valor máximo, ya que puede reducir la matriz a una matriz de 1 x 1 con ese valor 1, por definición.

Aquí hay una idea: construir 2 ⁿ -1 nxm matrices donde 1 <= m <= n. Procésalos uno tras otro. Para cada matriz nxm puedes calcular:

La suma máxima más alta posible (según arriba); y
Si no hay números positivos que le permitan atajar la respuesta.

Si (1) está por debajo de la suma máxima máxima calculada actualmente, puede descartar esta matriz nxm. Si (2) es verdadero, solo necesita una comparación simple con la suma máxima más alta actual.

Esto se conoce generalmente como una técnica de poda .

Además, puede comenzar diciendo que el número más alto en la matriz nxn es la suma máxima más alta ya que, obviamente, puede ser una matriz de 1 x 1.

Estoy seguro de que podría ajustar esto en un algoritmo de búsqueda basado en árbol recursivo (un poco más eficiente) con las pruebas anteriores, lo que le permitirá efectivamente eliminar (con suerte muchas) búsquedas innecesarias.

Dada una matriz n × n de números reales. Se le permite borrar cualquier número (de 0 a n) de filas y cualquier número (de 0 a n) de columnas, y luego se calcula la suma de las entradas restantes. Cree un algoritmo que descubra qué filas y columnas debe borrar para maximizar esa suma.

Calcule la suma de cada fila y columna. Esto se puede hacer en O (m) (donde m = n ^ 2)

Si bien hay filas o columnas que suman en negativo, elimine la fila o columna que tenga la suma más baja que sea menor que cero. Luego vuelva a calcular la suma de cada fila / columna.

La idea general es que siempre que haya una fila o una columna que se sume a nevative, eliminarla dará como resultado un mayor valor general. Debe eliminarlos de uno en uno y volver a calcularlos porque al eliminar esa fila / columna está afectando las sumas de las otras filas / columnas y pueden o no tener sumas negativas más.

Esto producirá un resultado óptimo óptimo. El tiempo de ejecución es O (mn) u O (n ^ 3)

Como nadie solicitó un algoritmo eficiente, use la fuerza bruta: genere todas las matrices posibles que pueden crearse eliminando filas y / o columnas de la matriz original, elija la mejor. Una versión ligeramente más eficiente, que probablemente se puede demostrar que aún es correcta, es generar solo aquellas variantes donde las filas y columnas eliminadas contienen al menos un valor negativo.

Creo que hay algunos ángulos de ataque que podrían mejorar con la fuerza bruta.

Memoria, ya que hay muchas secuencias distintas de ediciones que llegarán a la misma submatriz.
programación dinámica. Debido a que el espacio de búsqueda de matrices es altamente redundante, mi intuición es que habría una formulación de DP que puede ahorrar mucho trabajo repetido
Creo que hay un enfoque heurístico, pero no puedo concretarlo:
si hay un número negativo, puede tomar la matriz tal como está, eliminar la columna del número negativo o eliminar su fila; No creo que ningún otro "movimiento" resulte en una suma más alta. Para dos números negativos, sus opciones son: eliminar ninguno, eliminar uno, eliminar el otro o eliminar ambos (donde el acto de eliminación es al eliminar la fila o la columna).
Ahora supongamos que la matriz solo tiene un número positivo y el resto son todos <= 0. Claramente quieres eliminar todo menos la entrada positiva. Para una matriz con solo 2 entradas positivas y el resto <= 0, las opciones son: no hacer nada, reducir a una, reducir a la otra o reducir a ambas (resultando en una matriz de 1x2, 2x1 o 2x2) .
En general, esta última opción se derrumba (imagine una matriz con 50 positivos y 50 negativos), pero dependiendo de sus datos (algunos negativos o pocos positivos) podría proporcionar un atajo.

Digamos que n = 10.

La fuerza bruta (todos los conjuntos de filas posibles x todos los conjuntos de columnas posibles) toma

2 ^ 10 * 2 ^ 10 = ~ 1,000,000 nodos.

Mi primer enfoque fue considerar esto como una búsqueda de árbol, y usar

la suma de las entradas positivas es un límite superior para cada nodo en el subárbol

Como método de poda. Combinado con un algoritmo codicioso para generar buenos límites iniciales a bajo costo, esto produjo respuestas en alrededor de 80,000 nodos en promedio.

Pero hay una mejor manera ! luego me di cuenta de que

Arregle algunas opciones de filas X. Resolver las columnas óptimas para este conjunto de filas ahora es trivial (mantenga una columna si su suma de sus entradas en las filas X es positiva, de lo contrario, descártela).

Así que solo podemos fuerza bruta sobre todas las elecciones posibles de filas; esto toma 2 ^ 10 = 1024 nodos.

Agregar el método de poda redujo esto a 600 nodos en promedio.

Mantener ''sumas de columna'' y actualizarlas incrementalmente al atravesar el árbol de conjuntos de filas debe permitir que los cálculos (suma de matriz, etc.) en cada nodo sean O (n) en lugar de O (n ^ 2). Dando una complejidad total de O (n * 2 ^ n)

El problema es NP-hard . (Por lo tanto, no debe esperar un algoritmo de tiempo polinomial para resolver este problema. Sin embargo, podría haber algoritmos (tiempo no polinomial) que sean ligeramente mejores que la fuerza bruta). La idea detrás de la prueba de la dureza NP es que Si pudiéramos resolver este problema, entonces podríamos resolver el problema de la camarilla en un gráfico general. (El problema de la camarilla máxima es encontrar el conjunto más grande de vértices conectados por pares en una gráfica).

Específicamente, dado cualquier gráfico con n vértices, formemos la matriz A con las entradas a[i][j] siguiente manera:

a[i][j] = 1 para i == j (las entradas diagonales)
a[i][j] = 0 si el borde (i, j) está presente en el gráfico (y i≠j )
a[i][j] = -n-1 si el borde (i, j) no está presente en el gráfico.

Ahora, supongamos que resolvemos el problema de eliminar algunas filas y columnas (o, de manera equivalente, mantener algunas filas y columnas) para maximizar la suma de las entradas en la matriz. Entonces la respuesta da la camarilla máxima en el gráfico:

Reclamación : en cualquier solución óptima, no hay una fila i ni una columna j mantenidas para las que el borde (i, j) no esté presente en el gráfico. Prueba: a[i][j] = -n-1 y la suma de todas las entradas positivas es a lo sumo n , la selección (i, j) llevaría a una suma negativa. (Tenga en cuenta que eliminar todas las filas y columnas daría una mejor suma, de 0).
Reclamo : En (algunos) soluciones óptimas, el conjunto de filas y columnas que se mantienen es el mismo. Esto se debe a que, al comenzar con cualquier solución óptima, simplemente podemos eliminar todas las filas i para las que no se ha mantenido la columna i , y viceversa. Tenga en cuenta que, dado que las únicas entradas positivas son las diagonales, no disminuimos la suma (y, por la reclamación anterior, tampoco la aumentamos).

Todo lo cual significa que si la gráfica tiene una camarilla máxima de tamaño k , entonces nuestro problema de matriz tiene una solución con la suma k , y viceversa. Por lo tanto, si pudiéramos resolver nuestro problema inicial en el tiempo polinomial, entonces el problema de la camarilla también se resolvería en el tiempo polinomial. Esto prueba que el problema inicial es NP-hard . (En realidad, es fácil ver que la versión de decisión del problema inicial, ¿hay alguna forma de eliminar algunas filas y columnas para que la suma sea al menos k ? Está en NP, por lo que el problema inicial (versión de decisión del) es en realidad NP-complete .)

Es claramente NP-Completo (como se describe anteriormente). Teniendo en cuenta esto, si tuviera que proponer el mejor algoritmo que pudiera para el problema:

Pruebe algunas iteraciones de la programación de enteros cuadráticos, formulando el problema como: SUM_ij a_ij x_i y_j , con las variables x_i y y_j restringidas para que sean 0 o 1. Para algunas matrices, creo que esto encontrará una solución rápidamente, para los casos más difíciles No hay mejor que la fuerza bruta (y no sería mucho).
En paralelo (y utilizando la mayor parte de la CPU), use un algoritmo de búsqueda aproximado para generar soluciones cada vez mejores. La simulación de recocido se sugirió en otra respuesta, pero después de haber investigado sobre problemas de optimización combinatoria similares, mi experiencia es que la búsqueda tabú encontraría buenas soluciones más rápido. Es probable que esto sea casi óptimo en términos de divagar entre distintas soluciones "potencialmente mejores" en el menor tiempo, si utiliza el truco de actualizar incrementalmente los costos de los cambios individuales (vea mi artículo "Dominación de gráficos, búsqueda de tabú y el problema del pool de fútbol" ").
Utilice la mejor solución hasta el momento anterior para dirigir la primera al evitar las posibilidades de búsqueda que tienen límites inferiores peores que ella.

Obviamente, esto no está garantizado para encontrar la solución máxima. Pero, por lo general, lo haría cuando esto fuera factible y, de lo contrario, brindaría una muy buena solución local máxima. Si alguien tuviera una situación práctica que requiera tal optimización, esta es la solución que creo que funcionaría mejor.

¡Dejar de identificar que un problema puede ser NP-Completo no se verá bien en una entrevista de trabajo! (A menos que el trabajo esté en la teoría de la complejidad, pero aun así no lo haría). Es necesario sugerir buenos enfoques: ese es el punto de una pregunta como esta. Para ver lo que puede surgir bajo presión, porque el mundo real a menudo requiere abordar tales cosas.

Este es un problema de optimización y puede resolverse aproximadamente mediante un algoritmo iterativo basado en el recocido simulado :

Notación: C es el número de columnas.

Para J iteraciones:

Mire cada columna y calcule el beneficio absoluto de alternarla (desactívela si está actualmente activada o enciéndala si está actualmente desactivada). Eso le da valores de C, por ejemplo, -3, 1, 4. Una solución determinista codiciosa solo escogería la última acción (alternar la última columna para obtener un beneficio de 4) porque mejora localmente el objetivo. Pero eso podría encerrarnos en un óptimo local. En su lugar, probabilísticamente elegimos una de las tres acciones, con probabilidades proporcionales a los beneficios . Para hacer esto, conviértalos en una distribución de probabilidad poniéndolos a través de una función Sigmoide y normalizando. (¿O usa exp () en lugar de sigmoide ()?) Así que para -3, 1, 4 obtienes 0.05, 0.73, 0.98 del sigmoide y 0.03, 0.42, 0.56 después de la normalización. Ahora elija la acción de acuerdo con la distribución de probabilidad, por ejemplo, alternar la última columna con probabilidad 0.56, alternar la segunda columna con probabilidad 0.42, o alternar la primera columna con la pequeña probabilidad 0.03.
Realice el mismo procedimiento para las filas, lo que resultará en alternar una de las filas.

Iterar para iteraciones J hasta la convergencia.

También podemos, en las primeras iteraciones, hacer que cada una de estas distribuciones de probabilidad sea más uniforme, para que no nos quedemos atrapados en malas decisiones desde el principio. Entonces elevaríamos las probabilidades anormalizadas a una potencia 1 / T, donde T es alta en las primeras iteraciones y disminuye lentamente hasta que se acerca a 0. Por ejemplo, 0.05, 0.73, 0.98 desde arriba, aumentó a 1/10 resultados en 0.74 , 0.97, 1.0, que después de la normalización es 0.27, 0.36, 0.37 (por lo que es mucho más uniforme que el original 0.05, 0.73, 0.98).

Para probarlo de forma sencilla:

Necesitamos el subconjunto válido del conjunto de entradas {A00, A01, A02, ..., A0n, A10, ..., Ann} que máx. suma.

Primero computa todos los subconjuntos (el conjunto de potencias).

Un subconjunto válido es un miembro del conjunto de potencias que por cada dos entradas contenidas Aij y A (i + x) (j + y), contiene también los elementos A (i + x) j y Ai (j + y) (que son las esquinas restantes del rectángulo abarcado por Aij y A (i + x) (j + y)).

Aij ... . . . . ... A(i+x)(j+y)

De este modo, puede eliminar los que no sean válidos del conjunto de potencias y encontrar el que tenga la mayor suma en el resto.

Estoy seguro de que se puede mejorar mejorando un algoritmo para la generación de conjuntos de energía con el fin de generar solo subconjuntos válidos y al evitar el paso 2 (ajuste del conjunto de potencia).

Podemos mejorar la solución de fuerza bruta generalizada de Cletus al modelar esto como un gráfico dirigido. La matriz inicial es el nodo de inicio del gráfico; sus hojas son todas las matrices que faltan una fila o columna, y así sucesivamente. Es un gráfico en lugar de un árbol, porque el nodo para la matriz sin la primera columna y la fila tendrá dos padres: los nodos en los que solo falta la primera columna o fila.

Podemos optimizar nuestra solución convirtiendo el gráfico en un árbol: nunca hay ningún punto en explorar una submatriz con una columna o fila eliminada que viene antes de la que eliminamos para llegar al nodo actual, ya que la submatriz se obtendrá de todos modos.

Esta es una búsqueda de fuerza bruta, por supuesto, pero hemos eliminado los casos duplicados en los que eliminamos las mismas filas en diferentes órdenes.

Aquí hay una implementación de ejemplo en Python:

def maximize_sum(m): frontier = [(m, 0, False)] best = None best_score = 0 while frontier: current, startidx, cols_done = frontier.pop() score = matrix_sum(current) if score > best_score or not best: best = current best_score = score w, h = matrix_size(current) if not cols_done: for x in range(startidx, w): frontier.append((delete_column(current, x), x, False)) startidx = 0 for y in range(startidx, h): frontier.append((delete_row(current, y), y, True)) return best_score, best

Y aquí está la salida en la matriz de ejemplo de 280Z28:

>>> m = ((1, 1, 3), (1, -89, 101), (1, 102, -99)) >>> maximize_sum(m) (106, [(1, 3), (1, 101)])

Realmente no puedo producir un algoritmo en la parte superior de mi cabeza, pero para mí ''huele'' a programación dinámica, si sirve como punto de partida.

Sí, es un problema NP-completo.

Es difícil encontrar fácilmente la mejor submatriz, pero podemos encontrar fácilmente una mejor submatriz.

Supongamos que damos m puntos aleatorios en la matriz como "feeds". luego les permite extenderse automáticamente por las reglas como:

si agrega una nueva fila o columna a la matriz de alimentación, asegúrese de que la suma sea incremental.

, entonces podemos comparar m sub-matriz para encontrar la mejor.

Toma cada fila y cada columna y calcula la suma. Para una matriz de 2x2 esto será:

2 1 3 -10

Fila (0) = 3 Fila (1) = -7 Col (0) = 5 Col (1) = -9

Componer una nueva matriz

Cost to take row Cost to take column 3 5 -7 -9

Saque lo que necesite y luego comience de nuevo.

Solo busca valores negativos en la nueva matriz. Esos son valores que realmente se restan del valor de la matriz global. Termina cuando no hay más valores negativos de "SUMS" para sacar (por lo tanto, todas las columnas y filas suman algo al resultado final)

En una matriz nxn que sería O (n ^ 2) Log (n) creo

Gran edición: Sinceramente, no creo que haya una manera de evaluar una matriz y determinar si está maximizada, a menos que sea completamente positiva.

Tal vez necesite ramificarse, y comprender todas las vías de eliminación. Nunca, no, cuando una eliminación costosa permitirá una cantidad de eliminaciones mejores más adelante. Podemos hacer un cortocircuito si se encuentra el máximo teórico, pero, aparte de cualquier algoritmo, tendríamos que ser capaces de avanzar y retroceder. He adaptado mi solución original para lograr este comportamiento con recursión.

Edición de doble secreto: También sería un gran paso reducir la complejidad si cada iteración no tuviera que encontrar todos los elementos negativos. Teniendo en cuenta que no cambian mucho entre llamadas, tiene más sentido simplemente pasar sus posiciones a la siguiente iteración.

Toma una matriz, la lista de elementos negativos actuales en la matriz y el máximo teórico de la matriz inicial. Devuelve la suma máxima de la matriz y la lista de movimientos necesarios para llegar allí. En mi mente, la lista de movimientos contiene una lista de movimientos que denotan la fila / columna eliminada del resultado de la operación anterior.

Es decir: r1, r1

Se traduciría

-1 1 0 1 1 1 -4 1 -4 5 7 1 1 2 4 ===> 5 7 1

Retorno si suma de matriz es el máximo teórico
Encuentre las posiciones de todos los elementos negativos a menos que se haya pasado un conjunto vacío.
Calcular la suma de la matriz y almacenarla junto a una lista de movimientos vacía.
- Para cada elemento negativo:
  1. Calcula la suma de la fila y columna de ese elemento.
  2. clone la matriz y elimine la colección que tenga la suma mínima (fila / columna) de ese clon, tenga en cuenta esa acción como una lista de movimientos.
  3. clone la lista de elementos negativos y elimine cualquiera que se vea afectado por la acción realizada en el paso anterior.
  4. Recursivamente llame a este algoritmo que proporciona la matriz clonada, la lista de elementos negativos actualizada y el máximo teórico. Agregue la lista de movimientos devueltos a la lista de movimientos para la acción que produjo la matriz pasada a la llamada recursiva.
  5. Si el valor devuelto de la llamada recursiva es mayor que la suma almacenada, sustitúyalo y almacene la lista de movimientos devueltos.
Devuelve la suma almacenada y la lista de movimientos.

No estoy seguro de si es mejor o peor que el método de fuerza bruta, pero ahora maneja todos los casos de prueba. Incluso aquellos donde el máximo contiene valores negativos.

Cree un RowSums vector n-by-1, y un ColumnSums vector n-by-1. Inicialícelos a las sumas de fila y columna de la matriz original. O (n²)
Si alguna fila o columna tiene una suma negativa, elimine la edición: la que tenga el mínimo y actualice las sumas en la otra dirección para reflejar sus nuevos valores. En)
Deténgase cuando ninguna fila o columna tenga una suma menor que cero.

Esta es una variación iterativa que mejora en otra respuesta. Funciona en tiempo O (n²), pero falla en algunos casos mencionados en otras respuestas, que es el límite de complejidad para este problema (hay n² entradas en la matriz, e incluso para encontrar el mínimo que tiene que examinar cada celda una vez) .

Edición: la siguiente matriz no tiene filas ni columnas negativas, pero tampoco está maximizada y mi algoritmo no la detecta.

1 1 3 goal 1 3 1 -89 101 ===> 1 101 1 102 -99

La siguiente matriz tiene filas y columnas negativas, pero mi algoritmo selecciona las incorrectas para su eliminación.

-5 1 -5 goal 1 1 1 1 ===> 1 -10 2 -10 2 mine ===> 1 1 1