Clever Geek Handbook

パリンドローム問題のダイナミクスを使いこなす

私はもう学生ではありませんが、自由時間にはコンピューターサイエンスの資料を勉強しています。私は学び、共有することを楽しんでいます。最近、有名な教科書「アルゴリズム：構築と分析」で奇妙な問題に遭遇しました。この記事では、このタスクを使用した動的プログラミングの原則を示します。これは興味深いもので、それほど複雑ではありません。それを解決するために追加のデータ構造やライブラリを作成する必要はありません。言葉遣いは1つの文に収まります：



w長さの単語で最も長いpalindromicサブシーケンスを見つけますn。



猫の下で気にかけてください。



「サブストリング」と「シーケンス」の概念を混同しないでください。1つ目は隣接する文字のみを含み、2つ目は互いに任意に離れた文字で構成できます。たとえば、「数学」という単語のサブシーケンスは、「ポピー」（m ate m atm to a）、「attack」（m atm cm and ti ka）、または「label」（m atm e ma t and ka）になります。）。 「パリンドローム」とは、サブシーケンスを左から右および右から左に等しく読み取る必要があることを意味します。これは退化したケースですが、1文字のシーケンスもパリンドロームになります。 1行にそのようなpalidnromicサブシーケンスが多数存在する可能性があることは明らかです。一番長いものに興味があります。wパリンドローム自体の場合、答えは文字列全体になります。それ以外の場合は、何らかの方法で答えを探す必要があります。たとえば、「中括弧」という単語では、答えは「ooooo」になります。



簡単そうに聞こえますが、分析に取り掛かりましょう。まず、「正面から」解決してみましょう。単語には合計でnいくつのサブシーケンスがありますか？計算は簡単です。サブシーケンスを作成するときは、ith文字を使用するかどうかを選択します。各サブシーケンスは、nビット付きのバイナリ番号（おそらくゼロで始まる）と1対1で対応できることがわかります。そのような数しかないので2^n、サブシーケンスが1つ少なくなります。空とは見なしません。サーチスペースは成長とともに指数関数的に成長することがわかりnます。この調整により、正面からの決定を下す意味がないことがすぐに明らかになります。比較的小さな行であっても、そのようなプログラムは誰も望んでいません。n = 1000）何世紀にもわたって実行されます。コンピューターの要点は、機械的なタスクを私たちよりもはるかに速く処理することです。コンピューターが人よりも長くプログラムを実行する場合、なぜ「フェンシング」する価値があったのでしょうか。



小さな逸脱



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



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





, , . , !



記事の内容とコードの両方に関するフィードバックを歓迎します。私の電報：@outofbound



More articles:


All Articles