المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


آموزش:الگوریتم:برنامه‌ریزی پویا

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

مقدمه

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

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

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

روش حریصانه

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

مسائل نمونه

مراجع


ابزار صفحه