PDF de programación - Algoritmos con Python - Secuencias

Algoritmos con Python

Secuencias

26 de febrero de 2021

Índice

1 Ruta más corta en una cuadrícula

1.1 Definición . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2 Algoritmo en O(nm) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2 Distancia de edición de Levenshtein

2.1 Definición . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2 Algoritmo en O(nm) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3 Secuencia de operaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.4 Detalles de implementacion . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.5 Yendo más lejos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3 Subsecuencia común más larga

3.1 Definición . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2 Aplicación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.3 Algoritmo en O(nm) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.4 Observación clave . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.5 Aplicación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.6 Variante para varias secuencias dadas . . . . . . . . . . . . . . . . . . . . .
3.7 Variante con dos secuencias ordenadas . . . . . . . . . . . . . . . . . . . . .
3.8 En la práctica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2
2
2

3
3
3
4
4
5

6
6
6
7
7
7
8
8
8

4 La mayor secuencia creciente

9
9
4.1 Definición . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
4.2 Aplicación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.3 Algoritmo en O(n log n)
9
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.4 Detalles de la implementación . . . . . . . . . . . . . . . . . . . . . . . . . 10
4.5 Variante: Subsecuencia no decreciente . . . . . . . . . . . . . . . . . . . . . 11
4.6 Variante: Secuencia creciente común más larga . . . . . . . . . . . . . . . . 11

5 Estrategia ganadora en un juego de dos jugadores

12
5.1 Definición . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
5.2 Complejidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
5.3 Algoritmo por programación dinámica . . . . . . . . . . . . . . . . . . . . . 12

I

Introducción

¿Qué es la programación dinámica? Es un método para descomponer la resolución de un
problema en una combinación de soluciones de algunos de sus subproblemas. Primero cal-
culamos la solución de los subproblemas y los almacenamos para utilizarlos posteriormen-
te (principio de memoización), en un orden fijado según un barrido. Esta técnica se adapta
especialmente bien a los problemas sobre secuencias, en los que los subproblemas están
definidos, por ejemplo, sobre los prefijos de una secuencia.

1

1. Ruta más corta en una cuadrícula

1.1. Definición

Considere una cuadrícula de (n + 1) x (m + 1) celdas, etiquetadas (i, j) con 0 i
n y 0 j m. Las celdas están unidas por arcos ponderados: los predecesores de
una celda (i, j) son (i - 1, j), (i - 1, j - 1) e (i, j - 1), con la excepción de
celdas de la primera columna y la primera fila (consulte la Figura 1). El objetivo es encontrar
el camino más corto desde (0,0) a (n, m).

Figura 1: Ruta más corta

Ruta más corta en una cuadrícula dirigida, ilustrada por los arcos gruesos.

1.2. Algoritmo en O(nm)

Como este gráfico es dirigido y acíclico (abreviado DAG, para gráfico acíclico dirigido), po-
demos resolver este problema mediante programación dinámica, calculando las distancias
desde (0,0) a todas las celdas (i,j) en un cierto orden. En primer lugar, las distancias
a las celdas de la primera fila y la primera columna son fáciles de calcular, ya que existe
una ruta única hacia estas celdas. A continuación, calculamos las distancias a las celdas
(i, j) con 1 i n, 1 j m en orden lexicográfico. Cada distancia de (0,0) a una
(i, j) es el mínimo de tres alternativas, que se pueden determinar en tiempo constante,
ya que las distancias a los predecesores de (i, j) ya se han calculado.

2

2. Distancia de edición de Levenshtein

2.1. Definición

Dadas dos cadenas x, y, deseamos saber cuántas operaciones (inserción, eliminación o
sustitución) se requieren para transformar x en y. Esta distancia se usa, por ejemplo, en
el comando diff de Unix, que muestra línea por línea un número mínimo de operaciones
para transformar un archivo en otro.

2.2. Algoritmo en O(nm)

Para n = |x|, m = |y|, presentamos un algoritmo en O(nm) usando programación dinámi-
ca, vea la Figura 2. Construimos una matriz A[i, j] dando la distancia entre el prefijo de
x de longitud i y el prefijo de y de longitud j. Para comenzar, inicializamos A[0, j] = j y
A[i, 0] = i (las distancias desde la cadena vacía a los diversos prefijos de x e y).
Entonces, en general, cuando i, j 1, hay tres posibilidades para las últimas letras de los
prefijos. O se elimina xi, o se inserta yj (al final), o xi se reemplaza por yj (si aún no son
iguales). Esto da la siguiente fórmula de recurrencia, donde coincidencia es una función
booleana que devuelve 1 si sus argumentos son idénticos:

Esta función codifica el costo de una sustitución de letras, que se puede ajustar si se desea.
Por ejemplo, el costo podría depender de la distancia entre las letras del teclado.

3

Figura 2: Ruta óptima

Ruta más corta en un gráfico dirigido, determinando la distancia de edición entre dos palabras

2.3. Secuencia de operaciones

Además de calcular la distancia de edición entre las cadenas, sería bueno conocer las ope-
raciones necesarias para transformar x en y. Esto se puede hacer como en la búsqueda de
la ruta más corta en un gráfico. Al examinar las distancias de sus predecesores, podemos
determinar una opción que dé cuenta de una distancia mínima a un nodo. Por lo tanto,
podemos rastrear la ruta desde el nodo (n, m) hasta (0, 0) y, a lo largo de esta ruta,
producir la lista de operaciones correspondientes a las ediciones óptimas. Al final, basta
con invertir esta lista.

2.4. Detalles de implementacion

Tenga en cuenta que en la descripción del programa dinámico, la dimensión de la matriz
A es (n + 1) x (m + 1), mientras que las cadenas son de longitud n y m. Esto se debe a

4

que A tiene en cuenta todos los prefijos de x e y, incluida la cadena vacía
. Entonces x
tiene n + 1 prefijos e y tiene m + 1.

def levenshtein(x, y):

n = len(x)
m = len(y)
# Create the table A
#
#
A = [[i + j for j in range(m + 1)] for i in range(n + 1)]
for i in range(n):

Row 0 and column 0 are initialized as required
The remaining entries will be overwritten during the computation

for j in range(m):

A[i + 1][j + 1] = min(A[i][j + 1] + 1,
A[i + 1][j] + 1,
A[i][j] + int(x[i] != y[j])) # subst.

# insert
# delete

return A[n][m]

2.5. Yendo más lejos

Se han propuesto algoritmos con mejor desempeño en la práctica. Por ejemplo, si se cono-
ce un límite superior s para la distancia de edición, entonces el programa dinámico anterior
puede restringirse a entradas en A a una distancia de como máximo s de la diagonal, para
obtener una complejidad de O(s min{n, m}).

5

3. Subsecuencia común más larga

3.1. Definición
Sea Σ un conjunto de símbolos. Para dos secuencias s, x ∈ Σ∗ , se dice que s es una
subsecuencia de x si existen índices i1 < . . . < i|s| tales que xik = sk para todo k =
1, . . . , |s|. Dadas dos secuencias x, y ∈ Σ∗, deseamos encontrar una secuencia de longitud
máxima s ∈ Σ∗, que sea una subsecuencia tanto de x como de y.

Otra forma de ver el problema consiste en los emparejamientos. Buscamos un empareja-
miento máximo entre letras iguales de x e y tal que los enlaces entre los emparejamientos
no se crucen entre sí, véase la figura 3.

Figura 3: Subsecuencia común

El problema de la subsecuencia común más larga puede verse como una alineación máxima sin cruces
entre elementos iguales de las dos secuencias dadas. Por ejemplo, una alineación de las letras B cruzaría la
alineación de las letras D.

3.2. Aplicación

El programa ’diff’ informa de las diferencias entre dos archivos, expresadas como una
lista mínima de cambios de línea para que cualquiera de los dos archivos coincida con
el otro. Para ello, es necesario identificar la mayor subsecuencia común de líneas entre
ambos archivos Este problema también se plantea en bioinformática, por ejemplo al alinear
dos cadenas de bases nitrogenadas.

6

3.3. Algoritmo en O(nm)

Presentamos un algoritmo en O(nm), donde n = |x|, m = |y|. La idea es calcular para
cada 0 i n y 0 j m la subsecuencia común más larga de los prefijos x1 . . . xi e
y1 . . . yj. Esto da lugar a n*m subproblemas. La solución óptima para (i,j) puede calcu-
larse a partir de las soluciones para (i - 1,j), (i,j - 1), y (i - 1, j - 1), en tiempo
constante. Así, podemos resolver el problema para (n,m) en tiempo O(nm). El algoritmo
se basa en la siguiente observación.

3.4. Observación clave

Sea A[i,j] la subsecuencia común más larga de x1 . . . xi e y1 . . . yj . Si i = 0 o j = 0,
entonces A[i,j] está vacía. Si xi = yj , entonces necesariamente una de las letras xi, yj

no coincide en una solución óptima y A[i,j] es la secuencia más larga entre A[i - 1,j]
y A[i, j - 1]. Si xi = yj , entonces existe una solución óptima que hace coincidir estas
letras y A[i,j] es A [i − 1, j − 1] · xi. Aquí, el símbolo ’·’ representa la concatenación, y

por máximo nos referimos a la secuencia de longitud máxima.

3.5. Aplicación

En la implementación simplificada que se da a continuación, la variable A[i][j] no repre-
senta la secuencia A[i,j], sino que representa su longitud.

def longest_common_subsequence(x, y):

n = len(x)
m = len(y)

#
A = [[0 for j in range(m + 1)] for i in range(n + 1)]
for i in range(n):

-- compute optimal length

for j in range(m):

if x[i] == y[j]:

A[i + 1][j + 1] = A[i][j