ارسال پاسخ  ارسال موضوع 
 
امتیاز موضوع:
  • 0 رأی - میانگین امتیازات: 0
  • 1
  • 2
  • 3
  • 4
  • 5
مقاله: برنامه‌ریزی پویا
نویسنده پیام
مشخصات كاربر:
as@l
مدیر بازنشسته تالار
***
مدیر بازنشسته
ارسال ها:29,179
محل سکونت : تهران غایب
تاريخ ثبت نام: ۱۳ شهريور ۱۳۸۹
عضو شماره:171267
اعتبار: 115
نفر دوم برترین ارسال کننده
   
سپاس ها 0
سپاس شده 1035 بار در 1011 ارسال
ارسال: #1
مقاله: برنامه‌ریزی پویا
در علوم رایانه و ریاضیات، برنامه‌ریزی پویا روشی کارآمد برای حل مسائل جست‌وجو و بهینه‌سازی با استفاده از دو خصیصهٔ زیرمسئله‌های هم‌پوشان و زیرساخت‌های بهینه است. بر خلاف برنامه‌ریزی خطی، چارچوب استانداردی برای فرموله کردن مسائل برنامه‌ریزی پویا وجود ندارد. در واقع، آن‌چه برنامه‌ریزی پویا انجام می‌دهد ارائه روش برخورد کلی جهت حل این نوع مسائل است. در هر مورد، باید معادلات و روابط ریاضی مخصوصی که با شرایط آن مسئله تطبیق دارد نوشته شود.


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

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

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

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

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

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




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

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


موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  توانایی یادگیری ریاضیات از نوزادی آغاز می‌شود Lorax 0 182 ۱۸-۹-۱۳۹۲ ۰۲:۳۵ عصر
آخرین ارسال: Lorax
  ارایه کوتاهترین و جدیدترین روش اثبات یک قضیه ریاضی توسط محققان ایرانی Lorax 0 199 ۱۸-۹-۱۳۹۲ ۰۲:۳۴ عصر
آخرین ارسال: Lorax
  مسخ کافکا در دنیای هندسه! - حل یک معمای 40 ساله ریاضی Lorax 0 185 ۱۸-۹-۱۳۹۲ ۰۲:۳۴ عصر
آخرین ارسال: Lorax
  حدس گلد باخ Lorax 0 178 ۱۸-۹-۱۳۹۲ ۰۲:۳۳ عصر
آخرین ارسال: Lorax
  عدد شاد Lorax 0 182 ۱۸-۹-۱۳۹۲ ۰۲:۳۳ عصر
آخرین ارسال: Lorax

پرش به انجمن:


کاربرانِ درحال بازدید از این موضوع: 1 مهمان
به ایران فروم امتیاز دهید

به اين صفحه امتياز دهيد

با تشکر از حمايت شما