پاورپوینت روش حریصانه

بخشی از پاورپوینت

اسلاید 1 :

روش حریصانه
Greedy

اسلاید 2 :

الگوریتم حریصانه ، به ترتیب عناصر را انتخاب کرده ، هر بار آن عنصری را که طبق ملاکی معین ”بهترین“ به نظر می رسد، بدون توجه به انتخاب هایی که قبلا انجام داده یا در آینده انجام خواهد داد، بر می دارد.

اسلاید 3 :

الگوریتم حریصانه ، غالبا برای حل مسائل بهینه سازی به کار می روند.

در روش حریصانه ، تقسیم به نمونه های کوچک تر صورت نمی پذیرد.

اسلاید 4 :

الگوریتم حریصانه با انجام یک سری انتخاب، که هر یک در لحظه ای خاص ،بهترین به نظر می رسد عمل می کند، یعنی انتخاب در جای خود بهینه است.امید این است که یک حل بهینه سرتاسری یافت شود، ولی همواره چنین نیست.

برای یک الگوریتم مفروض باید تعیین کرد که آیا حل همواره بهینه است یا خیر.

اسلاید 5 :

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

اسلاید 6 :

الگوریتم حریصانه ، کار را با یک مجموعه تهی آغاز کرده به ترتیب عناصری به مجموعه اضافه می کند تا این مجموعه حلی برای نمونه ای از یک مسئله را نشان دهد.
هر دور تکرار ، شامل مولفه های زیر است:

اسلاید 7 :

1- روال انتخاب(Select)، برای انتخاب مولفه های بعدی جواب از مجموعه انتخاب های ممکن
2- بررسی امکان سنجی (Feasible)، تعیین می کند که آیا مجموعه جدید برای رسیدن به حل،عملی است یا خیر.
3- بررسی راه حل ،(Solution) برای بررسی اینکه مشخص کند در نهایت جواب حاصل شده است یا خیر.
4- یک تابع هدف : هدف بهینه کردن این تابع است.

اسلاید 8 :

روش حریصانه
set greedy(c){
s=Φ;
while(!solution (s) && c!= Φ){
X=select(c);
c=c-{x};
if(feasible(s,x))
s=sU{x}
}
if(solution(s))
return s;
else return Φ;
}

اسلاید 9 :

مسئله خرد کردن پول
می خواهیم باقی پول مشتری را با حداقل تعداد سکه ها پس بدهیم.
50 سنت
25 سنت
10 سنت
1 سنت
5 سنت
می خواهیم 57 سنت را پس دهیم.
{ } مجموعه اولیه

اسلاید 10 :

{ } اولیه
{50} امکان پذیر است اما جواب نیست
{50,50} امکان پذیر نیست پس 50 حذف می شود
{50,25} امکان پذیر نیست پس 25 حذف می شود
{50,10} امکان پذیر نیست پس 10 حذف می شود
{50,5} امکان پذیر است اما جواب نیست
{50,5,5} امکان پذیر نیست پس 5 حذف می شود
{50,5,1} امکان پذیر است اما جواب نیست
{50,5,1,1} جواب
50 سنت
25 سنت
10 سنت
1 سنت
5 سنت

اسلاید 11 :

آیا این روش همیشه جواب می دهد. مثلا اگر اندازه سکه ها به شکل دیگری بود ممکن است جواب ندهد.

روش حریصانه در مورد هر مسئله ای جواب نمی دهد. بلکه باید اثبات شود.

اسلاید 12 :

در حالت کلی دو خاصیت زیر را داشته باشد:
1- خاصیت انتخاب حریصانه
از آنجاییکه جواب بهینه سراسری از انتخاب های (حریصانه) بهینه محلی حاصل می شود و الگوریتم حریصانه همیشه بنا به خاصیت خود الگوریتم این عمل انتخاب بهینه محلی را انجام می دهد. البته باید ثابت کنیم که انتخاب حریصانه در هر مرحله در جهت به دست آوردن بهینه سراسری است بنابرین این خاصیت انتخاب بهینه را دارا است.
2- داشتن بهینه زیر ساختاری
یک مسئله دارای جواب بهینه است هرگاه هر زیر مسئله آن دازای جواب بهینه باشد و این مسئله باید برای هر مسئله اثبات شود.

اسلاید 13 :

1-4 درخت های پو شای کمینه
فرض کنید طراح شهری می خواهد چند شهر معین را با جاده به هم وصل کند، به قسمی که مردم بتوانند از هر شهر به شهر دیگر بروند. اگر محدودیت بودجه ای در کار باشد ، ممکن است طراح بخواهد این کار را با حداقل مقدار جاده کشی انجام دهد.

برای این مسئله دو الگوریتم حریصانه متفاوت : پریم و کروسکال بررسی می شود.

اسلاید 14 :

هر یک از این الگوریتم ها از یک ویژگی بهینه محلی استفاده می کند.

تضمینی وجود ندارد که یک الگوریتم حریصانه همواره حل بهینه بدهد،
ثابت می شود که الگوریتم های کروسکال و پریم همواره درخت های پوشای کمینه را ایجاد می کنند.

اسلاید 15 :

1-1-4الگوریتم پریم
الگوریتم پریم با زیر مجموعه ای تهی از یال های F و زیرمجموعه ای از رئوس Y آغاز می شود، زیرمجموعه حاوی یک راس دلخواه است. به عنوان مقداراولیه، {v1}
را به Y می دهیم . نزدیک ترین را س به Y ، راسی در V – Y است که توسط یالی با وزن کمینه به راسی در Y متصل است.

اسلاید 16 :

الگوریتم 1-4: الگوریتم پریم
void prim ( int n,
const number cost[ ] [ ],
set_ of_edges & F )
{
index i , vnear;
number min;
edge e;
index nearest [1..n-1];
// Viاندیس نزدیک ترین راس به
number mindist [1..n-1];
// به راس مجاور انتخاب شده viوزن یال
F = Ø ;

اسلاید 17 :

for ( i = 0 ; i < n ; i ++) { narest [i] = 0 ;
mindist [i] = cost [0] [i] ; }
do { min = ∞ ;
for ( i = 1 ; i < n ; i ++)
if ( 0 ≤ mindist [i] < min ) {
min = mindist [i] ;
indexmin = i ; }
e = edge connecting vertices indexed by near and nearest [ indexmin ] ;
F=F U {e}
mindist [ indexmin ] = -1 ;
for ( i = 1 ; i < n ; i ++)
if ( cost [i] [ indexmin ] < mindist [i]) {
mindist [i] = cost [i] [ indexmin ] ;
nearest [i] = indexmin ; }

} while( n-1 times );
}

اسلاید 18 :

تحلیل پیچیدگی زمانی در حالت معمول برای ا لگوریتم 1-4(الگوریتم پریم)
عمل اصلی: در حلقه do دو حلقه وجود دارد که هر یک (n – 1 )
بار تکرار می شود . اجرای دستورات داخل هر یک از آن ها را می توان
به عنوان یک بار اجرای عمل اصل در نظر گرفت.
اندازه ورودی: n ، تعداد رئوس.


T (n) = 2 ( n – 1) ( n – 1) Є θ ( n²)

اسلاید 19 :

مجموعه امید بخش
اگر گراف G=(V,E) یک گراف همبند بدون جهت باشد زیر مجموعه F از E را امید بخش می نامند هرگاه بتوان به آن یال هایی اضافه کرد و یک درخت پوشای مینیمم تشکیل داد.
{(5,4),(3,5)}
{(2,4)}
{(0,1),(2,1),(2,3)}

اسلاید 20 :

قضیه
G=(V,E) یک گراف همبند و بدون جهت می باشد. همچنین فرض کنید که F یک زیر مجموعه امید بخش از E است و Y مجموعه رئوس متصل شده توسط یال های موجود در F باشد اگر e یالی با وزن مینیمم باشد که یک راس از Y را به راسی از V-Y متصل می کند آنگاه
F U {e} نیز امید بخش است.