روش حریصانه (Greedy) یکی از روش‌های مشهور و پرکاربرد طراحی الگوریتم‌ها است که با ساختاری ساده در حل بسیاری از مسائل استفاده می‌شود. این روش اغلب در حل مسائل بهینه‌سازی استفاده شده و در پاره‌ای مواقع جایگزین مناسبی برای روش‌هایی مانند برنامه‌ریزی پویا است. در حالت کلی این روش سرعت و مرتبه اجرایی بهتری نسبت به روش‌های مشابه خود دارد؛ اما متناسب با مسئله ممکن است به یک جواب بهینه سراسری ختم نشود.
در روش حریصانه رسیدن به هدف در هر گام مستقل از گام قبلی و بعدی است. یعنی در هر مرحله برای رسیدن به هدف نهایی، مستقل از این که در مراحل قبلی چه انتخاب‌هایی صورت گرفته و انتخاب فعلی ممکن است چه انتخاب‌هایی در پی داشته باشد، انتخابی که در ظاهر بهترین انتخاب ممکن است صورت می‌پذیرد. به همین دلیل است که به این روش، روش حریصانه گفته می‌شود. زمانی که یک دزد عجول و حریص وارد خانه‌ای می‌شود، در مسیر حرکت خود هر وسیله و کالای با ارزشی را داخل کیسه می‌اندازد. وی در این حالت چندان توجهی نمی‌کند که چه اشیائی را قبلا برداشته و ممکن است در آینده چه اشیاء گرانبهاتری به دست آورد. او در هر گام تنها از بین اشیاء دم دست خود با ارزشترین آن را انتخاب کرده و به وسایل قبلی اضافه میکند.
این روش کاربردهای عمومی دیگری نیز دارد. زمانی که در مقابل خرید از یک فروشگاه یک اسکناس تحویل فروشنده داده می‌شود، وی با یک حساب سرانگشتی سعی میکند با حداقل اسکناس‌ها و سکه‌های ممکن باقیمانده پول را تولید کرده و به خریدار تحویل دهد. این حساب سرانگشتی ممکن است روش حریصانه باشد.
ساختار روش حریصانه
[برگرد بالا]
کلیت روش حریصانه در هر مرحله، انتخاب یک عنصر از عناصر موجود است. این عنصر قسمتی از جواب مسئله است که به مجموعه عناصر نهایی اضافه می‌شود. در طی این مسیر گام‌های زیر اتفاق می‌افتد:
1- روال انتخاب حریصانه: در این گام یک عنصر برای اضافه شدن به مجموعه جواب انتخاب می‌شود. معیار یا روال انتخاب عنصر برای اضافه شدن، ارزش آن عنصر است. بستگی به نوع مسئله هر عنصر ارزشی دارد که با ارزشترین آنها انتخاب می‌شود.
2- امکان‌سنجی و افزودن: پس از انتخاب یک عنصر به صورت حریصانه، باید بررسی شود که آیا امکان اضافه کردن آن به مجموعه جواب‌های قبلی وجود دارد یا نه. گاهی اضافه شدن عنصر یکی از شرایط اولیه مسئله را نقض میکند که باید به آن توجه نمود. اگر اضافه کردن این عنصر هیچ شرطی را نقض نکند، عنصر اضافه خواهد شد؛ وگرنه کنار گذاشته شده و بر اساس گام اول عنصر دیگری برای اضافه شدن انتخاب می‌شود. اگر گزینه دیگری برای انتخاب وجود نداشته باشد، اجرای الگوریتم به اتمام می‌رسد.
3- بررسی اتمام الگوریتم: در هر مرحله پس از اتمام گام 2 و اضافه شدن یک عنصر جدید به مجموعه جواب، باید بررسی کنیم که آیا به یک جواب مطلوب رسیده‌ایم یا نه؟ اگر نرسیده باشیم به گام اول رفته و چرخه را در مراحل بعدی ادامه می‌دهیم.
به زبان ساده، در روش حریصانه طی هر مرحله یک عنصر به روش حریصانه به مجموعه جواب اضافه شده، شرط محدودیت‌ها بررسی شده و در صورت نبود مشکل، عنصر و عناصر بعدی به همین ترتیب به مجموعه جواب اضافه می‌شوند. در طی این گام‌ها اگر به یک شرط نهایی خاص برسیم، یا امکان انتخاب عنصر دیگری برای اضافه کردن به مجموعه جواب وجود نداشته باشد، الگوریتم پایان یافته و مجموعه جواب به دست آمده به عنوان جواب بهینه ارائه می‌شود. توجه داشته باشید که ممکن است بر اساس نوع مسئله، ترتیب اضافه شدن عناصر به مجموعه جواب اهمیت داشته باشد.
مسئله خرد کردن پول (تولید پول)
[برگرد بالا]
مسئله خرد کردن پول از جمله مسائل کلاسیک طراحی الگوریتم‌ها است که مثال مناسبی برای شیوه عملکرد روش حریصانه است. هدف از این مسئله، تهیه کردن میزان مشخصی پول با حداقل استفاده از اسکناس‌ها و سکه‌های موجود است.
اگر از فروشگاهی 14 هزار تومان خرید کرده و یک اسکناس 50 هزار تومانی تحویل فروشنده دهید، فروشنده باید مبلغ 36 هزار تومان به شما بازگرداند. برای این کار روش‌های مختلفی وجود دارد. وی می‌تواند 36 اسکناس هزار تومانی یا 18 اسکناس دو هزار تومانی به شما بازگرداند؛ یا حتی 72 اسکناس 500 تومانی! به همین ترتیب ترکیبات مختلفی از اسکناس‌ها وجود دارد که مبلغ 36 هزار تومان را تولید می‌کنند. در نهایت معمولا سه اسکناس ده هزار تومانی، یک اسکناس پنج هزار تومانی و یک اسکناس هزار تومانی چیزی است که شما از فروشنده دریافت می‌کنید. البته ممکن است فروشنده به دلیل نداشتن اسکناس هزار تومانی از دو اسکناس 500 تومانی استفاده کند. ولی در حال حاضر فرض بر این است که از همه اسکناس‌ها به اندازه کافی موجود است.
فروشنده چگونه پرداخت این اسکناس‌ها را محاسبه میکند؟ پر ارزشترین اسکناس‌های موجود پنجاه هزار تومان ارزش دارند که برای مبلغ 36 هزار تومان مناسب نیستند. پس آن اسکناس‌ها کنار گذاشته می‌شوند. در مرحله بعد اسکناس ده هزار تومانی بررسی می‌شود. چون ده هزار کوچکتر از 36 هزار است، یک اسکناس ده هزار تومانی انتخاب شده و برای پرداخت به مشتری کنار گذاشته می‌شود. در ادامه مبلغ 26 هزار تومان باقیمانده است که باز هم می‌توان از اسکناس ده هزار تومانی استفاده کرد. پس فروشنده دو بار متوالی دیگر دو اسکناس ده هزار تومانی کنار می‌گذارد. به این ترتیب شش هزار تومان باقی می‌ماند که از ده هزار تومان کمتر است. پس انتخاب مجدد اسکناس ده هزار تومانی راه به جایی نمی‌برد و باید سراغ مبالغ کوچکتر رفت. اسکناس پنج هزار تومانی گزینه بعدی است و امکان انتخاب دارد. پس یک اسکناس از این نوع نیز انتخاب شده و تنها هزار تومان باقی می‌ماند. در این حالت اسکناس پنج هزار تومانی بزرگتر از مبلغ مورد نیاز است. پس انتخاب مجدد آن کنار گذاشته می‌شود. اسکناس بعدی دو هزار تومانی است که آن هم بزرگتر از هزار تومان است. از این اسکناس نیز صرف نظر کرده و نوبت به اسکناس بعدی با ارزش هزار تومان می‌رسد. در نهایت با یک اسکناس هزار تومانی مبلغ باقیمانده صفر شده و کل مبلغ مشتری آماده پرداخت است.
پیاده‌سازی مسئله خرد کردن پول به روش حریصانه
[برگرد بالا]
تابع زیر یک پیاده‌سازی از الگوریتم شرح داده شده به زبان برنامه‌نویسی ++C است:
int ChangeCoin(int Coins[], int Amount, int Result[]){
int i = 0, Count = 0, j = 0;
while(Coins[i] != -1 && Amount > 0){
if(Amount >= Coins[i]){
Amount -= Coins[i];
Result[j++] = Coins[i];
Count++;
}
else
i++;
}
if(Amount != 0)
return -1;
return Count;
}
در این تابع، Coins ارزش سکه‌ها و اسکناس‌های موجود و Amount مقدار مورد نیاز برای تولید را مشخص می‌کنند. پاسخ نهایی در آرایه Result قرار گرفته و تعداد آنها با متغیر Count به محل فراخوانی بازگشت داده می‌شود. فرض شده است انتهای لیست سکه‌ها و اسکناس‌ها با عدد 1- مشخص شده و به ترتیب نزولی مرتب هستند. یعنی عنصر اول بزرگترین اسکناس موجود است.
اگر ارزش سکه‌ها به گونه‌ای باشد که نتوان مقدار خاصی را تولید کرد، عدد 1- به عنوان تعداد سکه‌ها و اسکناس‌های یافت شده بازگردانده می‌شود. این حالت زمانی اتفاق می‌افتد که سکه یا اسکناس با ارزش یک واحد موجود نباشد. در غیر اینصورت هر مبلغی را حداقل با استفاده از همین سکه‌ها و اسکناس‌های یک واحدی می‌توان تولید کرد. مقدار بازگشتی تابع زمانی صفر می‌شود که مقدار Amount از همان ابتدا صفر بوده باشد.
اگرچه این روش عملکردی ساده دارد، اما همواره به جواب بهینه ختم نمیشود. مثلا اگر سکه‌هایی با ارزش 1، 7 و 10 واحد پول موجود بوده و هدف تولید مبلغی با ارزش 14 واحد باشد، بر اساس این روش ابتدا یک سکه با ارزش 10 واحد انتخاب می‌شود. برای 4 واحد باقیمانده چاره‌ای نیست جز اینکه چهار سکه یک واحدی انتخاب شود. پس در کل 5 سکه برای تولید 14 واحد انتخاب شد. این در حالی است که می‌شد تنها با انتخاب دو سکه 7 واحدی همان مبلغ را تولید کرد.
برای این مسئله الگوریتم دیگری با استفاده از روش برنامه‌نویسی پویا ارائه شده است که همواره به یک جواب بهینه - در صورت وجود - می‌رسد.
کاربردهای روش حریصانه
[برگرد بالا]
از جمله کاربردهای مشهور روش حریصانه مسائلی هستند که در ادامه معرفی می‌شوند.
1- مسئله کوله‌پشتی کسری: در این مسئله هدف پر کردن یک کوله‌پشتی از وسایل پر ارزشی است که وزن‌های مختلفی دارند. این کوله‌پشتی باید به نحوی پر شود که وزن بار آن از حد مجاز بیشتر نشده و ارزش وسایل داخل آن بیشینه باشد. در مسئله کوله‌پشتی کسری بر خلاف کوله‌پشتی صفر و یک این امکان وجود دارد که بتوان کسری از یک وسیله - مثل پارچه - را جدا کرده و به وسایل داخل کوله‌پشتی اضافه کرد.
2- تولید درخت پوشای کمینه: روش‌های پریم و کروسکال دو روش مشهور تولید درخت پوشای کمینه از یک گراف وزن‌دار هستند که از روش حریصانه بهره می‌برند. منظور از درخت پوشای کمینه، درخت پوشایی از گراف است که مجموع وزن یال‌های آن کمتر یا مساوی مجموع وزن یال‌های سایر درخت‌های پوشای آن گراف است.
3- محاسبه کوتاهترین مسیرهای تک‌مبدأ: زمانی که قصد داریم کوتاهترین مسیر از یک مبدأ مشخص به تمامی رئوس دیگر گراف را محاسبه کنیم، الگوریتمی مانند دایکسترا (دیکسترا، دایجسترا) با استفاده از روش حریصانه به کمک ما می‌آید.
4- کدگذاری و فشرده‌سازی اطلاعات: کد هافمن یکی از روش‌های فشرده‌سازی اطلاعات است با کدگذاری مجدد کاراکترهای موجود در اطلاعات بر اساس میزان استفاده آنها، سعی در کم کردن حجم فایل میکند. بر اساس این روش، کاراکتری با استفاده بالا با کد کوتاهتر و کاراکتری با استفاده کم با کد طولانی‌تر جایگزین می‌شود.
لازم به ذکر است که موارد اشاره شده به عنوان کاربردهای روش حریصانه بر خلاف مثال خرد کردن پول به طور قطع یک جواب بهینه تولید می‌کنند. این جواب اگرچه ممکن است منحصر به فرد نباشد، اما همواره بهینه بوده و مرتبه اجرایی آن معمولا کمتر یا مساوی روش‌هایی مانند تقسیم و غلبه یا برنامه‌نویسی پویا است.