تفاوت میان نسخه‌های «الگوریتم حریصانه»

'''روش حریصانه''' ((/Greedy (/ˈɡriːdi) یکی از روش‌های مشهور و پرکاربرد طراحی الگوریتم‌ها است که با ساختاری ساده در حل بسیاری از مسائل استفاده می‌شود. این روش اغلب در حل مسائل [[بهینه‌سازی برنامه|بهینه‌سازی]] استفاده شده و در پاره‌ای مواقع جایگزین مناسبی برای روش‌هایی مانند [[برنامه‌ریزی پویا]] است. در حالت کلی این روش سرعت و مرتبهٔ اجرایی بهتری نسبت به روش‌های مشابه خود دارد؛ اما متناسب با مسئله ممکن است به یک جواب بهینهٔ سراسری ختم نشود. این دسته از الگوریتم‌ها در [[علوم رایانه]] کاربرد وسیعی دارند.
 
[[پرونده:Greedy-search-path-example.gif|جایگزین=جست و جوی حریصانه|بندانگشتی|233x233پیکسل|جست و جوی حریصانه]]
 
در روش حریصانه رسیدن به هدف در هر گام مستقل از گام قبلی و بعدی است. یعنی در هر مرحله برای رسیدن به هدف نهایی، مستقل از این که در مراحل قبلی چه انتخاب‌هایی صورت گرفته و انتخاب فعلی ممکن است چه انتخاب‌هایی در پی داشته باشد، انتخابی که در ظاهر بهترین انتخاب ممکن است صورت می‌پذیرد. به همین دلیل است که به این روش، روش حریصانه گفته می‌شود. به طور مثال زمانی که یک دزد عجول و حریص وارد خانه‌ای می‌شود، در مسیر حرکت خود هر وسیله و کالای با ارزشی را داخل کیسه می‌اندازد. وی در این حالت چندان توجهی نمی‌کند که چه اشیائی را قبلاً برداشته و ممکن است در آینده چه اشیاء گرانبهاتری به دست آورد. او در هر گام تنها از بین اشیاء دم دست خود با ارزش‌ترین آن را انتخاب کرده و به وسایل قبلی اضافه می‌کند.
 
در بسیاری از موارد مسئله به‌طور مستقیم یا غیر مستقیم از ما می‌خواهند که یک [[متغیر]] را [[کمینه]] یا [[بیشینه]] کنیم. در اکثر مسائل از این دست ما باید تعدادی انتخاب انجام دهیم و مسئله در تعدادی مرحله حل شود. بازهٔ وسیعی از این مسائل توسط الگوریتم‌های حریصانه قابل حل هستند. <ref>{{پک|ابراهیم علایی فرادنبه - محمدرضا علایی|۱۳۹۲|ک=طراحی الگوریتم ایران|ص=258}}</ref>
 
 
== تاریخچه ==
 
درواقع شباهت دو دنباله بزرگ‌ترین عددی مثل xxx است که xxx عضو اول ابتدای هر دو دنباله با هم یکسان باشد.
 
 
== محدودیت‌های الگوریتم حریصانه ==
 
[[پرونده:Greedy-search-path-example.gif|جایگزین=جست و جوی حریصانه|بندانگشتی|233x233پیکسل|جستپیدا وکردن جویبزرگ‌ترین مسیر در گراف وزن‌دار با استفاده از روش حریصانه]]
 
چون روش این الگوریتم گرفتن بهترین تصمیم در هر مرحله است، در بسیاری از موارد به راه‌حل بهینه سراسری ختم نمی‌شود. عمده مسائلی که این الگوریتم به جواب درست منتج نمی‌شود، مسائل مربوط به گراف‌های وزن‌دار است؛ مثل [[مسئله فروشنده دوره‌گرد]] یا پیدا کردن بزرگ‌ترین مسیر در گراف وزن‌دار.
۱۰۸

ویرایش