آموزش ۰ تا ۱۰۰ الگوریتم حریصانه

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

الگوریتم حریصانه چیست؟

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

مثال ساده: فرض کنید در یک جنگل هستید و می‌خواهید به نزدیک‌ترین درخت برسید. اگر همیشه به نزدیک‌ترین درخت حرکت کنید، این روش مشابه الگوریتم حریصانه است؛ هرچند که تضمین نمی‌کند به بلندترین درخت برسید.

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

1. سادگی و کارآمدی: الگوریتم حریصانه اغلب از پیچیدگی زمانی O(n log n) یا O(n) برخوردار است و به همین دلیل در حل مسائل بزرگ مقیاس بسیار سریع عمل می‌کند.
2. انتخاب مرحله‌ای: این الگوریتم تصمیمات خود را به صورت مرحله‌ای و بدون بازگشت اتخاذ می‌کند.
3. نتایج نزدیک به بهینه: در بسیاری از موارد، نتایج الگوریتم حریصانه به راه‌حل‌های بهینه نزدیک هستند.

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

برای اجرای یک الگوریتم حریصانه، می‌توانید از این مراحل پیروی کنید:

1. تعریف مسئله و معیار بهینگی: ابتدا مشخص کنید که چه چیزی را می‌خواهید بهینه کنید (مثلاً کمینه کردن هزینه یا بیشینه کردن سود).
2. مرتب‌سازی داده‌ها: داده‌ها را بر اساس معیاری مشخص مرتب کنید.
3. انتخاب مرحله‌ای: در هر مرحله، گزینه‌ای را انتخاب کنید که بر اساس معیار بهینگی بهترین است.
4. بررسی شرایط توقف: الگوریتم را تا زمانی ادامه دهید که شرایط مسئله برآورده شوند.

نمونه‌هایی از کاربردهای الگوریتم حریصانه

1. مسئله انتخاب فعالیت‌ها

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

روش حل:

• ابتدا فعالیت‌ها را بر اساس زمان پایان مرتب کنید.
• فعالیت اول را انتخاب کنید.
• هر فعالیت بعدی را بررسی کنید؛ اگر با فعالیت‌های انتخاب‌شده هم‌پوشانی نداشت، آن را اضافه کنید.

مثال کد:

data = {
  "start_time": [2 , 6 , 4 , 10 , 13 , 7],
  "finish_time": [5 , 10 , 8 , 12 , 14 , 15],
  "activity": ["Homework" , "Presentation" , "Term paper" , "Volleyball" , "Lecture" , "Hangout"]
}

sorted_activities = sorted(zip(data["start_time"], data["finish_time"], data["activity"]), key=lambda x: x[1])
selected = [sorted_activities[0]]
for current in sorted_activities[1:]:
    if current[0] >= selected[-1][1]:
        selected.append(current)

print("Selected activities:", [act[2] for act in selected])

2. مسئله کوله‌پشتی کسری

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

روش حل:

• اقلام را بر اساس نسبت ارزش به وزن مرتب کنید.
• اقلام را یکی‌یکی اضافه کنید تا کوله‌پشتی پر شود.
• اگر وزن یک قلم از ظرفیت باقی‌مانده بیشتر باشد، تنها کسری از آن انتخاب می‌شود.

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

1. عدم تضمین بهینگی: در بسیاری از مسائل، الگوریتم حریصانه نمی‌تواند راه‌حل بهینه را تضمین کند. به عنوان مثال، در مسئله فروشنده دوره‌گرد، انتخاب مسیر حریصانه ممکن است بهترین مسیر را ارائه ندهد.
2. عدم انعطاف‌پذیری: این الگوریتم فقط یک‌بار اجرا می‌شود و نمی‌تواند نتایج را بازبینی کند.
3. وابستگی به مسئله: موفقیت الگوریتم حریصانه به نوع مسئله و ساختار آن بستگی دارد.

کاربردهای واقعی الگوریتم حریصانه

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

مزایا

1. سادگی و سرعت: الگوریتم حریصانه بسیار ساده و سریع است و در مسائل بزرگ مقیاس عملکرد خوبی دارد.
2. کاربرد گسترده: این الگوریتم در مسائل مختلفی از جمله شبکه‌های کامپیوتری، فشرده‌سازی داده‌ها و مسیر‌یابی استفاده می‌شود.

صحبت آخر

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

شما تا به حال از الگوریتم حریصانه در کجا استفاده کرده‌اید؟ تجربیات خود را با ما به اشتراک بگذارید یا اگر سوالی دارید، حتماً در بخش نظرات بنویسید!