الگوریتم های حریص

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

مثال کوچک:
فرض کنید تعداد نامحدودی سکه با ارزش های مختلف داریم و باید مقدار S را جمع آوری کنیم. بیایید دو مورد خاص را در نظر بگیریم که هر کدام را با یک الگوریتم حریصانه حل خواهیم کرد.
یعنی ما به صورت زیر عمل خواهیم کرد: در هر مرحله یک سکه با بالاترین ارزش (بهترین گزینه در مرحله) می گیریم که از مقدار باقی مانده تجاوز نمی کند.

الف) ارزش سکه ها 1، 5 و 10 و S = 27 باشد.
1) 10 بگیرید، S: 27 -> 17
2) 10 بگیرید، S: 17 -> 7
3) 5، S: 7 -> 2
4) 1، S: 2 -> 1
5) 1، S: 1 -> 0
در نتیجه آنها مقدار پنج سکه را به دست آوردند. شما می توانید بطور مستقل (مثلاً بروت فورس) مطمئن شوید که برای 4 سکه یا کمتر نمی توانید امتیاز 27 را کسب کنید.

ب) اسم سکه ها 1، 5 و 7 و S = 24 باشد.
1) 7 را بگیرید، S: 24 -> 17
2) 7، S: 17 -> 10
3) 7، S: 10 -> 3
4) 1، S: 3 -> 2
5) 1، S: 2 -> 1
6) 1، S: 1 -> 0.
ما با شش سکه امتیاز گرفتیم، اما می‌توانستیم با چهار سکه - دو سکه با ارزش اسمی 7 و دو سکه با ارزش اسمی 5 امتیاز S را کسب کنیم.

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