توضیح طولانی‌ترین زیردنباله مشترک و درخت‌های جستجوی دودویی بهینه

مسئله طولانی‌ترین زیردنباله مشترک

یک Subsequence (زیردنباله) از یک رشته با حذف صفر یا چند کاراکتر بدون تغییر ترتیب کاراکترهای باقی‌مانده استخراج می‌شود. مسئله Longest Common Subsequence (LCS) می‌پرسد: با داشتن دو دنباله، طولانی‌ترین زیردنباله مشترک بین هر دو را پیدا کن.

مثال:
X = "ABCBDAB"
Y = "BDCABA"

یک زیردنباله مشترک: "BCBA" (طول 4)
دیگری: "BDAB" (طول 4)
LCS در این حالت طول 4 دارد

این مسئله زیربنای ابزار diff مورد استفاده برای مقایسه نسخه‌های فایل، مقایسه توالی DNA در بیوانفورماتیک، و ابزارهای تشخیص سرقت ادبی است، که آن را به یکی از عملی‌ترین کاربردهای برنامه‌نویسی پویا تبدیل می‌کند.

ایجاد زیرساختار بهینه

فرض کن Xᵢ نشان‌دهنده اولین i کاراکتر رشته X باشد، و به‌طور مشابه برای Yⱼ. بینش ساختاری کلیدی، آخرین کاراکترهای هر دو دنباله را در نظر می‌گیرد.

اگر X[i] == Y[j]:
    LCS از Xᵢ و Yⱼ، LCS از Xᵢ₋₁ و Yⱼ₋₁ را
    دقیقاً با این کاراکتر متناظر گسترش می‌دهد

اگر X[i] ≠ Y[j]:
    LCS از Xᵢ و Yⱼ طولانی‌تر از این‌هاست:
    - LCS از Xᵢ₋₁ و Yⱼ (آخرین کاراکتر X را حذف کن)
    - LCS از Xᵢ و Yⱼ₋₁ (آخرین کاراکتر Y را حذف کن)

این رابطه بازگشتی برای c[i][j]، طول LCS از Xᵢ و Yⱼ، را می‌دهد:

c[i][j] = 0                              اگر i == 0 یا j == 0
c[i][j] = c[i-1][j-1] + 1                اگر i,j > 0 و X[i] == Y[j]
c[i][j] = max(c[i-1][j], c[i][j-1])      اگر i,j > 0 و X[i] ≠ Y[j]

ساخت راه‌حل پایین-به-بالا

LCS-LENGTH(X, Y, m, n):
  فرض کن c[0..m][0..n] و b[1..m][1..n] جدول‌های جدید باشند
  برای i = 1 تا m:
      c[i][0] = 0
  برای j = 0 تا n:
      c[0][j] = 0
  برای i = 1 تا m:
      برای j = 1 تا n:
          اگر X[i] == Y[j]:
              c[i][j] = c[i-1][j-1] + 1
              b[i][j] = "قطری"
          در غیر این صورت اگر c[i-1][j] ≥ c[i][j-1]:
              c[i][j] = c[i-1][j]
              b[i][j] = "بالا"
          در غیر این صورت:
              c[i][j] = c[i][j-1]
              b[i][j] = "چپ"
  c, b را برگردان

ردیابی مثال قبلی با X = "ABCBDAB" و Y = "BDCABA" جدولی را پر می‌کند که در نهایت c[7][6] مقدار ۴ را نگه می‌دارد، که با طول LCS پیدا‌شده با بازرسی بالا مطابقت دارد.

از آنجا که جدول Θ(mn) ورودی دارد و هرکدام O(1) زمان برای پر شدن با توجه به ورودی‌هایی که به آن‌ها بستگی دارد نیاز دارد، الگوریتم در زمان Θ(mn) اجرا می‌شود — بهبود چشمگیری نسبت به تعداد نمایی زیردنباله‌های ممکن که یک رویکرد brute-force ساده نیاز به بررسی آن‌ها دارد.

بازسازی زیردنباله واقعی

جدول کمکی b ثبت می‌کند کدام حالت در هر سلول اعمال شده، که اجازه می‌دهد طولانی‌ترین زیردنباله مشترک واقعی، نه فقط طولش، با ردیابی به‌عقب از b[m][n] تا مبدأ، با دنبال کردن حرکت‌های "قطری" برای جمع‌آوری کاراکترهای متناظر، و حرکت‌های "بالا" یا "چپ" برای پرش از موقعیت‌های غیرمتناظر، بازسازی شود.

درخت‌های جستجوی دودویی بهینه: نوع متفاوتی از بهینه‌سازی

درخت جستجوی دودویی که پیش‌تر در این مجموعه بحث شد فرض می‌کند هر کلید به‌طور برابر احتمال دارد جستجو شود. در بسیاری اپلیکیشن‌های واقعی، برخی کلیدها بسیار مکرر‌تر از دیگران جستجو می‌شوند، و شکل درخت باید این را منعکس کند: کلیدهای پردسترسی باید نزدیک‌تر به ریشه بنشینند، و هزینه جستجویشان را کمینه کنند، حتی اگر این یعنی کلیدهای کم‌دسترسی‌تر عمیق‌تر بنشینند.

با داشتن n کلید متمایز با احتمال‌های جستجوی شناخته‌شده p₁, ..., pₙ، مسئله Optimal Binary Search Tree (درخت جستجوی دودویی بهینه) ساختار درخت جستجوی دودویی‌ای می‌خواهد که هزینه کل جستجوی مورد انتظار را کمینه کند.

هزینه جستجوی مورد انتظار یک درخت T:
E[هزینه جستجو] = Σ (i=1 تا n) (depth_T(kᵢ) + 1) · pᵢ

جایی که depth_T(kᵢ) عمق کلید kᵢ در درخت T است
(ریشه عمق 0 دارد، پس دسترسی به آن 1 مقایسه هزینه دارد)

ایجاد ساختار بازگشتی

بینش کلیدی، مشابه از نظر روحی با ضرب زنجیره‌ای ماتریس که پیش‌تر در این مجموعه بحث شد، این است که یک درخت جستجوی دودویی بهینه روی یک بازه پیوسته از کلیدها یک ساختار بازگشتی دارد: هر کلیدی که به‌عنوان ریشه یک زیردرخت انتخاب شود، کلیدهای کوچک‌تر از آن باید زیردرخت چپ را تشکیل دهند، و کلیدهای بزرگ‌تر از آن باید زیردرخت راست را تشکیل دهند، و هرکدام از این زیردرخت‌ها باید خودشان برای بازه و مجموعه احتمال‌های مربوطه‌شان بهینه باشند.

فرض کن e[i][j] = هزینه مورد انتظار یک BST بهینه
              شامل کلیدهای kᵢ تا kⱼ

فرض کن w[i][j] = مجموع احتمال‌های pᵢ تا pⱼ
              (این افزایش هزینه اضافه‌کردن یک سطح دیگر
               به هر گره در زیردرخت را در نظر می‌گیرد،
               چون انتخاب یک ریشه عمق هر نواده
               را دقیقاً یک واحد افزایش می‌دهد)

e[i][j] = حداقل روی r (i ≤ r ≤ j) از:
            e[i][r-1] + e[r+1][j] + w[i][j]

حالت پایه: e[i][i-1] = 0  (زیردرخت خالی)

جمله w[i][j] صرف‌نظر از اینکه کدام ریشه r انتخاب شود اضافه می‌شود، چون انتخاب هر گره به‌عنوان ریشه یک زیردرخت، عمق هر گره دیگر در آن زیردرخت را دقیقاً یک سطح افزایش می‌دهد، و w[i][j] را به هزینه مورد انتظار کل اضافه می‌کند صرف‌نظر از اینکه زیردرخت داخلاً چگونه بیشتر ساختاردهی شود.

پر کردن جدول پایین-به-بالا

OPTIMAL-BST(p, n):
  فرض کن e[1..n+1][0..n], w[1..n+1][0..n], root[1..n][1..n] جدول‌های جدید باشند
  برای i = 1 تا n + 1:
      e[i][i-1] = 0
      w[i][i-1] = 0
  برای length = 1 تا n:
      برای i = 1 تا n - length + 1:
          j = i + length - 1
          e[i][j] = infinity
          w[i][j] = w[i][j-1] + p[j]
          برای r = i تا j:
              t = e[i][r-1] + e[r+1][j] + w[i][j]
              اگر t < e[i][j]:
                  e[i][j] = t
                  root[i][j] = r
  e, root را برگردان

الگوریتم با افزایش طول زیردرخت پیش می‌رود، دقیقاً مانند ضرب زنجیره‌ای ماتریس، چون e[i][j] فقط به ورودی‌های شامل بازه‌های دقیقاً کوتاه‌تر بستگی دارد. با Θ(n²) ورودی جدول، هرکدام نیازمند O(n) کار برای امتحان هر ریشه ممکن، زمان اجرای کل Θ(n³) است، که دقیقاً با پیچیدگی ضرب زنجیره‌ای ماتریس مطابقت دارد، انعکاسی از شباهت ساختاری بین دو مسئله.

چرا این دو مسئله دامنه برنامه‌نویسی پویا را نشان می‌دهند

طولانی‌ترین زیردنباله مشترک و درخت‌های جستجوی دودویی بهینه، با وجود حل مسائل عملی بسیار متفاوت — مقایسه رشته در مقابل بهینه‌سازی ساختار داده — هر دو از همان الگوی بنیادین برنامه‌نویسی پویا که پیش‌تر در این مجموعه ایجاد شد پیروی می‌کنند: شناسایی زیرساختار بهینه با در نظر گرفتن آخرین تصمیم گرفته‌شده (کدام کاراکترها متناظرند، یا کدام کلید ریشه می‌شود)، بیان راه‌حل به‌صورت یک رابطه بازگشتی روی زیرمسئله‌ها، و پر کردن یک جدول پایین-به-بالا به ترتیبی که تضمین می‌کند هر وابستگی از قبل محاسبه شده است. تشخیص این الگوی مشترک در سراسر مسائل به‌ظاهر نامرتبط، مهارت کلیدی برای به‌کارگیری برنامه‌نویسی پویا روی مسائل جدید هنوز‌ندیده‌شده است.