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

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

الگوریتم حریصانه همانند روش‌های پویا اغلب برای حل مسائل بهینه سازی مورد استفاده قرار می‌گیرد. در شیوه حریصانه در هر مرحله عنصری که بر مبنای معیاری معین ((بهترین))به نظر می رسد، بدون توجه به انتخاب هایی که قبلا انجام شده یا در آینده انجام خواهد شد،انتخاب می شود. الگوریتم های حریصانه اغلب راه حل های ساده ای هستند.در روش حریصانه برخلاف روش پویا ، مسأله به نمونه های کوچک تر تقسیم نمی شود.

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

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

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

فرض کنید یک مجموعهٔ s={a_۱،a_۲،….a_n} از n فعالیت پیشنهادی داریم که می خواهند از یک منبع استفاده نمایند، مانند یک تالار سخنرانی که در یک زمان می‌تواند تنها مورد استفادهٔ یک فعالیت قرار گیرد. هر فعالیت a_i دارای زمان شروع s_i و زمان خاتمهٔ f_i است به طوری که ۰≤s_i

F_۰≤f_۱≤f_۲≤…≤f_n≤f_n+۱ ادعا می کنیم که s_ij=ᴓ هرگاه i≥j باشد. فرض کنید یک فعالیت a_k€s_ij برای i≥j وجود دارد به طوری که a_i بعد از a_j در ترتیب مرتب قرار دارد. پس خواهیم داشت f_i≤s_k

اکنون فرض کنید جواب A_ij برای s_ij شامل فعالیت a_k می‌باشد.پس جواب‌های A_ik برای s_ik و A_kjبرای s_kj که در این جواب بهینه برای s_ij استفاده می‌شوند نیز باید بهینه باشند. بحث برش – و – الصاق معمول در این مورد بکار می‌رود. اگر یک جواب Á_ik برای s_ik می‌داشتیم که شامل فعالیت‌های بیشتری از Aik می‌بود، می‌توانستیم A_ik را از داخل A_ij برش داده و به داخل Á_ik الصاق نماییم، بنابراین یک جواب دیگر برای S_ij با تعداد فعالیت‌های بیشتری از A_ij تولید می‌شود. از آنجا که فرض کردیم A_ij یک جواب بهینه است، به یک تناقض رسیده ایم. به طور مشابه اگر جواب Á_kj برای s_kj را با فعالیت‌های بیشتر از A_kj می‌داشتیم، می‌توانستیم A_kj را با Á_kj جایگزین کنیم تا یک جواب با فعالیت‌های بیشتری از A_ij تولید نماییم.

اکنون از زیر ساختار بههینه خود استفاده کرده تا نشان دهیم که می‌توانیم یک جواب بهینه برای مسئله از روی جواب‌های بهینه زیر مسائل بسازیم. مشاهده کردم که هر جواب برای یک زیر مسئله غیر تهی s_ij شامل فعالیت a_k است و آنکه هر جواب بهنه در درون خود شامل جواب‌های بهینه نمونه زیر مسئله‌های s_ik و s_kj می‌باشد. بنابراین، می‌توانیم یک زیر مجموعه با ماکزیمم اندازه از فعالیت‌های متقابلاً سازگار درS_ijبسازیم. با تقسیم مسئله به دو زیرمسئله (یافتن زیر مجموعه‌های با ماکزیمم اندازه از فعالیت‌های متقابلا سازگار در s_ikو s_kj) و پیداکردن زیرمجموعه‌های با ماکزیمم اندازه A_ik و A_kjاز فعالیت‌های متقابلا سازگار برای این زیر مسائل وسپس تشکیل زیر مجموعه A_ij با ماکزیمم اندازه شامل فعالیت‌های متقابلا سازگار بصورت A_ik υ {a_k } υ A_kj=A_ij یک جواب بهینه برای کل مسئله یک جواب برای S۰،n+۱ است.
 

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

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

الگوریتم حریصانه همانند روش‌های پویا اغلب برای حل مسائل بهینه سازی مورد استفاده قرار می‌گیرد. در شیوه حریصانه در هر مرحله عنصری که بر مبنای معیاری معین ((بهترین))به نظر می رسد، بدون توجه به انتخاب هایی که قبلا انجام شده یا در آینده انجام خواهد شد،انتخاب می شود. الگوریتم های حریصانه اغلب راه حل های ساده ای هستند.در روش حریصانه برخلاف روش پویا ، مسأله به نمونه های کوچک تر تقسیم نمی شود.

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

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

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

فرض کنید یک مجموعهٔ s={a_۱،a_۲،….a_n} از n فعالیت پیشنهادی داریم که می خواهند از یک منبع استفاده نمایند، مانند یک تالار سخنرانی که در یک زمان می‌تواند تنها مورد استفادهٔ یک فعالیت قرار گیرد. هر فعالیت a_i دارای زمان شروع s_i و زمان خاتمهٔ f_i است به طوری که ۰≤s_i

F_۰≤f_۱≤f_۲≤…≤f_n≤f_n+۱ ادعا می کنیم که s_ij=ᴓ هرگاه i≥j باشد. فرض کنید یک فعالیت a_k€s_ij برای i≥j وجود دارد به طوری که a_i بعد از a_j در ترتیب مرتب قرار دارد. پس خواهیم داشت f_i≤s_k

اکنون فرض کنید جواب A_ij برای s_ij شامل فعالیت a_k می‌باشد.پس جواب‌های A_ik برای s_ik و A_kjبرای s_kj که در این جواب بهینه برای s_ij استفاده می‌شوند نیز باید بهینه باشند. بحث برش – و – الصاق معمول در این مورد بکار می‌رود. اگر یک جواب Á_ik برای s_ik می‌داشتیم که شامل فعالیت‌های بیشتری از Aik می‌بود، می‌توانستیم A_ik را از داخل A_ij برش داده و به داخل Á_ik الصاق نماییم، بنابراین یک جواب دیگر برای S_ij با تعداد فعالیت‌های بیشتری از A_ij تولید می‌شود. از آنجا که فرض کردیم A_ij یک جواب بهینه است، به یک تناقض رسیده ایم. به طور مشابه اگر جواب Á_kj برای s_kj را با فعالیت‌های بیشتر از A_kj می‌داشتیم، می‌توانستیم A_kj را با Á_kj جایگزین کنیم تا یک جواب با فعالیت‌های بیشتری از A_ij تولید نماییم.

اکنون از زیر ساختار بههینه خود استفاده کرده تا نشان دهیم که می‌توانیم یک جواب بهینه برای مسئله از روی جواب‌های بهینه زیر مسائل بسازیم. مشاهده کردم که هر جواب برای یک زیر مسئله غیر تهی s_ij شامل فعالیت a_k است و آنکه هر جواب بهنه در درون خود شامل جواب‌های بهینه نمونه زیر مسئله‌های s_ik و s_kj می‌باشد. بنابراین، می‌توانیم یک زیر مجموعه با ماکزیمم اندازه از فعالیت‌های متقابلاً سازگار درS_ijبسازیم. با تقسیم مسئله به دو زیرمسئله (یافتن زیر مجموعه‌های با ماکزیمم اندازه از فعالیت‌های متقابلا سازگار در s_ikو s_kj) و پیداکردن زیرمجموعه‌های با ماکزیمم اندازه A_ik و A_kjاز فعالیت‌های متقابلا سازگار برای این زیر مسائل وسپس تشکیل زیر مجموعه A_ij با ماکزیمم اندازه شامل فعالیت‌های متقابلا سازگار بصورت A_ik υ {a_k } υ A_kj=A_ij یک جواب بهینه برای کل مسئله یک جواب برای S۰،n+۱ است.