بخشی از پاورپوینت
اسلاید 1 :
درس طراحی الگوریتم ها
روش حریصانه
Greedy approach
اسلاید 2 :
Scrooge هرگز به آینده یا گذشته نمی اندیشید.
الگویتم حریصانه به شیوه scrooge عمل می کند.
به ترتیب عناصر داده ها را گرفته هر بار آن عنصری را که در حال حاضر طبق ملاکی معین بهترین به نظر می رسد بدون توجه به انتخاب هایی که قبلاً انجام داده یا در آینده انجام خواهد داد، برمی دارد.
اسلاید 3 :
روش حریصانه
غالباً برای حل مسائل بهینه سازی به کار می رود.(مانند برنامه نویسی پویا)
برای هر مسئله ای نمی تواند پاسخ بهینه را بدست آورد.
باید اثبات کرد که پاسخ همواره بهینه است یا خیر
در روش حریصانه تقسیم به نمونه های کوچکتر صورت نمی پذیرد.
با انجام یک سری انتخاب که در هر لحظه بهترین به نظر می رسد عمل می کند.
انتخاب بهینه در هر لحظه (بهینه محلی - Local Optimum)
تصمیم درباره انتخاب یا رد یکی از داده های ورودی غیرقابل برگشت است.
اسلاید 4 :
مثال (مسئله خرد کردن پول)
هدف برگرداندن باقیمانده پول با حداقل تعداد سکه ها می باشد.
حل با روش حریصانه
در آغاز هیچ سکه ای در مجموعه نداریم.
سکه با ارزش بیشتر انتخاب می شود. (روال انتخاب)
باید بررسی کنیم با افزودن این سکه به بقیه پول، جمع کل آنها از چیزی که باید باشد بیشتر می شود یا خیر.(بررسی امکان سنجی)
اگر با افزودن این سکه، بقیه پول از میزان لازم بیشتر نشود، این سکه به مجموعه اضافه می شود.
بررسی می شود که آیا تمام پول پرداخت شده است یا نه (بررسی راه حل)
اگر هنوز مقداری مانده بود مجدداً از مرحله انتخاب سکه، فرآیند تکرار می شود.
این تکرار تا زمانی انجام می شود که با سکه های موجود بقیه پول به طور کامل پرداخت گردد و یا اینکه امکان پرداخت پول با این سکه ها وجود نداشته باشد.
اسلاید 5 :
مثال (مسئله خرد کردن پول)
زمانی که این الگوریتم کار نمی کند:
پرداخت 18 سنت با سکه های 1 ، 6 و 7 سنتی
حریصانه: دو سکه 7 سنتی و چهار سکه 1 سنتی
بهینه: سه تا سکه 6 سنتی
پرداخت 16 سنت با سکه های 12، 10، 5 و 1 سنتی
حریصانه: یک سکه 12 سنتی و چهار سکه 1 سنتی
بهینه: یک سکه 10 سنتی، یک سکه 5 سنتی و یک سکه 1 سنتی
این الگوریتم همواره جواب بهینه را نمی دهد.
اسلاید 6 :
روش حریصانه
هر دور تکرار الگوریتم حریصانه شامل مراحل زیر است:
روال انتخاب: از بین عناصر، بهترین عنصر درنظر گرفته می شود. این انتخاب براساس یک معیار حریصانه که به طور محلی بهترین جواب را در هر لحظه انتخاب می کند شکل می گیرد.
بررسی امکان سنجی: بررسی می شود که آیا با انتخاب آن مولفه امکان رسیدن به جواب وجود دارد یا خیر
درصورت مثبت بودن پاسخ، آن مولفه را به مجموعه جواب اضافه می کنیم
در صورت منفی بودن پاسخ، آن مولفه را برای همیشه کنار می گذاریم.
بررسی جواب: با افزودن هر عنصر به مجموعه جواب، بررسی می کنیم اگر جواب مسئله حاصل شده است جواب بدست آمده بهینه فرض خواهد شد و کار تمام است.
اسلاید 7 :
کوله پشتی کسری
دراین مسئله امکان انتخاب کسری از هر شی وجود دارد. اگر کسر 0≤xi≤1 از شی i انتخاب شود ارزش pi xi بدست می آید.
هدف:
اسلاید 8 :
کوله پشتی کسری
راه حل های حریصانه:
مرتب کردن اشیا به ترتیب بیشترین ارزش و انتخاب آنها
مرتب کردن اشیا به ترتیب کمترین وزن و انتخاب آنها
مرتب کردن اشیا به ترتیب بیشترین مقدار ارزش واحد وزن (pi /wi) و انتخاب آنها
اسلاید 9 :
مثال
ظرفیت کوله پشتی 20 می باشد.
جدول زیر نتیجه سه راه حل مختلف بیان شده را نشان می دهد:
روش آخر – انتخاب براساس بیشترین ارزش هر واحد وزن شیئ، جواب بهینه را می دهد.
اسلاید 10 :
مسئله زمان بندی (scheduling)
دو نوع مسئله زمان بندی داریم:
کمینه سازی زمان کل در سیستم برای انتظار کشیدن و سرویس دهی (زمان بودن در سیستم)
مثال: آرایشگاه
زمان بندی با مهلت معین (scheduling with deadline)
اسلاید 11 :
۱- کمینه سازی زمان کل در سیستم
مثال:
زمان کل بودن در سیستم برای زمان بندی فوق
5 + (5 + 10) + (5+ 10 + 4) = 39
اسلاید 12 :
روش brute-force
لیست تمام زمان بندی های ممکن
زمان بندی [3,1,2] بهینه می باشد.
مرتبه الگوریتم برابر با تعداد حالات جایگشت کارها می باشد که از درجه فاکتوریل است.
اسلاید 13 :
روش حریصانه
ملاک انتخاب کارها:
ابتدا کاری انتخاب شود که زمان سرویس دهی کمتری داشته باشد.
این انتخاب باعث می شود کارهای بعدی کمتر منتظر بمانند و در نتیجه زمان کل بودن آنها در سیستم کاهش می یابد.
اسلاید 14 :
الگوریتم
برای یافتن زمان بندی بهینه، کارها را بر اساس زمان سرویس دهی آنها به ترتیب صعودی مرتب می کنیم.
کارها را به ترتیب زمان سرویس کمتر، انتخاب می کنیم.
پیچیدگی الگوریتم: O(n lgn)
میتوان با برهان خلف اثبات نمود که این روش همواره جواب بهینه را می دهد.
قضیه: تنها زمان بندي كه كل زمان بودن در سيستم را كمينه مي كند، زمان بندي اي است كه در آن كارها برحسب افزايش زمان سرويس مرتب مي شوند.
اسلاید 15 :
تعمیم مسئله
وقتی در سیستم بیشتر از یک سرویس دهنده داشته باشیم (m سرویس دهنده)
کارها بر اساس افزایش زمان سرویسشان مرتب می شوند.
سرویس دهنده اول، کار 1، سرویس دهنده دوم، کار 2 و .
کار سرویس دهنده اول زودتر از همه انجام شده و کار m+1 را انجام می دهد و..
اسلاید 16 :
۲- زمان بندی با مهلت معین
در این حالت، اجرای هر کاری باید تا زمان مشخصی شروع شود در غیر این صورت آن کار دیگر قابل اجرا نخواهد بود.
مدت زمان انجام کارها برابر است.
مسئله: تعیین زمان بندی با سود کل بیشینه، با این فرض که هر کاری دارای سودی است و فقط وقتی قابل حصول است که آن کار در مهلت مقررش شروع شود.
مثال: (زمان سرویس برای هر کار 1 واحد است)
اسلاید 17 :
همه زمان بندی های ممکن
زمان بندی [1, 2] غیر ممکن است.
اسلاید 18 :
اصطلاحات
دنباله امكان پذير (feasible): دنباله اي از كارها كه در آن همه كارها بتوانند به ترتيب و در مهلت مقرر خود آغاز شوند.
مثال: دنباله [ 1 , 4 ] امكان پذير ولي [1, 4 ] امكان پذير نمي باشد.
مجموعه امكان پذير: مجموعه اي از كارها كه براي آن حداقل يك دنباله امكان پذير وجود داشته باشد.
مثال: مجموعه {1, 4} امکان پذیر ولی {2, 4} امکان پذیر نمی باشد.
دنباله بهينه: يك دنباله امكان پذير با حداكثر سود
مثال: دنباله [ 4, 1 ] دنباله بهینه است.
اسلاید 19 :
بررسی امکان پذیری
فرض كنيد S مجموعه اي از كارها باشد. در اين صورت مجموعه S امكان پذير خواهد بود اگر و فقط اگر دنباله حاصل از مرتب شدن کارهای S بر اساس مهلت هاي غير نزولي، امكان پذير باشد.
مثال آيا مجموعه { 1, 2, 4, 7 } امكان پذير مي باشد.
خیر، زيرا كار 4 در مهلتش نمي تواند زمان بندي شود.
اسلاید 20 :
الگوریتم حریصانه
sort the jobs in non-increasing order by profit;
S = ᶲ;
while (the instance is not solved){
select next job; //selection procedure
if (S is feasible with this job added) //feasible check
add this job to S;
if (there are no more jobs) //solution check
the instance is solved;
}
Sort the elements within S, in non-decreasing order by deadline;
باید نشان داد که الگوریتم همواره جواب بهینه را می دهد.
اثبات: با استفاده از استقرا بر روی تعداد کارها انجام می شود. (مراجعه به کتاب)
