برنامه‌نویسی پویا چیست و چرا یادگیری آن ایده خوبی است؟

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

برنامه‌نویسی پویا چیست؟

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

برنامه‌نویسی پویا چه ویژگی‌های شاخصی دارد؟

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

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

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

درخت جستجوی دودویی یک درخت دودویی از عناصر است که معمولاً کلید نامیده می‌شوند به صورتی است که هر گره حاوی یک کلید است، کلیدهای موجود در زیردرخت چپ هر گره، کوچکتر یا مساوی کلید آن گره هستند و کلیدهای موجود در زیردرخت راست هر گره، بزرگتر یا مساوی کلید آن گره هستند

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

زیرساختار بهینه به این معناست که جواب یک مسئله بهینه‌سازی را بتوان از ترکیب جواب‌های بهینه زیرمسئله‌های آن به دست آورد. چنین زیرساختارهای بهینه‌ای معمولاً با رویکرد بازگشتی به دست می‌آیند؛ برای مثال، در گراف (G=(V,E، کوتاه‌ترین مسیرِ م از رأس آ به رأس ب، زیرساختار بهینه از خود نشان می‌دهد: هر رأس میانیِ ث از مسیرِ م را در نظر بگیرید. اگر م واقعاً کوتاه‌ترین مسیر باشد، آنگاه می‌توان آن را به دو زیرمسیر م۱ از آ تا ث و م۲ از ث تا ب در نظر گرفت، به نحوی که هر کدام از این‌ها کوتاه‌ترین مسیر بین دو سر خود هستند (به همان طریق برش و چسباندن کتاب مقدمه‌ای بر الگوریتم‌ها). بر این اساس، می‌توان جواب را به صورت بازگشتی بیان کرد، درست مانند الگوریتم‌های بلمن-فورد و فلوید-وارشال.

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

گراف زیرمسئله‌ها دقیقاً همین اطلاعات را برای یک مسئله در بر می‌گیرد. تصویر ۱ گراف زیرمسئله‌های دنباله‌های فیبوناچی را نشان می‌دهد. گراف زیرمسئله‌ها یک گراف جهت‌دار، شامل یک رأس به ازای هر زیرمسئله متمایز است و در صورتی یک یال جهت‌دار از رأس زیرمسئله x به رأس زیرمسئله y دارد که برای تعیین یک جواب بهینه برای زیرمسئله x مستقیماً نیاز به در نظر گرفتن یک جواب بهینه برای زیرمسئله y داشته‌ باشیم. برای نمونه، گراف زیرمسئله دارای یک یال از x به y است، در صورتی که یک رویه (procedure) بازگشتی بالا به پایین برای حل x، مستقیماً خود را برای حل y صدا بزند. می‌توان گراف زیرمسئله‌ها را یک نسخه کاهش‌یافته درخت بازگشتی برای روش بازگشتی بالا به پایین در نظر گرفت، به گونه‌ای که همه رئوس مربوط به یک زیرمسئله را یکی کنیم و یال‌ها را از والد به فرزند جهت‌دار کنیم.

روش پایین به بالا برای برنامه‌نویسی پویا رئوس گراف زیرمسئله‌ها را به ترتیبی در نظر می‌گیرد که همه زیرمسئله‌های مجاور یک زیرمسئله، پیش از آن حل شوند. در یک الگوریتم برنامه‌نویسی پویای پایین به بالا، رئوس گراف زیرمسئله‌ها را به صورتی در نظر می‌گیریم که «معکوس مرتب توپولوژیکی» یا «مرتب توپولوژیک وارون» زیرگراف مسئه‌ها است. به زبان دیگر، هیچ زیرمسئله‌ای تا زمانی که همه زیرمسئله‌هایی که به آن‌ها وابسته است حل نشده‌اند، در نظر گرفته ‌نمی‌شود. به‌طور مشابه، می‌توانیم رویکرد بالا به پایین (همراه به‌خاطرسپاری) برای برنامه‌نویسی پویا را به شکل جستجوی ژرفانخست گراف زیرمسئله‌ها ببینیم.

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

function fib(n)

    if n = 0   

        return 0       

    if n = 1   

        return 1       

    return fib(n − 1) + fib(n − 2) 

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

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

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

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

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

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