برنامه‌ریزی پویا

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

ویژگی‌ها

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

اصل بهینگی

اگر بنا باشد پرانتزبندی کل عبارت بهینه شود، پرانتزبندی زیرمساله‌ها هم باید بهینه باشند. یعنی بهینه بودن مساله، بهینه بودن زیرمساله‌ها را ایجاب می‌کند. پس می‌توان از روش برنامه‌نویسی پویا استفاده کرد.

حل بهینه، سومین مرحله از بسط یک الگوریتم برنامه نویسی پویا برای مسائل بهینه سازی است. مراحل بسط چنین الگوریتمی به شرح زیر است:

1- ارائه یک ویژگی بازگشتی که حل بهینه ی نمونه ای از مسئله را به دست می دهد.

2- محاسبه مقدار حل بهینه به شیوه­ی جزء به کل.

3- بنا کردن یک حل نمونه به شیوه­ی جزء به کل.

تمام مسائل بهینه­سازی را نمی­توان با برنامه نویسی پویا حل کرد چرا که باید اصل بهینگی در مسئله صدق کند.

اصل بهینگی در یک مسئله صدق می کند اگر یک حل بهینه برای نمونه­ای از مسئله، همواره حاوی حل بهینه برای همه­ی زیر نمونه­ها باشد

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

درخت­های جست­وجوی دودویی بهینه

درخت جست و جوی دودویی یک درخت دودویی از عناصر است که معمولا کلید نامیده می­شوند به قسمی که:

1- هر گره حاوی یک کلید است.

2- کلیدهای موجود در زیردرخت چپ هر گره، کوچک­تر یا مساوی کلید آن گره هستند.

3- کلیدهای موجود در زیردرخت راست هر گره، بزرگ­تر یا مساوی کلید آن گره هستند

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

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

1. شکاندن مسئله به بخش‌های کوچک‌تر
2. حل خود این زیرمسئله‌ها با شکاندن آن‌ها به صورت بازگشتی
3. استفاده از پاسخ‌های جزئی برای یافتن پاسخ کلی

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

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

• ’’’رویکرد بالا به پایین’’’: در این رویکرد مسئله به زیرمسئله‌هایی شکسته می‌شود و پاسخ هر زیرمسئله پس از محاسبه در جایی ذخیره می‌شود. در مراحل بعدی هر وقت به آن پاسخ نیاز بود پاسخ از روی حافظه خوانده می‌شود. این فرآیند ترکیبی از الگوریتم بازگشتی و ذخیره‌سازی در حافظه است.
• ’’’رویکرد پایین به بالا’’’: در این رویکرد همهٔ زیرمسئله‌های مورد نیازر از کوچک به بزرگ حل می‌شوند و از جواب‌ها بلافاصله برای محاسبهٔ بعدی‌ها استفاده می‌شود و فرایند محاسبه تا رسیدن به زیرمسئلهٔ مورد نیاز (که در وافع مسئلهٔ اصلی ماست) ادامه می‌یابد. بدیهی‌ست که در این حالت استفاده از الگوریتم بازگشتی ضروری نیست. مثال زیر این تفاوت‌ها را روشن تر می‌کند.

مثال

یک پیاده‌سازی ساده از یک تابع برای یافتن عدد فیبوناچی nام می‌تواند به شکل زیر باشد.

   function fib(n)
       if n = 0 
           return 0
       else if n = 1 
           return 1
       return fib(n − 1) + fib(n − 2)

برای مثال اگر از چنین تابعی (fib(5 را بخواهیم، تابع‌هایی که صدا می‌شوند به شکل زیر خواهند بود.

1. fib(5)
2. fib(4) + fib(3)
3. (fib(3) + fib(2)) + (fib(2) + fib(1))
4. ((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
5. (((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))

مشخص است که چنین فرایندی پر از محاسبات تکراری است.مثلاً عدد فیبوناچی دوم به تنهایی سه بار حساب شده‌است. در محاسبات بزرگ‌تر چنین تکرارهایی برنامه را به شدت کند می‌کنند. این الگوریتم دارای پیچیدگی زمانی نمایی است. حال فرض کنید ما یک آرایه دوتایی map داریم که عدد n را به مقدار عدد فیبوناچی nام مربوط کرده و ذخیره می‌کند. پیچیدگی زمانی چنین الگوریتمی n خواهد بود. همچنین میزان فضای اشغال‌شده‌اش هم از مرتبه n خواهد بود.

   var m := map(0 → 1, 1 → 1)
   function fib(n)
       if map m does not contain key n
           m[n] := fib(n − 1) + fib(n − 2)
       return m[n]

این نمونه‌ای از فرایند بالا به پایین بود. چون ابتدا مسئله را شکاندیم و بعد به محاسبه و ذخیرهٔ پاسخ زیرمسئله‌ها پرداختیم. در فرایند پایین به بالا برای حل چنین مسئله‌ای از عدد فیبوناچی یکم شروع می‌کنیم تا به عدد خواسته‌شده برسیم. بااین کار باز هم پیچیدگی زمانی از مرتبه n است.

function fib(n)
       var previousFib := 0, currentFib := 1
       if n = 0 
           return 0
       else if n = 1 
           return 1
       repeat n − 1 times
           var newFib := previousFib + currentFib
           previousFib := currentFib
           currentFib  := newFib
       return currentFib

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

تفاوت این روش و روش تقسیم و تسخیر

یکی از روش‌های پرکاربرد و مشهور طراحی الگوریتم روش برنامه‌نویسی پویا (یا برنامه‌ریزی پویا - Dynamic Programming) است. این روش همچون روش تقسیم و حل (Divide and Conquer) بر پایه تقسیم مساله بر زیرمساله‌ها کار می‌کند. اما تفاوت‌های چشم‌گیری با آن دارد.

زمانی که یک مساله به دو یا چند زیرمساله تقسیم می‌شود، دو حالت ممکن است پیش بیاید:

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

2- داده‌های زیرمساله وابسته به هم بوده و یا با هم اشتراک دارند. در این حالت به اصطلاح زیرمساله‌ها هم‌پوشانی دارند. نمونه بارز چنین مسائلی محاسبه جمله nام دنباله اعداد فیبوناچی است.

روش برنامه نویسی پویا غالبا" برای الگوریتمهایی بکار برده می‌شود که در پی حل مسئله‌ای بصورت بهینه می‌باشند.

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

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

روش برنامه نویسی پویا یک روش پایین به بالا است به این معنی که از حل مسائل کوچکتر به حل مسائل بزرگتر می‌رسیم. در حالیکه از نظر ساختاری روش تقسیم و تسخیر روشی است از بالا به پایین ،یعنی بطور منطقی (نه عملی) پردازش از مسئله اولیه آغاز شده و بسمت پایین و حل مسائل کوچکتر به پیش می‌رود.

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

                              (int bin(int n,int k
                                                 }
                                  ;[int i,j B[N][K
                           (++FOR(i=0;i<=n;i
                     (++for(j=0;j<=min;j
                      (if(j==0||j==i
                        ;1=[B[i][j
                                else
    ;[B[i][j]=B[i-1][j-1]+B[i-1][j
                                 ;[Return B[n][k
                                               {

منابع

• فردریک س. هیلیر- جرالد ج. لیبرمن، ترجمه محمد مدرس و اردوان آصف‌وزیری، تحقیق در عملیات، چاپ دهم تهران: نشر جوان، ۱۳82‎

پیوند به بیرون

• An Introduction to Dynamic Programming
• Dyna, a declarative programming language for dynamic programming algorithms
• Wagner, David B., 1995, "Dynamic Programming." An introductory article on dynamic programming in متمتیکا.
• Ohio State University: CIS 680: class notes on dynamic programming, by Eitan M. Gurari
• A Tutorial on Dynamic programming
• MIT course on algorithms - Includes a video lecture on DP along with lecture notes -- See lecture 15.
• More DP Notes
• King, Ian, 2002 (1987), "A Simple Introduction to Dynamic Programming in Macroeconomic Models." An introduction to dynamic programming as an important tool in economic theory.
• Dynamic Programming: from novice to advanced A TopCoder.com article by Dumitru on Dynamic Programming
• Algebraic Dynamic Programming - a formalized framework for dynamic programming, including an entry-level course to DP, University of Bielefeld
• Dreyfus, Stuart, "Richard Bellman on the birth of Dynamic Programming."
• Dynamic programming tutorial

• الگوریتمستان، روش برنامه نویسی پویا

جستارهای وابسته

• معادلات بلمن
• برنامه‌ریزی خطی
• فرایند مارکف
• ضرب زنجیره‌ای ماتریس
• مساله یافتن کوتاهترین مسیر