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

در علوم رایانه و ریاضیات، برنامه‌ریزی پویا یا داینامیک روشی کارآمد برای حل مسائل جستجو و بهینه‌سازی با استفاده از دو خصیصه زیرمسئله‌های هم‌پوشان و زیرساخت‌های بهینه است.
بر خلاف برنامه‌ریزی خطی، چارچوب استانداردی برای فرموله کردن مسائل برنامه‌ریزی پویا وجود ندارد. در واقع، آنچه برنامه‌ریزی پویا انجام می‌دهد ارائه روش برخورد کلی جهت حل این نوع مسائل است. در هر مورد، باید معادلات و روابط ریاضی مخصوصی که با شرایط آن مسئله تطبیق دارد نوشته شود.
تاریخچه
این روش در سال ۱۹۵۳ توسط ریاضی‌دانی به نام ریچارد بلمن معرفی شد. برنامه‌ریزی پویا در ریاضی و علوم رایانه روشی شناخته شده‌است که از آن در نوشتن الگوریتم‌های بهینه با استفاده از حذف اجرای چند باره یک زیر مسئله یکسان استفاده می‌شود. تعریف برنامه ریزی پویا در ریاضی و علوم رایانه متفاوت است. نشان داده شده‌است که روش علوم رایانه‌ای برای برنامه ریزی پویا کارایی بالاتری دارد زیرا محاسبات تکراری را حذف می‌کند در حالی که در روش ریاضی برنامه ریزی پویا امکان کاهش فضای حافظه بیشتر است.
برنامه‌ریزی پویا شبیه روش تقسیم و حل مسائل را با استفاده از ترکیب کردن جواب زیرمساله‌ها حل می‌کند. الگوریتم تقسیم و حل، مسئله را به زیر مسئله‌های مستقل تقسیم می‌کند و پس از حل زیر مسئله‌ها به صورت بازگشتی، نتایج را با هم ترکیب کرده و جواب مساله اصلی را بدست می‌آورد. به عبارت دقیق‌تر، برنامه ریزی پویا در مواردی قابل استفاده است که زیرمساله‌ها مستقل نیستند؛ یعنی زمانی که زیرمساله‌ها دارای زیر-زیر مسئله‌های یکسان هستند. در این حالت روش تقسیم و حل با اجرای مکرر زیرمساله‌های یکسان، بیشتر از میزان لازم محاسبات انجام می‌دهد. یک الگوریتم برنامه ریزی پویا زیرمساله‌ها را یک بار حل و جواب آن‌ها را در یک جدول ذخیره می‌کند و با این کار از تکرار اجرای زیرمساله‌ها در زمانی که مجددا به جواب آن‌ها نیاز است جلوگیری می‌کند.
ویژگی‌ها
برنامه‌ریزی پویا دارای دو ویژگی اصلی است که در زیر بیان می‌شوند.
اصل بهینگی
اگر بنا باشد پرانتزبندی کل عبارت بهینه شود، پرانتزبندی زیرمسئله‌ها هم باید بهینه باشند. یعنی بهینه بودن مسئله، بهینه بودن زیرمسئله‌ها را ایجاب می‌کند.
پس می‌توان از روش برنامه‌نویسی پویا استفاده کرد.
حل بهینه، سومین مرحله از بسط یک الگوریتم برنامه‌نویسی پویا برای مسائل بهینه‌سازی است. مراحل بسط چنین الگوریتمی به شرح زیر است:
ارائه یک ویژگی بازگشتی که حل بهینه نمونه‌ای از مسئله را به دست می‌دهد.
محاسبه مقدار حل بهینه به شیوه‌ی جزء به کل.
بنا کردن یک حل نمونه به شیوه‌ی جزء به کل.
تمام مسائل بهینه سازی را نمی‌توان با برنامه‌نویسی پویا حل کرد چرا که باید اصل بهینگی در مسئله صدق کند.
اصل بهینگی در یک مسئله صدق می‌کند اگر یک حل بهینه برای نمونه‌ای از مسئله، همواره حاوی حل بهینه برای همه‌ی زیر نمونه‌ها باشد
در روش برنامه‌نویسی پویا اغلب از یک آرایه برای ذخیره نتایج جهت استفاده مجدد استفاده شده، و زیرمسائل به صورت جزء به کل حل می‌شوند. در مورد این مسئله، ابتدا زیرمسائلی که تنها از دو ماتریس تشکیل شده‌اند محاسبه می‌شوند. سپس زیرمسائلی که از سه ماتریس تشکیل شده‌اند محاسبه می‌شوند. این دسته از زیرمسائل به زیرمسائلی متشکل از دو ماتریس تجزیه می‌شوند که قبلا محاسبات آن‌ها صورت گرفته، و نتایج آن‌ها در آرایه ذخیره شده‌اند. در نتیجه نیاز به محاسبه مجدد آن‌ها نیست. به همین ترتیب در مرحله بعد زیرمسائل با چهار ماتریس محاسبه می‌شوند، و الی آخر.
درختهای جستوجوی دودویی بهینه
درخت جستجوی دودویی یک درخت دودویی از عناصر است که معمولا کلید نامیده می‌شوند به قسمی که:
هر گره حاوی یک کلید است.
کلیدهای موجود در زیردرخت چپ هر گره، کوچکتر یا مساوی کلید آن گره هستند.
کلیدهای موجود در زیردرخت راست هر گره، بزرگتر یا مساوی کلید آن گره هستند
زیرسازه بهینه
استفاده از روش زیرسازه بهینه به این معناست که مسئله را به زیرمسئله‌هایی کوچک‌تر بشکانیم و برای هر یک از این زیرمسئله‌ها پاسخی بهینه بیابیم و پاسخ بهینه مسئله کلی را از کنار هم قرار دادن این پاسخ‌های بهینه جزئی به دست آوریم. مثلا در هنگام حل مسئله یافتن کوتاه‌ترین مسیر از یک راس یک گراف به راسی دیگر، می‌توانیم کوتاه‌ترین مسیر تا مقصد از همه رئوس مجاور را به دست آوریم و از آن برای جواب کلی استفاده کنیم. به‌طور کلی حل مسئله از این روش شامل سه مرحله است.
شکاندن مسئله به بخش‌های کوچک‌تر
حل خود این زیرمسئله‌ها با شکاندن آن‌ها به صورت بازگشتی
استفاده از پاسخ‌های جزئی برای یافتن پاسخ کلی
زیرمسئله‌های هم‌پوشان
گفته می‌شود مسئله‌ای دارای زیرمسئله‌های هم‌پوشان است اگر بتوان مسئله را به زیرمسئله‌های کوچکتری شکست که پاسخ هرکدام چند بار در طول فرایند حل مورد استفاده قرار بگیرد. برنامه‌ریزی پویا کمک می‌کند تا هر کدام از این پاسخ‌ها فقط یک بار محاسبه شوند فرایند حل از بابت دوباره‌کاری هزینه‌ای را متحمل نشود. برای مثال در دنباله فیبوناچی برای محاسبه عدد چهارم دنباله به دانستن عدد سوم نیاز داریم. برای محاسبه عدد پنجم هم باز به عدد سوم نیاز داریم. حال اگر مثلا در شرایطی بخواهیم عدد ششم دنباله فیبوناچی را حساب کنیم، در این محاسبه هم مقدار عدد پنجم را می‌خواهیم و هم مقدار عدد چهارم را. اگر تصمیم بگیریم اعداد چهارم و پنجم را به نوبت حساب کنیم در هنگام محاسبه هرکدام به مقدار عدد سوم نیاز پیدا می‌کنیم و باید دوباره آن را محاسبه کنیم.
برای جلوگیری از این محاسبات چندباره، معمولا الگوریتمهایی که مبتنی بر برنامه‌ریزی پویا هستند از یکی از دو راه زیر استفاده می‌کنند.
’’’رویکرد بالا به پایین’’’: در این رویکرد مسئله به زیرمسئله‌هایی شکسته می‌شود و پاسخ هر زیرمسئله پس از محاسبه در جایی ذخیره می‌شود. در مراحل بعدی هر وقت به آن پاسخ نیاز بود پاسخ از روی حافظه خوانده می‌شود. این فرایند ترکیبی از الگوریتم بازگشتی و ذخیره‌سازی در حافظه است.
’’’رویکرد پایین به بالا’’’: در این رویکرد همه زیرمسئله‌های مورد نیاز از کوچک به بزرگ حل می‌شوند و از جواب‌ها بلافاصله برای محاسبه بعدی‌ها استفاده می‌شود و فرایند محاسبه تا رسیدن به زیرمسئله مورد نیاز (که در وافع مسئله اصلی ماست) ادامه می‌یابد. بدیهی‌ست که در این حالت استفاده از الگوریتم بازگشتی ضروری نیست. مثال زیر این تفاوت‌ها را روشن‌تر می‌کند.
مثال
یک پیاده‌سازی ساده از یک تابع برای یافتن عدد فیبوناچی nام می‌تواند به شکل زیر باشد.
function fib(n)
if n = 0
return 0
else if n = 1
return 1
return fib(n − 1) + fib(n − 2)
برای مثال اگر از چنین تابعی (fib(5 را بخواهیم، تابع‌هایی که صدا می‌شوند به شکل زیر خواهند بود.
fib(5)
fib(4) + fib(3)
(fib(3) + fib(2)) + (fib(2) + fib(1))
((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
(((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
mn := fib(n − 1) + fib(n − 2)
return mn
این نمونه‌ای از فرایند بالا به پایین بود. چون ابتدا مسئله را شکستیم و بعد به محاسبه و ذخیره پاسخ زیرمسئله‌ها پرداختیم.
در فرایند پایین به بالا برای حل چنین مسئله‌ای از عدد فیبوناچی یکم شروع می‌کنیم تا به عدد خواسته‌شده برسیم. با این کار باز هم پیچیدگی زمانی از مرتبه 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 هم نیازی نیست. فضای ذخیره از مرتبه ۱ کفایت می‌کند. علت این که همیشه از رویکرد پایین به بالا استفاده نمی‌کنیم این است که گاهی از قبل نمی‌دانیم باید کدام زیرمسئله‌ها را حل کنیم تا به مرحله اصلی برسیم، یا این که مجبوریم زیرمسئله‌هایی که استفاده نمی‌شوند را هم حل کنیم.
تفاوت این روش و روش تقسیم و غلبه
یکی از روش‌های پرکاربرد و مشهور طراحی الگوریتم روش برنامه‌نویسی پویا (یا برنامه‌ریزی پویا - Dynamic Programming) است. این روش همچون روش تقسیم و حل (Divide and Conquer) بر پایه تقسیم مسئله بر زیرمسئله‌ها کار می‌کند. اما تفاوت‌های چشم‌گیری با آن دارد.
زمانی که یک مسئله به دو یا چند زیرمسئله تقسیم می‌شود، دو حالت ممکن است پیش بیاید:
داده‌های زیرمسئله‌ها هیچ اشتراکی با هم نداشته و کاملا مستقل از هم هستند. نمونه چنین مواردی مرتب‌سازی آرایه‌ها با روش ادغام یا روش سریع است که داده‌ها به دو قسمت تقسیم شده و به صورت مجزا مرتب می‌شوند. در این حالت داده‌های یکی از بخش‌ها هیچ ارتباطی با داده‌های بخش دیگر نداشته و در نتیجه حاصل از آن بخش اثری ندارند. معمولا روش تقسیم و حل برای چنین مسائلی کارایی خوبی دارد.
داده‌های زیرمسئله وابسته به هم بوده یا با هم اشتراک دارند. در این حالت به اصطلاح زیرمسئله‌ها هم‌پوشانی دارند. نمونه بارز چنین مسائلی محاسبه جمله nام دنباله اعداد فیبوناچی است.
روش برنامه‌نویسی پویا غالبا برای الگوریتمهایی بکار برده می‌شود که در پی حل مسئله‌ای به صورت بهینه می‌باشند.
در روش تقسیم و غلبه ممکن است برخی از زیرمسائل کوچکتر با هم برابر باشند که در این صورت زیرمسائل برابر بطور تکراری چندین مرتبه حل می‌شوند که این یکی از معایب روش تقسیم و غلبه است.
ایده‌ای که در فرای روش برنامه‌نویسی پویا نهفته‌است جلوگیری از انجام این محاسبات تکراری است و روشی که معمولا برای این عمل بکارگرفته می‌شود استفاده از جدولی برای نگهداری نتایج حاصل از حل زیرمسائل است. در این صورت اگر الگوریتم به زیرمسئله‌ای برخورد کرد که پیش از این حل شده است، به جای حل مجدد آن، نتیجه محاسبه قبلی را از جدول برداشته و کار را با زیرمسئله بعدی دنبال می‌کند.
روش برنامه‌نویسی پویا یک روش پایین به بالا است به این معنی که از حل مسائل کوچکتر به حل مسائل بزرگتر می‌رسیم. در حالیکه از نظر ساختاری روش تقسیم و غلبه روشی است از بالا به پایین، یعنی بطور منطقی (نه عملی) پردازش از مسئله اولیه آغاز شده و به سمت پایین و حل مسائل کوچکتر به پیش می‌رود.
الگوریتم ضریب دو جمله‌ای با استفاده از برنامه‌ریزی پویا
ورودی‌ها : اعداد صحیح و مثبت n و k که در آن k ≤ n است.
خروجی‌ها : bin2 ضریب دو جمله‌ای (n¦k)
(int bin2 ( int n , int k
index i,j
;int B 0..K
(++for (i=0; i <= n ;i
(++for (j=0;j <= min(i,k);j
(if (j == 0
j == i
۱ =Bij
else
;Bij=Bi-1j-1+Bi-1j
;return Bnk