Hispanopedia Wiki
Articulo de referencia

Problema de submatriz máxima

Visualización de cómo cambian los subconjuntos en función de las posiciones inicial y final de un subconjunto. Cada línea de color corresponde a un índice inicial fijo en el arr...

Hispanopedia WikiContenido en espanolLectura gratuita
Visualización de cómo cambian los subconjuntos en función de las posiciones inicial y final de un subconjunto. Cada línea de color corresponde a un índice inicial fijo en el arreglo. El punto más a la izquierda de una línea representa el subconjunto de un solo elemento que comienza en ese índice, y cada punto subsiguiente extiende el subconjunto con un elemento hacia la derecha. La coordenada x de un punto es el índice del último elemento del subconjunto, y la coordenada y es la suma del subconjunto. En este caso, el arreglo original del que se toman los subconjuntos es [2, 3, -1, -20, 5, 10].

En ciencias de la computación , el problema de la suma máxima de submatrices , también conocido como el problema de la suma máxima de segmentos , es la tarea de encontrar una submatriz contigua con la suma más grande, dentro de una matriz unidimensional dada A[1...n] de números. Se puede resolver enO(norte){\displaystyle O(n)}tiempo yO(1){\displaystyle O(1)}espacio.

Formalmente, la tarea consiste en encontrar índicesi{\displaystyle i}yj{\displaystyle j}con1≤i≤j≤norte{\displaystyle 1\leq i\leq j\leq n}, de tal manera que la suma

∑incógnita=ijA[incógnita]{\displaystyle \sum _{x=i}^{j}A[x]}

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

Por ejemplo, para el conjunto de valores [ − 2, 1, − 3, 4, − 1, 2, 1, − 5, 4], el subconjunto contiguo con la suma más grande es [4, − 1, 2, 1], con una suma de 6.

Algunas propiedades de este problema son:

  1. Si el arreglo contiene solo números no negativos, entonces el problema es trivial; un subarreglo máximo es el arreglo completo.
  2. Si el arreglo contiene solo números no positivos, entonces una solución es cualquier subarreglo de tamaño 1 que contenga el valor máximo del arreglo (o el subarreglo vacío, 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 ] divide y vencerás , [ 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 subconjunto 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 una submatriz rectangular con suma máxima en una matriz 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² ) usando sumas de prefijos [ 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 resolverlo. 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³ ) utilizando el algoritmo de Kadane como subrutina o mediante 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 . Existe cierta evidencia de que no existe un algoritmo significativamente más rápido; un algoritmo que resuelva el problema del subconjunto máximo bidimensional en tiempo O( n³ − ε ), para cualquier ε > 0, implicaría un algoritmo igualmente rápido para el problema de los caminos más cortos entre 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 por computadora .

El análisis de secuencias genómicas emplea algoritmos de submatrices máximas para identificar segmentos biológicos importantes de secuencias de proteínas con propiedades inusuales, asignando puntuaciones a puntos dentro de la secuencia: positivas cuando está presente un motivo a reconocer y negativas cuando no lo está. Posteriormente, se busca la submatriz máxima entre estas puntuaciones. Estos problemas incluyen segmentos conservados, regiones ricas en GC, repeticiones en tándem, filtros de baja complejidad, dominios de unión al ADN y regiones de alta carga. [ 11 ]

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

El algoritmo de Kadane

No se admiten submatrices vacías

El algoritmo de Kadane escanea el array dado.A[1…norte]{\displaystyle A[1\ldots n]}de izquierda a derecha. En elj{\displaystyle j}En el paso n, calcula el subconjunto con la suma más grande que termina enj{\displaystyle j}; esta suma se mantiene en la variable current_sum. [ nota 3 ] Además, calcula la submatriz con la suma más grande en cualquier lugar deA[1…j]{\displaystyle A[1\ldots j]}, mantenido en variable best_sum, [ nota 4 ] y se obtiene fácilmente como el máximo de todos los valores current_sumvistos hasta ahora, cf. línea 7 del algoritmo.

Como invariante de bucle , en elj{\displaystyle j}En el paso t, el antiguo valor de current_summantiene el máximo sobre todosi∈{1,…,j−1}{\displaystyle i\in \{1,\ldots ,j-1\}}de la sumaA[i]+⋯+A[j−1]{\displaystyle A[i]+\cdots +A[j-1]}. Por lo tanto,current_sum+A[j]{\displaystyle +A[j]}[ nota 5 ] es el máximo sobre todosi∈{1,…,j−1}{\displaystyle i\in \{1,\ldots ,j-1\}}de la sumaA[i]+⋯+A[j]{\displaystyle A[i]+\cdots +A[j]}. Extender este último máximo para que también cubra el casoi=j{\displaystyle i=j}, basta con considerar también el subarreglo unitarioA[j…j]{\displaystyle A[j\;\ldots \;j]}Esto se hace en la línea 6 asignandomáximo(A[j],{\displaystyle \max(A[j],}current_sum+A[j]){\displaystyle +A[j])}como el nuevo valor de current_sum, que después de eso tiene el máximo sobre todosi∈{1,…,j}{\displaystyle i\in \{1,\ldots ,j\}}de la sumaA[i]+⋯+A[j]{\displaystyle A[i]+\cdots +A[j]}.

Por lo 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 subconjunto contiguo."""mejor_suma = float ( '-inf' )suma_actual = 0para x en números :suma_actual = máximo ( x , suma_actual + x )mejor_suma = máximo ( 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 garantizar la corrección, se debe generar una excepción cuando el array de entrada esté vacío, ya que un array vacío no tiene un subarreglo no vacío máximo. Si el array no está vacío, su primer elemento podría usarse en lugar de infinito negativo, si fuera necesario para evitar la mezcla de valores numéricos y no numéricos.

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

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

Submatrices vacías admitidas

El algoritmo de Kadane, tal como se publicó originalmente, sirve para resolver la variante del problema que permite submatrices vacías. [ 4 ] [ 7 ] En dicha variante, la respuesta es 0 cuando la entrada no contiene elementos positivos (incluso cuando la entrada está vacía). La variante se obtiene con dos cambios en el código: en la línea 3, best_sumdebe inicializarse a 0 para tener en cuenta la submatriz vacía.A[0…−1]{\displaystyle A[0\ldots -1]}

mejor_suma = 0 ;

y la línea 6 del bucle forcurrent_sum debe actualizarse a max(0, current_sum + x). [ nota 6 ]

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

Como invariante de bucle , en elj{\displaystyle j}En el paso t, el antiguo valor de current_summantiene el máximo sobre todosi∈{1,…,j}{\displaystyle i\in \{1,\ldots ,j\}}de la sumaA[i]+⋯+A[j−1]{\displaystyle A[i]+\cdots +A[j-1]}. [ nota 7 ] Por lo tanto,current_sum+A[j]{\displaystyle +A[j]} es el máximo sobre todosi∈{1,…,j}{\displaystyle i\in \{1,\ldots ,j\}}de la sumaA[i]+⋯+A[j]{\displaystyle A[i]+\cdots +A[j]}. Extender este último máximo para que también cubra el casoi=j+1{\displaystyle i=j+1}, basta con considerar también el subarreglo vacíoA[j+1…j]{\displaystyle A[j+1\;\ldots \;j]}Esto se hace en la línea 6 asignandomáximo(0,{\displaystyle \max(0,}current_sum+A[j]){\displaystyle +A[j])}como el nuevo valor de current_sum, que después de eso tiene el máximo sobre todosi∈{1,…,j+1}{\displaystyle i\in \{1,\ldots ,j+1\}}de la sumaA[i]+⋯+A[j]{\displaystyle A[i]+\cdots +A[j]}El código C / Frama-C verificado por máquina de ambas variantes se puede encontrar aquí .

Calcular la posición del mejor subconjunto

El algoritmo puede modificarse para que también registre los índices inicial y final del subconjunto máximo.

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

Complejidad

La complejidad temporal del algoritmo de Kadane esO(norte){\displaystyle O(n)}y su complejidad espacial esO(1){\displaystyle O(1)}. [ 4 ] [ 7 ]

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) mostraron cómo encontrar las k sumas de subarreglos más grandes en una matriz unidimensional, en el límite de tiempo óptimo.O(norte+k){\displaystyle O(n+k)}.

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

Véase también

Notas

  1. ↑ Mediante el uso de una tabla precalculada de sumas acumuladasS[k]=∑incógnita=1kA[incógnita]{\displaystyle S[k]=\sum _{x=1}^{k}A[x]}para calcular la suma de la submatriz∑incógnita=ijA[incógnita]=S[j]−S[i−1]{\displaystyle \sum _{x=i}^{j}A[x]=S[j]-S[i-1]}en tiempo constante
  2. ↑ ya que cada algoritmo debe al menos escanear el arreglo una vez, lo que ya toma O ( n ) tiempo.
  3. ↑ mencionadoMaxEndingHereen Bentley (1989) ycen Gries (1982)
  4. ↑ mencionadoMaxSoFaren Bentley (1989) ysen Gries (1982)
  5. ↑ En el código Python a continuación,A[j]{\displaystyle A[j]}se expresa como x, con el índicej{\displaystyle j}implícito.
  6. ↑ Si bien Bentley (1989) no menciona esta diferencia, usarxen lugar de0en la versión anterior sin submatrices vacías logra mantener su invariante de buclecurrent_sum=máximoi∈{1,...,j−1}A[i]+...+A[j−1]{\displaystyle =\max _{i\in \{1,...,j-1\}}A[i]+...+A[j-1]}al comienzo de laj{\displaystyle j}º paso.
  7. ↑ Esta suma es0{\displaystyle 0}cuandoi=j{\displaystyle i=j}, correspondiente a la submatriz vacíaA[j…j−1]{\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. 1 2 3 Bentley 1989 , pág. 74.
  5. 1 2 Bentley 1984 , págs. 868-869.
  6. ↑ Bentley 1989 , págs. 76-77.
  7. 1 2 3 Gries 1982 , pág. 211.
  8. ↑ Gries 1982 , págs. 209-211.
  9. ↑ Bird 1989 , Sec.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 et al. (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 abajo , y describe solo los cambios.
  14. ↑ Bengtsson y Chen 2007 .

Referencias

  • Alves, Carlos ER; Cáceres, Edson; Song, Siang W. (2004), "Algoritmos BSP/CGM para subsecuencia máxima y submatriz máxima", en Kranzlmüller, Dieter; Kacsuk, Péter; Dongarra, Jack J. (eds.), Avances recientes en máquinas virtuales paralelas e interfaz de paso de mensajes, 11.ª Reunión del Grupo Europeo de Usuarios de PVM/MPI, Budapest, Hungría, 19-22 de septiembre de 2004, Actas , Lecture Notes in Computer Science, vol.  3241, Springer, pp. 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 ajustada para rectángulos de peso máximo", 43º Coloquio internacional sobre autómatas, lenguajes y programación (ICALP 2016) , Actas internacionales de Leibniz en informática (LIPIcs), vol.  55, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, págs.  81:1–81:13, doi : 10.4230/LIPIcs.ICALP.2016.81 , ISBN 978-3-95977-013-2, S2CID 12720136 
  • Bae, Sung Eun (2007), Algoritmos secuenciales y paralelos para el problema generalizado del subconjunto máximo (PDF) (tesis doctoral), Universidad de Canterbury, S2CID 2681670 , archivado del original (PDF) el 26 de octubre de 2017. .
  • Bae, Sung Eun; Takaoka, Tadao (2006), "Algoritmos mejorados para el problema de subarreglos \emph{K}-máximos", The Computer Journal , 49 (3): 358–374 , doi : 10.1093/COMJNL/BXL007
  • Bengtsson, Fredrik; Chen, Jingsen (2007), Cálculo óptimo de segmentos con puntuación máxima (PDF) (Informe de investigación), Universidad Tecnológica de Luleå
  • Bentley, Jon (1984), "Programming Pearls: Algorithm Design Techniques", 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 y bucles" , 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 la Biología Molecular, 6-10 de agosto de 1999, Heidelberg, Alemania , AAAI, pp. 234-241 . 
  • Takaoka, Tadao (2002), "Algoritmos eficientes para el problema del subconjunto máximo mediante la 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 submatriz máxima basados ​​en la multiplicación de matrices" , Actas del 9.º Simposio sobre Algoritmos Discretos (SODA) : 446–452 , ISBN 978-0-89871-410-4Consultado el 17 de noviembre de 2018 .{{citation}}: CS1 mantenimiento: parámetro de trabajo con ISBN ( enlace )
  • Weddell, Stephen John; Read, Tristan; Thaher, Mohammed; Takaoka, Tadao (2013), "Algoritmos de submatrices máximas para su uso en imágenes astronómicas", Journal of Electronic Imaging , 22 (4) 043011, Bibcode : 2013JEI....22d3011W , doi : 10.1117/1.JEI.22.4.043011
  • TAN, Lirong. "Problemas de suma máxima de submatrices contiguas" (PDF) . Archivado del original (PDF) el 10 de octubre de 2015. Consultado el 26 de octubre de 2017 .
  • Mu, Shin-Cheng (2010). "El problema de la suma máxima de segmentos: su origen y una derivación" .
  • "Notas sobre el problema del subconjunto máximo" . 2012.
  • www.algorithmist.com
  • alexeigor.wikidot.com
  • Problema de suma subsecuente máxima en Rosetta Code
  • Página de geeksforgeeks sobre el algoritmo de Kadane