الگوریتمستان

نوشته‌های یک علاقه‌مند به حوزه‌های برنامه‌نویسی، الگوریتم، حل مسئله و ریاضیات دوست داشتنی

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

روش حریصانه (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- کدگذاری و فشرده‌سازی اطلاعات: کد هافمن یکی از روش‌های فشرده‌سازی اطلاعات است با کدگذاری مجدد کاراکترهای موجود در اطلاعات بر اساس میزان استفاده‌ی آنها، سعی در کم کردن حجم فایل می‌کند. بر اساس این روش، کاراکتری با استفاده‌ی بالا با کد کوتاهتر و کاراکتری با استفاده‌ی کم با کد طولانی‌تر جایگزین می‌شود.

  

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

◄  پیوندها برای مطالعه‌ی بیشتر
مسعود اقدسی‌فام

مسعود اقدسی‌فام هستم.

یک معلم علاقه‌مند به تحقیق، تدریس و نوشتن در حوزه‌های برنامه‌نویسی، الگوریتم و حل مسئله :)

اشتراک‌گذاری نوشته
algs.ir/spn6tw5     اشتراک‌گذاری در LinkedIn     اشتراک‌گذاری در Twitter     ارسال با Telegram     ارسال با WhatsApp
امتیاز به نوشته
  • 1
  • 2
  • 3
  • 4
  • 5

نام: *  

پست الکترونیک:

وب‌سایت:

متن پیام: *  

01 02 06 07 08 09 10 11 12 13 14


• آوا
یکشنبه، ۲۶ آذر ماه ۱۳۹۱، ساعت ۰۰:۳۴

سلام

سایتتون عالیه

فقط 111111111111111 خواهش دارمممممممم

می شه درمورد آسمان خراش ها در طراحی الگوریتم یه مطلب جامع برام بفرستید؟؟؟؟؟؟؟؟؟

داریییییییییییید؟؟؟؟

ممنون میشم زیاد


• ساعدی
جمعه، ۲۰ اردیبهشت ماه ۱۳۹۲، ساعت ۱۳:۵۳

خدا امواتتو بیامرزه ادمین جان.عالی بود.ئست گلت درد نکنه.06


• محسن
جمعه، ۲۰ اردیبهشت ماه ۱۳۹۲، ساعت ۲۰:۰۱

بسیار عالی

مطلب رو خیلی قابل فهم کرده بودید

ممنون و سپاس

یا حق


• سمیرا
جمعه، ۱ آذر ماه ۱۳۹۲، ساعت ۱۷:۵۶

سلام

میشه خواهش کنک به این سوال جواب بدید:

یکی از الگوریتم هایی که به روش greedyخوردکردن یک اسکناس به تعدادی سکه است که شباهت زیادی به  کوله پشتی دارد این الگوریتم را یافته توضیح دهید چرا این الگوریتم همیشه جواب بهینه نمی دهد


• سعید
یکشنبه، ۱ دی ماه ۱۳۹۲، ساعت ۱۶:۵۸

با سلام...

چرا الگوریتم درخت پوشای ماکزیمم (MAX) جایی پیدا نمیشود.

کمک کنید لطفا...

02


• احمد
دوشنبه، ۱۲ آبان ماه ۱۳۹۳، ساعت ۱۷:۴۷

04 همون وری خودمون


• امیر
سه‌شنبه، ۲ شهریور ماه ۱۳۹۵، ساعت ۱۲:۳۶

سایتتون بسیار عالیه

امیدوارم همیشه رو به پیشرفت حرکت کنید


• رحیم
سه‌شنبه، ۹ آذر ماه ۱۳۹۵، ساعت ۲۳:۵۰

اجرکم عندالله عالی بود


• dolphin
جمعه، ۲۱ اردیبهشت ماه ۱۳۹۷، ساعت ۲۱:۰۷

دم شما گرم


• پیشی کوچولو!
سه‌شنبه، ۲۲ خرداد ماه ۱۳۹۷، ساعت ۲۰:۳۳

با سلام خدمت ادمین سایت، خدا خیرت بده حداقل شما کامل مسئله رو توضیح دادی! ای ول!060606060303


• حسین محمدی
شنبه، ۱۰ آذر ماه ۱۳۹۷، ساعت ۱۹:۳۶

آقا عالیه سایتتون

خدا قوت


کمی آمار
  • عمر نوشته:  ۳۴۶۵ روز
  • تعداد امتیاز ثبت شده:  ۶۲ امتیاز
  • میانگین امتیازها:  ۴.۶۳ از ۵.۰۰
  • بازدید امروز:  ۰ بازدید
  • بازدید ۲۴ ساعت گذشته:  ۶ بازدید
  • بازدید ۷ روز گذشته:  ۶۰ بازدید
  • بازدید ۳۰ روز گذشته:  ۲۷۹ بازدید
  • بازدید ۱ سال گذشته: ۳۱۳۹ بازدید
  • کل بازدیدها: ۸۱۴۸ بازدید
برچسب‌ها
#آمادگی مسابقه برنامه‌نویسی  #آموزش الگوریتم  #مسئله‌های الگوریتمی  #برنامه‌نویسی ++C  #الگوریتم  #نمونه سوالات مسابقه برنامه‌نویسی  #حل مسئله‌‌ی الگوریتمی  #برنامه‌نویسی  #منبع آموزشی  #حل سوالات مسابقات برنامه‌نویسی  #الگوریتم‌های تقسیم و غلبه  #نمونه سوال مسابقه ACM  #الگوریتم‌های برنامه‌نویسی پویا  #الگوریتم‌های بازگشتی  #کتاب الکترونیکی  #آموزش ساختمان داده‌ها  #تکنیک‌های طراحی الگوریتم  #محاسبات ریاضی  #گراف  #دانلود کتاب  #حل سوالات ACM-ICPC  #الگوریتم‌های مرتب‌سازی  #سوالات مسابقات ACM-ICPC  #Python  #پیمایش گراف  #ساختمان داده  #کتاب مسابقات برنامه‌نویسی  #الگوریتم‌های گراف  #حل سوالات UVa Online Judge  #الگوریتم‌های مسیریابی  #الگوریتم‌های حریصانه  #درخت‌ها  #سوالات UVa Online Judge  #جستجوی اول سطح  #ماتریس  #الگوریتم‌های کوتاهترین مسیر  #درخت پوشا  #الگوریتم دایکسترا  #ویدئوی آموزشی  #معرفی وب‌سایت  #الگوریتم فلوید-وارشال  #مسئله‌ی کوله‌پشتی  #جستجوی اول عمق  #کتابخانه قالب استاندارد ++C  #صف  #سوالات مسابقات برنامه‌نویسی بیان  #الگوریتم‌های عقبگرد  #حل سوالات Timus Online Judge