الگوریتم های Greedy نوعی استراتژی الگوریتمی هستند که انتخاب بهینه را در هر مرحله با امید به یافتن بهینه سازی جهانی انجام می دهد، آنها به طور گسترده در حل مشکلات بهینه سازی مورد استفاده قرار می گیرند که در آن تصمیمات محلی منجر به یک راه حل بهینه در سطح جهانی می شوند.این مقاله مفهوم الگوریتم های حریص را بررسی می کند، نمونه های عملی را ارائه می دهد و نشان می دهد که چگونه محاسبات مرتبط را انجام دهند.

الگوریتم های گرانه چه هستند؟

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

نمونه های عملی

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

محاسبه ها و اجرای

مشکل تغییر سکه را در نظر بگیرید که هدف آن تغییر برای مقدار معینی با استفاده از کوچکترین سکه ها است، فرض کنید که رمزهای سکه 1، 5، 10 و 25 سنت هستند و مقدار هدف 63 سنت است. رویکرد حریص شامل انتخاب بزرگترین سکه کمتر یا مساوی با مقدار باقی مانده در هر مرحله است.

محاسبه مرحله به مرحله:

  • 25 سنت را انتخاب کنید (مزامیر: 63 - 25 = 38)
  • 25 سنت را انتخاب کنید (در حال حاضر: 38 - 25 = 13)
  • 10 سنت را انتخاب کنید (در حال حاضر: 13 تا 10 = 3
  • ۱ درصد را انتخاب کنید (مزامیر: ۳-۱ = ۲)
  • ۱- ۱ درصد را انتخاب کنید (متوجه: ۲-۱ = ۱)
  • ۱ درصد را انتخاب کنید (اول: ۱-۱ = ۰)

مجموع سکه های مورد استفاده: 6.