Problema de submatriz máxima

Problema en informática

Visualización de cómo cambian las submatrices en función de las posiciones inicial y final de una muestra. Cada submatriz contigua posible se representa mediante un punto en una línea de color. La coordenada y de ese punto representa la suma de la muestra. Su coordenada x representa el final de la muestra y el punto más a la izquierda de esa línea de color representa el inicio de la muestra. En este caso, la matriz de la que se toman las muestras es [2, 3, -1, -20, 5, 10].

En informática , el problema de la suma máxima de subconjuntos , también conocido como el problema de la suma máxima de segmentos , es la tarea de encontrar un subconjunto contiguo con la suma más grande, dentro de una matriz unidimensional dada A[1...n] de números. Se puede resolver en tiempo y espacio. ${\displaystyle O(n)}$ ${\displaystyle O(1)}$

Formalmente, la tarea es encontrar índices y con , tales que la suma ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle 1\leq i\leq j\leq n}$

${\displaystyle \sum _{x=i}^{j}A[x]}$

es lo más grande posible. (Algunas formulaciones del problema también permiten considerar el subconjunto vacío; por convención, la suma de todos los valores del subconjunto vacío es cero). Cada número en el conjunto de entrada A podría ser positivo, negativo o cero. ^[1]

Por ejemplo, para la matriz de valores [−2, 1, −3, 4, −1, 2, 1, −5, 4], la submatriz contigua con la suma más grande es [4, −1, 2, 1], con suma 6.

Algunas propiedades de este problema son:

1. Si la matriz contiene todos los números no negativos, entonces el problema es trivial; una submatriz máxima es la matriz completa.
2. Si la matriz contiene todos los números no positivos, entonces una solución es cualquier submatriz de tamaño 1 que contenga el valor máximo de la matriz (o la submatriz vacía, si está permitido).
3. Varias submatrices diferentes pueden tener la misma suma máxima.

Aunque este problema se puede resolver utilizando varias técnicas algorítmicas diferentes, incluyendo fuerza bruta, ^[2] dividir y vencer, ^[3] programación dinámica, ^[4] y reducción a caminos más cortos, un algoritmo simple de una sola pasada conocido como algoritmo de Kadane lo resuelve de manera eficiente.

Historia

El problema del subarreglo máximo fue propuesto por Ulf Grenander en 1977 como un modelo simplificado para la estimación de máxima verosimilitud de patrones en imágenes digitalizadas. ^[5]

Grenander buscaba encontrar un subarreglo rectangular con suma máxima, en un arreglo bidimensional de números reales. Un algoritmo de fuerza bruta para el problema bidimensional se ejecuta en tiempo O ( n ⁶ ); debido a que esto era prohibitivamente lento, Grenander propuso el problema unidimensional para comprender mejor su estructura. Grenander derivó un algoritmo que resuelve el problema unidimensional en tiempo O ( n ² ), ^{[nota 1]} mejorando el tiempo de ejecución de fuerza bruta de O ( n ³ ). Cuando Michael Shamos se enteró del problema, ideó de la noche a la mañana un algoritmo de divide y vencerás O ( n log n ) para él. Poco después, Shamos describió el problema unidimensional y su historia en un seminario de la Universidad Carnegie Mellon al que asistió Jay Kadane , quien diseñó en un minuto un algoritmo de tiempo O ( n ), ^{[5] [6] [7]} que es lo más rápido posible. ^{[nota 2]} En 1982, David Gries obtuvo el mismo algoritmo de tiempo O ( n ) aplicando la "estrategia estándar" de Dijkstra ; ^[8] en 1989, Richard Bird lo derivó mediante manipulación puramente algebraica del algoritmo de fuerza bruta utilizando el formalismo de Bird-Meertens . ^[9]

La generalización bidimensional de Grenander se puede resolver en tiempo O( n ³ ) ya sea utilizando el algoritmo de Kadane como una subrutina, o a través de un enfoque de divide y vencerás. Tamaki y Tokuyama (1998) y Takaoka (2002) propusieron algoritmos ligeramente más rápidos basados ​​en la multiplicación de matrices de distancia . Hay cierta evidencia de que no existe un algoritmo significativamente más rápido; un algoritmo que resuelva el problema de subarreglo máximo bidimensional en tiempo O( n ^3−ε ), para cualquier ε>0, implicaría un algoritmo igualmente rápido para el problema de caminos más cortos de todos los pares . ^[10]

Aplicaciones

Los problemas de submatrices máximas surgen en muchos campos, como el análisis de secuencias genómicas y la visión artificial .

El análisis de secuencias genómicas emplea algoritmos de subarreglo máximo para identificar segmentos biológicos importantes de secuencias de proteínas que tienen propiedades inusuales, asignando puntajes a puntos dentro de la secuencia que son positivos cuando está presente un motivo a reconocer y negativos cuando no lo está, y luego buscando el subarreglo máximo entre estos puntajes. Estos problemas incluyen segmentos conservados, regiones ricas en GC, repeticiones en tándem, filtro de baja complejidad, dominios de unión al ADN y regiones de alta carga. ^[11]

En la visión artificial , las imágenes de mapa de bits generalmente constan solo de valores positivos, para los cuales el problema de subarreglo máximo es trivial: el resultado es siempre el arreglo completo. Sin embargo, después de restar un valor umbral (como el valor de píxel promedio) de cada píxel, de modo que los píxeles superiores al promedio sean positivos y los píxeles inferiores al promedio sean negativos, el problema de subarreglo máximo se puede aplicar a la imagen modificada para detectar áreas brillantes dentro de ella. ^[12]

Algoritmo de Kadane

No se admiten submatrices vacías

El algoritmo de Kadane escanea la matriz dada de izquierda a derecha. En el paso n, calcula la submatriz con la suma más grande que termina en ; esta suma se mantiene en la variable . ^{[nota 3]} Además, calcula la submatriz con la suma más grande en cualquier parte de , se mantiene en la variable , ^{[nota 4]} y se obtiene fácilmente como el máximo de todos los valores de vistos hasta ahora, cf. línea 7 del algoritmo. ${\displaystyle A[1\ldots n]}$ ${\displaystyle j}$ ${\displaystyle j}$current_sum ${\displaystyle A[1\ldots j]}$best_sumcurrent_sum

Como invariante de bucle , en el paso n, el valor anterior de contiene el máximo sobre toda la suma . Por lo tanto, ^{[nota 5]} es el máximo sobre toda la suma . Para extender el último máximo para cubrir también el caso , es suficiente considerar también el subarreglo singleton . Esto se hace en la línea 6 asignando como el nuevo valor de , que después contiene el máximo sobre toda la suma . ${\displaystyle j}$current_sum ${\displaystyle i\in \{1,\ldots ,j-1\}}$ ${\displaystyle A[i]+\cdots +A[j-1]}$current_sum ${\displaystyle +A[j]}$ ${\displaystyle i\in \{1,\ldots ,j-1\}}$ ${\displaystyle A[i]+\cdots +A[j]}$ ${\displaystyle i=j}$ ${\displaystyle A[j\;\ldots \;j]}$ ${\displaystyle \max(A[j],}$current_sum ${\displaystyle +A[j])}$current_sum ${\displaystyle i\in \{1,\ldots ,j\}}$ ${\displaystyle A[i]+\cdots +A[j]}$

Por tanto, el problema se puede resolver con el siguiente código, ^[13] expresado en Python .

def  max_subarray ( números ): """Encuentra la suma más grande de cualquier submatriz contigua.""" mejor_suma  =  float ( '-inf' ) suma_actual  =  0 para  x  en  números : suma_actual  =  máx ( x ,  suma_actual  +  x ) mejor_suma  =  max ( mejor_suma ,  suma_actual ) devolver  mejor_suma

Si la entrada no contiene ningún elemento positivo, el valor devuelto es el del elemento más grande (es decir, el valor más cercano a 0), o infinito negativo si la entrada estaba vacía. Para que sea correcto, se debe generar una excepción cuando la matriz de entrada esté vacía, ya que una matriz vacía no tiene un máximo de submatriz no vacía. Si la matriz no está vacía, se podría usar su primer elemento en lugar de infinito negativo, si es necesario para evitar mezclar valores numéricos y no numéricos.

El algoritmo se puede adaptar al caso que permite submatrices vacías o realizar un seguimiento de los índices inicial y final de la submatriz máxima.

Este algoritmo calcula el subarreglo máximo que termina en cada posición a partir del subarreglo máximo que termina en la posición anterior, por lo que puede verse como un caso trivial de programación dinámica .

Se admiten submatrices vacías

El algoritmo original de Kadane resuelve la variante del problema cuando se admiten submatrices vacías. ^{[4] [7]} Esta variante devolverá 0 si la entrada no contiene elementos positivos (incluso cuando la entrada está vacía). Se obtiene mediante dos cambios en el código: en la línea 3, best_sumdebe inicializarse a 0 para tener en cuenta la submatriz vacía ${\displaystyle A[0\ldots -1]}$

 mejor_suma  =  0 ;

y la línea 6 del bucle for current_sumdebe actualizarse como max(0, current_sum + x). ^{[nota 6]}

 suma_actual  =  máx ( 0 ,  suma_actual  +  x )

Como invariante de bucle , en el paso n, el valor anterior de contiene el máximo sobre toda la suma . ^{[nota 7]} Por lo tanto, es el máximo sobre toda la suma . Para extender el último máximo para cubrir también el caso , es suficiente considerar también el subarreglo vacío . Esto se hace en la línea 6 asignando como el nuevo valor de , que después contiene el máximo sobre toda la suma . El código C / Frama-C verificado por máquina de ambas variantes se puede encontrar aquí. ${\displaystyle j}$current_sum ${\displaystyle i\in \{1,\ldots ,j\}}$ ${\displaystyle A[i]+\cdots +A[j-1]}$current_sum ${\displaystyle +A[j]}$ ${\displaystyle i\in \{1,\ldots ,j\}}$ ${\displaystyle A[i]+\cdots +A[j]}$ ${\displaystyle i=j+1}$ ${\displaystyle A[j+1\;\ldots \;j]}$ ${\displaystyle \max(0,}$current_sum ${\displaystyle +A[j])}$current_sum ${\displaystyle i\in \{1,\ldots ,j+1\}}$ ${\displaystyle A[i]+\cdots +A[j]}$

Calcular la mejor posición del subarreglo

El algoritmo también se puede modificar para realizar un seguimiento de los índices inicial y final de la submatriz máxima.

Debido a la forma en que este algoritmo utiliza subestructuras óptimas (el subarreglo máximo que termina en cada posición se calcula de manera simple a partir de un subproblema relacionado pero más pequeño y superpuesto: el subarreglo máximo que termina en la posición anterior), este algoritmo puede verse como un ejemplo simple/trivial de programación dinámica .

Complejidad

La complejidad en tiempo de ejecución del algoritmo de Kadane es y su complejidad espacial es . ^{[4] [7]} ${\displaystyle O(n)}$ ${\displaystyle O(1)}$

Generalizaciones

Se pueden plantear problemas similares para matrices de dimensiones superiores, pero sus soluciones son más complicadas; véase, por ejemplo, Takaoka (2002). Brodal y Jørgensen (2007) demostraron cómo encontrar las k sumas de subarreglos más grandes en una matriz unidimensional, en el límite de tiempo óptimo . ${\displaystyle O(n+k)}$

La suma máxima de k submatrices disjuntas también se puede calcular en el límite de tiempo óptimo . ^[14] ${\displaystyle O(n+k)}$

Véase también

• Problema de suma de subconjuntos

Notas

1. Utilizando una tabla precalculada de sumas acumulativas para calcular la suma del subarreglo en tiempo constante ${\displaystyle S[k]=\sum _{x=1}^{k}A[x]}$ ${\displaystyle \sum _{x=i}^{j}A[x]=S[j]-S[i-1]}$
2. ya que cada algoritmo debe al menos escanear la matriz una vez, lo que ya toma O ( n ) tiempo
3. nombrado MaxEndingHereen Bentley (1989) y cen Gries (1982)
4. nombrado MaxSoFaren Bentley (1989) y sen Gries (1982)
5. En el código Python a continuación, se expresa como , con el índice izquierdo implícito. ${\displaystyle A[j]}$x ${\displaystyle j}$
6. Aunque Bentley (1989) no menciona esta diferencia, el uso de xen lugar de 0en la versión anterior sin submatrices vacías logra mantener su bucle invariante al comienzo del paso n.current_sum ${\displaystyle =\max _{i\in \{1,...,j-1\}}A[i]+...+A[j-1]}$ ${\displaystyle j}$
7. Esta suma es cuando , correspondiente al subarreglo vacío . ${\displaystyle 0}$ ${\displaystyle i=j}$ ${\displaystyle A[j\ldots j-1]}$

Notas

1. Bentley 1989, pág. 69.
2. Bentley 1989, pág. 70.
3. Bentley 1989, pág. 73.
4. Bentley 1989, pág. 74.
5. Bentley 1984, pág. 868-869.
6. Bentley 1989, pág. 76-77.
7. Gries 1982, pág. 211.
8. Gries 1982, pág. 209-211.
9. Bird 1989, Secc.8, p.126.
10. Backurs, Dikkala y Tzamos 2016.
11. Ruzzo y Tompa (1999); Alves, Cáceres y Canción (2004)
12. Bae y Takaoka (2006); Weddell y otros (2013)
13. Bentley 1989, pág. 78,171. Bentley, al igual que Gries, introduce primero la variante que admite submatrices vacías (véase más adelante) y describe únicamente los cambios.
14. Bengtsson y Chen 2007.

Referencias

• Alves, Carlos ER; Cáceres, Edson; Song, Siang W. (2004), "Algoritmos BSP/CGM para máxima subsecuencia y máxima submatriz", en Kranzlmüller, Dieter; Kacsuk, Péter; Dongarra, Jack J. (eds.), Avances recientes en máquinas virtuales paralelas e interfaces de paso de mensajes, 11.ª reunión del grupo de usuarios europeos de PVM/MPI, Budapest, Hungría, 19-22 de septiembre de 2004, Actas , Lecture Notes in Computer Science, vol. 3241, Springer, págs. 139-146, doi :10.1007/978-3-540-30218-6_24, ISBN 978-3-540-23163-9
• Backurs, Arturs; Dikkala, Nishanth; Tzamos, Christos (2016), "Resultados de dureza ajustados para rectángulos de peso máximo", Proc. 43.° Coloquio internacional sobre autómatas, lenguajes y programación : 81:1–81:13, doi : 10.4230/LIPIcs.ICALP.2016.81 , S2CID  12720136
• Bae, Sung Eun (2007), Algoritmos secuenciales y paralelos para el problema del subarreglo máximo generalizado (PDF) (tesis doctoral), Universidad de Canterbury, S2CID  2681670, archivado desde el original (PDF) el 2017-10-26.
• Bae, Sung Eun; Takaoka, Tadao (2006), "Algoritmos mejorados para el problema del subarreglo de \emph{K}-máximo", The Computer Journal , 49 (3): 358–374, doi :10.1093/COMJNL/BXL007
• Bengtsson, Fredrik; Chen, Jingsen (2007), Cálculo óptimo de segmentos con la máxima puntuación (PDF) (Informe de investigación), Universidad Tecnológica de Luleå
• Bentley, Jon (1984), "Perlas de programación: técnicas de diseño de algoritmos", Communications of the ACM , 27 (9): 865–873, doi :10.1145/358234.381162, S2CID  207565329
• Bentley, Jon (mayo de 1989), Programming Pearls (¿2.ª ed.?), Reading, MA: Addison Wesley, ISBN 0-201-10331-1
• Bird, Richard S. (1989), "Identidades algebraicas para el cálculo de programas", The Computer Journal , 32 (2): 122–126, doi :10.1093/comjnl/32.2.122
• Brodal, Gerth Stølting; Jørgensen, Allan Grønlund (2007), "Un algoritmo de tiempo lineal para el problema de k sumas máximas", Fundamentos matemáticos de la informática 2007 , Lecture Notes in Computer Science, vol. 4708, Springer-Verlag, págs. 442–453, doi :10.1007/978-3-540-74456-6_40, ISBN 978-3-540-74455-9.
• Gries, David (1982), "Una nota sobre la estrategia estándar para desarrollar invariantes de bucles y bucles" (PDF) , Science of Computer Programming , 2 (3): 207–241, doi :10.1016/0167-6423(83)90015-1, hdl :1813/6370
• Ruzzo, Walter L.; Tompa, Martin (1999), "Un algoritmo de tiempo lineal para encontrar todas las subsecuencias de puntuación máxima", en Lengauer, Thomas; Schneider, Reinhard; Bork, Peer; Brutlag, Douglas L.; Glasgow, Janice I.; Mewes, Hans-Werner; Zimmer, Ralf (eds.), Actas de la Séptima Conferencia Internacional sobre Sistemas Inteligentes para Biología Molecular, 6-10 de agosto de 1999, Heidelberg, Alemania , AAAI, págs. 234-241
• Takaoka, Tadao (2002), "Algoritmos eficientes para el problema de subarreglo máximo mediante multiplicación de matrices de distancia", Electronic Notes in Theoretical Computer Science , 61 : 191–200, doi : 10.1016/S1571-0661(04)00313-5.
• Tamaki, Hisao; Tokuyama, Takeshi (1998), "Algoritmos para el problema de subarreglo máximo basado en la multiplicación de matrices", Actas del 9.º Simposio sobre algoritmos discretos (SODA) : 446–452, ISBN 978-0-89871-410-4, consultado el 17 de noviembre de 2018
• Weddell, Stephen John; Read, Tristan; Thaher, Mohammed; Takaoka, Tadao (2013), "Algoritmos de subarreglos máximos para uso en imágenes astronómicas", Journal of Electronic Imaging , 22 (4): 043011, Bibcode :2013JEI....22d3011W, doi :10.1117/1.JEI.22.4.043011

Enlaces externos

• TAN, Lirong. "Problemas de suma máxima de submatrices contiguas" (PDF) . Archivado desde el original (PDF) el 2015-10-10 . Consultado el 2017-10-26 .
• Mu, Shin-Cheng (2010). "El problema de la suma máxima de segmentos: su origen y una derivación".
• "Notas sobre el problema del subarreglo máximo". 2012.
• www.algorithmist.com
• alexeigor.wikidot.com
• Problema de suma subsiguiente máxima en Rosetta Code
• Página de geeksforgeeks sobre el algoritmo de Kadane