پایه‌های برنامه‌نویسی پویا: برش میله، زنجیره ماتریس، و اصول اصلی

چه چیزی برنامه‌نویسی پویا را از تقسیم‌و‌غلبه متفاوت می‌کند

تقسیم‌و‌غلبه، که پیش‌تر در این مجموعه بحث شد، یک مسئله را به زیرمسئله‌های مستقل که هیچ کاری بین خودشان به اشتراک نمی‌گذارند تجزیه می‌کند. Dynamic Programming (برنامه‌نویسی پویا) برای یک دسته متفاوت از مسائل اعمال می‌شود: مسائلی که زیرمسئله‌هایشان هم‌پوشانی دارند، به این معنا که همان زیرمسئله کوچک‌تر به‌طور مکرر در سراسر شاخه‌های مختلف بازگشت مورد نیاز است. بازگشت ساده این زیرمسئله‌های مشترک را هر بار از صفر دوباره محاسبه می‌کرد، و مقدار عظیمی کار را هدر می‌داد. برنامه‌نویسی پویا هر زیرمسئله متمایز را دقیقاً یک‌بار حل می‌کند و نتیجه را برای استفاده مجدد ذخیره می‌کند.

مسئله برش میله: یک مثال کامل اول

با داشتن یک میله به طول n و یک جدول قیمت‌ها p[i] برای میله‌هایی به طول i، هدف تعیین حداکثر درآمد قابل‌دستیابی با برش میله به قطعات و فروش آن قطعات است.

مثال جدول قیمت:
طول i:     1  2  3  4  5  6  7  8
قیمت p:    1  5  8  9  10 17 17 20

یک میله به طول ۴ می‌تواند به‌طور کامل برای ۹ فروخته شود، به دو قطعه به طول ۲ برای ۵+۵=۱۰ بریده شود، یا به یک قطعه به طول ۱ و یک به طول ۳ برای ۱+۸=۹ بریده شود، و همین‌طور. راه‌حل بهینه برای طول ۴ در نهایت بریدن به دو قطعه به طول ۲ است، که ۱۰ درآمد دارد.

راه‌حل بازگشتی ساده

درآمد یک میله به طول n می‌تواند به‌طور بازگشتی بیان شود: هر برش اول ممکن به طول i را امتحان کن، و به‌طور بازگشتی برای بهترین روش برش n-i باقی‌مانده حل کن.

CUT-ROD(p, n):
  اگر n == 0:
      0 را برگردان
  q = -infinity
  برای i = 1 تا n:
      q = max(q, p[i] + CUT-ROD(p, n - i))
  q را برگردان

این فرمول بازگشتی درست است، اما زمان اجرایش نمایی است: T(n) = Θ(2ⁿ)، چون به‌طور مکرر همان زیرمسئله‌ها را دوباره محاسبه می‌کند. برای مثال، محاسبه CUT-ROD(p, 4) نیازمند محاسبه CUT-ROD(p, 2) چندین بار از طریق مسیرهای بازگشتی مختلف است، و هرکدام از آن‌ها CUT-ROD(p, 1) و CUT-ROD(p, 0) را به‌طور مکرر دوباره محاسبه می‌کنند.

بالا-به-پایین با Memoization

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

MEMOIZED-CUT-ROD(p, n):
  فرض کن r[0..n] یک آرایه جدید باشد، مقداردهی‌شده با -infinity
  MEMOIZED-CUT-ROD-AUX(p, n, r) را برگردان

MEMOIZED-CUT-ROD-AUX(p, n, r):
  اگر r[n] ≥ 0:
      r[n] را برگردان         // از قبل محاسبه شده
  اگر n == 0:
      q = 0
  در غیر این صورت:
      q = -infinity
      برای i = 1 تا n:
          q = max(q, p[i] + MEMOIZED-CUT-ROD-AUX(p, n - i, r))
  r[n] = q
  q را برگردان

برنامه‌نویسی پویای پایین-به-بالا

یک رویکرد جایگزین، معمولاً به‌دلیل سادگی‌اش و اغلب فاکتورهای ثابت بهتر ترجیح داده می‌شود، زیرمسئله‌ها را به یک ترتیب خاص — کوچک‌ترین اول — حل می‌کند، طوری که هروقت یک زیرمسئله بزرگ‌تر به یک کوچک‌تر نیاز داشته باشد، از قبل محاسبه شده است.

BOTTOM-UP-CUT-ROD(p, n):
  فرض کن r[0..n] یک آرایه جدید باشد
  r[0] = 0
  برای j = 1 تا n:
      q = -infinity
      برای i = 1 تا j:
          q = max(q, p[i] + r[j - i])
      r[j] = q
  r[n] را برگردان

هم نسخه memoized و هم نسخه پایین-به-بالا در زمان Θ(n²) اجرا می‌شوند، بهبود چشمگیری نسبت به بازگشت ساده نمایی، چون هرکدام از n+1 زیرمسئله دقیقاً یک‌بار حل می‌شود، و هر راه‌حل در بدترین‌حالت O(n) کار نیاز دارد.

یک مثال پیچیده‌تر: ضرب زنجیره‌ای ماتریس

ضرب یک زنجیره از ماتریس‌ها A₁ × A₂ × ... × Aₙ را در نظر بگیرید. ضرب ماتریس، که پیش‌تر در این مجموعه بحث شد، شرکت‌پذیر است، پس نتیجه صرف‌نظر از پرانتزبندی یکسان است، اما تعداد ضرب‌های اسکالر مورد نیاز می‌تواند بسته به ترتیبی که ضرب‌ها انجام می‌شوند به‌طور عظیمی متفاوت باشد.

مثال: A₁ (10×100)، A₂ (100×5)، A₃ (5×50)

پرانتزبندی ((A₁A₂)A₃):
A₁A₂ هزینه 10·100·5 = 5,000 ضرب دارد، نتیجه 10×5 است
(A₁A₂)A₃ هزینه 10·5·50 = 2,500 ضرب دارد
مجموع: 7,500 ضرب

پرانتزبندی (A₁(A₂A₃)):
A₂A₃ هزینه 100·5·50 = 25,000 ضرب دارد، نتیجه 100×50 است
A₁(A₂A₃) هزینه 10·100·50 = 50,000 ضرب دارد
مجموع: 75,000 ضرب

تفاوت یک فاکتور ۱۰ برای فقط سه ماتریس است — شکاف برای زنجیره‌های طولانی‌تر به‌طور چشمگیری بزرگ‌تر می‌شود، که انتخاب پرانتزبندی را برای کارایی حیاتی می‌کند.

تعریف ساختار بازگشتی

فرض کن m[i][j] حداقل تعداد ضرب‌های اسکالر مورد نیاز برای محاسبه حاصل‌ضرب Aᵢ...Aⱼ باشد. ایده بازگشتی کلیدی در نظر گرفتن هر موقعیت ممکن k است که آخرین ضرب (تقسیم "بیرونی‌ترین") می‌تواند در آن رخ دهد.

m[i][j] = 0                                    اگر i == j
m[i][j] = حداقل روی k (i ≤ k < j) از:
            m[i][k] + m[k+1][j] + pᵢ₋₁·pₖ·pⱼ

جایی که pᵢ₋₁, pᵢ ابعاد ماتریس Aᵢ هستند

این رابطه بازگشتی می‌گوید: برای برخی نقطه تقسیم k، ابتدا حاصل‌ضرب بخش چپ Aᵢ...Aₖ را به‌طور بهینه محاسبه کن، سپس حاصل‌ضرب بخش راست Aₖ₊₁...Aⱼ را به‌طور بهینه محاسبه کن، سپس این دو ماتریس حاصل را با هم ضرب کن، و هر kای که مجموع را کمینه کند انتخاب کن.

محاسبه پایین-به-بالا

از آنجا که m[i][j] به زیرمسئله‌های شامل زنجیره‌های کوتاه‌تر بستگی دارد، محاسبه بر اساس طول زنجیره پیش می‌رود، از طول ۱ تا طول کامل زنجیره n.

MATRIX-CHAIN-ORDER(p, n):
  فرض کن m[1..n][1..n] و s[1..n][1..n] جدول‌های جدید باشند
  برای i = 1 تا n:
      m[i][i] = 0
  برای length = 2 تا n:
      برای i = 1 تا n - length + 1:
          j = i + length - 1
          m[i][j] = infinity
          برای k = i تا j - 1:
              cost = m[i][k] + m[k+1][j] + p[i-1]·p[k]·p[j]
              اگر cost < m[i][j]:
                  m[i][j] = cost
                  s[i][j] = k       // نقطه تقسیم بهینه را به‌خاطر بسپار
  m, s را برگردان

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

دو ویژگی ضروری برای برنامه‌نویسی پویا

هر دو مثال بالا دو ویژگی مشترک دارند که با هم نشان می‌دهند چه زمانی برنامه‌نویسی پویا تکنیک درستی برای یک مسئله بهینه‌سازی مشخص است.

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

یک مسئله Optimal Substructure (زیرساختار بهینه) نشان می‌دهد اگر یک راه‌حل بهینه برای مسئله، درون خودش راه‌حل‌های بهینه برای زیرمسئله‌ها را داشته باشد. در برش میله، بهترین روش برش یک میله به طول n، یک راه‌حل بهینه برای طول باقی‌مانده پس از اولین برش را ترکیب می‌کند. در ضرب زنجیره‌ای ماتریس، پرانتزبندی بهینه کل زنجیره، پرانتزبندی‌های بهینه زیرزنجیره‌های چپ و راست در نقطه تقسیم انتخاب‌شده را ترکیب می‌کند.

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

زیرمسئله‌های هم‌پوشان

یک مسئله Overlapping Subproblems (زیرمسئله‌های هم‌پوشان) دارد وقتی یک الگوریتم بازگشتی ساده به‌طور مکرر دقیقاً همان زیرمسئله‌ها را بازدید می‌کند، به‌جای اینکه همیشه زیرمسئله‌های کاملاً جدید تولید کند، همان‌طور که در یک الگوریتم تقسیم‌و‌غلبه معمولی مانند merge sort اتفاق می‌افتد. این دقیقاً چرایی این است که ذخیره راه‌حل‌های زیرمسئله، یا از طریق memoization یا یک جدول پایین-به-بالا، چنین سرعت چشمگیری فراهم می‌کند: بدون زیرمسئله‌های هم‌پوشان، هیچ چیزی برای به‌دست‌آوردن از کش‌کردن نتایج وجود نخواهد داشت.

چرا این دو ویژگی برای تشخیص مسائل جدید اهمیت دارند

وقتی با یک مسئله بهینه‌سازی جدید مواجه می‌شویم، بررسی این دو ویژگی تشخیص استاندارد برای این است که آیا برنامه‌نویسی پویا یک تکنیک مناسب است. اگر یک مسئله زیرساختار بهینه داشته باشد اما زیرمسئله‌هایش هم‌پوشانی نداشته باشند (هر فراخوانی بازگشتی واقعاً زیرمسئله‌های متمایزی تولید می‌کند)، تقسیم‌و‌غلبه، که پیش‌تر در این مجموعه بحث شد، معمولاً رویکرد طبیعی‌تر و به‌همان‌اندازه کارآمدی است. این دقیقاً ترکیب زیرساختار بهینه و هم‌پوشانی قابل‌توجه زیرمسئله است که استراتژی memoization یا جدول‌بندی برنامه‌نویسی پویا را با یک بهبود مجانبی نسبت به بازگشت ساده به‌صرفه می‌کند.