En informática , el problema de subarreglos de suma máxima es la tarea de encontrar un subarreglo contiguo con la suma más grande, dentro de un arreglo unidimensional dado A [1 ... n] de números. Formalmente, la tarea es encontrar índices y con , tal que la suma
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 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:
- Si la matriz contiene todos los números no negativos, entonces el problema es trivial; un subarreglo máximo es el arreglo completo.
- Si el arreglo contiene todos los 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).
- Varias submatrices diferentes pueden tener la misma suma máxima.
Este problema se puede resolver utilizando varias técnicas algorítmicas diferentes, que incluyen fuerza bruta, [2] divide y vencerás, [3] programación dinámica, [4] y reducción a las rutas más cortas. [ cita requerida ]
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 estaba buscando encontrar un subconjunto 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 un tiempo O ( n 6 ); 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 2 ), [nota 1] mejorando el tiempo de ejecución de fuerza bruta de O ( n 3 ). Cuando Michael Shamos se enteró del problema, de la noche a la mañana ideó un algoritmo de divide y vencerás O ( n log n ) . 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 como 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 la manipulación puramente algebraica del algoritmo de fuerza bruta utilizando el formalismo Bird-Meertens . [9]
La generalización bidimensional de Grenander se puede resolver en tiempo O ( n 3 ) utilizando el algoritmo de Kadane como subrutina o mediante un enfoque de divide y vencerás. Tamaki y Tokuyama (1998) y Takaoka (2002) han propuesto algoritmos ligeramente más rápidos basados en la multiplicación de matrices de distancias . Existe alguna evidencia de que no existe un algoritmo significativamente más rápido; un algoritmo que resuelve el problema de subconjunto máximo bidimensional en un 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 subarreglos máximos 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 subarreglos máximos para identificar segmentos biológicos importantes de secuencias de proteínas. [ cita requerida ] 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. [ cita requerida ]
En visión por computadora , los algoritmos de subarreglo máximo se utilizan en imágenes de mapa de bits para detectar el área más brillante en una imagen.
Algoritmo de Kadane
Ejecución de ejemplo |
---|
El algoritmo original de Kadane resuelve la versión del problema cuando se admiten subarreglos vacíos. Escanea la matriz dadade izquierda a derecha. En elth paso, calcula el subarreglo con la suma más grande terminando en ; esta suma se mantiene en variable current_sum
. [nota 3] Además, calcula el subarreglo con la mayor suma en cualquier lugar en, mantenido en variable best_sum
, [nota 4] y fácilmente obtenido como el máximo de todos los valores de current_sum
vistos hasta ahora, cf. línea 7 del algoritmo.
Como un ciclo invariante , en elth paso, el antiguo valor de current_sum
mantiene el máximo sobre todos de la suma . [nota 5] Por lo tanto,current_sum
[nota 6] es el máximo de todos de la suma . Para extender este ú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 asignandocurrent_sum
como el nuevo valor de current_sum
, que después de eso tiene el máximo sobre todos de la suma .
Por lo tanto, el problema se puede resolver con el siguiente código, [4] [7] expresado aquí en Python :
def max_subarray ( números ): "" "Encuentre la mayor suma de cualquier subarreglo contiguo." "" best_sum = 0 # o: float ('- inf') suma_actual = 0 para x en números : suma_actual = max ( 0 , suma_actual + x ) best_sum = max ( best_sum , current_sum ) return best_sum
Esta versión del algoritmo devolverá 0 si la entrada no contiene elementos positivos (incluso cuando la entrada está vacía).
Para la variante del problema que no permite subarreglos vacíos, best_sum
debe inicializarse a infinito negativo en su lugar [11] y también en el bucle for current_sum
debe actualizarse como max(x, current_sum + x)
. [nota 7] En ese caso, si la entrada no contiene ningún elemento positivo, el valor devuelto es el del elemento más grande (es decir, el valor menos negativo), o infinito negativo si la entrada estaba vacía.
El algoritmo se puede modificar para realizar un seguimiento de los índices de inicio y finalización del subarreglo máximo también:
def max_subarray ( números ): "" "Encuentre un subarreglo contiguo con la mayor suma." "" best_sum = 0 # o: float ('- inf') best_start = best_end = 0 # o: Ninguno suma_actual = 0 para current_end , x en enumerate ( números ): si suma_actual <= 0 : # Iniciar una nueva secuencia en el elemento actual current_start = current_end suma_actual = x otra cosa : # Extiende la secuencia existente con el elemento actual suma_corriente + = x if current_sum > best_sum : best_sum = current_sum best_start = current_start best_end = current_end + 1 # el +1 es para hacer que 'best_end' sea exclusivo return best_sum , best_start , best_end
En Python, las matrices se indexan a partir de 0 y el índice final generalmente se excluye, de modo que la submatriz [22, 33] en la matriz [-11, 22, 33, -44] comenzaría en el índice 1 y terminaría en el índice. 3.
Debido a la forma en que este algoritmo utiliza subestructuras óptimas (el subarreglo máximo que termina en cada posición se calcula de una 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 simple / ejemplo trivial de programación dinámica .
La complejidad del tiempo de ejecución del algoritmo de Kadane es . [4] [7]
Generalizaciones
Pueden plantearse 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 un arreglo unidimensional, en el tiempo óptimo.
Los subarreglos de suma máxima k -disjuntos también se pueden calcular en el límite de tiempo óptimo. [12]
Ver también
- Problema de suma de subconjuntos
Notas
- ^ Utilizando una tabla precalculada de sumas acumulativas para calcular la suma del subarreglo en tiempo constante
- ^ dado que cada algoritmo debe al menos escanear la matriz una vez, lo que ya lleva O ( n ) tiempo
- ^ nombrado
MaxEndingHere
en Bentley (1989) yc
en Gries (1982) - ^ nombrado
MaxSoFar
en Bentley (1989) ys
en Gries (1982) - ^ Esta suma es Cuándo , correspondiente al subarreglo vacío .
- ^ En el código de Python a continuación,se expresa como
x
, con el índice dejado implícito. - ↑ Si bien Bentley (1989) no menciona esta última modificación, logra mantener invariante el bucle modificado
current_sum
al principio de el paso.
Referencias
- ^ Bentley 1989 , p. 69.
- ^ Bentley 1989 , p. 70.
- ^ Bentley 1989 , p. 73.
- ↑ a b c Bentley , 1989 , p. 74.
- ↑ a b Bentley , 1984 , p. 868-869.
- ^ Bentley 1989 , p. 76-77.
- ↑ a b c Gries , 1982 , p. 211.
- ^ Gries 1982 , p. 209-211.
- ^ Bird 1989 , sección 8, p.126.
- ^ Backurs, Dikkala y Tzamos 2016 .
- ^ Bentley 1989 , p. 78.171.
- ^ Bengtsson y Chen 2007 .
- Backurs, Arturs; Dikkala, Nishanth; Tzamos, Christos (2016), "Resultados de dureza ajustada 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 de subarreglo máximo generalizado (PDF) (tesis de doctorado), Universidad de Canterbury, S2CID 2681670 , archivado desde el original (PDF) el 26 de octubre de 2017.
- Bengtsson, Fredrik; Chen, Jingsen (2007), Computación óptima de segmentos de máxima puntuación (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 (2nd? Ed.), Reading, MA: Addison Wesley, ISBN 0-201-10331-1
- Bird, Richard S. (1989), "Identidades algebraicas para el cálculo de programas" (PDF) , The Computer Journal , 32 (2): 122-126, doi : 10.1093 / comjnl / 32.2.122[ enlace muerto ]
- Brodal, Gerth Stølting; Jørgensen, Allan Grønlund (2007), "Un algoritmo de tiempo lineal para el problema de k sumas máximas", Mathematical Foundations of Computer Science , Lecture Notes in Computer Science, 4708 , Springer-Verlag, pp. 442-453, doi : 10.1007 / 978 -3-540-74456-6_40.
- Gries, David (1982), "A Note on the Standard Strategy for Developing Loop Invariants and Loops" (PDF) , Science of Computer Programming , 2 (3): 207–241, doi : 10.1016 / 0167-6423 (83) 90015 -1 , hdl : 1813/6370
- Takaoka, Tadao (2002), "Algoritmos eficientes para el problema de subarreglos máximos por 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 noveno simposio sobre algoritmos discretos (SODA) : 446–452 , consultado el 17 de noviembre de 2018
enlaces externos
- TAN, Lirong. "Problemas de suma máxima de subarreglos contiguos" (PDF) . Archivado desde el 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 del segmento: su origen y una derivación" .
- "Notas sobre el problema del subarreglo máximo" . 2012.
- www.algorithmist.com
- alexeigor.wikidot.com
- mayor problema de suma subsecuente en el código Rosetta
- página geeksforgeeks sobre el algoritmo de Kadane