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

روش حریصانه (Greedy) یکی از روش‌های مشهور و پرکاربرد طراحی الگوریتم‌ها است که با ساختاری ساده در حل بسیاری از مسائل استفاده می‌شود. این روش اغلب در حل مسائل بهینه‌سازی استفاده شده و در پاره‌ای مواقع جایگزین مناسبی برای روش‌هایی مانند برنامه‌ریزی پویا است. در حالت کلی این روش سرعت و مرتبهٔ اجرایی بهتری نسبت به روش‌های مشابه خود دارد؛ اما متناسب با مسئله ممکن است به یک جواب بهینهٔ سراسری ختم نشود.

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

جست و جوی حریصانه

ساختار روش حریصانه

کلیت روش حریصانه در هر مرحله، انتخاب یک عنصر از عناصر موجود است. این عنصر قسمتی از جواب مسئله است که به مجموعه عناصر نهایی اضافه می‌شود. در طی این مسیر گام‌های زیر اتفاق می‌افتد:

1. روال انتخاب حریصانه (Selection): در این گام یک عنصر برای اضافه شدن به مجموعه جواب انتخاب می‌شود. معیار یا روال انتخاب عنصر برای اضافه شدن، ارزش آن عنصر است. بسته به نوع مسئله هر عنصر ارزشی دارد که با ارزشترین آنها انتخاب می‌شود.
2. امکان‌سنجی و افزودن (Feasible): پس از انتخاب یک عنصر به صورت حریصانه، باید بررسی شود که آیا امکان اضافه کردن آن به مجموعه جواب‌های قبلی وجود دارد یا نه. گاهی اضافه شدن عنصر یکی از شرایط اولیهٔ مسئله را نقض می‌کند که باید به آن توجه نمود. اگر اضافه کردن این عنصر هیچ شرطی را نقض نکند، عنصر اضافه خواهد شد؛ وگرنه کنار گذاشته شده و بر اساس گام اول عنصر دیگری برای اضافه شدن انتخاب می‌شود. اگر گزینهٔ دیگری برای انتخاب وجود نداشته باشد، اجرای الگوریتم به اتمام می‌رسد.
3. بررسی اتمام الگوریتم (Solution): در هر مرحله پس از اتمام گام 2 و اضافه شدن یک عنصر جدید به مجموعه جواب، باید بررسی کنیم که آیا به یک جواب مطلوب رسیده‌ایم یا خیر؟ اگر نرسیده باشیم به گام اول رفته و چرخه را در مراحل بعدی ادامه می‌دهیم.

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

 set_greedy(C){
    S = ∅
    while(!solution(s)&&C != ∅){
        X = select(C);
        C = C - {x};
        if (feasible(S,{x})){
            S = S + {x}
        }
    }
    if(solution(S)){
        return S;
    }
    else:
        return ∅;
  }

تفاوت‌های الگوریتم حریصانه و برنامه‌نویسی پویا

• الگوریتم حریصانه در هر مرحله بهترین جواب محلی را پیدا می‌کند؛ اما در برنامه‌نویسی پویا مسئله به تعدادی زیر مسئله تقسیم می‌شود.
• الگوریتم حریصانه هیچ‌گاه در جواب خود بازنگری نمی‌کند.
• در الگوریتم حریصانه تضمینی برای جواب نهایی بهینه وجود ندارد.
• این الگوریتم در زمان بهینه اجرا می‌شود.

تاریخچه

نام این روش از شخصیت معروف اسکروج گرفته شده‌است. یکی از تفریحات و انگیزه‌های اسکروج، به دست آوردن پول بیشتر بود؛ الگوریتم حریصانه (Greedy) نیز مانند شیوه اسکروج می‌باشد؛ مثلاْ فرض کنید اسکروج در یک مسابقه شرکت کرده‌است و باید در مرحله اول مسابقه یک درب را انتخاب کند، به ازای انتخاب هر درب فقط می‌تواند درب‌های بعد آن را باز کند و پول دریافت کند:

در مرحله اول باید بین دو درب، اولی پنج سکه و دومی دو سکه، انتخاب کند؛ چون او حریص است بهترین انتخاب را در لحظه انتخاب درب اول می‌داند.

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

کاربردها

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

مثال

• مسئله رنگ‌آمیزی راس‌های گراف:

با تعداد m رنگ داده شده، راس‌های گراف باید به گونه‌ای رنگ شوند که هیچ دو راس مجاوری دارای رنگ مشابه نباشند. هدف رنگ کردن راس‌ها به شیوه‌ای است که هیچ دو راس مجاوری دارای رنگ مشابه نباشند. هیچ الگوریتم کارآمدی برای رنگ‌آمیزی گراف با حداقل رنگ‌های ممکن وجود ندارد و این مسئله از جمله مسائل «ان‌پی کامل» (NP Complete) محسوب می‌شود. «الگوریتم‌های تقریبی» (Approximate Algorithms) گوناگونی برای حل این مسئله وجود دارند،که رنگ‌آمیزی آزمند از جمله آنهاست.

• مسئله کوله پشتی:

ما n شی و یک کوله پشتی داریم که هر شی دارای وزنی است؛ ظرفیت کوله پشتی نیز محدود است. ما می‌خواهیم ارزش شی‌های قرار داده شده در کوله‌پشتی ماکزیمم شود: ما به دنبال $\sum _{k=1}^{N}p_{i}x_{i}$ Max هستیم، طوری که $\sum _{i=1}^{n}w_{i}x_{i}$ کمتر از W (بیشترین وزنی که در کوله پشتی قرار می‌گیرد. حال باتوجه به روش حریصانه، راه حل‌های زیر موجودند:

1. هدف پیدا کردن بیشترین ارزش است، بنابراین اشیا را بر اساس سود آن‌ها به ترتیب نزولی مرتب کرده و اشیا با بیشترین ارزش را تا زمانی که کوله‌پشتی ظرفیت داشته باشد انتخاب می‌کنیم.
2. وزن اشیا تاثیر منفی دارد؛ یعنی انتخاب شی با وزن بیشتر به سرعت کوله پشتی را پر می‌کند؛ بنابراین اشیا را به ترتیب صعودی بر اساس وزن در نظر گرفته و هنگامی که ظرفیت کوله‌پشتی به حداکثر نرسیده است، اشیا با وزن کمتر را انتخاب می‌کنیم.
3. ارزش اشیا تاثیر مثبت و وزن آن‌ها تاثیر منفی دارد، بنابراین بهتر است نسبت p_i / x_i را محاسبه و به ترتیب نزولی مرتب کنیم، تا زمانی ظرفیت کوله‌پشتی به حداکثر نرسیده است، اشیا را از این لیست را انتخاب کنیم.

جواب‌های حاصل از مورد ۱ و ۲ لزوماً بهینه نیستند اما جواب حاصل از روش سوم بهینه است. کد مربوط به روش سوم در زیر آمده است:

  void greedy_knap_sack(w, n){
    sort(p, w)
    for(i = 0; i < n; i++){
        x[i] = 0
    }
    u = w
    for(i = 0; i < n; i++){
        if(w[i] > u){
            break
    }
        x[i] = 1
        u = u - w[i]
    }
    if (i < n){
        x[i] = u / w[i]
    }
}

• کد گذاری هافمن:

کدگذاری هافمن یک الگوریتم مقایسه داده است که از الگوریتم حریصانه برای پیاده سازی استفاده می‌کند و بر اساس تعداد تکرارهای یک کاراکتر در یک فایل است.

الگوریتم حریصانه کمترین تعداد سکه‌هایی که باعث شود مسئله تغییر نماید را تعیین می‌نماید. این‌ها مراحل یک انسان هستند که سکه با مقدار ۳۶ را با استفاده از سکه‌های با مقادیر ۱ و ۵ و ۱۰ و ۲۰ تعیین می‌کند. سکه با بزرگترین مقدار و کوچکتر از تغییرات باقی‌مانده به عنوان بهینه محلی انتخاب می‌گردد (توجه کنید که در حالت معمول مسئله پیدا کردن تغییرات بااستفاده از برنامه‌ریزی پویا یا Linear programming Integer unknowns جواب بهینه را پیدا می‌کند). پول آمریکا و دیگر کشورها نمونه‌های خاصی هستند که با استفاده از الگوریتم حریصانه می‌توان جواب بهینه آن‌ها را پیدا کرد). در بسیاری از موارد مسئله از ما می‌خواهد که یک متغیر را کمینه یا بیشینه کنیم یا اینکه صورت مسئله مستقیماً از ما نمی‌خواهد که چیزی را کمینه یا بیشینه کنیم اما می‌توان این مسئله را تبدیل به یک چنین مسئله‌ای کرد. در اکثر مسائل از این دست ما باید تعدادی انتخاب انجام دهیم و مسئله در تعدادی مرحله حل شود. بازهٔ وسیعی از این مسائل توسط الگوریتم‌های حریصانه قابل حل‌اند. الگوریتم‌های حریصانه در هر مرحله در نظر می‌گیرند که کدام انتخاب در حال حاضر بهترین وضعیت را برای ما رقم می‌زند و آن را انجام می‌دهند بدون در نظر گرفتن این که انجام این حرکت در آینده ممکن است به ضرر ما تمام شود؛ بنابراین الگوریتم‌های حریصانه همیشه جواب درست را به ما نمی‌دهند اما خیلی وقت‌ها هم اینطور نیست این دسته از الگوریتم‌ها در علوم رایانه کاربرد وسیعی دارند.

حال مثالی برای این‌گونه الگوریتم‌ها می‌آوریم:

فرض کنید می‌خواهیم n تومان را با سکه های ۲۵ تومانی، ۱۰ تومانی، ۵ تومانی و ۱ تومانی پرداخت کنیم؛ به‌ طوری‌ که کمترین تعداد سکه را بپردازیم. ما می‌توانیم یک الگوریتم حریصانه برای حل این مسئله ارائه دهیم که تعداد سکه بهینه را در هر مرحله به دست آورد. برای این کار ما در هر مرحله بزرگترین سکه‌ای را که از پول باقی‌مانده تجاوز نکند انتخاب می‌کنیم در این صورت تعداد سکه‌ها بهینه خواهدبود.

 prededure change(${c_{1}},{c_{2}},{...},{c_{r}}:valueofdenominationsofcoin,wherer{c_{1}}>{c_{2}}>{...}>{c_{r}};n:apositiveinteger$
 for i:=1 to r
 while n≤${c_{i}}$
 begin
 add a coin with value ${c_{i}}$ to change
 n:=n-${c_{i}}$
 end

مثال دیگری که می‌توان عنوان کرد مسئلهٔ زمان‌بندی چندین فعالیت در حال رقابت است که نیاز به استفادهٔ منحصربه‌فرد از یک منبع مشترک با هدف انتخاب مجموعه‌ای با ماکزیمم اندازه از فعالیت‌هایی که متقابلاً با یکدیگر سازگارند، دارند.

فرض کنید یک مجموعهٔ s={a1,a2، ….an} از n فعالیت پیشنهادی داریم که می‌خواهند از یک منبع استفاده نمایند، مانند یک تالار سخنرانی که در یک زمان می‌تواند تنها مورد استفادهٔ یک فعالیت قرار گیرد. هر فعالیت ai دارای زمان شروع si و زمان خاتمهٔ fi است به‌طوری‌که 0 ≤ si < fi < ∞. اگر فعالیت ai انتخاب شود، می‌تواند در طول بازهٔ [si, fi) رخ دهد.

تعریف: فعالیت‌های ai و aj سازگار هستند، اگر بازه‌های [si, fi) و [sj, fj) همپوشانی نداشته باشند.

مسئله انتخاب فعالیت عبارت است از انتخاب یک زیرمجموعه با ماکزیمم اندازه از فعالیت‌های متقابلاً سازگار. برای مثال مجموعهٔ s زیر از فعالیت‌ها را در نظر بگیرید که آن‌ها را به ترتیب صعودی یکنواخت از زمان‌های خاتمه مرتب کرده‌ایم:

 i -> 1 2 3 4 5 6 7 8 9 10 11
 si -> 1 3 0 5 3 5 6 8 8 2 12
 fi -> 4 5 6 7 8 9 10 11 12 13 14

برای این مثال زیر مجموعهٔ {a3, a9, a11} شامل فعالیت‌های متقابلاً سازگار است.

اگرچه این زیرمجموعه ماکزیمم نیست، چون زیرمجموعهٔ {a1, a4, a9, a11} بزرگ‌تر از آن است. در حقیقت {a1, a4, a9, a11} بزرگ‌ترین زیرمجموعه از فعالیت‌های متقابلاً سازگار است. حال یک الگوریتم حریصانه بازگشتی برای حل مسئلهٔ زمان‌بندی فعالیت‌ها ارائه خواهیم نمود.

با تعریف مجموعهٔ sij={ak € s: fi≤sk<fk≤sj} شروع می‌کنیم، به‌طوری‌که sij زیر مجموعه‌ای از فعالیت‌ها در S است که می‌توانند بعد از خاتمه فعالیت ai شروع شده و قبل از شروع فعالیت aj خاتمه یابند. در حقیقت sij شامل همه فعالیت‌هایی است که با ai و aj و همچنین با همه فعالیت‌هایی که بعد از خاتمه ai خاتمه نیافته و همه فعالیت‌هایی که قبل از شروع aj شروع نمی‌شوند، سازگارند. به منظور بیان کل مسئله، فعالیت‌های ساختگی a0 و an+1 را اضافه کرده و توافق می‌کنیم که f0=0 و sn+1=∞ پس S=S0,n+1 و محدودهٔ تغییر iو j به صورت 0≤I,j≤n+1 خواهد بود. دامنهٔ تغییر I و j را به صورت زیر می‌توانیم بیشتر محدود کنیم. فرض می‌کنیم که فعالیت‌ها در یک ترتیب یکنواخت صعودی از زمان‌های خاتمه مرتب شده‌اند:

F0≤f1≤f2≤…≤fn≤fn+1 ادعا می‌کنیم که sij=ᴓ هرگاه i≥j باشد. فرض کنید یک فعالیت ak€sij برای i≥j وجود دارد به‌طوری‌که ai بعد از aj در ترتیب مرتب قرار دارد. پس خواهیم داشت fi≤sk<fk≤sj<fj. بنابراین fi<fj که با این فرض که ai بعد از aj در ترتیب مرتب قرار دارد در تناقض است. می‌توانیم نتیجه بگیریم با این فرض که فعالیت‌ها را در یک ترتیب صعودی یکنواخت از زمان‌های خاتمه مرتب کرده‌ایم، فضای زیر مسائل انتخاب زیر مجموعه با ماکزیمم اندازه شامل فعالیت‌های متقابلاً سازگاراز sij است، که 0≤i<j≤n+1 با آگاهی از این مطلب که تمام sijهای دیگر تهی هستند.

برای مشاهده زیر ساختار مسئله انتخاب فعالیت، تعدادی زیرمسئله غیر تهی sij را در نظر بگیرید؛ و فرض کنید که یک جواب برای sij شامل تعدادی فعالیت ak است. به‌طوری‌که fi ≤ sk <fk ≤ sj. استفاده از فعالیت ak سبب ایجاد دو زیر مسئله می‌شود، sik(فعالیت‌های که پس از خاتمه فعالیت aiشروع شده و قبل از شروع فعالیت akخاتمه می‌یابند) وskj(فعالیت‌های که پس از خاتمه akشروع شده و قبل از شروع فعالیت ajخاتمه می‌یابند)، که هرکدام از یک زیر مجموعه شامل فعالیت‌های داخل sij تشکیل شده‌اند. جواب sij اجتماع جواب‌های مربوط به sik و skj است، همراه با فعالیت ak. بنابراین تعداد فعالیت‌ها در جواب sij برابر اندازه جواب skj به علاوه یک (برای ak) می‌باشد.

اکنون فرض کنید جواب Aij برای sij شامل فعالیت ak می‌باشد. پس جواب‌های Aik برای sik و Akjبرای skj که در این جواب بهینه برای sij استفاده می‌شوند نیز باید بهینه باشند. بحث برش – و – الصاق معمول در این مورد بکار می‌رود. اگر یک جواب Áik برای sik می‌داشتیم که شامل فعالیت‌های بیشتری از Aik می‌بود، می‌توانستیم Aik را از داخل Aij برش داده و به داخل Áik الصاق نماییم، بنابراین یک جواب دیگر برای Sij با تعداد فعالیت‌های بیشتری از Aij تولید می‌شود. از آنجا که فرض کردیم Aij یک جواب بهینه است، به یک تناقض رسیده‌ایم. به‌طور مشابه اگر جواب Ákj برای skj را با فعالیت‌های بیشتر از Akj می‌داشتیم، می‌توانستیم Akj را با Ákj جایگزین کنیم تا یک جواب با فعالیت‌های بیشتری از Aij تولید نماییم.

اکنون از زیر ساختار بههینه خود استفاده کرده تا نشان دهیم که می‌توانیم یک جواب بهینه برای مسئله از روی جواب‌های بهینه زیر مسائل بسازیم. مشاهده کردم که هر جواب برای یک زیر مسئله غیر تهی sij شامل فعالیت ak است و آنکه هر جواب بهنه در درون خود شامل جواب‌های بهینه نمونه زیر مسئله‌های sik و skj می‌باشد؛ بنابراین، می‌توانیم یک زیر مجموعه با ماکزیمم اندازه از فعالیت‌های متقابلاً سازگار درSijبسازیم. با تقسیم مسئله به دو زیرمسئله (یافتن زیر مجموعه‌های با ماکزیمم اندازه از فعالیت‌های متقابلاً سازگار در sikو skj) و پیدا کردن زیرمجموعه‌های با ماکزیمم اندازه Aik و Akjاز فعالیت‌های متقابلاً سازگار برای این زیر مسائل و سپس تشکیل زیر مجموعه Aij با ماکزیمم اندازه شامل فعالیت‌های متقابلاً سازگار به صورت Aik υ {ak } υ Akj=Aij یک جواب بهینه برای کل مسئله یک جواب برای S0,n+1 است.

الگوریتم حریص برای حل مسئله پول خرد

مسئله:پس دادن بقیه پول مشتری با استفاده از سکه‌های موجود.

ورودی:انواع سکه‌های موجود(1 سنتی، 5سنتی، 10سنتی، 20سنتی، 25سنتی و نیم دلاری).

خروجی:پس دادن بقیه پول با حداقل تعداد سکه‌ها.

 (set Greedy-Applying(c
 }
 ;{1٬5,10٬20٬25٬50}=C
 ;[0]=S
 (∅=!While(!solution(s)&&c
 }
 ;(X=SELECT(C
 ;{C=C-{x
 ((IF(FEASIBLE(S,X
 ;{S=S+{X
 {
 ((if(solution(s
 ;return S
 else
 (∅)return
 {

مثال1

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

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

خریداری از یک فروشگاه یک جنس 64تومانی می‌خرد و 100 تومان به فروشنده می‌دهد و فروشنده باید 36 تومان به او برگرداند. اگر فروشنده سکه‌های 50٬25٬10٬5٬1تومانی (از هرکدام حداقل یک نمونه) داشته باشد چگونه می‌تواند بقیه پول خریدار را برگرداند به نحوی که تعداد سکه ها (در کل) کمترین مقدار ممکن باشد؟

یک راه حل حریصانه به این صورت است:

در ابتدا هیچ سکه در مجموعه جواب نداریم. از بین سکه‌های موجود بزرگ‌ترین ممکن یعنی 25 تومانی را انتخاب می‌کنیم. این مرحله از الگوریتم حریصانه راروال انتخاب(select procedure) گویند. اگر یک سکه 25 تومانی دیگر را انتخاب کنیم حاصل از 36 تومان بیشتر شده، لذا آن را کنار گذاشته به سراغ سکه 10 تومانی می‌رویم. حال بررسی می‌کنیم اگر این سکه 10 تومانی را به مجموعه انتخابی قبلی اضافه کنیم حاصل از 36 تومان بیشتر می‌شود یا خیر. این مرحله را تحقیق عملی بودن(feasibililty check) می‌نامند. حال اگر این 10 تومان را به25 تومان جمع مجموعه انتخاب شده 35 می‌شود که هنوز به 36 نرسیده‌است. این مرحله را تحقیق حل شدن(Solution check) می‌گوییم. در ادامه سکه‌های دیگر را به ترتیب مقایسه می‌کنیم و در نهایت با انتخاب سکه یک تومانی در کل با 3 سکه (25 تومانی و 10 تومانی و یک تومانی) 36 تومان به دست می‌آید و این حداقل تعداد سکه ممکن است.

توجه کنید در انتخاب فوق ملاک انتخاب، برای انتخاب بهترین سکه در هر مرحله (بهینه محلی) سکه است و در انتخاب سکه در هر مرحله به انتخاب‌های قبلی و بعدی کاری نداریم. در این شیوه اجازه فکر کردن دربارهٔ یک انتخاب انجام شده را نداریم یعنی هنگامی که سکه‌ای پذیرفته شد به‌طور دائم جزو حل به حساب می‌آید و هنگامی هم که سکه‌ای رد می‌شود به‌طور دائم از حل کنار گذاشته می‌شود.

همان‌طور که مشاهده کردید این روش بسیار ساده است، ولی اصلی‌ترین نکنه این است که آیا این روش الزاماً به یک حل بهینه می‌رسد؟ در رابطه با مسئله خاص فوق می‌توان اثبات کرد که جواب بهینه است ولی با مثال زیر نشان می‌دهیم که ممکن است این گونه نباشد.

مثال2

فرض کنید قرار است به فردی 16 تومان پس بدهیم. سکه‌های موجود 1٬5٬10٬12٬25تومانی است (با این که ما در ایران سکه 12 تومانی نداریم ولی این فرض را بکنید که داریم).

با الگوریتم حریصانه فوق به این نتیجه می‌رسیم که باید به این فرد یک سکه 12 تومانی و 4 سکه 1 تومانی بدهیم یعنی جمعاً 5 سکه. در حالی که حل بهینه مسئله فوق یک سکه 10 تومانی، یک سکه 5 تومانی و یک سکه یک تومانی است یعنی در کل 3 سکه.

از مثال فوق نتیجه می‌گیریم که هر الگوریتم حریصانه الزاماً حل بهینه را نمی‌دهد و برای هر مسئله خاص باید اثبات کنیم که آیا الگوریتم حریصانه برای آن، جواب بهینه می‌دهدیا خیر و این موضوع اغلب سخت‌ترین مرحله کار است.

با توجه به مثال‌های فوق می‌توان مراحل روش حریصانه را به این صورت بیان کرد:

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

روال انتخاب: این روال عنصر بعدی را طبق یک معیار حریصانه انتخاب می‌کند. این انتخاب یک شرط بهینه را در همان برهه برآورده می‌سازد.

تحقیق عملی بودن: در این مرحله مشخص می‌شود که آیا مجموعه جدید به دست آمده، برای رسیدن به حل عملی است یا خیر.

تحقیق حل: مشخص می‌سازد که آیا مجموعه جدید، نمونه مورد نظر را حل کرده‌است یا خیر

مثال

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

s=[item1,item2,item3,...,itemn]

Wi=item1وزن Pi=itemiارزش W=حداکثر وزنی که کوله پشتی قادر به تحمل آن است. وwi,pi,wهمگی اعداد صحیحی هستند. راه حل جستجوی جامع این است که همهٔ زیر مجموعه‌های این nقطعه را در نظر بگیریم، زیرمجموعه‌هایی را که وزن کل آن‌ها از wفراتر نرود، کنار می‌گذاریم و از میان آن‌هایی که باقی می‌ماند، آن را که بیشترین ارزش را دارد،انتخاب می‌کنیم

منابع

• مقدمه‌ای بر الگوریتم‌ها - پدیدآورنده: تامس کورمن، چارلز لیزرسان، رونالد دیوست، کلیفورد اشتاین - (clrs)
• درس و کنکور طراحی الگوریتم، مؤلف: حمیدرضا مقسمی،انتشارات گسترش علوم پایه
• علایی فرادنبه - علایی، ابراهیم،محمدرضا (۱۳۹۲). طراحی الگوریتم. تهران: انتشارات راه.

• Discrete Mathematics and its Applications, Kenneth H.Rosen, fifth edition

• Greedy Algorithm Archives - GeeksforGeeks