تفاوت میان نسخه‌های «الگوریتم حریصانه»

بدون خلاصه ویرایش
return ∅;
}</source><br />
== روش اثبات درستی ==
هرچند روش یکتایی برای اثبات درستی الگوریتم حریصانه وجود ندارد ولی روش زیر در خیلی از مواقع الگوریتم را اثبات می‌کند.
روش اثبات به این صورت است که دنباله تصمیمات اتخاذ شده در هر مرحله را در نظر گرفته، دنباله‌ای بهینه پیدا کرده که با دنباله ساخته شده یکسان باشد(منظور از دنباله بهینه، دنباله‌ای از کار‌هاست که جواب بهینه را به ما می‌دهد). برای پیدا کردن دنباله، ابتدا یک دنباله بهینه را درنظر گرفته، در هر مرحله یک دنباله شبیه‌تر به دنباله خودمان پیدا می‌کنیم که بهینه باشد و سرانجام دنباله‌ای که پیدا کردیم با دنباله ما یکسان می‌شود.
 
میزان شباهت دنباله E=e1, e2,..., enE = e_1,\ e_2,...,\ e_nE=e1​, e2​,..., en​ و F=f1, f2,..., fmF = f_1,\ f_2,...,\ f_mF=f1​, f2​,..., fm​ را بزرگ‌ترین اندیسی مثل xxx در نظر می‌گیریم که ∀y≤x:ey=fy\forall_{y \le x} : e_y =f_y∀y≤x​:ey​=fy​
 
درواقع شباهت دو دنباله بزرگ‌ترین عددی مثل xxx است که xxx عضو اول ابتدای هر دو دنباله با هم یکسان باشد.
 
== محدودیت‌های الگوریتم حریصانه: ==
۲۷

ویرایش