اليوم: السبت 19 يونيو 2021 , الساعة: 3:38 م


اعلانات
محرك البحث




خوارزمية جشعة أمثلة

آخر تحديث منذ 26 يوم و 8 ساعة 895 مشاهدة

اعلانات
عزيزي زائر الموقع تم إعداد وإختيار هذا الموضوع خوارزمية جشعة أمثلة فإن كان لديك ملاحظة او توجيه يمكنك مراسلتنا من خلال الخيارات الموجودة بالموضوع.. وكذلك يمكنك زيارة القسم وتصفح المواضيع المتنوعه... آخر تحديث للمعلومات بتاريخ اليوم 24/05/2021

أمثلة



مسألة الرحالة التاجر تاجر يريد أن يمر بعدد من الأحياء لبيع بضاعته. هدفه هو إيجاد المسار الأقصر الذي يمر بكل الأحياء. وفق طريقة الخوارزمية الجشعة، على التاجر أن ينظر كل مرة إلى خريطته ويسافر إلى أقرب حي لم يزره بعد.


في هذه الحالة طريقة الخوارزمية الجشعة لا تعطي بالضرورة الحل الأفضل. كما هو واضح، من الممكن أن يتجاهل التاجر حياً معيناً لأنه وجد حي آخر أقرب إليه, وأن يضطر بنهاية الأمر إلى العودة إلى هذا الحي بنهاية المسار ويسلك طريقاً أطول.


مثال آخر هو تحديد عدد القطع النقدية الأقل المطلوب لجمع 36 قطعة نقدية، حيث أن قيم القطع النقطية هم 1، 5، 10 و 20. وفق طريقة الخوارزيمة الجشعة، بكل مرحلة نختار القطعة النقدية ذات القيمة الأكبر، ولكن أقل من باقي القيمة المطلوبة لإكمال المجموع.


المواصفات


بشكل عام، للخوارزميات الجشعة خمسة عناصر هي



  1. مجموعة مرشحة يتم انشاء الحل منها

  2. اختيار الوظيفة والتي يتم من خلالها اختيار افضل مرشح لإضافته الى الحل

  3. الغرض من الوظيفة والتي تستخدم لتحديد ما إذا كان يمكن استخدام مرشح للمساهمة في الحل

  4. الهدف من الوظيفة والتي تحدد قيمة للحل او حل جزئي

  5. وظيفة الحل والتي تحدد عندما نكتشف الحل الكامل


الخوارزمية الجشعة الجشعين تنتج حلولا جيدة لبعض المسائل الرياضية ، دون غيرها. معظم المشاكل التي يطبق عليها هذه الخوارزميا لها خاصيتين

الجشع في اختيارالممتلكات يمكننا أن نجعل أي خيار يبدو أفضل في الوقت الحالي وبعد ذلك حل المشاكل الثانوية التي تنشأ فيما بعد. الاختيار المتحققة بواسطة خوارزمية الجشع قد تعتمد على الخيارات التي تحققت حتى الان، ولكن ليس على خيارات المستقبل أو جميع الحلول للمشاكل الثانوية. ذلك بشكل متكرر يجعل خيار الجشع واحدا تلو الآخر، والحد من كل مشكلة معينة في واحدة أصغر. وبعبارة أخرى، خوارزمية الجشع لا يكن ان تتراجع عن خياراتها. هذا هو الفرق الرئيسي بينها وبين البرمجة الديناميكية ، وهي شاملة ومضمونة لإيجاد الحل.


بعد كل مرحلة، البرمجة الديناميكية تتخذ القرارات على أساس كل القرارات التي اتخذت في المرحلة السابقة، وربما تعيد النظر في مسار المرحلة السابقة للخوارزمية كطريقا للحل.


البنيه الامثل المشكلة المعروضة البنيه الافضل إذا كان الحل الأمثل للمشكلة يتضمن الحلول المثلى للمشاكل فرعية. Introduction to Algorithms (Cormen, Leiserson, Rivest, and Stein) 2001, Chapter 16 Greedy Algorithms .


حالات الفشل


Greedy Glouton.svg يسار تصغير 280 تبدأ من ِA خوارزمية الجشع توجد القيمه العظمى المحليه m وتتجاهل القيمه العظمى العالميه ’M

Greedy-search-path-example يسار تصغير 280 يهدف الوصول إلى أكبر مبلغ، في كل خطوة، فإن خوارزمية الجشع اختيار ما يبدو أن يكون الخيار الأمثل ، لذلك فإنه سيتم اختيار 12 بدلا من 3 في الخطوة الثانية، ولن تصل إلى أفضل الحلول، التي يحتوي على 99

بالنسبة للعديد من المشاكل الأخرى، تفشل الخوارزميات الجشعة لإنتاج الحل الأمثل، وربما قد تنتج حلول فريدة من نوعها قد تكون أسوأ حل ممكن. ومن الأمثلة على ذلك مشكلة الرحالة التاجر رجل المبيعات المذكورة أعلاه لكل عدد من المدن، وهناك نقل المسافات بين المدن التي أقرب جار للكشف عن مجريات الأمور لتنتج أسوأ جولة محتملة فريدة من نوعها .(G. Gutin, A. Yeo and A. Zverovich, 2002)

الانواع


ويمكن وصف الخوارزميات الجشعة بأنها قصيرة النظر ، وأيضا غير قابلة للاسترداد. فهي مثالية فقط للمشاكل التي قد تكون أفضل بنية تحتية .على الرغم من هذا، لكثير من المشاكل البسيطة (مثل إعطاء التغير)، خوارزميات الأنسب هي الخوارزميات الجشعة. ومع ذلك، فمن المهم ، أن نلاحظ أن خوارزمية الجشع ويمكن استخدام كخوارزمية لتحديد ترتيب أولويات الخيارات ضمن البحث، أو فرع وقيد (التزام ) للخوارزمية. هناك عدد قليل من اشكال مختلفة لخوارزمية الجشع



  • نقى خوارزميات الجشع

  • تعامد الخوارزميات الجشعة

  • • تمهل خوارزميات الجشع


التطبيقات


الخوارزميات الجشعة في الغالب (ولكن ليس دائما) تفشل في العثور على الحل الأمثل على الصعيد الشامل(الاعم او العالمي)، لأنها عادة لا تعمل بشكل شامل على كافة البيانات. يمكنهم تقديم التزامات لبعض الخيارات في وقت مبكر جدا والتي تمنعهم من العثور على أفضل حل شامل في وقت لاحق. على سبيل المثال، الخوارزميات التلوين الجشع المعروفة لمشكلة التلوين لرسم البياني ولجميع المشاكل NP-Complete لا تجد دائما الحلول المثلى. ومع ذلك، فهي مفيدة لأنها سريعة التفكير، كثيرا ما توفر تقديرات تقريبية إلى ألافضل.

إذا كانت الخوارزمية الجشع تثمر لانتاج الحل الأمثل الشمول (الاعم) لفئة مشكلة معينة معطاة، فإنه يصبح عادة الأسلوب المفضل لأنه أسرع من الطرق المثلى الأخرى مثل البرمجة الديناميكية . ومن أمثلة هذه الخوارزميات الجشعة هي خوارزمية كروسكال و خوارزمية بريم لإيجاد الحد الأدنى من الأشجار minimum spanning tree التي تغطي، وخوارزمية للعثور على الأشجار هوفمان المثلى ترميز هوفمان شجرة هوفمان .


نظري matroid ، ونظرية أعم من greedoids ، توفر فئات كاملة من هذه الخوارزميات.


ويبدو أن الخوارزميات الجشعة تظهر في توجيه شبكة routing كذلك. باستخدام التوجيه الجشع، يتم توجيه رسالة إلى العقدة المجاورة التي هي الأقرب إلى الوجهة. يمكن تحديد مفهوم مكان العقدة (وبالتالي التقارب ) من خلال موقعه الفعلي، كما هو الحال في التوجيه الجغرافي geographic routing المستخدمة من قبل مخصصة الشبكات ad hoc networks . الموقع قد يكون أيضا بناء اصطناعيا كاملا كما هو الحال في توجيه العالم الصغير small world routing وجدول تجزئة توزيع

distributed hash table


الامثله




  • مشكلة اختيار النشاط هو سمة لهذه الفئة من المشاكل، حيث كان الهدف هو اختيار الحد الأقصى لعدد الأنشطة التي لا تتصادم مع بعضها البعض.

  • في لعبة الكمبيوتر ماكنتوش كريستال كويست الهدف هو جمع البلورات، بطريقة مماثلة لمشكلة السفر لرجل المبيعات. لعبة لديها طريقة العرض، حيث تستخدم اللعبة خوارزمية الجشع للذهاب الى كل بلورة(كريستال). الذكاء الاصطناعي لا يحسب العقبات، وبالتالي فإن طريقة العرض غالبا ما تنتهي بسرعة.

  • السعي مطابقة The matching pursuit مثال على خوارزمية الجشع تطبيقها على إشارة التقريب.

  • خوارزمية الجشع وجدت الحل الأمثل لمشكلة في العثور على ثلاث دوائر منفصلة ضمن مثلث معطى لتحقيق أقصى قدر من المساحة الكلية للدوائر. وخمن أن نفس خوارزمية الجشع هي الأمثل لأي عدد من الدوائر.

  • ويستخدم خوارزمية الجشع لبناء شجرة هوفمان خلال هوفمان الترميز(كود) حيث يجده الحل الأمثل.

  • في التعلم شجرة القرارات، وتستخدم خوارزميات الجشع شيوعا، ولكن ليست مضمونة لإيجاد الحل الأمثل.



_

Greedy algorithm 36 cents.svg يسار تصغير 280 استخدام لخوارزيمة جشعة لتحديد عدد القطع النقدية الأقل المطلوب لجمع 36 قطعة نقدية، حيث أن قيم القطع النقطية هم 1، 5، 10 و 20


خوارزمية جشعة هي خوارزمية التي تستند على حدس مهني الحدس المهني الذي يتم عن طريقه اختيار الإمكانية الأفضل المرئية في المرحلة الحالية, من دون الأخذ بالحسبان تأثير هذه الخطوة على تكملة الحل. cite web last Black first Paul E. greedy algorithm url http //xlinux.nist.gov/dads//HTML/greedyalgo.html work Dictionary of Algorithms and Data Structures publisher National Institute of Standards and Technology U.S. National Institute of Standards and Technology (NIST) accessdate 17 August date 2 February 2005 الخوارزميات الجشعة مشهورة في حل رياضيات الاستمثال مشاكل الاستمثال ، حيث يتم بواستطهن محاولة الوصول إلى الجواب الأفضل.

شاركنا رأيك

كلمات مرتبطه: خوارزمية جشعة أمثلة
 
التعليقات

لم يعلق احد حتى الآن .. كن اول من يعلق بالضغط هنا

أقسام الموقع المتنوعة أوجدت لخدمة الزائر ليسهل عليه تصفح الموقع بسلاسة وأخذ المعلومات تصفح هذا الموضوع خوارزمية جشعة أمثلة ويمكنك مراسلتنا في حال الملاحظات او التعديل او الإضافة او طلب حذف الموضوع ...آخر تعديل اليوم 24/05/2021



شاهد الجديد لهذه المواقع
شاهد الجديد لهذه المواقع
شاهد الجديد لهذه المواقع