بستن پنجره
فرادرس - مجموعه آموزش‌های ویدئویی  مهندسی کامپیوتر - طراحی الگوریتم - ساختمان داده
بستن پنجره     نوشته‌های پربازدید اخیر

»    محاسبه‌ی دترمینان ماتریس

»    اشاره‌گرها در زبان ++C

»    حلقه‌های تکرار در ++C

»    معمای هشت وزیر

»    الگوریتم جستجوی اول سطح (BFS)

»    مسابقه‌ی برنامه‌نویسی آنلاین Codeforces Round 406

»    درخت جستجوی دودویی

بستن پنجره
وبگاه
این صفحه
اشتراک‌گذاری در LinkedIn     Cloob     اشتراک‌گذاری در Twitter
اشتراک‌گذاری در Facebook     ارسال با Telegram     Google Plus
بستن پنجره
وبگاه     این صفحه
اشتراک‌گذاری در LinkedIn     Cloob     اشتراک‌گذاری در Twitter     اشتراک‌گذاری در Facebook     ارسال با Telegram     Google Plus
روش حریصانه - الگوریتمستان
الگوریتمستان
3714.625.00
  »  

       

آشنایی با روش حریصانه و کاربردهای آن مانند مسأله‌ی خرد کردن پول

روش حریصانه (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
10             i++;
11     }
12     if(Amount != 0)
13         return -1;
14     return Count;
15 }

  

    در این تابع، Coins ارزش سکه‌ها و اسکناس‌های موجود و Amount مقدار مورد نیاز برای تولید را مشخص می‌کنند. پاسخ نهایی در آرایه Result قرار گرفته و تعداد آنها با متغیر Count به محل فراخوانی بازگشت داده می‌شود. فرض شده است انتهای لیست سکه‌ها و اسکناس‌ها با عدد 1- مشخص شده و به ترتیب نزولی مرتب هستند. یعنی عنصر اول بزرگترین اسکناس موجود است.

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

    اگرچه این روش عملکردی ساده دارد، اما همواره به جواب بهینه ختم نمی‌شود. مثلا اگر سکه‌هایی با ارزش 1، 7 و 10 واحد پول موجود بوده و هدف تولید مبلغی با ارزش 14 واحد باشد، بر اساس این روش ابتدا یک سکه با ارزش 10 واحد انتخاب می‌شود. برای 4 واحد باقیمانده چاره‌ای نیست جز اینکه چهار سکه‌ی یک واحدی انتخاب شود. پس در کل 5 سکه برای تولید 14 واحد انتخاب شد. این در حالی است که می‌شد تنها با انتخاب دو سکه‌ی 7 واحدی همان مبلغ را تولید کرد.

    برای این مسأله الگوریتم دیگری با استفاده از روش برنامه‌نویسی پویا ارائه شده است که همواره به یک جواب بهینه - در صورت وجود - می‌رسد.

      

کاربردهای روش حریصانه

  [بازگشت به فهرست]

از جمله کاربردهای مشهور روش حریصانه مسائلی هستند که در ادامه معرفی می‌شوند.

    1- مسأله‌ی کوله‌پشتی کسری: در این مسأله هدف پر کردن یک کوله‌پشتی از وسایل پر ارزشی است که وزن‌های مختلفی دارند. این کوله‌پشتی باید به نحوی پر شود که وزن بار آن از حد مجاز بیشتر نشده و ارزش وسایل داخل آن بیشینه باشد. در مسأله‌ی کوله‌پشتی کسری بر خلاف کوله‌پشتی صفر و یک این امکان وجود دارد که بتوان کسری از یک وسیله - مثل پارچه - را جدا کرده و به وسایل داخل کوله‌پشتی اضافه کرد.

    2- تولید درخت پوشای کمینه: روش‌های پریم و کروسکال دو روش مشهور تولید درخت پوشای کمینه از یک گراف وزن‌دار هستند که از روش حریصانه بهره می‌برند. منظور از درخت پوشای کمینه، درخت پوشایی از گراف است که مجموع وزن یال‌های آن کمتر یا مساوی مجموع وزن یال‌های سایر درخت‌های پوشای آن گراف است.

    3- محاسبه‌ی کوتاهترین مسیرهای تک‌مبدأ: زمانی که قصد داریم کوتاهترین مسیر از یک مبدأ مشخص به تمامی رئوس دیگر گراف را محاسبه کنیم، الگوریتمی مانند دایکسترا (دیکسترا، دایجسترا) با استفاده از روش حریصانه به کمک ما می‌آید.

    4- کدگذاری و فشرده‌سازی اطلاعات: کد هافمن یکی از روش‌های فشرده‌سازی اطلاعات است با کدگذاری مجدد کاراکترهای موجود در اطلاعات بر اساس میزان استفاده‌ی آنها، سعی در کم کردن حجم فایل می‌کند. بر اساس این روش، کاراکتری با استفاده‌ی بالا با کد کوتاهتر و کاراکتری با استفاده‌ی کم با کد طولانی‌تر جایگزین می‌شود.

      

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


این نوشته آخرین بار در تاریخ جمعه، ۲۰ آذر ماه ۱۳۹۴ مورد بازنویسی نگارشی قرار گرفته است.
پیوندها برای مطالعه‌ی بیشتر
نوشته‌های مرتبط
فرادرس - مجموعه آموزش‌های ویدئویی  مهندسی کامپیوتر - طراحی الگوریتم - ساختمان داده
        بررسی مسأله‌ی اعداد اردوش (Erdos Numbers) یا فاصله‌ی همکاری اردوش از سوالات آمادگی مسابقات برنامه‌نویسی
        معرفی کتاب Programming Challenges برای علاقه‌مندان حل سوالات الگوریتمی و شرکت‌کنندگان مسابقات برنامه‌نویسی یا معرفی پیوند دانلود فایل‌های صوتی، تصویری و اسلایدهای کلاس درس نویسنده
        آشنایی با الگوریتم دایکسترا برای یافتن کوتاهترین مسیر تک‌مبدأ در گراف وزن‌دار بدون یال منفی با قطعه کد به زبان ++C
        معرفی کتاب Art of Programming Contest برای علاقه‌مندان حل سوالات الگوریتمی و شرکت‌کنندگان مسابقات برنامه‌نویسی با قابلیت دانلود نسخه‌ی الکترونیکی
        معرفی کتاب Introduction to Algorithms: A Creative Approach
        آشنایی با روش برنامه‌نویسی پویا (یا برنامه‌ریزی پویا، برنامه‌سازی پویا - Dynamic Programming) به عنوان یکی از روش‌های پر کاربرد طراحی الگوریتم برای حل بهینه‌ی مسائل با مثالی از محاسبه‌ی دنباله‌ی فیبوناچی
        معرفی کتاب Introduction to Algorithms (ویراست سوم) به عنوان مرجع مباحث طراحی الگوریتم‌ها و ساختمان داده‌ها
        آشنایی با روش Divide and Conquer (تقسیم و حل / تقسیم و غلبه) و کاربردهای آن در مرتب‌سازی، جستجو و حل مسائل الگوریتمی دیگر
        بحث در مورد ضرب زنجیره‌ای ماتریس‌ها و روش پیاده‌سازی الگوریتم پرانتزبندی بهینه‌ی آن با روش تقسیم و حل و روش برنامه‌نویسی پویا
پیوند کوتاه صفحه دسته‌بندی
امتیاز نوشته
  • 1
  • 2
  • 3
  • 4
  • 5
ارسال پیام

نام: *  

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

وبگاه:

متن پیام: *

right 01 02 03 04 05 06 07 08 09 10 11 12 13 14 left

 


» رحیم

سه‌شنبه، ۹ آذر ماه ۱۳۹۵، ساعت ۲۳:۵۰
اجرکم عندالله عالی بود

» امیر

سه‌شنبه، ۲ شهریور ماه ۱۳۹۵، ساعت ۱۲:۳۶
سایتتون بسیار عالیه
امیدوارم همیشه رو به پیشرفت حرکت کنید

» احمد

دوشنبه، ۱۲ آبان ماه ۱۳۹۳، ساعت ۱۷:۴۷
04 همون وری خودمون

» سعید

یکشنبه، ۱ دی ماه ۱۳۹۲، ساعت ۱۶:۵۸
با سلام...
چرا الگوریتم درخت پوشای ماکزیمم (MAX) جایی پیدا نمیشود.
کمک کنید لطفا...
02

» سمیرا

جمعه، ۱ آذر ماه ۱۳۹۲، ساعت ۱۷:۵۶
سلام
میشه خواهش کنک به این سوال جواب بدید:
یکی از الگوریتم هایی که به روش greedyخوردکردن یک اسکناس به تعدادی سکه است که شباهت زیادی به  کوله پشتی دارد این الگوریتم را یافته توضیح دهید چرا این الگوریتم همیشه جواب بهینه نمی دهد

» محسن

جمعه، ۲۰ اردیبهشت ماه ۱۳۹۲، ساعت ۲۰:۰۱
بسیار عالی
مطلب رو خیلی قابل فهم کرده بودید
ممنون و سپاس
یا حق

» ساعدی

جمعه، ۲۰ اردیبهشت ماه ۱۳۹۲، ساعت ۱۳:۵۳
خدا امواتتو بیامرزه ادمین جان.عالی بود.ئست گلت درد نکنه.06

» آوا

یکشنبه، ۲۶ آذر ماه ۱۳۹۱، ساعت ۰۰:۳۴
سلام
سایتتون عالیه
فقط 111111111111111 خواهش دارمممممممم
می شه درمورد آسمان خراش ها در طراحی الگوریتم یه مطلب جامع برام بفرستید؟؟؟؟؟؟؟؟؟
داریییییییییییید؟؟؟؟
ممنون میشم زیاد