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

روش حریصانه (Greedy (/ˈɡri:di/)) یکی از روش‌های مشهور و پرکاربرد طراحی الگوریتم‌ها است که با ساختاری ساده در حل بسیاری از مسائل استفاده می‌شود. این روش اغلب در حل مسائل بهینه‌سازی استفاده شده و در پاره‌ای مواقع جایگزین مناسبی برای روش‌هایی مانند برنامه‌ریزی پویا است. در حالت کلی این روش سرعت و مرتبهٔ اجرایی بهتری نسبت به روش‌های مشابه خود دارد؛ اما متناسب با مسئله ممکن است به یک جواب بهینهٔ سراسری ختم نشود. این دسته از الگوریتم‌ها در علوم رایانه کاربرد وسیعی دارند.

این الگوریتم در هر مرحله، انتخاب بهینه را انجام می دهد تا بتواند راه بهینه برای حل کل مسئله را بیابد. در سایت های فارسی، نام این الگوریتم را حریصانه ترجمه کرده اند ولی من ترجیح می دهم با همان Greedy ادامه بدهم. الگوریتم‌های Greedy در برخی مشکلات کاملاً موفق هستند، مانند کدگذاری هافمن (Huffman encoding) که برای فشرده‌سازی داده‌ها استفاده می‌شود، یا الگوریتم Dijkstra که برای یافتن کوتاه‌ترین مسیر از طریق یک گراف استفاده می‌شود.

الگوریتم Greedy دارای 5 جز است:

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

درس طراحی الگوریتم یکی از دروس مهم رشته کارشناسی کامپیوتر است که یادگیری آن نسبتا سخت است.

در زیر جزوه ای از  این بخش گردآوری شده است.

نویسنده : حمید کمیزی