المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


آموزش:الگوریتم:الگوریتم‌های حریصانه

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

تعریف

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

ویژگی‌ها

الگوریتم‌های حریصانه همیشه گزینه‌ای را انتخاب می‌کنند که در آن لحظه به نظر بهترین می‌آید، یعنی انتخاب های بهینه‌ی محلی (نسبی) انجام می‌دهند تا در انتها به یک جواب بهینه‌ برای مسئله برسند. پس می‌توان انتظار داشت این الگوریتم‌ها همواره به جواب بهینه ختم نشوند، برای مثال در مسئله‌ی خرد کردن پول روش حریصانه برای مجموعه سکه‌های $\{1,3,4\}$ و $6$ واحد پول جواب غیر بهینه را می‌دهد.

6=4+1+1  (Greedy)
6=3+3    (Optimal)

اما در بسیاری از مسائل برای مثال در مسئله‌ی زمانبندی پردازه‌ها ثابت می‌شود جواب همواره بهینه است.

کابردها

الگوریتم‌های حریصانه معمولا سریع هستند و پیاده سازی راحتی دارند.گر چه در بعضی از مسائل جواب نسبی به دست آمده توسط این الگوریتم ها با جواب بهینه تفاوت دارد، اما گاهی حتی در چنین مسائلی (به خصوص مسائلی با پیچیدگی بالا و یا NP) جواب به دست آمده تخمین خوبی از جواب واقعی است.

مثال: الگوریتمی ارائه دهید که در گراف ساده‌ی G یک تطابق با اندازه‌ی بیشتر از نصف تطابق بیشینه بیابد.

پاسخ

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

مسائل نمونه

مراجع


ابزار صفحه