ترويض الديناميات في مشكلة المتجانسات

لم أعد طالبًا ، لكنني في وقت فراغي أقوم بدراسة مواد في علوم الكمبيوتر. أنا أستمتع بالتعلم والمشاركة. صادفت مؤخرًا مشكلة غريبة في الكتاب المدرسي الشهير "الخوارزميات: البناء والتحليل". في هذه المقالة ، سأشرح مبادئ البرمجة الديناميكية باستخدام هذه المهمة. إنه أمر مثير للاهتمام ، وليس معقدًا للغاية ، ولا تحتاج إلى كتابة أي هياكل بيانات أو مكتبات إضافية لحلها. الصياغة تتناسب مع جملة واحدة:

ابحث عن أطول تواتر متناظر في كلمة wطويلة n.

من يهتم ، من فضلك ، تحت القط.

لا تخلط بين مفهومي "السلسلة الفرعية" و "التسلسل". يتضمن الأول أحرفًا متجاورة فقط ، ويمكن أن يتكون الثاني من أحرف بشكل تعسفي بعيدًا عن بعضها البعض. على سبيل المثال ، في كلمة "رياضيات" ، ستظهر كلمة "الخشخاش" ( m ate m atm to a) ، أو "attack" (m atm cm and ti ka ) أو "التسمية" ( m atm e ma t and ka). تعني "Palindromic" أنه يجب قراءة النتيجة اللاحقة بالتساوي من اليسار إلى اليمين ومن اليمين إلى اليسار. سيكون تسلسل حرف واحد أيضًا متناوبًا ، على الرغم من أن هذه حالة متدهورة. من الواضح أنه يمكن أن يكون هناك العديد من مثل هذه التكرارات المتلاحقة في سطر واحد. نحن مهتمون بأطول واحد. إذا كان wالمتماثل نفسه ، فستكون الإجابة هي السلسلة بأكملها. خلاف ذلك ، يجب البحث عن الإجابة بطريقة ما ، على سبيل المثال ، في كلمة "دعامة" ستكون الإجابة "ooooo".

يبدو الأمر بسيطًا ، دعنا ننتقل إلى التحليل. أولاً ، دعنا نحاول حل "وجهاً لوجه". كم عدد اللاحقات للكلمة في المجموع n؟ من السهل حسابها. عند تأليف لاحقة ، إما أن نأخذ iالحرف أو لا. اتضح أنه يمكن وضع كل تتابعات لاحقة في مراسلات فردية برقم ثنائي يحتوي على nوحدات بت (ربما تبدأ بالأصفار). نظرًا لوجود مثل هذه الأرقام فقط 2^n، سيكون هناك عدد أقل من التكرارات اللاحقة ، لأن نحن لا نعتبرها فارغة. اتضح أن مساحة البحث تنمو باطراد مع النمو 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