پیش از خواندن این مطلب، دانستن مطالب زیر ضروری است:
__________________________________________________ _____________________
روش برنامه نویسی پویا (Dynamic Programming) غالبا" برای الگوریتمهایی بکار برده می‌شود که در پی حل مسئله‌ای بصورت بهینه می‌باشند.
در روش تقسیم و تسخیر ممکن است برخی از زیرمسائل کوچکتر با هم برابر باشند که در این صورت زیرمسائل برابر بطور تکراری چندین مرتبه حل می‌شوند که این یکی از معایب روش تقسیم و تسخیر است.
ایده‌ای که در فرای روش برنامه نویسی پویا نهفته است جلوگیری از انجام این محاسبات تکراری است و روشی که معمولا" برای این عمل بکارگرفته می‌شود استفاده از جدولی برای نگهداری نتایج حاصل از حل زیرمسائل است. در این صورت اگر الگوریتم به زیرمسئله‌ای برخورد کرد که پیش از این حل شده است، بجای حل مجدد آن، نتیجه محاسبه قبلی را از جدول برداشته و کار را با زیرمسئله بعدی دنبال می‌کند.
روش برنامه نویسی پویا یک روش پایین به بالا است (Bottom-Top Technique) به این معنی که از حل مسائل کوچکتر به حل مسائل بزرگتر می‌رسیم. در حالیکه از نظر ساختاری روش تقسیم و تسخیر روشی است از بالا به پایین (Top-Down Technique) یعنی بطور منطقی (نه عملی) پردازش از مسئله اولیه آغاز شده و بسمت پایین و حل مسائل کوچکتر به پیش می‌رود.
برای دریافت بهتر مفهوم روش برنامه نویسی پویا، در ادامه الگوریتم یافتن تعداد تبدیلهای (Combinations) تعداد k عضو از یک مجموعه n عضوی را با استفاده از دو روش برنامه نویسی پویا و تقسیم و تسخیر ارائه و سپس با هم مقایسه می کنیم.
فرمول محاسبه تعداد تبدیلهای k از n بصورت زیر است:
C(n,k) = n! / (k! * (n - k)!) (0 <= k <= n)
فرمول بالا را می توان با روابط زیر بگونه‌ای دیگر بیان نمود:
1 (k = 0 یا k = n)
C(n,k) =
C(n-1,k-1) + C(n-1,k) (0 < k < n)
بدین ترتیب الگوریتم تقسیم و تسخیری که برای حل این مسئله حاصل می‌شود بصورت زیر است:
function C(n : integer; k : integer) return integer
begin
if k = 0 or k = n then
return 1;
else
return C(n-1, k-1) + C(n-1, k);
end if;
end C;
وش برنامه نویسی پویا از همان رابطه بالا استفاده می کند با این تفاوت که در این روش جدولی به ابعاد (n+1)*(k+1) تبدیل ممکن لازم است تا تعداد تبدیلهای j از i را برای هر i از صفر تان n و هر j از صفر تا k ذخیره کرد.
محاسباتی که باید به ترتیب انجام شوند عبارتند از:
- خانه‌های هم ارز جدول با تبدیلهای 0 از i و 1 از 1 مقدار ثابت 1 پر می‌شوند.
- خانه‌های باقیمانده جدول با افزایش i+j به ازای تبدیلهای j از i محاسبه و پر می‌شوند.
یادآوری می‌کنم که چون برای محاسبه تبدیل j از i تنها لازم است که حاصل تبدیلهای j-1 از i-1 و j از i-1 را داشته باشیم، محاسبه مقادیر خانه‌های جدول به ترتیب صعودی i+j تضمین می کند که خانه‌های مورد نیاز جدول برای محاسبه تبدیل j از i از پیشتر محاسبه شده‌اند.
الگوریتم حل این مسئله با روش برنامه نویسی پویا بصورت زیر است:
function C(n : integer; k : integer) return integer
type table is array (0..n, 0..k) of integer;
bc : table;
i, j, k : integer;
sum : integer;
begin
{ Initializes fixed table entries }
for i in 0..n loop
bc(i,0) := 1;
end loop;
bc(1,1) := 1;
{ Calculates the rest of table entries }
sum := 3; i := 2; j := 1;
while sum <= n+k loop
bc(i,j) := bc(i-1,j-1) + bc(i,j-1);
i := i-1; j := j+1;
if i < j or j > k then
sum := sum + 1;
if sum <= n+1 then
i := sum-1; j := 1;
else
i := n; j := sum-n;
end if;
end if;
end loop;
return bc(n,k);
end C;
حال به مقایسه دو الگوریتم می‌پردازیم:
در الگوریتم پیاده سازی شده در روش تقسیم و تسخیر، در بدترین حالت ورودی (k=n/2) زمان اجرای الگوریتم تقریبا" برابر خواهد بود با <span dir=ltr>O((2^n)/n)</span>. با وجود اینکه شرح الگوریتم بسیار ساده است (چون مستقیما" رابطه شرح داده شده برای صورت مسئله پیاده سازی شده است) اما با وجود چنین زمان اجرایی استفاده از این الگوریتم برای nهای بزرگ کاملا" غیر عملی است.
در روش برنامه نویسی پویا چون الگوریتم دقیقا" تنها یک بار تعداد تبدیلهای k از n را محاسبه می‌کند بسیار بهره‌ور‌تر و بهینه‌تر است. زمان اجرای این الگوریتم <span dir=ltr>O(n*k)</span> است که برای بدترین حالت (k=n/2) برابر <span dir=ltr>O(n^2)</span> خواهد بود.
مثال یافتن تعداد تبدیلهای k از n مثالی است که تمام خصوصیات کلیدی الگوریتمهای برنامه نویسی پویا را به نمایش می گذارد:
- یک جدول از تمام نتایج زیر مسائل ساخته می‌شود.
- خانه‌های جدول برای کوچکترین زیر مسائل مقدار دهی اولیه می شود.
- خانه های باقیمانده جدول با ترتیبی دقیق (یعنی مطابق با افزایش اندازه زیر مسئله) با استفاده از خانه‌هایی که از پیشتر مقدار دهی شده‌اند، محاسبه و مقدار دهی می‌شوند.
- هر خانه دقیقا" فقط یک بار محاسبه می‌شود.
- آخرین مقداری که محاسبه می‌شود پاسخ مسئله اولیه است.
- پیاده سازی بر اساس ساختار تکرار است (هیچوقت از ساختار بازگشت استفاده نمی‌شود، حتی اگر تحلیل یک مسئله بطور طبیعی راه حلی بازگشتی پیشنهاد دهد).
پاسخ با نقل قول
نوشته شده توسط Kambiz
