El algoritmo SMAWK es un algoritmo para encontrar el valor mínimo en cada fila de una matriz totalmente monótona definida implícitamente . Lleva el nombre de las iniciales de sus cinco inventores, Peter Shor , Shlomo Moran , Alok Aggarwal, Robert Wilber y Maria Klawe . [1]
Aporte
Para los propósitos de este algoritmo, una matriz se define como monótona si el valor mínimo de cada fila ocurre en una columna que es igual o mayor que la columna del mínimo de la fila anterior. Es totalmente monótono si la misma propiedad es cierta para cada submatriz (definida por un subconjunto arbitrario de las filas y columnas de la matriz dada). De manera equivalente, una matriz es totalmente monótona si no existe una submatriz de 2 × 2 cuyos mínimos de fila se encuentran en las esquinas superior derecha e inferior izquierda. Cada matriz de Monge es totalmente monótona, pero no necesariamente al revés.
Para el algoritmo SMAWK, la matriz a buscar debe definirse como una función, y esta función se proporciona como entrada al algoritmo (junto con las dimensiones de la matriz). Luego, el algoritmo evalúa la función cada vez que necesita conocer el valor de una celda de matriz en particular. Si esta evaluación toma O ( 1 ), entonces, para una matriz con r filas y c columnas, el tiempo de ejecución y el número de evaluaciones de funciones son ambos O ( c (1 + log ( r / c ))). Esto es mucho más rápido que el tiempo O ( r c ) de un algoritmo ingenuo que evalúa todas las celdas de la matriz.
Método
La idea básica del algoritmo es seguir una estrategia de poda y búsqueda en la que el problema a resolver se reduce a un solo subproblema recursivo del mismo tipo cuyo tamaño es menor en un factor constante. Para hacerlo, el algoritmo primero procesa previamente la matriz para eliminar algunas de sus columnas que no pueden contener un mínimo de filas, utilizando un algoritmo basado en pila similar al del escaneo de Graham y todos los algoritmos de valores más pequeños más cercanos . Después de esta fase del algoritmo, el número de columnas restantes será como máximo igual al número de filas. A continuación, el algoritmo se llama a sí mismo de forma recursiva para encontrar los mínimos de fila de las filas pares de la matriz. Finalmente, al buscar las columnas entre las posiciones de mínimos consecutivos de filas pares, el algoritmo completa los mínimos restantes en las filas impares.
Aplicaciones
Las principales aplicaciones de este método presentadas en el artículo original de Aggarwal et al. estaban en geometría computacional , en encontrar el punto más alejado de cada punto de un polígono convexo y en encontrar polígonos envolventes óptimos. Investigaciones posteriores encontraron aplicaciones del mismo algoritmo en la división de párrafos en líneas , [2] predicción de estructura secundaria de ARN , [3] alineación de secuencias de ADN y proteínas , [4] [5] la construcción de códigos de prefijo , [6] y umbral de imagen , [7] entre otros.
Referencias
- ^ Aggarwal, Alok; Klawe, Maria M .; Moran, Shlomo ; Shor, Peter ; Wilber, Robert (1987), "Aplicaciones geométricas de un algoritmo de búsqueda de matrices", Algorithmica , 2 (2): 195-208, doi : 10.1007 / BF01840359 , MR 0895444.
- ^ Wilber, Robert (1988), " Revisión del problema de subsecuencia de peso mínimo cóncavo", Journal of Algorithms , 9 (3): 418–425, doi : 10.1016 / 0196-6774 (88) 90032-6 , MR 0955150
- ^ Larmore, Lawrence L .; Schieber, Baruch (1991), "Programación dinámica en línea con aplicaciones para la predicción de la estructura secundaria del ARN", Journal of Algorithms , 12 (3): 490–515, doi : 10.1016 / 0196-6774 (91) 90016-R , MR 1114923.
- ^ Russo, Luís MS (2012), "Propiedades de Monge de alineación de secuencias", Ciencias de la computación teóricas , 423 : 30–49, doi : 10.1016 / j.tcs.2011.12.068 , MR 2887979.
- ^ Crochemore, Maxime; Landau, Gad M .; Ziv-Ukelson, Michal (2003), "Un algoritmo de alineación de secuencia subcuadrática para matrices de puntuación sin restricciones", SIAM Journal on Computing , 32 (6): 1654–1673 (electrónico), CiteSeerX 10.1.1.57.8562 , doi : 10.1137 / S0097539702402007 , MR 2034254.
- ^ Bradford, Phil; Golin, Mordecai J .; Larmore, Lawrence L .; Rytter, Wojciech (2002), "Códigos óptimos sin prefijo para costos de letras desiguales: programación dinámica con la propiedad Monge", Journal of Algorithms , 42 (2): 277–303, CiteSeerX 10.1.1.45.5501 , doi : 10.1006 / jagm.2002.1213 , MR 1895977.
- ^ Luessi, M .; Eichmann, M .; Schuster, GM; Katsaggelos, AK (2006), "Nuevos resultados sobre el umbral de imagen multinivel óptimo y eficiente", IEEE International Conference on Image Processing , págs. 773–776, CiteSeerX 10.1.1.461.663 , doi : 10.1109 / ICIP.2006.312426 , ISBN 978-1-4244-0480-3.