الگوریتم حریصانه
From Wikipedia, the free encyclopedia
روش حریصانه یا الگوریتم حریصانه (به انگلیسی: Greedy algorithm) یکی از روشهای مشهور و پرکاربرد طراحی الگوریتمها است که با ساختاری ساده در حل بسیاری از مسائل استفاده میشود. این روش اغلب در حل مسائل بهینهسازی به کار میرود و در پارهای مواقع جایگزین مناسبی برای روشهایی مانند برنامهریزی پویا است. در حالت کلی این روش سرعت و مرتبهٔ اجرایی بهتری نسبت به روشهای مشابه خود دارد؛ اما متناسب با مسئله ممکن است به یک جواب بهینهٔ سراسری ختم نشود. این دسته از الگوریتمها در علوم رایانه کاربرد وسیعی دارند.
در روش حریصانه رسیدن به هدف در هر گام مستقل از گام قبلی و بعدی است؛ یعنی در هر مرحله برای رسیدن به هدف نهایی، مستقل از این که در مراحل قبلی چه انتخابهایی صورت گرفته و انتخاب فعلی ممکن است چه انتخابهایی در پی داشته باشد، انتخابی صورت میپذیرد که در ظاهر بهترین انتخاب ممکن است. به همین دلیل است که به این روش، روش حریصانه گفته میشود. بهطور مثال، زمانی که یک دزد عجول و حریص وارد خانهای میشود، در مسیر حرکت خود هر وسیله و کالای با ارزشی را داخل کیسه میاندازد. وی در این حالت چندان توجهی نمیکند که چه اشیایی را قبلاً برداشته و ممکن است در آینده چه اشیاء گرانبهاتری به دست آورد. او در هر گام تنها از بین اشیای دمدست خود باارزشترین آن را انتخاب کرده و به وسایل قبلی اضافه میکند.
این روش کاربردهای عمومی نیز دارد. بهطور مثال زمانی که در مقابل خرید از یک فروشگاه یک اسکناس تحویل فروشنده داده میشود، وی با یک حساب سرانگشتی سعی میکند با حداقل اسکناسها و سکههای ممکن باقیماندهٔ پول را تولید کرده و به خریدار تحویل دهد. این حساب سرانگشتی ممکن است روش حریصانه باشد.
در بسیاری از موارد مسئله بهطور مستقیم یا غیرمستقیم از ما میخواهند که یک متغیر را کمینه یا بیشینه کنیم. در اکثر مسائل اینچنینی ما باید تعدادی انتخاب انجام دهیم و مسئله در تعدادی مرحله حل شود. بازهٔ وسیعی از این مسائل توسط الگوریتمهای حریصانه قابل حل هستند.[1]