پاورپوینت تکنیک حریصانه در حل مسائل (pptx) 27 اسلاید

دسته بندی : پاورپوینت

نوع فایل : PowerPoint (.pptx) ( قابل ویرایش و آماده پرینت )

تعداد اسلاید: 27 اسلاید

قسمتی از متن PowerPoint (.pptx) :

بنام خدا 1 2 یک مسئله: چهار نفر مي خواهند از يك پل در كمتر از 18 دقيقه رد شوند . اين افراد تنها يك فانوس دارند و همچنين در آن واحد تنها 2 نفر مي توانند از پل رد شوند . روش عبور را به آنها نشان دهيد. زمان رد شدن آنها به صورت زير است: A = 1 min , B = 2 min , C = 5 min , D = 10 min 3 تکنیک حریصانه در حل مسائل  فصل3 4 برای پاسخ دادن به یک مسئله در حالت کلی دو رهیافت (approach)وجود دارد : 1.هدف گرا : یعنی مبتنی بر یک رویکرد آگاهانه بردار پاسخ را بسازیم. .2متد گرا : یعنی جست و جو حالات ممکن فضای پاسخ و مقایسه آن ها تا رسیدن به جواب (بهینه) . راهکار اول را روش حریصانه گویند. این روش ، زمان حل مسئله را به شدت کاهش می دهد. اما مشکل این است که در بسیاری از مسائل معیار حریصانه ای وجود ندارد به همین دلیل به سراغ روش های دیگر می رویم.الگوریتم های حریصانه به طور موثری برای حل مسائل بهینه سازی استفاده می شود . مثلا برای یافتن کوتاه ترین مسیر بین یک گره و گره های دیگر در یک شبکه ، یا یافتن بهترین ترتیب اجرای مجموعه ای از کار ها ی داری محدودیت زمانی از الگوریتم های حریصانه استفاده می کنیم. 5 برگشت به مسئله قبل: چهار نفر مي خواهند از يك پل در كمتر از 18 دقيقه رد شوند . اين افراد تنها يك فانوس دارند و همچنين در آن واحد تنها 2 نفر مي توانند از پل رد شوند . روش عبور را به آنها نشان دهيد. زمان رد شدن آنها به صورت زير است: A = 1 min , B = 2 min , C = 5 min , D = 10 min 6 حل اگر افراد به ترتیب زیر از روی پل عبور کنند مجموع زمان عبور آنها 17 دقيقه خواهد بود. نکته : این زمان كوتاهترين زمان ممكن براي رد شدن از پل است . مسئله 1 (كوله پشتي) اين مسئله به شكل هاي مختلفي وجود دارد . در اينجا ساده ترين شكل آن را در نظر مي گيريم. n شي و يك كوله پشتي مفروض است . براي i=1,2,3,…,n داراي وزن مثبت Wi و ارزش Pi است. كوله پشتي تحمل وزن W را دارد. مي خواهيم كوله پشتي را با تعدادي از اين اشيا پر كنيم به طوري كه مجموع وزن اشيا انتخاب شده از W تجاوز نكند و مجموع ارزش آن ها ماكزيمم باشد. در ساده ترين شكل مسئله فرض مي كنيم كه اشيا قابل تقسيم به قطعات كوچك تر باشد. به طوري كه بتوان كسر xi از شي i كه در آن 1 X i 0 باشد را انتخاب كرد. (اگر اشيا قابل شكستن نباشند مسئله مشكل تر خواهد بود.) براي انتخاب بهترين شي برخی از انواع تابع انتخاب ممكن است به نظر آيد: انتخاب به ترتيب با ارزش ترين شي انتخاب بر اساس سبك ترين شي انتخاب بر اساس بزرگ ترين Pi/Wi اين سه روش را براي مثال زير امتحان مي كنيم : 7 مثال پنج شي با مشخصات زير مفروض است. اگر W=100 كوله پشتي را چگونه پر كنيم تا بهاي آن ماكزيمم باشد ؟ 8 10 20 30 40 50 P=20 P=30 P=66 P=40 P=60 حل از حل مسئله با سه روش فوق جدول زير حاصل مي شود : 9