الگوریتم حریص چیست: مثال ، برنامه ها ، محدودیت ها و موارد دیگر

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

برنامه تحصیلات تکمیلی: توسعه کامل وب پشته

الگوریتم حریص چیست؟

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

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

پیچیدگی زمان اجرا مرتبط با یک راه حل حریص بسیار منطقی است. با این حال ، شما می توانید یک راه حل حریص را فقط در صورتی که بیانیه مشکل از دو ویژگی ذکر شده در زیر پیروی کند ، پیاده سازی کنید:

• خاصیت انتخاب حریص: انتخاب بهترین گزینه در هر مرحله می تواند به یک راه حل بهینه جهانی (کلی) منجر شود.
• زیر ساخت بهینه: اگر یک راه حل بهینه برای مشکل کامل شامل راه حل های بهینه برای زیرزمین ها باشد ، مشکل دارای یک زیر ساخت بهینه است.

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

مراحل ایجاد یک الگوریتم حریص

با پیروی از مراحل ذکر شده در زیر ، شما می توانید یک راه حل حریص را برای بیانیه مشکل داده شده تدوین کنید:

• مرحله 1: در یک مشکل معین ، بهترین زیر ساخت یا زیرزمین را پیدا کنید.
• مرحله 2: تعیین کنید که راه حل شامل چه مواردی خواهد بود (به عنوان مثال ، بزرگترین مبلغ ، کوتاهترین مسیر).
• مرحله 3: برای پیشبرد همه زیرنویس ها و ایجاد یک راه حل بهینه ، یک فرآیند تکراری ایجاد کنید.

دوره جدید: توسعه کامل پشته برای مبتدیان

بیایید یک مشکل در دنیای واقعی را برطرف کنیم و یک راه حل حریص را برای آن تهیه کنیم.

مشکل: الکس فردی بسیار شلوغ است. او زمان T را برای انجام کارهای جالب اختصاص داده است. او می خواهد در این زمان اختصاص یافته T. تا آنجا که ممکن است کارهای زیادی انجام دهد. برای این کار ، وی آرایه ای از جدول زمانی را برای تکمیل لیستی از موارد موجود در برنامه سفر خود ایجاد کرده است.

اکنون ، در اینجا باید بفهمیم که الکس در زمان T او چه چیزهایی را می تواند انجام دهد.

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

• آرایه A را به ترتیب صعودی مرتب کنید.
• یک بار یک زمان را انتخاب کنید.
• پس از انتخاب Timestamp ، مقدار Timestamp را به Current_Time اضافه کنید.
• شماره_ف_ته ها را با یک افزایش دهید.
• مراحل 2 تا 4 را تکرار کنید تا مقدار فعلی_ زمان به T برسد.

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

بیانیه مشکل: بهترین مسیر را برای رسیدن به شهر مقصد از نقطه شروع داده شده با استفاده از یک روش حریص پیدا کنید.

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

• از راس منبع شروع کنید.
• یک راس را در یک زمان با حداقل وزن لبه (فاصله) از راس منبع انتخاب کنید.
• اگر لبه اتصال یک چرخه را تشکیل ندهد ، راس انتخاب شده را به یک ساختار درخت اضافه کنید.
• تا زمانی که به راس مقصد برسید ، حاشیه حاشیه های مجاور را به درخت اضافه کنید.

انیمیشن ارائه شده در زیر توضیح می دهد که چگونه مسیرها برای رسیدن به شهر مقصد انتخاب می شوند.

دوره کامل توسعه دهنده وب پشته

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

عوامل ذکر شده در زیر محدودیت های یک الگوریتم حریص است:

1. الگوریتم حریص بر اساس اطلاعات موجود در هر تکرار ، بدون در نظر گرفتن مشکل گسترده تر ، قضاوت می کند. از این رو بهترین پاسخ برای هر مشکلی ایجاد نمی کند.
2. بخش مشکل ساز برای یک الگوریتم حریص ، تجزیه و تحلیل دقت آن است. حتی با وجود راه حل مناسب ، نشان دادن دلیل دقیق آن دشوار است.
3. مشکلات بهینه سازی (الگوریتم Dijkstra) با لبه های نمودار منفی با استفاده از یک الگوریتم حریص قابل حل نیست.

با حرکت به جلو ، بیایید به برخی از برنامه های یک الگوریتم حریص نگاه کنیم.

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

در زیر چند برنامه کاربردی الگوریتم حریص وجود دارد:

• مورد استفاده برای ساخت حداقل درختان پوششی: الگوریتم های پریم و کروسکال که برای ساخت حداقل درختان پوشانده استفاده می شوند ، الگوریتم های حریص هستند.
• برای اجرای رمزگذاری هافمن مورد استفاده قرار می گیرد: از یک الگوریتم حریص برای ساختن یک درخت هافمن استفاده می شود که یک تصویر ، صفحه گسترده یا فیلم را در یک فایل فشرده شده بدون ضرر فشرده می کند.
• برای حل مشکلات بهینه سازی مورد استفاده قرار می گیرد: نمودار - رنگ آمیزی نقشه ، نمودار - پوشش راس ، مشکل کوله پشتی ، مشکل برنامه ریزی شغلی و مشکل انتخاب فعالیت ، مشکلات بهینه سازی کلاسیک با استفاده از یک الگوریتمی حریص حل می شوند.

خصوصیات یک روش حریص

روش حریص روشی ساده و ساده برای حل مشکلات بهینه سازی است. این شامل انتخاب محلی بهینه در هر مرحله با امید به یافتن بهینه جهانی است. مزیت اصلی روش حریص این است که اجرای و درک آن آسان است. با این حال ، همیشه پیدا کردن بهترین راه حل تضمین نمی شود و می تواند بسیار کند باشد.

روش حریص با انجام انتخاب محلی بهینه در هر مرحله به امید یافتن بهینه جهانی کار می کند. این کار را می توان با به حداقل رساندن یا به حداکثر رساندن عملکرد هدف در هر مرحله انجام داد. مزیت اصلی روش حریص این است که اجرای و درک آن نسبتاً آسان است. با این حال ، استفاده از این روش برخی از مضرات وجود دارد. اول ، روش حریص برای یافتن بهترین راه حل تضمین نمی شود. دوم ، می تواند کاملاً کند باشد. سرانجام ، اغلب اثبات اینكه روش حریص در واقع بهینه جهانی را پیدا خواهد كرد ، دشوار است.

یکی از مشهورترین نمونه های روش حریص ، مشکل کوله پشتی است. در این مشکل به ما مجموعه ای از موارد داده می شود که هرکدام دارای وزن و ارزش هستند. ما می خواهیم زیر مجموعه مواردی را پیدا کنیم که ضمن به حداقل رساندن وزن ، مقدار را به حداکثر می رساند. روش حریص به سادگی در هر مرحله مورد را با بالاترین مقدار در نظر می گیرد. با این حال ، این ممکن است بهترین راه حل نباشد. به عنوان مثال ، مجموعه موارد زیر را در نظر بگیرید:

مورد 1: وزن = 2 ، مقدار = 6

مورد 2: وزن = 2 ، مقدار = 3

مورد 3: وزن = 4 ، مقدار = 5

روش حریص مورد 1 و مورد 3 را برای مقدار کل 11 می گیرد. بهترین راه حل.

نمونه های بسیاری دیگر از روش حریص وجود دارد. مشهورترین مورد احتمالاً الگوریتم برنامه نویسی هافمن است که برای فشرده سازی داده ها استفاده می شود. در این الگوریتم مجموعه ای از نمادها به ما داده می شود که هر کدام دارای وزن هستند. ما می خواهیم زیر مجموعه نمادهایی را پیدا کنیم که طول متوسط کد را به حداقل می رساند. روش حریص به سادگی نماد را با کمترین وزن در هر مرحله می گیرد. با این حال ، این ممکن است بهترین راه حل نباشد. به عنوان مثال ، مجموعه زیر از نمادها را در نظر بگیرید:

نماد 1: وزن = 2 ، کد = 00

نماد 2: وزن = 3 ، کد = 010

نماد 3: وزن = 4 ، کد = 011

روش حریص نماد 1 و نماد 3 را برای وزن کامل 6 می گیرد. با این حال ، راه حل بهینه گرفتن نماد 2 و نماد 3 ، برای وزن کامل 7 است. بنابراین ، روش حریص همیشه پیدا نمی کندبهترین راه حل.

روش حریص روشی ساده و ساده برای حل مشکلات بهینه سازی است. با این حال ، همیشه پیدا کردن بهترین راه حل تضمین نمی شود و می تواند بسیار کند باشد. هنگام استفاده از روش حریص ، مهم است که این معایب را در ذهن داشته باشید.

اجزای الگوریتم حریص

چهار مؤلفه اصلی برای هر الگوریتم حریص وجود دارد:

1. مجموعه ای از راه حل های نامزد (که به طور معمول به عنوان نمودار نشان داده می شود)
2. روشی برای رتبه بندی نامزدها با توجه به برخی معیارها
3. عملکرد انتخابی که با توجه به رتبه بندی ، بهترین نامزد را از مجموعه انتخاب می کند
4. روشی برای "هرس" مجموعه نامزدها ، به طوری که هیچ راه حلی را که بدتر از آن است که قبلاً انتخاب کرده است ، ندارد.

دو مؤلفه اول ساده هستند - راه حل های نامزد می توانند هر چیزی باشند ، و معیارهای رتبه بندی نیز می تواند هر چیزی باشد. عملکرد انتخاب معمولاً فقط موضوع انتخاب نامزد با بالاترین رتبه است.

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

دوره کامل توسعه دهنده Java Stack

کد شبه الگوریتم های حریص

یک نمونه از کد شبه برای یک الگوریتم حریص در زیر آورده شده است:

// جریان فعلی = حالت اولیه مشکل در حالی که (جریان فعلی! = هدف هدف)retu currentState;>

کد شبه فوق ساختار اصلی یک الگوریتم حریص را نشان می دهد. اولین قدم تنظیم وضعیت فعلی به حالت اولیه مشکل است. در مرحله بعد ، ما حلقه می زنیم تا وضعیت فعلی برابر با حالت هدف باشد. در داخل حلقه ، حالت بعدی را انتخاب می کنیم که می خواهیم به آن حرکت کنیم. این کار با استفاده از تابعی به نام cheledextState () انجام می شود. سرانجام ، ما وضعیت فعلی را با دولت بعدی که تازه انتخاب کرده ایم برابر است و به حالت هدف بازگردیم.

کد شبه برای عملکرد انتخاب شده () در زیر آورده شده است:

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

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

مضرات استفاده از الگوریتم های حریص

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

نتیجه

در این مقاله الگوریتم حریص ، شما یاد گرفتید که یک الگرافیک برنامه نویسی حریص چیست و خواص و مراحل ساخت یک راه حل حریص را کشف کرده اید. در این مقاله همچنین برنامه ها مورد بحث قرار گرفته و محدودیت های الگوریتم حریص را ذکر می کند. شما همچنین نمونه ای از این الگوریتم را دیدید که به درک مفهوم کمک می کند. اگر می خواهید یک روش سریع و آسان برای درک الگوریتم حریص الگوریتمی ، ما به شما توصیه می کنیم این فیلم را تماشا کنید: https://youtu. be/ilywrsp7zzk.

هر روز ، محصولات ، ابزارها و برنامه های جدید وارد بازار می شوند. و صدها زبان و چارچوب برنامه نویسی هر روز در حوزه توسعه نرم افزار مورد استفاده قرار می گیرد. از این رو ، برای شما بسیار مهم است که از مفاهیم ساختار داده فراتر بروید و پایه های توسعه برنامه تعاملی را پوشش دهید. دوره های توسعه نرم افزار SimpleLea بستر مناسبی را برای شما فراهم می کند تا بتوانید هنر توسعه نرم افزار را تسلط دهید. دوره های موجود در این کاتالوگ می تواند به شما در بهبود شانس خود در تبدیل شدن به یک توسعه دهنده نرم افزار کمک کند. بنابراین ، پیش بروید و شروع به کاوش کنید!

اگر در مورد این مقاله در مورد الگوریتم حریص ، سؤالی دارید ، لطفاً آنها را در کادر نظرات در انتهای این صفحه بگذارید. ما در سریعترین زمان با پاسخ ها برمی گردیم.

درباره نویسنده

عنبر بوچ

Amber Butch بنیانگذار OneVisibility است و از سال 2005 به عنوان نویسنده مستقل و بازاریاب دیجیتال فعالیت می کند. به عنوان یک بازاریاب دیجیتال فصلی ، او در پشت این واقعیت ایستاده است که محتوا هنگام افزایش آگاهی و وفاداری برند ، پادشاه است.