Clever Geek Handbook

Controlando a dinâmica no problema dos palíndromos

Não sou mais estudante, mas nas horas vagas estudo matérias em Ciência da Computação. Gosto de aprender e compartilhar. Recentemente me deparei com um problema curioso no famoso livro "Algoritmos: Construção e Análise". Neste artigo, demonstrarei os princípios da programação dinâmica usando essa tarefa. É interessante, não é muito complicado e você não precisa escrever nenhuma estrutura de dados ou biblioteca adicional para resolvê-lo. O texto se encaixa em uma frase:



Encontre a subseqüência palíndrômica mais longa em uma palavra de wcomprimento n.



Quem se importa, por favor, em gato.



Não confunda os conceitos de "substring" e "sequência". O primeiro inclui apenas letras adjacentes, e o segundo pode ser composto de letras arbitrariamente distantes umas das outras. Por exemplo, na palavra "matemática" subsequências irá "papoila" ( m comeram m atm para um), a "ataque" (m atm cm e ti ka ) ou um "marcador" ( m atm e ma t e ka) "Palíndromo" significa que a subsequência deve ser lida igualmente da esquerda para a direita e da direita para a esquerda. Uma sequência de uma letra também será palíndrômica, embora este seja um caso degenerado. É claro que pode haver muitas dessas subseqüências palidnrômicas em uma linha. Estamos interessados ​​no mais longo. Se for wo próprio palíndromo, a resposta será toda a string. Caso contrário, a resposta deve ser procurada de alguma forma, por exemplo, na palavra "chave" a resposta será "ooooo".



Parece simples, vamos começar a analisar. Primeiro, vamos tentar resolver "de frente". Quantas subsequências uma palavra tem no total n? É fácil calcular. Ao compor uma subsequência, ou pegamos a iésima letra ou não. Acontece que cada subsequência pode ser colocada em correspondência um-para-um com um número binário com nbits (possivelmente começando com zeros). Uma vez que existem apenas esses números 2^n, haverá uma subsequência a menos, porque não consideramos vazio. Acontece que o espaço de busca cresce exponencialmente com o crescimento n. Esse alinhamento imediatamente deixa claro que não há sentido em tomar uma decisão frontal. Ninguém quer um programa que, mesmo em linhas relativamente pequenas (comn = 1000) será executado por séculos. O ponto principal dos computadores é que eles lidam com tarefas mecânicas muito mais rápido do que nós, e se um computador executa um programa por mais tempo do que uma pessoa, então por que valeu a "cerca"?



Pequena digressão



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



— "" , — , — , . .. "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.





, , . , !



Agradeço qualquer feedback sobre o conteúdo do artigo e sobre o código. Meu telegrama: @outofbound



More articles:


All Articles