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

[[Image:|thumb|۲۸۰px|left| الگورتم حریصانه کمترین تعداد سکه هایی که باعث شود مسئله تغییر نماید را تعیین می نماید .اینها مراحل یک انسان هستند که سکه با مقدار ۳۶ را با استفاده از سکه‌های با مقادیر ۱و۵و۱۰و۲۰ تعیین می کند. سکه با بزرگترین مقدار و کوچکتر از تغییرات باقی مانده بعنوان بهینه محلی انتخواب می گردد(توجه کنید که در حالت معمول مسئله پیدا کردن تغییرات بااستفاده از برنامه‌ریزی پویا یا integer programming جواب بهینه را پیدا می کند).پول آمریکا و دیگر کشورهانمونه‌های خاصی هستند که با استفاده از الگوریتم حریصانه می توان جواب بهینه آنهارا پیدا کرد).]] در بسیاری از موارد مسئله از ما می‌خواهد که یک متغیر را کمینه یا بیشینه کنیم و یا اینکه صورت مسئله مستقیما از ما نمی‌خواهد که چیزی را کمینه یا بیشینه کنیم اما می‌توان این مسئله را تبدیل به یک چنین مسئله‌ای کرد. در اکثر مسائل از این دست ما باید تعدادی انتخاب انجام دهیم و مسئله در تعدادی مرحله حل شود. بازهٔ وسیعی از این مسائل توسط الگوریتم‌های حریصانه قابل حل‌اند. الگوریتم‌های حریصانه در هر مرحله در نظر می‌گیرند که کدام انتخاب در حال حاضر بهترین وضعیت را برای ما رقم می‌زند و آن را انجام می‌دهند بدون در نظر گرفتن این که انجام این حرکت در آینده ممکن است به ضرر ما تمام شود. بنابراین الگوریتم‌های حریصانه همیشه جواب درست را به ما نمی‌دهند اما خیلی وقت‌ها هم اینطور نیست این دسته از الگوریتم‌ها در علوم رایانه کاربرد وسیعی دارند.

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

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

        prededure change(${c_1},{c_2},{...},{c_r}:value of denominations of coin,wherer {c_1}>{c_2}>{...}>{c_r};n:a positive integer$
                                                                    for i:=۱ to r    
                                                                        while n≤${c_i}$
                                                                            begin 
                                       add a coin with value ${c_i}$ to change
                                                                  n:=n-${c_i}$
                                                                              end

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

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

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

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

                                                                                      i -> ۱  ۲  ۳  ۴  ۵  ۶   ۷  ۸    ۹  ۱۰  ۱۱          
                                                                                      si -> 1  3  0  5  3  5   6  8    8   2  12      
                                                                                      fi -> 4  5  6  7  8  9  10  11  12  13  14

برای این مثال زیر مجموعهٔ {a۳،a۹،a۱۱} شامل فعالیت‌های متقابلا سازگار است.

اگرچه این زیرمجموعه ماکزیمم نیست، چون زیرمجموعهٔ {a۱،a۴،a۹،a۱۱} بزرگ‌تر از آن است. در حقیقت {a۱،a۴،a۹،a۱۱} بزرگ‌ترین زیرمجموعه از فعالیت‌های متقابلاً سازگار است. حال یک الگوریتم حریصانه بازگشتی برای حل مسئلهٔ زمان‌بندی فعالیت‌ها ارائه خواهیم نمود.

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

F۰≤f۱≤f۲≤…≤fn≤fn+۱ ادعا می کنیم که sij=ᴓ هرگاه i≥j باشد. فرض کنید یک فعالیت ak€sij برای i≥j وجود دارد به طوری که ai بعد از aj در ترتیب مرتب قرار دارد. پس خواهیم داشت fi≤sk<fk≤sj<fj. بنابراین fi<fj که با این فرض که ai بعد از aj در ترتیب مرتب قرار دارد در تناقض است. می‌توانیم نتیجه بگیریم با این فرض که فعالیت‌ها رادر یک ترتیب صعودی یکنواخت از زمان‌های خاتمه مرتب کرده ایم، فضای زیر مسائل انتخاب زیر مجموعه با ماکزیمم اندازه شامل فعالیت‌های متقابلا سازگاراز sij است، که ۰≤i<j≤n+۱ با آگاهی از این مطلب که تمام 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 یک جواب بهینه برای کل مسئله یک جواب برای S۰،n+۱ است.

منابع

• مقدمه‌ای بر الگوریتم‌ها - پدیدآورنده: تامس کورمن، چارلز لیزرسان، رونالد دیوست، کلیفورد اشتاین -(clrs)

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