مدرسه بهینه سازی جلسه هشتم: Dynamic Programming


Notice: Undefined index: tie_hide_meta in /home/power/domains/powersim.ir/public_html/wp-content/themes/sahifa/framework/parts/meta-post.php on line 3

مدرسه بهینه سازی جلسه هشتم: Dynamic Programming

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

پاورسیم
پاورسیم

سرفصل ها:

یافتن گراف مسیر

حل به روش الگوریتم حریصانه

در الگوریتم حریصانه ابتدا Node با بیشترین وزن انتخاب می شود و پس از انتخاب این Node  الگوریتم اجازه ندارد رئوس مجاور را انتخاب کند زیرا در غیر این صورت مجموعه مستقل نخواهد بود.

حل به روش الگوریتم تقسیم وحل

رای استفاده از روش تقسیم و حل ابتدا گراف را باید به دو زیرمجموعه  تقسیم کرده و سعی  کنیم که مسأله را برای هر زیرگراف حل کنیم

حل با یک راهکار جدید

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

راهکارهای کلی برنامه ریزی پویا

مسأله کوله پشتی

کوله پشتی با تکرار

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

مسأله فاصله ویرایشی

در زیر PDF آموزشی برای شما پیوست شده که الگوریتم ها و شبه کدها روش های بیان شده در بالا را در خود دارد.

دانلود فایل

برای دانلود کد متلب شبیه سازی مسئله بهره برداری از واحدها Uint Commitment با استفاده از روش Dynamic Programming نیز می توانید به لینک زیر مراجعه کنید.  DP-UC

درباره مدیر

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

ببینید حتما...

مدرسه بهینه سازی جلسه هفتم: آموزش کامل پیاده سازی شبکه های عصبی

آموزش کامل پیاده سازی شبکه های عصبی روش پیش بینی شبکه های عصبی در مهندسی …

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *