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

بدون خلاصه ویرایش
روش اثبات به این صورت است که دنباله تصمیمات اتخاذ شده در هر مرحله را در نظر گرفته، دنباله‌ای بهینه پیدا کرده که با دنباله ساخته شده یکسان باشد(منظور از دنباله بهینه، دنباله‌ای از کار‌هاست که جواب بهینه را به ما می‌دهد). برای پیدا کردن دنباله، ابتدا یک دنباله بهینه را درنظر گرفته، در هر مرحله یک دنباله شبیه‌تر به دنباله خودمان پیدا می‌کنیم که بهینه باشد و سرانجام دنباله‌ای که پیدا کردیم با دنباله ما یکسان می‌شود.
 
میزان شباهت دنباله E=e1, e2,..., enEen E = e_1,\ e_2,...,\ e_nE=e1​, e2​,..., en​ و F=f1, f2,..., fmFfm 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 عضو اول ابتدای هر دو دنباله با هم یکسان باشد.
 
== محدودیت‌های الگوریتم حریصانه: ==
 
چون روش این الگوریتم گرفتن بهترین تصمیم در هر مرحله است، در بسیاری از موارد به راه‌حل بهینه سراسری ختم نمی‌شود. عمده مسائلی که این الگوریتم به جواب درست منتج نمی‌شود، مسائل مربوط به گراف‌های وزن‌دار است؛ مثل [[مسئله فروشنده دوره‌گرد]] یا پیدا کردن بزرگ‌ترین مسیر در گراف وزن‌دار.
۲۷

ویرایش