Clever Geek Handbook

Apprivoiser la dynamique du problème des palindromes

Je ne suis plus étudiant, mais pendant mon temps libre, j'étudie les matériaux en informatique. J'aime apprendre et partager. Récemment, je suis tombé sur un problème curieux dans le célèbre manuel "Algorithmes: Construction et Analyse". Dans cet article, je vais démontrer les principes de la programmation dynamique en utilisant cette tâche. C'est intéressant, pas très compliqué, et vous n'avez pas besoin d'écrire des structures de données ou des bibliothèques supplémentaires pour le résoudre. Le libellé tient dans une phrase:



Trouvez la sous-séquence palindromique la plus longue dans un mot de wlongueur n.



Peu importe, s'il vous plaît, sous le chat.



Ne confondez pas les concepts de «sous-chaîne» et de «séquence». Le premier ne comprend que les lettres adjacentes et le second peut être composé de lettres arbitrairement éloignées les unes des autres. Par exemple, dans le mot «mathématiques», les sous-séquences seront «pavot» ( m ate m atm à a), «attaque» (m atm cm et ti ka ) ou une «étiquette» ( m atm e ma t et ka). «Palindromique» signifie que la sous-séquence doit être lue également de gauche à droite et de droite à gauche. Une séquence d'une lettre sera également palindromique, bien qu'il s'agisse d'un cas dégénéré. Il est clair qu'il peut y avoir de nombreuses sous-séquences palidnromiques sur une ligne. Nous nous intéressons au plus long. Si wle palindrome lui-même, la réponse sera la chaîne entière. Sinon, la réponse doit être recherchée d'une manière ou d'une autre, par exemple, dans le mot "accolade", la réponse sera "ooooo".



Cela semble simple, passons à l'analyse. Essayons d'abord de résoudre "de front". Combien de sous-séquences un mot a-t-il au total n? C'est facile à calculer. Lors de la composition d'une sous-séquence, nous prenons la ie lettre ou non. Il s'avère que chaque sous-séquence peut se voir attribuer une correspondance biunivoque avec un nombre binaire avec des nbits (éventuellement commençant par des zéros). Puisqu'il n'y a que de tels nombres 2^n, il y aura une sous-séquence de moins, car nous ne considérons pas vides. Il s'avère que l'espace de recherche croît de manière exponentielle avec la croissance n. Cet alignement montre immédiatement qu'il ne sert à rien de prendre une décision frontale. Personne ne veut un programme qui, même sur des lignes relativement petites (avecn = 1000) sera exécuté pendant des siècles. L'intérêt des ordinateurs est qu'ils font face aux tâches mécaniques beaucoup plus rapidement que nous, et si un ordinateur exécute un programme plus longtemps qu'une personne, alors pourquoi cela valait-il la «clôture»?



Petite digression



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



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





, , . , !



J'apprécie tout commentaire à la fois sur le contenu de l'article et sur le code. Mon télégramme: @outofbound



More articles:


All Articles