درود مهمان گرامی!   ورود   )^(   ثبت نام زمان کنونی: ۹-۸-۱۳۹۳, ۰۵:۱۹ عصر


 

سرزمین بلاگ حامد اسکندری

ارسال پاسخ  ارسال موضوع 
 
امتیاز موضوع:
  • 0 رأی - میانگین امتیازات: 0
  • 1
  • 2
  • 3
  • 4
  • 5

حالت موضوعی | حالت خطی
مقاله: برنامه‌ریزی پویا
نویسنده پیام
مدیر بازنشسته تالار
مدیر بازنشسته
***
غایب
ارسال‌ها: 29,179
تاریخ عضویت: ۱۳ شهريور ۱۳۸۹
اعتبار: 115
سپاس ها 0
سپاس شده 1044 بار در 1019 ارسال
ارسال: #1
مقاله: برنامه‌ریزی پویا

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


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

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

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

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

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

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




موضوع‌های مرتبط با این موضوع...
مقاله در مورد آشنايي با ماتريسها
مقاله در مورد آمار و احتمالات
مقاله در مورد آلیاژهای سرامیکی
مقاله: نقش تازه ریاضیدانان در بازارهای بورس
مقاله: مغز کودکان و ریاضیات
مقاله: جایزه ویژه انجمن ریاضیات آمریکا به استاد ایرانی
مقاله: ریاضیات در هند و یونان
مقاله: سری لورانت ، سری تیلور ، و تبدیل لاپلاس .. !
مقاله: تئوری منطق فازی
مقاله: محبت در کلاس ریاضی

۲۳-۸-۱۳۸۹ ۱۰:۴۶ صبح
یافتن تمامی ارسال‌های این کاربر نقل قول این ارسال در یک پاسخ

ارسال پاسخ  ارسال موضوع 

کاربرانِ درحال بازدید از این موضوع: 1 مهمان
پرش به انجمن:


موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  مقاله در مورد آشنايي با ماتريسها saeedas52 1 1,093 ۱۱-۵-۱۳۹۳ ۱۰:۵۶ عصر
آخرین ارسال: klik3000
Thumbs Up پاسخ تشریحی دین و زندگی کنکور ریاضی 93 زندگی کن 0 244 ۶-۴-۱۳۹۳ ۱۱:۰۰ عصر
آخرین ارسال: زندگی کن
  توانایی یادگیری ریاضیات از نوزادی آغاز می‌شود Lorax 0 303 ۱۸-۹-۱۳۹۲ ۰۳:۳۵ عصر
آخرین ارسال: Lorax
  ارایه کوتاهترین و جدیدترین روش اثبات یک قضیه ریاضی توسط محققان ایرانی Lorax 0 324 ۱۸-۹-۱۳۹۲ ۰۳:۳۴ عصر
آخرین ارسال: Lorax
  مسخ کافکا در دنیای هندسه! - حل یک معمای 40 ساله ریاضی Lorax 0 305 ۱۸-۹-۱۳۹۲ ۰۳:۳۴ عصر
آخرین ارسال: Lorax

درباره ایران فروم

تالار گفتگوی ایرانیان از سال 1387 هجری شمسی فعالیت خود را آغاز کرده و هم اکنون با بیش از 750.000 کاربر ثابت بزرگ ترین تالار گفتگوی فارسی زبان در جهان می باشد.

برای سفارش تبلیغات در ایران فروم کلیک کنید

جستجو در انجمن