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

در الگوریتم های حریصانه از یک جواب تهی شروع کرده و با تخصیص مقادیر به متغیرهای تصمیم در هر مرحله، سعی در به دست آوردن یک جواب کامل می شود. تخصیص مقدار برای هر متغیر در الگوریتم های حریصانه با تعریف یک مجموعه عناصر برای ایجاد جواب آغاز می شود. یک جواب از مسئله با انتخاب عناصر این مجموعه برای متغیرها به دست می آید. در هر گام از الگوریتم های حریصانه یکی از عناصر با کمترین هزینه از بین مجموعه عناصر تخصیص داده نشده برای اضافه شدن به جواب جزیی انتخاب می شود. جستجوی حریصانه یا نزدیک بینانه در هر مرحله بهترین انتخاب از عناصر جواب را بدون در نظرگرفتن این که این انتخاب در آینده چه تبعاتی دارد انجام می دهند.
به عبارتی در جستجوی حریصانه همیشه حرکتی که به جواب بهینه محلی که به کمترین مقدار افزایش در تابع ارزیابی جواب منجر می شود، انجام می گردد. تنها در مسائل خاصی می توان الگوریتم حریصانه ارائه کرد که همواره جواب بهینه تولید کند. (نائبی و کیانفر، 1391)
الگوريتم   حريصانه يک الگوريتم جستجوگر است که براي حل مسائل بهينه سازي به کار مي رود. اين الگوريتم به ترتيب عناصر داده ها را گرفته و هر بار عنصري را که طبق يک معيار معين، "بهترين" است، بدون توجه به انتخاب هاي قبلي و انتخاب هاي آينده، برمي گزيند. الگوريتم حريصانه غالبًا به راه حل هايي بسيار ساده و کار آمد منجر مي شود.
در الگوريتم حريصانه با انجام يک سري انتخاب، بهينه سازي انجام می شود. هر يک از انتخاب هاي انجام شده در طي اجراي الگوريتم، در لحظه انتخاب، بهترين گزينه به نظر مي رسند، يعني در واقع انتخاب صورت گرفته در آن لحظه بهينه است. هدف نهايي الگوريتم دست يابي به يک حل بهينه سرتاسري است. (جلالی و حسینی ، 1388)

مراحل اجراي الگوريتم حريصانه

در الگوريتم حريصانه ابتدا يک مجموعه تهي از نقاط متناظر با جواب ها به صورت اوليه تشکيل مي شود، سپس براي حل مسئله بهينه سازي سه مرحله اصلي زير انجام مي گيرد
الف-فرآيند انتخاب: الگوريتم در اين مرحله عنصر بعدي را که بايد به مجموعه اضافه شود، انتخاب مي کند. انتخاب طبق يک ملاک حريصانه انجام مي شود که يک شرط بهينه را در همان مرحله برآورده مي سازد.
ب-فرآيند امکان سنجي: در اين مرحله امکان پذيري مجموعه جديد براي رسيدن به حل نهايي بررسي مي شود.
ج-بررسي راه حل: در اين مرحله تعيين مي شود که آيا مجموعه جديد، حل مورد نظر را ارائه مي کند يا خير.
در زير، الگوريتم حريصانه با يک مثال ساده تشريح مي شود. فروشندگان کالا پس از فروش کالا و دريافت پول معمو لا براي پس دادن بقيه پول به خريداران دچار مشکل مي شوند. زيرا مشتريان مايل نيستند مقدار زيادي پول خرد دريافت کنند. بنابراين هدف فروشندگان نه تنها پس دادن بقيه پول به ميزان صحيح، بلکه انجام اين کار با حداقل تعداد اسکناس يا سکه ممکن است. براي سادگي فرض مي شود که مابقي پولي که فروشنده بايد به مشتري پس دهد تنها از نوع سکه باشد.
بنابراين حل اين مسئله عبارت است از مجموعه اي از سکه ها که جمع آن ها معادل بقيه پول مشتري باشد. حل بهينه همين مجموعه با حداقل تعداد سکه ها انجام مي شود. روش حريصانه براي اين مسئله به اين صورت است. در آغاز هيچ سکه اي در مجموعه جواب وجود ندارد. لذا ابتدا بزرگ ترين سکه از نظر ارزش بهينه محلي انتخاب مي شود. اين کار در الگوريتم حريصانه "فرآيند انتخاب" ناميده می شود.
در مرحله بعد بايد ديد که آيا با افزودن سکه بعدي که باز هم به صورت حريصانه انتخاب شده و داراي بيشترين ارزش ممکن است، جمع کل ارزش سکه ها از مجموع پولي که فروشنده بايد پس بدهد بيشتر مي شود يا خير؟ اين کار در الگوريتم حريصانه "فرآيند امکان سنجي" ناميده مي شود. اگر ارزش مجموع سکه ها از ميزان مورد نظر کمتر بود اين سکه به مجموعه سکه ها اضافه شده و ميزان مجموع سکه ها با مقدار مورد نظر مقايسه مي شود. اين عمل "بررسي راه حل" ناميده مي شود. روال انتخاب پي در پي تکرار مي شود تا مجموع سکه ها با ميزان پول مورد نظر براي پس دادن به مشتري برابر شود. اين فرآيند را يک فرآيند "حريصانه" مي نامند زيرا روال انتخاب صرفًا شامل در نظر گرفتن و انتخاب حريصانه ي بزرگترين سکه بعدي است. از ميان روش هايي که براي اجراي فرآيندهاي فوق در يک الگوريتم حريصانه ارائه شده است، يکي از مهمترين و بهترين روش ها، روش ديکسترا است که بر روي يک گراف وزن دار و جهت دار اجرا مي شود. (جلالی و حسینی، 1388)

  • تهران
  • 09350579640-09124635768
  • 01152218786
  • این آدرس ایمیل توسط spambots حفاظت می شود. برای دیدن شما نیاز به جاوا اسکریپت دارید

ارسال پیام

  Mail is not sent.   Your email has been sent.
Top