برنامه‌نویسی پویا: تفاوت میان نسخه‌ها
محتوای حذف‌شده محتوای افزوده‌شده
MohandesWiki (بحث | مشارکت‌ها) |
FreshmanBot (بحث | مشارکت‌ها) جز اصلاح فاصله مجازی + اصلاح نویسه با استفاده از AWB |
||
خط ۳:
== تاریخچه ==
این روش در سال ۱۹۵۳ توسط ریاضی‌دانی به نام [[ریچارد بلمن]] معرفی شد. برنامهریزِی پویا در ریاضی و علوم رایانه روشی شناخته شده‌است که از آن در نوشتن الگوریتم‌های بهینه با استفاده از حذف اجرای چند بارهٔ یک زیر مسئله یکسان استفاده می‌شود. تعریف برنامه ریزِی پویا در ریاضی و علوم رایانه متفاوت است. نشان داده شده‌است که روش علوم
برنامه ریزِی پویا شبیه روش تقسیم و حل مسائل را با استفاده از ترکیب کردن جواب زیرمسأله‌ها حل می‌کند. [[الگوریتم تقسیم و حل]]، مسئله را به زیر مسئله‌های مستقل تقسیم می‌کند و پس از حل زیر مسئله‌ها به صورت بازگشتی،نتایج را با هم ترکیب کرده و جواب مسألهاصلی را بدست می‌آورد. به عبارت دقیق تر، برنامه ریزِی پویا در مواردی قابلاستفاده است که زیرمسأله‌ها مستقل نیستند؛ یعنی زمانی که زیرمسأله‌ها دارای زیر-زیر مسئله‌های یکسان هستند. دراین حالت روش تقسیم و حل با اجرای مکرر زیرمسأله‌های یکسان، بیشتر از میزان لازم محاسبات انجام می‌دهد. یکالگوریتم برنامه ریزِی پویا زیرمسأله‌ها را یک بار حل و جواب
== ویژگی‌ها ==
خط ۱۶:
حل بهینه، سومین مرحله از بسط یک الگوریتم [[برنامه‌نویسی]] پویا برای مسائل [[بهینه‌سازی]] است. مراحل بسط چنین الگوریتمی به شرح زیر است:
# ارائه یک ویژگی بازگشتی که حل بهینهٔ
# محاسبه مقدار حل بهینه به شیوهی جزء به کل.
# بنا کردن یک حل نمونه به شیوهی جزء به کل.
خط ۲۳:
اصل بهینگی در یک مسئله صدق می‌کند اگر یک حل بهینه برای نمونهای از مسئله، همواره حاوی حل بهینه برای همهی زیر نمونه‌ها باشد
در روش برنامه‌نویسی پویا اغلب از یک آرایه برای ذخیره نتایج جهت استفاده مجدد استفاده شده، و زیرمسائل به صورت جزء به کل حل می‌شوند. در مورد این مسئله، ابتدا زیرمسائلی که تنها از دو ماتریس تشکیل شده‌اند محاسبه می‌شوند. سپس زیرمسائلی که از سه ماتریس تشکیل شده‌اند محاسبه می‌شوند. این دسته از زیرمسائل به زیرمسائلی متشکل از دو ماتریس تجزیه می‌شوند که قبلاً محاسبات
درختهای جستوجوی دودویی بهینه
خط ۱۱۰:
ایده‌ای که در فرای روش برنامه‌نویسی پویا نهفته‌است جلوگیری از انجام این محاسبات تکراری است و روشی که معمولاً برای این عمل بکارگرفته می‌شود استفاده از جدولی برای نگهداری نتایج حاصل از حل زیرمسائل است. در این صورت اگر [[الگوریتم]] به زیرمسئله‌ای برخورد کرد که پیش از این [[حل شده]] است، بجای حل مجدد آن، نتیجه محاسبه قبلی را از جدول برداشته و کار را با زیرمسئله بعدی دنبال می‌کند.
روش برنامه‌نویسی پویا یک روش پایین به بالا است به این معنی که از حل مسائل کوچکتر به حل مسائل بزرگتر می‌رسیم. در حالیکه از نظر ساختاری روش تقسیم و غلبه روشی است از بالا به پایین، یعنی بطور منطقی (نه عملی) پردازش از مسئله اولیه آغاز شده و
== الگوریتم ضریب دو
'''ورودی‌ها :''' اعداد صحیح و مثبت n و k که در آن k ≤ n است.
'''خروجی‌ها :''' bin2 ضریب دو
(int''' bin2 ('''int''' n , '''int''' k'''
| |||