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

پرش به ناوبری پرش به جستجو
بدون خلاصه ویرایش
روش اثبات به این صورت است که دنباله تصمیمات اتخاذ شده در هر مرحله را در نظر گرفته، دنباله‌ای بهینه پیدا کرده که با دنباله ساخته شده یکسان باشد(منظور از دنباله بهینه، دنباله‌ای از کار‌هاست که جواب بهینه را به ما می‌دهد). برای پیدا کردن دنباله، ابتدا یک دنباله بهینه را درنظر گرفته، در هر مرحله یک دنباله شبیه‌تر به دنباله خودمان پیدا می‌کنیم که بهینه باشد و سرانجام دنباله‌ای که پیدا کردیم با دنباله ما یکسان می‌شود.
 
میزان شباهت دنباله <math> E = e_1,\ e_2,...,\ e_n​ </math> و F=f1, f2,..., fm F = 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 عضو اول ابتدای هر دو دنباله با هم یکسان باشد.
۲۷

ویرایش

منوی ناوبری