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

روش اثبات به این صورت است که دنباله تصمیمات اتخاذ شده در هر مرحله را در نظر گرفته، دنباله‌ای بهینه پیدا کرده که با دنباله ساخته شده یکسان باشد(منظور از دنباله بهینه، دنباله‌ای از کار‌هاست که جواب بهینه را به ما می‌دهد). برای پیدا کردن دنباله، ابتدا یک دنباله بهینه را درنظر گرفته، در هر مرحله یک دنباله شبیه‌تر به دنباله خودمان پیدا می‌کنیم که بهینه باشد و سرانجام دنباله‌ای که پیدا کردیم با دنباله ما یکسان می‌شود.

 

 

درواقع شباهت دو دنباله بزرگ‌ترین عددی مثل xxx است که xxx عضو اول ابتدای هر دو دنباله با هم یکسان باشد.

 

 

چون روش این الگوریتم گرفتن بهترین تصمیم در هر مرحله است، در بسیاری از موارد به راه‌حل بهینه سراسری ختم نمی‌شود. عمده مسائلی که این الگوریتم به جواب درست منتج نمی‌شود، مسائل مربوط به گراف‌های وزن‌دار است؛ مثل [[مسئله فروشنده دوره‌گرد]] یا پیدا کردن بزرگ‌ترین مسیر در گراف وزن‌دار.