El algoritmo SMAWK es un algoritmo para hallar el valor mínimo en cada fila de una matriz totalmente monótona definida implícitamente . Recibe su nombre de las iniciales de sus cinco inventores, Peter Shor , Shlomo Moran , Alok Aggarwal, Robert Wilber y Maria Klawe . [1]
Para los fines de este algoritmo, una matriz se define como monótona si el valor mínimo de cada fila se encuentra en una columna que es igual o mayor que la columna del mínimo de la fila anterior. Es totalmente monótona si la misma propiedad es verdadera 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 2×2 cuyos mínimos de fila estén en las esquinas superior derecha e inferior izquierda. Toda matriz Monge es totalmente monótona, pero no necesariamente al revés.
Para el algoritmo SMAWK, la matriz que se va 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 saber 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 la función 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.
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 único subproblema recursivo del mismo tipo cuyo tamaño es menor por un factor constante. Para ello, el algoritmo primero preprocesa la matriz para eliminar algunas de sus columnas que no pueden contener un mínimo de fila, utilizando un algoritmo basado en pila similar al del escaneo de Graham y los algoritmos de todos los 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 los mínimos de filas pares consecutivos, el algoritmo completa los mínimos restantes en las filas impares.
Las principales aplicaciones de este método presentadas en el artículo original de Aggarwal et al. fueron en geometría computacional , en la búsqueda del punto más alejado de cada punto de un polígono convexo y en la búsqueda de 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 la estructura secundaria del ARN , [3] alineamiento de secuencias de ADN y proteínas , [4] [5] la construcción de códigos de prefijo , [6] y umbralización de imágenes , [7] entre otros.