Algoritmo de Ruzzo-Tompa

El algoritmo de Ruzzo-Tompa o algoritmo RT ^{[ 1 ]} es un algoritmo de tiempo lineal para encontrar todas las subsecuencias contiguas, no superpuestas y de puntuación máxima en una secuencia de números reales. ^{[ 2 ]} El algoritmo de Ruzzo-Tompa fue propuesto por Walter L. Ruzzo y Martin Tompa. ^{[ 3 ]} Este algoritmo es una mejora con respecto a los algoritmos de tiempo cuadrático conocidos anteriormente. ^{[ 1 ]} La subsecuencia de puntuación máxima del conjunto producido por el algoritmo también es una solución al problema de la submatriz máxima .

El algoritmo Ruzzo-Tompa tiene aplicaciones en bioinformática , ^{[ 4 ]} web scraping , ^{[ 5 ]} y recuperación de información . ^{[ 6 ]}

El problema de encontrar todas las subsecuencias máximas se define de la siguiente manera: Dada una lista de puntuaciones numéricas reales${\displaystyle x_{1},x_{2},\ldots ,x_{n}}$, encuentra la lista de subsecuencias contiguas que da la mayor puntuación total, donde la puntuación de cada subsecuencia${\displaystyle S_{i,j}=\sum _{i\leq k\leq j}x_{k}}$. Las subsecuencias deben ser disjuntas (no superpuestas) y tener una puntuación positiva. ^{[ 9 ]}

Existen varios enfoques para resolver el problema de todas las subsecuencias de puntuación máxima. Un enfoque natural es utilizar algoritmos existentes de tiempo lineal para encontrar la subsecuencia máxima (véase el problema de la submatriz máxima ) y luego encontrar recursivamente las subsecuencias máximas a la izquierda y a la derecha de la subsecuencia máxima. El análisis de este algoritmo es similar al de Quicksort : la subsecuencia máxima podría ser pequeña en comparación con el resto de la secuencia, lo que lleva a un tiempo de ejecución de${\displaystyle O(n^{2})}$en el peor de los casos.

La implementación estándar del algoritmo Ruzzo-Tompa se ejecuta en${\displaystyle O(n)}$El algoritmo requiere tiempo y espacio O ( n ), donde n es la longitud de la lista de puntuaciones. Utiliza programación dinámica para construir progresivamente la solución final resolviendo incrementalmente subconjuntos cada vez mayores del problema. La descripción del algoritmo proporcionada por Ruzzo y Tompa es la siguiente:

Lee las puntuaciones de izquierda a derecha y mantén la suma acumulada de las puntuaciones leídas. Mantén una lista ordenada.${\displaystyle I_{1},I_{2},\ldots ,I_{j}}$de subsecuencias disjuntas. Para cada subsecuencia${\displaystyle I_{j}}$, registrar el total acumulado${\displaystyle L_{j}}$de todas las puntuaciones hasta pero sin incluir la puntuación más a la izquierda de${\displaystyle I_{j}}$y el total${\displaystyle R_{j}}$hasta e incluyendo la puntuación más a la derecha de${\displaystyle I_{j}}$.

Las listas están inicialmente vacías. Las puntuaciones se leen de izquierda a derecha y se procesan de la siguiente manera. Las puntuaciones no positivas no requieren procesamiento especial, por lo que se lee la siguiente puntuación. Una puntuación positiva se incorpora a una nueva subsecuencia.${\displaystyle I_{k}}$de longitud uno que luego se integra en la lista mediante el siguiente proceso:

1. La lista${\displaystyle I}$se busca de derecha a izquierda el valor máximo de${\displaystyle j}$satisfactorio${\displaystyle L_{j}<L_{k}}$
2. Si no existe tal cosa${\displaystyle j}$, luego añade${\displaystyle I_{k}}$hasta el final de la lista.
3. Si existe tal cosa${\displaystyle j}$, y${\displaystyle R_{j}\geq R_{k}}$, luego añade${\displaystyle I_{k}}$hasta el final de la lista.
4. De lo contrario (es decir, existe tal aj, pero${\displaystyle R_{j}<R_{k}}$), extender la subsecuencia${\displaystyle I_{k}}$a la izquierda para abarcar todo hasta la puntuación más a la izquierda inclusive en${\displaystyle I_{j}}$. Eliminar subsecuencias${\displaystyle I_{j},I_{j}+1,\ldots ,I_{k}-1}$de la lista y agregar${\displaystyle I_{k}}$hasta el final de la lista. Reconsidere la subsecuencia recientemente extendida.${\displaystyle I_{k}}$(ahora renumerado)${\displaystyle I_{j}}$) como en el paso 1.

Una vez que se llega al final de la entrada, todas las subsecuencias que quedan en la lista${\displaystyle I}$son máximos. ^{[ 2 ]}

El siguiente código Python implementa el algoritmo de Ruzzo-Tompa:

def ruzzo_tompa ( puntuaciones ):"""Algoritmo de Ruzzo-Tompa."""k = 0total = 0# Asignación de matrices de tamaño nI , L , R , Lidx = [[ 0 ] * len ( puntuaciones ) para _ en rango ( 4 )]para i , s en enumerate ( puntuaciones ):total += ssi s > 0 :# Almacenar I[k] por índices (inicio, fin) de puntuacionesI [ k ] = ( i , i + 1 )Lidx [ k ] = iL [ k ] = total - sR [ k ] = totalmientras sea verdadero :maxj = Ningunopara j en rango ( k - 1 , - 1 , - 1 ):si L [ j ] < L [ k ]:maxj = jromperSi maxj no es None y R [ maxj ] < R [ k ]:I [ maxj ] = ( Lidx [ maxj ], i + 1 )R [ maxj ] = totalk = maxjdemás :k += 1romper# Obtención de subsecuencias máximas utilizando índices almacenadosdevolver [ puntuaciones [ I [ l ][ 0 ] : I [ l ][ 1 ]] para l en rango ( k )]

• Problema de submatriz máxima
• Ordenación rápida

• Ali, Syed Arslan; Raza, Basit; Malik, Ahmad Kamran; Shahid, Ahmad Raza; Faheem, Muhammad; Alquhayz, Hani; Kumar, Yogan Jaya (2020). "Un enfoque de red neuronal profunda (OCI-DBN) optimizado y mejorado para la predicción de enfermedades cardíacas basado en el algoritmo genético apilado de Ruzzo-Tompa" . Acceso IEEE . 8. Instituto de Ingenieros Eléctricos y Electrónicos (IEEE): 65947–65958 . Bibcode : 2020IEEEA...865947A . doi : 10.1109/access.2020.2985646 . ISSN 2169-3536 . S2CID 215817246 .