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

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

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

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

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

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

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

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

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

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

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

  1. ارائه یک ویژگی بازگشتی که حل بهینهٔ نمونه‌ای از مسئله را به دست می‌دهد.
  2. محاسبه مقدار حل بهینه به شیوهٔ جزء به کل.
  3. بنا کردن یک حل نمونه به شیوهٔ جزء به کل.

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

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

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

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

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

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

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

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

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

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

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

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

مثال[ویرایش]

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

 function fib(n)
 if n = 0
 return 0
 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
 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) بر پایه تقسیم مسئله بر زیرمسئله‌ها کار می‌کند. اما تفاوت‌های چشم‌گیری با آن دارد.

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

  1. داده‌های زیرمسئله‌ها هیچ اشتراکی با هم نداشته و کاملاً مستقل از هم هستند. نمونه چنین مواردی مرتب‌سازی آرایه‌ها با روش ادغام یا روش سریع است که داده‌ها به دو قسمت تقسیم شده و به صورت مجزا مرتب می‌شوند. در این حالت داده‌های یکی از بخش‌ها هیچ ارتباطی با داده‌های بخش دیگر نداشته و در نتیجۀ حاصل از آن بخش، اثری ندارند. معمولاً روش تقسیم و حل برای چنین مسائلی کارایی خوبی دارد.
  2. داده‌های زیرمسئله وابسته به هم بوده یا با هم اشتراک دارند. در این حالت به اصطلاح زیرمسئله‌ها هم‌پوشانی دارند. نمونه بارز چنین مسائلی محاسبه جمله 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
                                                                                                          {

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

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

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

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

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