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

[kluivert]

سلام
میشه در مورد الگوریتم حریصانه توضیح کامل بدین؟

[Reyhane7]

الگوریتم حریصانه ، به ترتیب عناصر را گرفته ، هر بار آن عنصری را که طبق ملاکی معین ”بهترین“ به نظر می رسد، بدون توجه به انتخاب هایی که قبلا انجام داده یا در آینده انجام خواهد داد، بر می دارد.

الگوریتم حریصانه ، همانند برنامه نویسی پویا غالبا برای حل مسائل بهینه سازی به کار می روند، ولی روش حریصانه صراحت بیشتری دارد.

در روش حریصانه ، تقسیم به نمونه های کوچک تر صورت نمی پذیرد.

الگوریتم حریصانه با انجام یک سری انتخاب، که هر یک در لحظه ای خاص ،بهترین به نظر می رسد عمل می کند، یعنی انتخاب در جای خود بهینه است.امید این است که یک حل بهینه سرتاسری یافت شود، ولی همواره چنین نیست.

برای یک الگوریتم مفروض باید تعیین کرد که آیا حل همواره بهینه است یا خیر.

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

1- روال انتخاب، عنصربعدی را که باید به مجموعه اضافه شود،انتخاب می کند.انتخاب طبق یک ملاک حریصانه است.
2- بررسی امکان سنجی ، تعیین می کند که آیا مجموعه جدید برای رسیدن به حل،عملی است یا خیر.
3- بررسی راه حل ، تعیین می کند که آیا مجموعه جدید ، حل نمونه را ارائه می کند یا خیر.

[Reyhane7]

الگوریتم­های حریصانه (Greedy Algorithms) :
این دسته از الگوریتم­ها برای بدست آوردن یک جواب از مسئله همواره سعی می­کنند که ساده­ترین و در عین حال پر ارزش­ترین انتخاب­ها را انجام دهند. انتخاب این گزینه­ها در هر مرحله ممکن است باعث شود مسئله به بیراهه منجر شود و الگوریتم حریصانه بهترین جواب را برای مسئله اراده نکند یا اینکه ممکن است نتواند حتی یک جواب از مسئله را بدست آورد.
ü مجموعه C: مجموعه­ای ازتمام کاندیداهای ممکن که ممکن است به عنوان جواب مسئله انتخاب شوند.
ü مجموعه S: مجموعه­ایست که درنهایت قرار است به یک جواب از مسئله منتهی شود. در ابتدا تهی بوده و در نهایت در صورت وجود جواب به یک جواب از مسئله منجر می­شود.
ü تابع Select : ورودی این تابع مجموعه C و خروجی آن عنصری از مجموعه C می­باشد.
ü بدیهی است با انتخاب عنصری از C این عنصر از مجموعه­ای از کاندید­ها یعنی C باید حذف شود. تابع Select با توجه به نوع Greedy که در مسئله تعریف می­شود عمل می­نماید.
ü تابع Solution: بررسی می­کند که مجموعه S یک جواب از مسئله است یا خیر. ورودی آن مجموعه S و خروجی آن یک مقدار Boolean می­باشد.
ü تابع Feasible: ورودی آن مجموعه S و عنصر انتخاب شده از مجموعه C بوسیله­ی تابع Select است.این تابع بررسی می­کند که ببیند آیا امکان اضافه شدن عنصر به مجموعه S وجود دارد یا خیر. نتیجه­ی این بررسی بصورت Boolean در خروجی تابع ظاهر می­شود.
توجه کنید از آنجا که شبه­کد تا زمانی تکرار می­شود که یا به جواب برسد یا مجموعه C تهی شود، هیچگاه در حلقه­ی بینهایت گیر نمی­کند، مگر آنکه مجموعه­ی انتخابی نا متناهی باشد

[Reyhane7]

مقالات و اسلايدهاي زير را نيز دانلود کنيد:


روش حریصانه (Greedy) (http://qompnu.ac.ir/uploads/1_27_chapter51.ppt)


الگوريتم حريصانه (http://ce.kashanu.ac.ir/vahidipour/Alg/Resource/Chapter-4-I.ppt)



Greedy Algorithms (http://www.cis.upenn.edu/%7Ematuszek/cit594-2007/Lectures/39-greedy.ppt)