Dynamic Programming (DP) is an algorithmic technique for solving an optimization problem by breaking it down into simpler subproblems and utilizing the fact that the optimal solution to the overall problem depends upon the optimal solution to its subproblems. more...

برای طراحی الگوریتم‌ها 5 رویکرد معروف و کلاسیک وجود دارد:
    - رویکرد تقسیم و غلبه (Divide & Conquer)
    - رویکرد برنامه‌نویسی پویا (Dynamic Programming)
    - رویکرد حریصانه (Greedy)
    - رویکرد عقبگرد (Backtracking)
    - رویکرد شاخه و قید (Branch & Bound)
معمولا الگوریتم حل مسئله‌های کلاسیک و الگوریتمی با یکی از این روش‌ها طراحی می‌شود. در این مطلب قصد دارم شما را قدم به قدم با رویکرد برنامه‌نویسی پویا (Dynamic Programming) آشنا کنم.

پیشنهاد می‌شود قبل از پرداختن به این مطلب، رویکرد تقسیم و غلبه (Divide & Conquer) را مطالعه نمایید.

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

هنگامی از برنامه‌نویسی پویا استفاده می‌کنیم که پس از تقسیم مسئله به اندازه‌های کوچک‌تر، زیرمسئله‌های به‌وجود آمده باهم هم‌پوشانی (Ovelapping) داشته باشند.

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

در این پایگاه دانش برای حل مسئله‌های زیر از رویکرد برنامه‌نویسی پویا استفاده کرده‌ایم:
    - محاسبه‌ی ضریب دوجمله‌ای
    - کوتاه‌ترین مسیر در گراف - روش فلوید
    - ضرب زنجیری ماتریس‌ها
    - مسئله‌ی فروشنده‌ی دوره‌گرد
    - بزرگترین زیررشته‌ی مشترک
    - یافتن مسیر در ماتریس

در برنامه‌نویسی پویا نتیجه‌ی حل زیرمسئله‌ها را ذخیره می‌کنیم و در آینده درصورت نیاز، از نتیجه‌ی محاسبات قبلی بجای حل مجدد آن‌ها استفاده می‌کنیم.

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

درخت محاسبات جمله‌ی ششم دنباله‌ی فیبوناچی (اعداد، نشانگر شماره‌ی جملات هستند)

در درخت محاسبات بالا همانطور که می‌بینید برای محاسبه‌ی جمله‌ی ششم، محاسبه‌ی جملات پنجم و چهارم لازم است. اما برای محاسبه‌ی جمله‌ی پنجم، محاسبه‌ی جملات چهارم و سوم را نیاز داریم. ملاحظه می‌کنید که تا اینجای کار جمله‌ی چهارم دوبار محاسبه شده است. به همین ترتیب جمله‌ی سوم 3 بار محاسبه می‌شود. در کل برای بدست آورن جمله‌ی ششم (که مقدارش برابر 8 است) 7 عمل جمع انجام می‌دهیم درحالی‌که بر روی کاغذ می‌توان تنها با 4 عمل جمع آن را بدست آورد. هرچند در این مثال کوچک تعداد تکرارها کم است، اما با بزرگ شدن اندازه‌ی مسئله تعداد محاسبات تکراری خیلی زیاد می‌شود. می‌توان ثابت کرد تعداد محاسبات (عمل جمع) برای محاسبه‌ی بازگشتی جمله‌ی iاُم از رابطه‌ی زیر بدست می‌آید:

برای آشنایی با دنباله‌ی فیبوناچی و دریافت جزئیات بیشتر، مطلب دنباله‌ی فیبوناچی را ببینید.

که در آن S_i تعداد عملیات جمع برای محاسبه‌ی مقدار جمله‌ی iاُم است. و با حل آن به رابطه‌ی زیر می‌رسیم:

که در آن F_i مقدار جمله‌ی iاُم دنباله‌ی فیبوناچی است، و این یعنی برای محاسبه‌ی هر جمله مانند f به f-1 عمل جمع نیاز داریم. به‌عنوان مثال عدد 75025 که جمله‌ی بیست و پنجم دنباله‌ی فیبوناچی است، بر روی کاغذ با 23 عمل جمع قابل محاسبه است، اما با پیاده سازی بازگشتی به روش تقسیم و غلبه 75024 عمل جمع انجام می‌شود.

بیایید مقادیر محاسبه شده را در یک آرایه ذخیره کنیم و در مراحل بعدی از آن مقادیر استفاده کنیم. یعنی برای محاسبه‌ی هر جمله، ابتدا بررسی کنیم که آیا مقدار آن قبلا محاسبه شده یا خیر؟ اگر محاسبه شده، پس بدون محاسبه‌ی مجدد از همان مقدار استفاده کنیم در غیر این‌صورت مقدار آن را محاسبه کرده و برای استفاده‌های بعدی ذخیره کنیم. این کار در برنامه‌ی زیر که به زبان C++ نوشته شده پیاده سازی شده‌است:

1#include <iostream>
2using namespace std;
3int n, f[100] = { 0 };
4int Fibo(int n) {
5  if (f[n] == 0)
6    f[n] = Fibo(n - 1) + Fibo(n - 2);
7  return f[n];
8}
9void main() {
10  f[1] = f[2] = 1;
11  cin >> n;
12  cout << Fibo(n);
13}

1#include <iostream>
2using namespace std;
3int n, f1 = 1, f2 = 1;
4int Fibo(int n) {
5  int f = 1;
6  for (int i = 3; i <= n; i++) {
7    f = f1 + f2;
8    f2 = f1;
9    f1 = f;
10  }
11  return f;
12}
13void main() {
14  cin >> n;
15  cout << Fibo(n);
16}