الگوریتم Greedy (حریصانه) به همراه مثال و تمرین

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

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

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

الگوریتم حریصانه (Greedy Algorithm) یک روش حل مسئله است که در هر مرحله، تصمیمی را براساس اطلاعات فعلی می‌گیرد که به نظر خودش بهترین است، بدون درنظر گرفتن تأثیر تصمیمات آینده. الگوریتم حریصانه همیشه بهترین گزینه را در هر مرحله انتخاب می‌کند، و به همین دلیل باید امیدوار باشیم که این تصمیمات به نتیجه بهینه در مسئله کلی منجر بشوند.

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

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

یک مثال عملی از الگوریتم حریصانه 

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

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

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

•  گنجینه 1: 10 سکه
•  گنجینه 2: 5 سکه
•  گنجینه 3: 8 سکه
•  گنجینه 4: 12 سکه

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

این روند را به صورت مکرر تکرار می‌کنید تا تمام گنجینه‌ها بررسی شوند. در این صورت الگوریتم حریصانه به شما کمک می‌کند تا بیشترین تعداد سکه‌ها را جمع آوری کنید و به نتیجه بهینه برسید.

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

یک مثال دیگر از الگوریتم حریصانه در مسائل

به عنوان یک مثال دیگر، فرض کنید که شما به دنبال راهی برای سفر از یک شهر به شهر دیگر هستید. در این مسئله، هدف شما انتخاب مسیری است که کمترین هزینه را برای سفر داشته باشد. هر شهر با شهرهای دیگر به صورت مستقیم متصل است و هزینه سفر بین هر دو شهر مشخص است.

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

به عنوان مثال، فرض کنید سه شهر A، B و C وجود دارند و هزینه سفر بین آن‌ها به صورت زیر است:

•  هزینه سفر از A به B: 100 واحد
•  هزینه سفر از A به C: 150 واحد
•  هزینه سفر از B به C: 50 واحد

با استفاده از الگوریتم حریصانه، شما در این مرحله شهر B را انتخاب خواهید کرد زیرا هزینه سفر از شهر A به B کمتر است. سپس شما به شهر B می‌رفته و از آنجا باید تصمیم بگیرید که به کدام شهر بروید.

در مرحله بعدی، شما شهر C را انتخاب خواهید کرد چرا که هزینه سفر از شهر B به C کمتر است. با انتخاب شهر C، شما به شهر مقصد خود رسیده‌اید.

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

تفاوت الگوریتم حریصانه با الگوریتم‌های دیگر چیست؟

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

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

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

مزایا و معایب استفاده از الگوریتم حریصانه

به طور کلی، استفاده از الگوریتم حریصانه دارای مزایا و معایب خاصی است. در زیر مزایا و معایب اصلی الگوریتم حریصانه را بیان می‌کنم:

مزایا:

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

معایب:

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

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

چگونه الگوریتم حریصانه را در پایتون پیاده سازی کنیم؟

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

def greedy_algorithm(problem):

    # متغیرهای لازم را مقداردهی اولیه کنید

    solution = []  # جواب نهایی

    # دسته‌های مورد نظر را بر اساس معیار حریصانه انتخاب کنید

    while problem_is_not_solved:  # تا زمانی که مسئله حل نشده است

        item = select_next_item(problem)  # انتخاب بعدی به صورت حریصانه

        if is_feasible(item, solution):  # بررسی صحت قیدها با جواب فعلی

            solution.append(item)  # اضافه کردن آیتم به جواب نهایی

            update_problem(item, problem)  # به روزرسانی مسئله بر اساس آیتم انتخاب شده

    return solution

در اینجا problem ورودی مسئله است که شامل اطلاعات و شرایط مسئله است. شما باید توابع select_next_item، is_feasible و update_problem را بر اساس نیازهای خاص مسئله پیاده‌سازی کنید.

تابع select_next_item بر اساس معیار حریصانه، بعدی را انتخاب می‌کند. تابع is_feasible  بررسی می‌کند که آیا انتخاب فعلی با جواب نهایی قابل قبول است یا خیر. در نهایت، تابع update_problem مسئله را بر اساس آیتم انتخاب شده به روزرسانی می‌کند.

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

def select_next_item(problem):

    # انتخاب کوچکترین عنصر

    return min(problem)

def is_feasible(item, solution):

    # همیشه قابل قبول است

    return True

def update_problem(item, problem):

    # حذف آیتم از مسئله

    problem.remove(item)

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