ناب لرنینگ |
بزرگترین بانک اطلاعاتی پروژه های دانشجویی روش حریصانه (Greedy) یکی از روش‌های مشهور و پرکاربرد طراحی الگوریتم‌ها است که با ساختاری ساده در حل بسیاری از مسائل استفاده می‌شود. این روش اغلب در حل مسائل بهینه‌سازی استفاده شده و در پاره‌ای مواقع جایگزین مناسبی برای روش‌هایی مانند برنامه‌ریزی پویا است. در حالت کلی این روش سرعت و مرتبه‌ی اجرایی بهتری نسبت به روش‌های مشابه خود دارد؛ اما متناسب با مسئله ممکن است به یک جواب بهینه‌ی سراسری ختم نشود.
در روش حریصانه رسیدن به هدف در هر گام مستقل از گام قبلی و بعدی است. یعنی در هر مرحله برای رسیدن به هدف نهایی، مستقل از این که در مراحل قبلی چه انتخاب‌هایی صورت گرفته و انتخاب فعلی ممکن است چه انتخاب‌هایی در پی داشته باشد، انتخابی که در ظاهر بهترین انتخاب ممکن است صورت می‌پذیرد. به همین دلیل است که به این روش، روش حریصانه گفته می‌شود. زمانی که یک دزد عجول و حریص وارد خانه‌ای می‌شود، در مسیر حرکت خود هر وسیله و کالای با ارزشی را داخل کیسه می‌اندازد. وی در این حالت چندان توجهی نمی‌کند که چه اشیائی را قبلا برداشته و ممکن است در آینده چه اشیاء گرانبهاتری به دست آورد. او در هر گام تنها از بین اشیاء دم دست خود با ارزشترین آن را انتخاب کرده و به وسایل قبلی اضافه میکند.
این روش کاربردهای عمومی دیگری نیز دارد. زمانی که در مقابل خرید از یک فروشگاه یک اسکناس تحویل فروشنده داده می‌شود، وی با یک حساب سرانگشتی سعی میکند با حداقل اسکناس‌ها و سکه‌های ممکن باقیمانده‌ی پول را تولید کرده و به خریدار تحویل دهد. این حساب سرانگشتی ممکن است روش حریصانه باشد.
تاریخچه
نام این روش از شخصیت معروف اسکروج گرفته شده‌است. یکی از تفریحات و انگیزه‌های اسکروج، به دست آوردن پول بیشتر بود؛ الگوریتم حریصانه (Greedy) نیز مانند شیوه اسکروج می‌باشد؛ مثلاً فرض کنید اسکروج در یک مسابقه شرکت کرده‌است و باید در مرحله اول مسابقه یک درب را انتخاب کند، به ازای انتخاب هر درب فقط می‌تواند درب‌های بعد آن را باز کند و پول دریافت کند:
در مرحله اول باید بین دو درب، اولی پنج سکه و دومی دو سکه، انتخاب کند؛ چون او حریص است بهترین انتخاب را در لحظه انتخاب درب اول می‌داند.
در مرحله دوم درب بعد از درب اول دارای سه سکه است و او با هشت سکه خارج می‌شود؛ حال درب بعد از درب دوم را بررسی می‌کنیم؛ ممکن است دارای یک سکه باشد که در این صورت انتخاب حریصانه اسکروج بهینه بوده است یا ممکن است ده سکه باشد که در این صورت نشان می‌دهد که انتخاب بهینه در هر مرحله لزوماً منجر به سود بیشینه نمی‌شود.
ساختار روش حریصانه
کلیت روش حریصانه در هر مرحله، انتخاب یک عنصر از عناصر موجود است. این عنصر قسمتی از جواب مسئله است که به مجموعه عناصر نهایی اضافه می‌شود. در طی این مسیر گام‌های زیر اتفاق می‌افتد:
1- روال انتخاب حریصانه: در این گام یک عنصر برای اضافه شدن به مجموعه جواب انتخاب می‌شود. معیار یا روال انتخاب عنصر برای اضافه شدن، ارزش آن عنصر است. بستگی به نوع مسئله هر عنصر ارزشی دارد که با ارزشترین آنها انتخاب می‌شود.
2- امکان‌سنجی و افزودن: پس از انتخاب یک عنصر به صورت حریصانه، باید بررسی شود که آیا امکان اضافه کردن آن به مجموعه جواب‌های قبلی وجود دارد یا نه. گاهی اضافه شدن عنصر یکی از شرایط اولیه‌ی مسئله را نقض میکند که باید به آن توجه نمود. اگر اضافه کردن این عنصر هیچ شرطی را نقض نکند، عنصر اضافه خواهد شد؛ وگرنه کنار گذاشته شده و بر اساس گام اول عنصر دیگری برای اضافه شدن انتخاب می‌شود. اگر گزینه‌ی دیگری برای انتخاب وجود نداشته باشد، اجرای الگوریتم به اتمام می‌رسد.
3- بررسی اتمام الگوریتم: در هر مرحله پس از اتمام گام 2 و اضافه شدن یک عنصر جدید به مجموعه جواب، باید بررسی کنیم که آیا به یک جواب مطلوب رسیده‌ایم یا نه؟ اگر نرسیده باشیم به گام اول رفته و چرخه را در مراحل بعدی ادامه می‌دهیم.
به زبان ساده، در روش حریصانه طی هر مرحله یک عنصر به روش حریصانه به مجموعه جواب اضافه شده، شرط محدودیت‌ها بررسی شده و در صورت نبود مشکل، عنصر و عناصر بعدی به همین ترتیب به مجموعه جواب اضافه می‌شوند. در طی این گام‌ها اگر به یک شرط نهایی خاص برسیم، یا امکان انتخاب عنصر دیگری برای اضافه کردن به مجموعه جواب وجود نداشته باشد، الگوریتم پایان یافته و مجموعه جواب به دست آمده به عنوان جواب بهینه ارائه می‌شود. توجه داشته باشید که ممکن است بر اساس نوع مسئله، ترتیب اضافه شدن عناصر به مجموعه جواب اهمیت داشته باشد.
مسئله‌ی خرد کردن پول (تولید پول)
مسئله‌ی خرد کردن پول از جمله مسائل کلاسیک طراحی الگوریتم‌ها است که مثال مناسبی برای شیوه‌ی عملکرد روش حریصانه است. هدف از این مسئله، تهیه کردن میزان مشخصی پول با حداقل استفاده از اسکناس‌ها و سکه‌های موجود است.
اگر از فروشگاهی 14 هزار تومان خرید کرده و یک اسکناس 50 هزار تومانی تحویل فروشنده دهید، فروشنده باید مبلغ 36 هزار تومان به شما بازگرداند. برای این کار روش‌های مختلفی وجود دارد. وی می‌تواند 36 اسکناس هزار تومانی یا 18 اسکناس دو هزار تومانی به شما بازگرداند؛ یا حتی 72 اسکناس 500 تومانی! به همین ترتیب ترکیبات مختلفی از اسکناس‌ها وجود دارد که مبلغ 36 هزار تومان را تولید می‌کنند. در نهایت معمولا سه اسکناس ده هزار تومانی، یک اسکناس پنج هزار تومانی و یک اسکناس هزار تومانی چیزی است که شما از فروشنده دریافت می‌کنید. البته ممکن است فروشنده به دلیل نداشتن اسکناس هزار تومانی از دو اسکناس 500 تومانی استفاده کند. ولی در حال حاضر فرض بر این است که از همه‌ی اسکناس‌ها به اندازه‌ی کافی موجود است.
فروشنده چگونه پرداخت این اسکناس‌ها را محاسبه میکند؟ پر ارزشترین اسکناس‌های موجود پنجاه هزار تومان ارزش دارند که برای مبلغ 36 هزار تومان مناسب نیستند. پس آن اسکناس‌ها کنار گذاشته می‌شوند. در مرحله‌ی بعد اسکناس ده هزار تومانی بررسی می‌شود. چون ده هزار کوچکتر از 36 هزار است، یک اسکناس ده هزار تومانی انتخاب شده و برای پرداخت به مشتری کنار گذاشته می‌شود. در ادامه مبلغ 26 هزار تومان باقیمانده است که باز هم می‌توان از اسکناس ده هزار تومانی استفاده کرد. پس فروشنده دو بار متوالی دیگر دو اسکناس ده هزار تومانی کنار می‌گذارد. به این ترتیب شش هزار تومان باقی می‌ماند که از ده هزار تومان کمتر است. پس انتخاب مجدد اسکناس ده هزار تومانی راه به جایی نمی‌برد و باید سراغ مبالغ کوچکتر رفت. اسکناس پنج هزار تومانی گزینه‌ی بعدی است و امکان انتخاب دارد. پس یک اسکناس از این نوع نیز انتخاب شده و تنها هزار تومان باقی می‌ماند. در این حالت اسکناس پنج هزار تومانی بزرگتر از مبلغ مورد نیاز است. پس انتخاب مجدد آن کنار گذاشته می‌شود. اسکناس بعدی دو هزار تومانی است که آن هم بزرگتر از هزار تومان است. از این اسکناس نیز صرف نظر کرده و نوبت به اسکناس بعدی با ارزش هزار تومان می‌رسد. در نهایت با یک اسکناس هزار تومانی مبلغ باقیمانده صفر شده و کل مبلغ مشتری آماده‌ی پرداخت است.
کاربردهای روش حریصانه
1– مسئله‌ی کوله‌پشتی کسری: در این مسئله هدف پر کردن یک کوله‌پشتی از وسایل پر ارزشی است که وزن‌های مختلفی دارند. این کوله‌پشتی باید به نحوی پر شود که وزن بار آن از حد مجاز بیشتر نشده و ارزش وسایل داخل آن بیشینه باشد. در مسئله‌ی کوله‌پشتی کسری بر خلاف کوله‌پشتی صفر و یک این امکان وجود دارد که بتوان کسری از یک وسیله – مثل پارچه – را جدا کرده و به وسایل داخل کوله‌پشتی اضافه کرد.
2- تولید درخت پوشای کمینه: روش‌های پریم و کروسکال دو روش مشهور تولید درخت پوشای کمینه از یک گراف وزن‌دار هستند که از روش حریصانه بهره می‌برند. منظور از درخت پوشای کمینه، درخت پوشایی از گراف است که مجموع وزن یال‌های آن کمتر یا مساوی مجموع وزن یال‌های سایر درخت‌های پوشای آن گراف است.
3- محاسبه‌ی کوتاهترین مسیرهای تک‌مبدأ: زمانی که قصد داریم کوتاهترین مسیر از یک مبدأ مشخص به تمامی رئوس دیگر گراف را محاسبه کنیم، الگوریتمی مانند دایکسترا (دیکسترا، دایجسترا) با استفاده از روش حریصانه به کمک ما می‌آید.
4- کدگذاری و فشرده‌سازی اطلاعات: کد هافمن یکی از روش‌های فشرده‌سازی اطلاعات است با کدگذاری مجدد کاراکترهای موجود در اطلاعات بر اساس میزان استفاده‌ی آنها، سعی در کم کردن حجم فایل میکند. بر اساس این روش، کاراکتری با استفاده‌ی بالا با کد کوتاهتر و کاراکتری با استفاده‌ی کم با کد طولانی‌تر جایگزین می‌شود.
