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

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

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

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

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

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

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

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

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

بررسی مثالی برای درک بهتر

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

فرض کنیم در فروشگاه، سه نوع کالا وجود دارد، لپ تاپ، پاور بانک، اسپیکر.

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

جمع بندی

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

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

خیلی ممنون از اینکه وقت گذاشتید و این مقاله رو مطالعه کردید، ممنون میشم نظرتون رو بهم بگید.