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

از ویکی‌پدیا، دانشنامهٔ آزاد
(تغییرمسیر از برنامه‌ریزی پویا)
پرش به: ناوبری، جستجو

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

تاریخچه[ویرایش]

این روش در سال ۱۹۵۳ توسط ریاضی‌دانی به نام ریچارد بلمن معرفی شد. برنامهریزِی پویا در ریاضی و علوم رایانه روشی شناخته شده است که از آن در نوشتن الگوریتم‌های بهینه با استفاده از حذف اجرای چند بارهٔ یک زیر مسئله یکسان استفاده می‌شود. تعریف برنامه ریزِی پویا در ریاضی و علوم رایانه متفاوت است. نشان داده شده است که روش علوم رایانه ای برای برنامه ریزِی پویا کارایی بالاتری دارد زیرا محاسبات تکراری را حذف می‌کند در حالی که در روش ریاضی برنامه ریزِی پویا امکان کاهش فضای حافظه بیشتر است.

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

ویژگی‌ها[ویرایش]

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

اصل بهینگی[ویرایش]

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

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

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

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

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

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

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

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

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

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

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

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

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

زیرسازه بهینه[ویرایش]

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

  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 هم نیازی نیست. فضای ذخیره از مرتبه ۱ کفایت می‌کند. علت این که همیشه از رویکرد پایین به بالا استفاده نمی‌کنیم این است که گاهی از قبل نمی‌دانیم باید کدام زیرمسئله‌ها را حل کنیم تا به مرحله اصلی برسیم، یا این که مجبوریم زیرمسئله‌هایی که استفاده نمی‌شوند را هم حل کنیم.

تفاوت این روش و روش تقسیم و غلبه[ویرایش]

یکی از روش‌های پرکاربرد و مشهور طراحی الگوریتم روش برنامه‌نویسی پویا (یا برنامه‌ریزی پویا - 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..n][0..K
                                                                                     (++for (i=0; i <= n ;i
                                                                         (++for (j=0;j <= min(i,k);j
                                                                           (if (j == 0 || j == i
 ۱ =[B[i][j
                                                                                            else
                                                              ;[B[i][j]=B[i-1][j-1]+B[i-1][j
                                                                                        ;[return B[n][k
                                                                                                          {

پانویس[ویرایش]

منابع[ویرایش]

  • هیلیر، فردریک؛ لیبرمن، جرالد.ج (۱۳۸۲). تحقیق در عملیات، ترجمه محمد مدرس و اردوان آصف‌وزیری، تهران: نشر جوان، چاپ دهم.
  • نیپولیتان، ریچارد؛ نعیمی‌پور، کیومرث (۱۳۹۰). طراحی الگوریتم‌ها، ترجمه عین‌الله جعفرنژاد قمی، بابل: انتشارات علوم رایانه.

پیوند به بیرون[ویرایش]

جستارهای وابسته[ویرایش]