الگوریتم حریصانه (Greedy)
الگوریتم حریصانه: انتخاب بهینه محلی در هر گام؛ مسئله سکه‌ها و انتخاب فعالیت و اینکه کجا حریصی جواب می‌دهد
الگوریتم حریصانه چیست؟
Greedy Algorithm در هر گام، بهترین انتخاب محلی (فعلی) را می‌کند و هرگز به عقب برنمی‌گردد — امیدوار است سری از انتخاب‌های خوب محلی، به جواب خوب سراسری برسد.
مثال کلاسیک: مسئله سکه‌ها
پرداخت ۳۶۰ تومان با سکه‌های [۲۰۰، ۱۰۰، ۵۰، ۱۰]:
- حریصانه: بزرگ‌ترین سکه ممکن ← ۲۰۰
- باقی ۱۶۰ ← بزرگ‌ترین: ۱۰۰
- باقی ۶۰ ← ۵۰
- باقی ۱۰ ← ۱۰ ✓
جواب: ۴ سکه — بهینه! اما همیشه؟ با سکه‌های [۱، ۳، ۴] برای ۶: حریصانه ۴+۱+۱ = ۳ سکه، اما بهینه ۳+۳ = ۲ سکه است!
کی حریصی جواب بهینه می‌دهد؟
دو ویژگی لازم:
- ویژگی انتخاب حریصانه: انتخاب محلی بهینه، جواب سراسری بهینه را خراب نمی‌کند
- ساختار بهینه: جواب بهینه، زیرمسئله‌های بهینه دارد
اثبات این ویژگی‌ها سخت‌ترین بخش است! (مثلاً در دایکسترا و Kruskal اثبات شده‌اند)
مثال: انتخاب فعالیت
از میان جلسات همپوشان، بیشترین تعداد جلسه را برگزار کن:
- فعالیت‌ها را بر اساس زمان پایان مرتب کن
- اولین را بردار
- هر فعالیت بعدی که بعد از پایان قبلی شروع می‌شود را بردار
این حریصی (انتخاب زودترین پایان) بهینه اثبات شده است!
حریصانه در برابر برنامه‌نویسی پویا
| ویژگی | حریصانه | برنامه‌نویسی پویا |
|---|---|---|
| تصمیم‌ها | قطعی، بدون بازگشت | همه گزینه‌ها بررسی می‌شوند |
| سرعت | سریع (معمولاً O(n log n)) ✓ | کندتر |
| تضمین بهینه | فقط با اثبات ویژگی‌ها | همیشه ✓ |
| مثال | دایکسترا، Kruskal، Huffman | کوله‌پشتی ۰/۱، فیبوناچی |
الگوریتم‌های حریصانه معروف
- دایکسترا: همیشه نزدیک‌ترین رأس (مبحث گراف)
- Kruskal/Prim: سبک‌ترین یال (MST)
- Huffman: فشرده‌سازی با کدهای بهینه
- Kruskal: زمان‌بندی بهینه
هشدار: قبل از اعتماد به حریصی، با مثال نقض امتحان کنید! حریصی بدون اثبات = جواب احتمالاً غلط. کوله‌پشتی ۰/۱ مثال کلاسیک جایی است که حریصی شکست می‌خورد.
جمع‌بندی
- هر گام: بهترین انتخاب محلی، بدون بازگشت
- سریع اما فقط با اثبات ویژگی‌ها بهینه
- قهرمان‌ها: دایکسترا، MST، Huffman، انتخاب فعالیت
- شک حریصی؟ ← مثال نقض بساز یا سراغ DP برو
این مبحث بخشی از دوره آموزش کامل ساختار داده و الگوریتم است.