Clever Geek Handbook

Domesticar la dinámica en el problema de los palíndromos

Ya no soy estudiante, pero en mi tiempo libre estudio materiales en Informática. Disfruto aprendiendo y compartiendo. Recientemente me encontré con un problema curioso en el famoso libro de texto "Algoritmos: construcción y análisis". En este artículo, demostraré los principios de la programación dinámica usando esta tarea. Es interesante, no muy complicado y no necesita escribir ninguna estructura de datos o bibliotecas adicionales para resolverlo. La redacción encaja en una frase:



Encuentre la subsecuencia palindrómica más larga en una palabra de wlongitud n.



A quién le importa, por favor, debajo del gato.



No confunda los conceptos de "subcadena" y "secuencia". El primero incluye solo letras adyacentes, y el segundo puede estar compuesto por letras arbitrariamente alejadas entre sí. Por ejemplo, en la palabra "matemáticas" las subsecuencias "amapola" ( m ate m atm a a), el "ataque" (m atm cm y ti ka ) o una "etiqueta" ( m atm e ma t y ka). "Palindromic" significa que la subsecuencia debe leerse por igual de izquierda a derecha y de derecha a izquierda. Una secuencia de una letra también será palindrómica, aunque este es un caso degenerado. Está claro que puede haber muchas subsecuencias palidnrómicas de este tipo en una línea. Nos interesa el más largo. Si wel palíndromo en sí, entonces la respuesta será la cadena completa. De lo contrario, la respuesta debe buscarse de alguna manera, por ejemplo, en la palabra "corchete" la respuesta será "ooooo".



Suena simple, vayamos al análisis. Primero, intentemos resolver "de frente". ¿Cuántas subsecuencias tiene una palabra en total n? Es fácil de calcular. Al componer una subsecuencia, tomamos la iletra th o no. Resulta que cada subsecuencia se puede poner en correspondencia uno a uno con un número binario con nbits (posiblemente comenzando con ceros). Dado que solo hay tales números 2^n, habrá una subsecuencia menos, porque no consideramos vacío. Resulta que el espacio de búsqueda crece exponencialmente con el crecimiento n. Esta alineación deja claro de inmediato que no tiene sentido tomar una decisión de frente. Nadie quiere un programa que, incluso en líneas relativamente pequeñas (conn = 1000) se ejecutará durante siglos. El objetivo de las computadoras es que hacen frente a las tareas mecánicas mucho más rápido que nosotros, y si una computadora ejecuta un programa más tiempo que una persona, entonces ¿por qué valía la pena "cercar un huerto"?



Pequeña digresión



, - ? , , ? , (, ) , . ? — , . , , , - . , , -. , , .



— "" , — , — , . .. "time-space trade-off" ( ), "" , . , , . " " , . -. "" "" "", "", . "" - , . , , . , . , - . — .



, . , , . (P vs. NP). ( " "), , .



.





. , . , — , . (), . " " , . , . . "" . , .. , .. :



  • .
  • , .. .


  • .


? , f . , f (.. "").



. w , . , ? , , . , . , , . , - .



, , . palindrome[i, j] w[i, j]. palindrome[1, n]. . , , palindrome[1, n]. ? , w[1, n-1], w[2, n], w[2, n-1]. w , w[1] + palindrome[2, n-1] + w[n]. :



  1. palindrome[j, i] = , j > i
  2. palindrome[i, i] = w[i].
  3. palindrome[i, j] = w[i] + palindrome[i + 1, j - 1] + w[j] w[i] = w[j]
  4. palindrome[i, j] = max{palindrome[i+1, j], palindrome[i, j-1], palindrome[i+1, j-1]}

    . , Python - :


def solve(s):
    palindromes = [['' for i in range(len(s))] for j in range(len(s))]
    n = len(s) - 1
    result = solve_memoized_rec(s, palindromes, 0, n)
    return result

def solve_memoized_rec(s, palindromes, i, j):
    if palindromes[i][j]:
        return palindromes[i][j]
    else:
        if i > j:
            solution = ''
        elif i == j:
            solution = s[i]
        elif s[i] == s[j]:
            prev = solve_memoized_rec(s, palindromes, i + 1, j - 1)
            solution = s[i] + prev + s[j]
        else:
            from_left = solve_memoized_rec(s, palindromes, i + 1, j)
            from_right = solve_memoized_rec(s, palindromes, i, j - 1)
            both = solve_memoized_rec(s, palindromes, i + 1, j - 1)
            solution = max(from_left, from_right, both, key=len)
        palindromes[i][j] = solution
        return solution


solve_memoized_rec palindromes, . , , . , - ( ). , , , . — . — , n (, ). , .. off-by-one error.



" ", " " palindromes. "". , "" palindromes[1, n].



:



def solve_iterative(s):
    n = len(s)
    palindromes = [['' for i in range(n)] for j in range(n)]
    for k in range(1, n + 1):
        for i in range(n - k + 1):
            j = i + k - 1
            if i == j:
                solution = s[i]
            elif s[i] == s[j]:
                solution = s[i] + palindromes[i + 1][j - 1] + s[j]
            else:
                solution = max(palindromes[i + 1][j], palindromes[i][j - 1], palindromes[i + 1][j - 1], key=len)
            palindromes[i][j] = solution
    return palindromes[0][n - 1]


, , i > j. , n^2.





, , . , !



Agradezco cualquier comentario tanto sobre el contenido del artículo como sobre el código. Mi telegrama: @outofbound



More articles:


All Articles