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

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

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

تاریخچه برنامه‌ریزی پویا و دینامیک

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

روش علوم رایانه‌ای برای برنامه‌ریزی پویا کارایی بالاتری دارد زیرا محاسبات تکراری را حذف می‌کند در حالی که در روش ریاضی برنامه‌ریزی پویا امکان کاهش فضای حافظه بیشتر است. این روش نباید با پویایی سیستم‌ها اشتباه گرفته شود.

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

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

یک مسئله باید دارای دو مشخصهٔ کلیدی باشد تا بتوان برنامه‌نویسی پویا را برای آن به کار برد:

  • زیرساختار بهینه
  • زیرمسئله‌های همپوشان

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

اصل بهینگی

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

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

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

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

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

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

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

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

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

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

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

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

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

نتیجه‌گیری

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

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

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