Clever Geek Handbook

Menjinakkan dinamika dalam masalah palindrome

Saya bukan lagi seorang siswa, tetapi di waktu luang saya mempelajari materi di Ilmu Komputer. Saya menikmati belajar dan berbagi. Baru-baru ini saya menemukan masalah aneh dalam buku teks terkenal "Algorithms: Construction and Analysis". Pada artikel ini, saya akan mendemonstrasikan prinsip-prinsip pemrograman dinamis menggunakan tugas ini. Ini menarik, tidak terlalu rumit, dan Anda tidak perlu menulis struktur data atau pustaka tambahan untuk menyelesaikannya. Kata-katanya cocok menjadi satu kalimat:



Menemukan subsequence palindromic terpanjang di kata wpanjang n.



Siapa yang peduli, tolong, di bawah kucing.



Jangan bingung dengan konsep "substring" dan "sequence". Yang pertama hanya mencakup huruf yang berdekatan, dan yang kedua dapat terdiri dari huruf-huruf yang saling berjauhan. Misalnya, dalam kata "matematika" subsequences akan "poppy" ( m makan m atm untuk a), "serangan" (m atm cm dan ti ka ) atau "label" ( m atm e ma t dan ka). "Palindromik" berarti bahwa urutan harus dibaca secara merata dari kiri ke kanan dan dari kanan ke kiri. Urutan satu huruf juga akan menjadi palindromik, meskipun ini merupakan kasus yang merosot. Jelas bahwa ada banyak urutan palidnromik dalam satu baris. Kami tertarik dengan yang terpanjang. Jika wpalindrom itu sendiri, maka jawabannya adalah seluruh string. Jika tidak, jawabannya harus dicari entah bagaimana, misalnya pada kata "brace" jawabannya adalah "ooooo".



Kedengarannya sederhana, mari kita ke analisisnya. Pertama, mari kita coba memecahkan masalah "langsung". Berapa banyak urutan yang dimiliki sebuah kata n? Mudah dihitung. Saat membuat surat berikutnya, kami mengambil ihuruf ke atau tidak. Ternyata setiap urutan dapat dimasukkan ke dalam korespondensi satu-ke-satu dengan bilangan biner dengan nbit (mungkin dimulai dengan nol). Karena hanya ada angka seperti itu 2^n, maka akan ada satu urutan yang berkurang, karena kami tidak menganggap kosong. Ternyata ruang pencarian tumbuh secara eksponensial dengan pertumbuhan n. Penyelarasan ini segera memperjelas bahwa tidak ada gunanya membuat keputusan langsung. Tidak ada yang menginginkan program itu, bahkan pada jalur yang relatif kecil (dengann = 1000) akan dieksekusi selama berabad-abad. Inti dari komputer adalah bahwa mereka menangani tugas-tugas mekanis jauh lebih cepat daripada kita, dan jika komputer menjalankan program lebih lama dari orang, lalu mengapa itu layak untuk "pagar"?



Penyimpangan kecil



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



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





, , . , !



Saya menyambut baik umpan balik apa pun baik tentang konten artikel dan kode. Telegram saya: @outofbound



More articles:


All Articles