Clever Geek Handbook

Die Dynamik im Palindrom-Problem zähmen

Ich bin kein Student mehr, aber in meiner Freizeit studiere ich Materialien in Informatik. Ich lerne und teile gerne. Kürzlich bin ich im berühmten Lehrbuch "Algorithmen: Konstruktion und Analyse" auf ein merkwürdiges Problem gestoßen. In diesem Artikel werde ich die Prinzipien der dynamischen Programmierung anhand dieser Aufgabe demonstrieren. Es ist interessant, nicht sehr kompliziert, und Sie müssen keine zusätzlichen Datenstrukturen oder Bibliotheken schreiben, um es zu lösen. Der Wortlaut passt in einen Satz:



Finden Sie die längste palindromische Teilfolge in einem Wort der wLänge n.



Wen kümmert es bitte unter Katze.



Verwechseln Sie nicht die Konzepte "Teilzeichenfolge" und "Sequenz". Der erste enthält nur benachbarte Buchstaben, und der zweite kann aus Buchstaben bestehen, die beliebig weit voneinander entfernt sind. Zum Beispiel werden in dem Wort "Mathematik" Teilsequenzen "Mohn" ( m ate m atm bis a), der "Angriff" (m atm cm und ti ka ) oder ein "Etikett" ( m atm e ma t und ka)). "Palindrom" bedeutet, dass die Teilsequenz von links nach rechts und von rechts nach links gleichermaßen gelesen werden muss. Eine Folge von einem Buchstaben ist ebenfalls palindrom, obwohl dies ein entarteter Fall ist. Es ist klar, dass es in einer Zeile viele solcher palidnromischen Teilsequenzen geben kann. Wir interessieren uns für die längste. Wenn wdas Palindrom selbst, dann ist die Antwort die ganze Zeichenfolge. Andernfalls muss die Antwort irgendwie gesucht werden, zum Beispiel im Wort "Klammer" lautet die Antwort "ooooo".



Es klingt einfach, kommen wir zur Analyse. Versuchen wir zunächst, "frontal" zu lösen. Wie viele Teilsequenzen hat ein Wort insgesamt n? Es ist einfach zu berechnen. Wenn wir eine Teilsequenz zusammenstellen, nehmen wir entweder den idritten Buchstaben oder nicht. Es stellt sich heraus, dass jede Teilsequenz in eine Eins-zu-Eins-Entsprechung mit einer Binärzahl mit nBits (möglicherweise beginnend mit Nullen) gebracht werden kann. Da es nur solche Zahlen 2^ngibt, wird es eine Folge weniger geben, weil wir betrachten nicht leer. Es stellt sich heraus, dass der Suchraum mit dem Wachstum exponentiell wächst n. Diese Ausrichtung macht sofort deutlich, dass es keinen Sinn macht, eine direkte Entscheidung zu treffen. Niemand will ein Programm, das auch in relativ kleinen Zeilen (mitn = 1000) wird für Jahrhunderte ausgeführt. Der springende Punkt bei Computern ist, dass sie mechanische Aufgaben viel schneller erledigen als wir. Wenn ein Computer ein Programm länger als eine Person ausführt, warum hat es sich dann gelohnt, "zu fechten"?



Kleiner Exkurs



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



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





, , . , !



Ich freue mich über jede Rückmeldung sowohl zum Inhalt des Artikels als auch zum Code. Mein Telegramm: @outofbound



More articles:


All Articles