مقدمه

بسیاری از مسائل برنامه نویسی تنها با استفاده از Dynamic Programming حل میشوند در این نوشتار سعی شده که طرح کلی برنامه نویسی پویا و دلیل و مزایای استفاده از آن با چندین پیاده سازی برای تابع Fibonacci بیان شود. در مطالب آینده مثال های مهم تر و به نسبت پیچیده تری قرار میگیرد.


برنامه نویسی پویا یا Dynamic Programming چیست ؟

همه شما کم و بیش با الگوریتم ها یا برنامه هایی که به صورت بازگشتی عمل میکنند اطلاع دارید. حل یک مسئله با حل کردن یک یا چندین زیر مسئله .

در استفاده از تکنیک برنامه نویسی پویا ما حل مسئله را توسط حل مسئله های کوچکتر بیان میکنیم با این تفاوت که با ذخیره سازی از محاسبه دوباره اجتناب میکنیم.


ساده ترین تکه کد ای که میتوان برای Fibonacci نوشت تابع زیر است:

int fib(int n){
   if ( n <= 1 )
      return n;
   return fib(n-1) + fib(n-2);
}

این تابع برخلاف سادگی ای که برای برنامه نویس دارد پیچیدگی زمانی زیادی برای کامپیوتر در محاسبات N های بالا ایجاد میکند برای مثال برای محاسبه مقدار Fibonacci 20 تابع های زیر به مقدار گفته شده اجرا میشود.

fib(0) Runs = 4181 Times
fib(1) Runs = 6765 Times
fib(2) Runs = 4181 Times
fib(3) Runs = 2584 Times
fib(4) Runs = 1597 Times
fib(5) Runs = 987 Times
fib(6) Runs = 610 Times
fib(7) Runs = 377 Times
fib(8) Runs = 233 Times
fib(9) Runs = 144 Times
fib(10) Runs = 89 Times
fib(11) Runs = 55 Times
fib(12) Runs = 34 Times
fib(13) Runs = 21 Times
fib(14) Runs = 13 Times
fib(15) Runs = 8 Times
fib(16) Runs = 5 Times
fib(17) Runs = 3 Times
fib(18) Runs = 2 Times
fib(19) Runs = 1 Times
fib(20) Runs = 1 Times

میبینیم که برای مثال کل بدنه تابع fib(7) به تعداد 377 بار اجرا شده است که شامل فراخانی توابع زیر مسئله میشود.

مشخص است که در تمامی این 377 دفعه یک مقدار بازگردانده شده است. پس در واقع در 376 دفعه بعد کار بیهوده ای انجام شد که برای کامپیوتر هزینه اضافی به همراه داشت.

برای از بین بردن هزینه اضافه که در بازگشتی ها داریم از برنامه نویسی پویا استفاده میکنیم.


استفاده از برنامه نویسی پویا را میتوان به دو گروه تقسیم کرد:


1 - Memoization یا بیاد آوری ( از بالا به پایین )

یک پیاده سازی از نوع بیاد آوری برای تابع Fibonacci رو در زیر میبینید. در این کد ما با دو آرایه visited و value از تکرار بدنه تابع fib برای یک N جلوگیری کردیم. این تابع بسیار سریعتر از تابع بازگشتی بالا میباشد و بدنه تابع برای اعداد 0 تا 20 تنها یکبار اجرا میشود. از بالا به پایین یعنی اینکه برای محاسبه جواب مسئله پیچیده ( بالا ) به مرور به جواب مسئله ساده ( پایین ) برسیم.

#include<iostream>
using namespace std;
#define MAXN 110
bool visited[MAXN]={false};
int value[MAXN];
int fib(int n){
	if(visited[n]==true)
		return value[n];
	visited[n]=true;
	if(n<=1) return value[n]=1;
	return value[n]=fib(n-1)+fib(n-2);
}

int main(){
	cout<<"fib(20)="<<fib(20)<<endl;
	return 0;
}

2 - Tabulation یا جدول سازی ( از پایین به بالا )

پیاده سازی با جدول یا از پایین به بالا تابع Fibonacci به شکل زیر میباشد. از پایین به بالا یعنی از جواب ساده ترین مسئله که در دسترس هست ( پایین ) به جواب های پیچیده تر ( بالا ) برسیم. این نوع پیاده سازی را میتوان در خطوط کمتر و بدون تابع نویسی هم انجام داد که برای حفظ طرح کلی کد پرهیز شد. 

#include<iostream>
using namespace std;
#define MAXN 110
int value[MAXN]={1,1};
void init(){
	for(int i=2;i<MAXN;i++){
		value[i]=value[i-1]+value[i-2];
	}
}
int fib(int n){
	return value[n];
}

int main(){
	init();
	cout<<"fib(20)="<<fib(20)<<endl;
	return 0;
}


در هر دو روش مشاهده می کنید که ما با تکنیک برنامه نویسی پویا مرتبه تابع Fibonacci را از O(2n) به O(N) کاهش دادیم که در N های بزرگ بسیار تاثیر گزار و قابل مشاهده است.

توجه کنید که مقدار fib(100) از محدوده int بیشتر است و اینجا برای سادگی بیشتر از int استفاده شده است.


چه زمانی استفاده از برنامه نویسی پویا بی تاثیر است؟

همانگونه که در تعریف گفته شد برنامه نویسی پویا نوع بهتری برای بازگشتی میباشد. اما زمانی که تابع بازگشتی به گونه ای است که تکرار کم رخ میدهد. و همچنین ما به دفعات نیاز به مقادیر مختلف نداریم تبدیل بازگشتی به پویا باعث کاهش مرتبه نشده و نوعی تلف کردن حافظه محسوب میشود.