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

برنامه نویسی / برنامه ریزی پویا تکنیکی برای حل مسائل بازگشتی به شکلی بهینه است.

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

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

• بازگشتی : شکستن و حل زیر مسائل به صورت بازگشتی
• ذخیره سازی : نگه داری جواب حل زیرمسائل برای جلوگیری از محاسبه احتمالی تکراری

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

سری فیبوناچی به زبان ساده می گوید که عدد بعدی دنباله از جمع دو عدد قبلی آن به دست می آید. به طور دقیق تر به شکل زیر تعریف می شود.

تعریف سری فیبوناچی

حل ساده و بازگشتی معادله بالا در زبان جاوا به شکل زیر است:

public class Fibonacci{
	public static int recursiveFibo(int x) {
			if (x == 0)
				return 0;
			if (x == 1)
				return 1;
			else {
				int f = recursiveFibo(x - 1) + recursiveFibo(x - 2);
				return f;
			}

		}
	public static void main(String[] args){
		System.out.println(recursiveFibo(10));
	}
}

حالا اگر بخواهیم طبق کد بالا و به صورت دستی، فیبوناچی ۴ را حساب کنیم، و در واقع جمله پنجم این سری را به دست بیاوریم، فراخوانی ها به شکل زیر است:

فراخوانی های بازگشتی سری فیبوناچی به ازای ۴

همانطور که در تصویر بالا می بینید، برای محاسبه (Fibonacci(4 به محاسبه (Fibonacci(3 و (Fibonacci(2 نیاز است و برای محاسبه (Fibonacci(3 شما به محاسبه (Fibonacci(2 و (Fibonacci(1 نیاز دارید.
خب تا همین جا دو بار به محاسبه (Fibonacci(2 نیاز پیدا شده است؛ اگر مقدار آن را دفعه اول ذخیره کرده باشیم، نیازی به محاسبه بازگشتی برای مرتبه دوم نیست. اینجاست که تکنیک برنامه ریزی پویا بهینگی را به حل این مسئله اضافه می کند.

پیچیدگی زمانی حل بازگشتی فیبوناچی:

T(n) = T(n-1) + T(n-2) + 1 = 2ⁿ = O(2ⁿ)

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

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

public class Fibonacci{
	public static int fibDP(int x) {
			int fib[] = new int[x + 1];
			fib[0] = 0;
			fib[1] = 1;
			for (int i = 2; i < x + 1; i++) {
				fib[i] = fib[i - 1] + fib[i - 2];
			}
		return fib[x];
		}
	public static void main(String[] args){
		System.out.println(fibDP(10));
	}
}

پیچیدگی زمانی کد برنامه ریزی پویای فیبوناچی بالا: (O(n پیچیدگی فضای مورد استفاده: (O(n

دو خاصیت اصلی برنامه ریزی پویا

اگر بخواهیم یک مسئله را با برنامه ریزی پویا حل کنیم، آن مسئله دو خاصیت را حتما باید داشته باشد:

1. برخی یا همه زیربخش های مسئله با هم اشتراک داشته باشند
2. زیرساختار بهینه در مسئله باشد

همانطور که بالاتر دیدیم برای محاسبه بازگشتی (Fibonacci(4 از دو مسیر بازگشتی فراخوانی مختلف، دو بار (Fibonacci(2 فراخوانی شد و این زیربخش ها با هم اشتراک دارند.

زیرساختار بهینه هم به این صورت تعریف می شود: گفته می شود که یک مسئله دارای زیرساختار بهینه است اگر یک جواب بهینه مسئله بتواند از پاسخ های بهینه زیرمسئله هایش تشکیل شود (جواب های بهینه برای زیرمسئله ها، جواب بهینه کل را بسازد).

دو رویکردها اصلی برنامه ریزی پویا

• پایین به بالا
• بالا به پایین

رویکرد پایین به بالا:

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

در پیاده سازی بالایی از محاسبه فیبوناچی با تکنیک برنامه ریزی را که ارائه کرده بودیم، از همین رویکرد پایین به بالا استفاده شده بود. اما در زیر آن دوباره نشان داده شده است.

public class Fibonacci{
	public static int fibDP(int x) {
		int fib[] = new int[x + 1];
		fib[0] = 0;
		fib[1] = 1;
		for (int i = 2; i < x + 1; i++) {
			fib[i] = fib[i - 1] + fib[i - 2];
		}
		return fib[x];
	}
	public static void main(String[] args){
		System.out.println(fibDP(10));
	}
}

رویکرد بالا به پایین:

تفاوت این رویکرد با رویکرد قبلی، در عدم محاسبه برخی زیربخش هاست. در واقع در رویکرد بالا به پایین برنامه ریزی پویا، زیرمسائلی که جواب حل آن ها هیچگاه نیاز نخواهد شد، هیچ وقت هم محاسبه نخواهند شد. بنابراین در مواردی که به ۱. نوع (ذات) مسئله یا ۲. نحوه شکستن زیرمسائل مربوط می شود، حل رویکرد بالا به پایین از حل پایین به بالا بهینه تر است.

کد بالا به پایین برنامه ریزی پویای به دست آوردن جمله N+1 ام سری فیبوناچی به شکل زیر است

public class Fibonacci{
	public static int fibTopDown(int n, int [] fib) {
		if(n==0) return 0;
		if(n==1) return 1;
		if(fib[n]!=0){
			return fib[n];
		}else{
			fib[n] = fibTopDown(n-1, fib) + fibTopDown(n-2, fib);
			return fib[n];
		}
	}
	public static void main(String[] args){
		int n = 10;
		int [] fib = new int[n+1];
		System.out.println(fibTopDown(n, fib));
	}
}

در این مطلب از وبسایت اوپن مایند، سعی شد به طور خلاصه و سریع، اصل مفهوم و دلیل نیاز به تکنیک حل برنامه ریزی پویا و دو رویکرد آن بررسی شود.

در این زمینه اگر سوالی برای شما پیش آمده، در قسمت نظرات مطرح کنید.