روش حریصانه

روش حریصانه

روش حریصانه مقاله ای مناسب در قالب وورد با 37 صفحه مفید و مجزا

 

نمونه متن :

 

مقدمه

روش كلي :

          شايد روش حريصانه صريح ترين تكنيك طراحي باشد . اين شيوه مي تواند براي حل طيف وسيعي از مسائل گوناگون بكار رود . اغلب اين مسائل ، نه همه آنها n ورودي دارند و ما را وادار به پيدا كردن زير مجموعـه اي با بعضي محدوديت ها مي كنند . هر زير مجموعه اي كه اين شرايط و محدوديت ها را دارا باش ديك جواب ممكن ناميده مي شود . در اينجا لازم است جواب ممكني پيدا شو دكه مقدار يك تاج مقصود را حداقل يا حداكثر مي كند . اين جواب ، يك جواب بهينه ناميده مي شود . معمولا روش واضحي براي تعيين يك جواب ممكن اما نه لزوما جواب بهينه وجود دارد . شخصيت كلاسيك چارلز ديكنز ، ابنزراسكروج ، شايد حريص ترين فردي باش دكه تا كنون در خيال يا واقعيت ديده ايم . به خاطر داريدكه اسكروج هرگز به آينده يا گذشته نمي انديشيد . هر روز تنها انگيزه اي كه داشت چنگ آوردن طلاي بيشتر بود . پس از آنكه عيد پارسال او را به ياد سال گذشته انداخت و عيد سال بعد او را از سال آينده آگاه ساخت به روش آزمندانه خود پايان داد .

          الگوريتم حريصانه نيز به شيوه اسكروج عمل مي كند . يعني به ترتيب عناصر داده ها را گرفته هر بار آن عنصري را كه طبق ملاكي معين «بهترين» به نظر مي رسد بدون توجه به انتخاب هايي كه قبلا انجام داده يا در آينده انجام خواهد داد ، بر مي دارد . بنابراين احساس بوجود آيد كه الگوريتم هاي حريصانه مشكل دارند زيرا اسكروج و واژه «حريصانه» بار معنايي منفي دارند . زيرا اين الگوريتم ها غالبا به راه حلهايي بسيار ساده و كارآمد منجر مي شوند .

 

 

روش حريصانه (Greedy)

 روش حريصانه پيشنهاد مي كند كه مي توان الگوريتمي نوشت كه به صورت مرحله اي عمل كند و در هر زمان يك ورودي را بررسي كند . در هر مرحله تصميم گيري مي شو دكه يك ورودي مشخص به فرد جزء جواب بهينه است يا خير . اين كار با بررسي وروديها به ترتيب تعيين شده به وسيله روال انتخاب انجام مي شود . اگر نتيجه افزودن ورودي بعدي به جواب بهينه نا تمام يك مقدار غير ممكن باشد اين ورودي به جواب ناتمام افزوده نمي شود . در غير اين صورت اين ورودي افزوده مي شود ، روال انتخاب خود بر مبناي معيار بهينه سازي خاصي استوار است . اين معيار تابع مقصود باشد .

          الگوريتمهاي حريصانه ، همانند برنامه نويسي پويا غالبا براي حل مسائل بهينه‌سازي به كار مي روند . ولي روش حريصانه ، صراحت بيشتري دارد . در برنامه نويسي پويا ، ا ز يك ويژگي پويا براي تقسيم نمونه اي به نمونه هاي كوچكتر استفاده مي‌شود . در روش حريصانه ، تقسيم به نمونه هاي كوچكتر صورت نمي گيرد . الگوريتم حريصانه با انجام يك سري انتخاب ، كه هر يك در لحظه اي خاص ، بهترين به نظر مي رسد عمل مي كند ، يعني انتخاب در جاي خود بهينه است . اميد اين است كه در يك حل بهينه سرتاسري يافت شود ولي همواره چنين نيست . براي يك الگوريتم مفروض بايد تعيين كرد كه آيا حل همواره بهينه سرتاسري يافت شود ولي همواره چنين نيست . براي يك الگوريتم مفروض بايد تعيين كرد كه آيا حل همواره بهينه است يا خير . با يك مثال ساده روش حريصانه را نشان مي دهيم . جو كه فروشنده يك فروشگاه است غالبا براي دادن بقيه پول به خريدار ، دچار مشكل مي شود . مشتريان معمولا مايل نيستند مقدار زيادي پول خرد بگيرند . براي مثال اكثر مشتريان اگر براي بقيه پول خود كه 78% دلار است ، 87 سكه يك سنتي دريافت كنند عصباني مي شوند . بنابراين هدف ولي نه تنها دادن بقيه پول به ميزان صحيح ، بلكه انجام اين كار با حداقل تعداد سكه ممكن است . يك حل براي نمونه اي از اين مسند عبارت از مجموعه اي از سكه هاست كه جمع آنها معادل بقيه پول مشتري شده حل بهينه همين مجموعه با حداقل تعداد سكه ها انجام مي شود . روش حريصانه براي اين مسند به شيوه اي كه در ادامه خواهد آمد پيش مي رود . در آغاز هيچ سكه اي در مجموعه نداريم . جو بزرگترين سكه را از لحاظ ارزش پيدا مي كند . يعني مدرك   و براي اينكه كدام سكه بهترين است (بهينه محلي) ارزش سكه است . اين را در الگوريتم حريصانه ، روال انتخاب مي نامند . سپس بايد ببيند كه آيا افزودن اين سكه به بقيه پول ، جمع كل آنها از چيزي كه بايد باشد ، بيشتر مي رود يا خير . اين را در الگوريتم حريصانه ، روال انتخاب مي نامند . اين را در الگوريتم حريصانه تحقيق عملي بودن مي نامند . اگر با افزودن اين سكه بقيه پول ، از ميزان لازم بيشتر نشود اين سكه به مجموعه افزوده مي شود سپس تحقيق مي كند تا ببيند كه آيا مقدار بقيه پول با ميزان لازم برابر شده است يا خير . اين موضوع را در الگوريتم حريصانه تحقيق حل شدن مي گويند . اگر برابر نبودند با استفاد هاز روال انتخاب يك سكه ديگر انتخاب مي كند و فرايند تكرار مي شود . او چندين بار اين كار را انجام مي دهد كه مقدار با ميزان لازم برابر يا اينكه ديگر سكه اي برايش باقي نماند .

          در مورد اخير ، قادر به بازگرداندن مقدار دقيق بقيه پول نيست . يك الگوريتم سطح بالا ،‌ براي اين روال در زير خواهد آمد

While (there are more coins and instance is not solved)

{

                   crab the largest remaining coin ;

                   if (adding the coin makes the change cxceed the amount owed )

                   reject the coin ;

          else

                   add the coin to the change

                   if the total value of the change equals the amount owed)

                             the instance is solved

          }

 

          در تحقيق عملي بودن ، هنگامي كه تعيين مي كنيم كه افزودن يك سكه باعث فراتر رفتن بقيه پول از حد لازم مي شود ، در مي يابيم كه مجموعه به دست آمده از افزايش آن سكه را نمي توان براي ارائه حل براي نمونه ، كامل كرد . بنابراين ، آن مجموعه غير عملي بوده و رد مي شود . اين الگوريتم را حريصانه مي ناميم . زيرا روال انتخاب صرفا شامل گرفتن حريصانه بزرگترين سكه بعدي بدون انديشيدن به عواقب چنين انتخابي است . هيچ فرصتي براي انديشيدن دوباره به يك انتخاب نيست . هنگامي كه سكه اي پذيرفته شد ، به طور دائمي در حل گنجانده مي شود ، هنگاميكه سكه اي رد شد ، به طور دائمي از حل مطرود مي گردد . اين روال بسيار ساده است ولي به ولي آيا به حل بهينه منجر مي شود ؟ يعني در اين مسئله هنگامي كه حل آن امكان پذير است ، آيا حل فراهم آمده توسط الگوريتم ، حاوي حداقل تعداد سكه هاي مورد نياز براي دادن بقيه پول هست يا خير ؟ اگر سكه ها ، سكه هاي آمريكايي (يك سنتي ، پنج سنتي ، ده سنتي ، بيست وپنج سنتي و نيم دلاري ) باشند و اگر از هر كدام حداقل يك عدد موجود باشد ، الگوريتم حريصانه همواره در صورت وجود حل ، حل بهينه را بر مي گرداند .

          روش حريصانه را  به طور خلاصه به طريق زير مطرح مي كنيم . الگوريتم حريصانه ،‌كار را با يك مجموعه تهي آغاز كرده به ترتيب عناصري به مجموعه اضافه مي كند تا اين مجموعه حلي براي نمونه اي از يك مسئله را نشان دهد . هر دور تكرار شامل مولفه هاي زير است :

  • روال انتخاب ، عنصر بعدي را كه بايد به مجموعه اضافه شود ، انتخاب مي كند . انتخاب طبق مدرك حريصانه اجرا مي شو دكه يك شرط بهينه را در همان برآورده مي كند .
  • تحقيق عملي بودن ، تعيين مي كند كه آيا مجموعه جديد براي رسيدن به حل عملي است يا خير .
  • تحقيق حل ، تعيين مي كند كه آيا مجموعه جديد ، حل نمونه را به دست مي دهد يا خير ...

دریافت فایل


روش حریصانه

روش حریصانه,روش حریصانه چیست,تحقیق در مورد روش حریصانه,مقاله روش حریصانه

عمومی و آزاد

فایل های جدید

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