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