الگوریتم Greedy در برنامه‌نویسی چیست؟ + مزایا و معایب و کاربردهای آن

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

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

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

الگوریتم Greedy چیست؟

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

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

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

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

1. الگوریتم Minimal Spanning Tree (MST)
2. الگوریتم کوتاه‌ترین مسیر داکسترا (DIJKSTRA)
3. بهینه‌سازی انتخاب فعالیت (ACTIVE SELECTION PROBLEM)
4. کدگذاری هافمن (برای فشرده سازی داده ها بدون خرابی و آسیب استفاده می شود.)
5. پروتکل مسیریابی از طریق میانبرها (OSPF)

خصوصیات کلی الگوریتم Greedy

1. الگوریتم Greedy شامل یک زنجیره از تصمیم‌هایی است که باید در هر مرحله بدون در نظرگرفتن مرحله بعد اجرا شود. بنابراین در هر مرحله امکان بازگشت و تعویض انتخاب وجود ندارد.
2. این الگوریتم، لزوما همیشه بهترین نتیجه را ندارد و گاهی حتی ممکن است نتایج حاصل از عملکرد گریدی بدترین نتیجه ممکن باشند.
3. الگوریتم گریدی نسبت به سایر الگوریتم‌های مشابه مانند الگوریتم پویا سرعت عمل بالاتری دارد. در واقع الگوریتم‌هایی مانند الگوریتم پویا، باید تمامی گزینه‌های موجود را بررسی کنند، درصورتی که الگوریتم گریدی تنها یک گزینه را برای انتخاب بهینه‌ترین حالت در نظر می‌گیرد.
4. گاهی ممکن است الگوریتم گریدی به راه حلی برسد که تنها نزدیک به بهینه‌ترین راه‌حل است و در واقع جواب نهایی مطلوب ما نمی‌باشد.
5. الگوریتم گریدی برای بسیاری از مسائل قابل استفاده است که بسیاری از آن‌ها در زندگی واقعی کاربرد دارند؛ مانند برنامه‌ریزی برای چندین رویداد یا مسیریابی از سریع‌ترین مسیر.

ساختار الگوریتم Greedy

ساختار کلی این الگوریتم به این صورت است که متغیر S یا Solution خروجی کد است که در ابتدا خالی است. متغیر C یک مجموعه از ورودی‌هاست که توسط select انتخاب شده و سپس از مجموعه C حذف می‌شوند. تابع امکان پذیری یا feasible وظیفه بررسی ورودی‌های C را دارد. اگر با تأیید feasible امکان اضافه شدن توابع وجود داشته باشد، خروجی یا همان S به دست می‌آید. اما اگر رد شود، الگوریتم همان نقطه متوقف می‌شود.

چه مسائلی مناسب الگوریتم Greedy هستند؟

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

1- مسئله باید دارای خاصیت حریصانه باشد.

باید در هر مرحله از کار با الگوریتم گریدی، گزینه‌ای وجود داشته باشد تا الگوریتم آن را به دیگر گزینه‌ها ترجیح دهد. به طور مثال فکر کنید چند کیسه پول دارید که در هر کدام اسکناس‌های 50 تومانی 10 تومانی و 2 تومانی وجود داشته باشد. حال اگر بخواهید 62 تومان برداشت کنید؛ می‌توانید با استفاده از فرمول زیر از الگوریتم گریدی کمک بگیرید:

62−>[−50]12−>[−10]2−>[−2]0

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

2- این مسئله باید دارای زیرساخت بهینه باشد

بهتر است پاسخ مسئله موردنظر به کمک الگوریتم Greedy قابل حل باشد. برای درک بهتر این نکته به مثال قبلی برمی‌گردیم. گفته شد که در مرحله نخست، الگوریتم گریدی برای ما باارزش‌ترین جواب یعنی اسکناس 50 تومانی را انتخاب کرد. حال می‌توان جواب مسئله قبلی را در معادله Y=X-50=12 قرار داد که از معادله عدد 12 به دست می‌آید. گزینه‌های انتخابی در این مرحله اسکناس 10 و 2 دلاری است. حالا اگر انتخاب‌های حریصانه این مرحله را باهم ترکیب کنیم معادله زیر به دست می‌آید.

{50,10,2} ={10,2} ∪ {50}

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

اصطلاحات کلیدی استفاده شده در الگوریتم Greedy

برخی از اصطلاحات به صورت کلی با الگوریتم Greedy شناخته می‌شوند. در همین راستا از بین رایج‌ترین اصطلاحات می‌توان به موارد زیر اشاره کرد:

تابع هدف

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

مجموعه کاندیدها

متغیرهای ورودی تابع هدف در الگوریتم گریدی که در مثال ما اسکناس های 50، 10 و 2 تومانی بودند، به عنوان مجموع کاندیدها معرفی می‌شوند.

تابع انتخاب

انتخاب عنصر بعدی در الگوریتم، به عهده تابع انتخاب یا همان select است. به طور مثال در مرحله نخست، ما اسکناس 50 تومانی را با معیاری حریصانه انتخاب کردیم که کدنویسی آن به صورت زیر قابل نمایش است. این تابع یکی از شروط انتخاب مورد حداکثر یا بهینه در هر مرحله است.

INT SELECT(candidate_set C)

return max_element(C)

تابع امکان‌سنجی

فرض کنید در مجموع کاندیداها، اسکناس 20 تومانی هم وجود داشت. در مرحله اول، اسکناس 50 تومانی انتخاب شده و به مرحله بعد می‌رویم. در این مرحله طبق روال الگوریتم گریدی، باید گزینه‌ای که بیشترین ارزش را دارد یعنی اسکناس 20 تومانی رو انتخاب کنیم؛ اما جمع 50 با 20 برابر با 70 می‌شود که از جواب مطلوب ما که عدد  62 است، بیشتر خواهد شد. کار تابع امکان‌سنجی در این مرحله، بررسی ورودی‌ها و سنجش امکان استفاده از آن‌هاست. اگر تابعی، از جواب مطلوب بزرگ‌تر باشد، تابع امکان‌سنجی آن را حذف کرده و به سراغ متغیر بعدی می‌رود.

مزایای الگوریتم Greedy

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

معایب الگوریتم Greedy

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

الگوریتم گریدی در یک نگاه

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

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

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