📝 أسئلة اختبارية
عدد الأسئلة: 2
سؤال 5: صف طريقة عمل البحث المحلي.
- أ) يبدأ بحل عشوائي ويبحث في جميع الحلول الممكنة بشكل منهجي.
- ب) يستخدم خوارزمية جشعة فقط دون أي تحسينات لاحقة.
- ج) يبدأ بحل أولي ثم يبحث محلياً في جواره عن حل أفضل من خلال عمليات صغيرة مثل التبديل.
- د) يحسب جميع التباديل الممكنة ويختار الأفضل منها مباشرة.
الإجابة الصحيحة: البحث المحلي هو خوارزمية تحسين تبدأ بحل أولي (مثل الحل الجشع) ثم تبحث محلياً في جوار الحل الحالي عن حل أفضل من خلال عمليات تبديل صغيرة (مثل تبديل مهمتين في الجدولة). تستمر في التكرار حتى لا يمكن تحسين الحل أكثر أو تصل إلى عدد محدد من التكرارات.
الشرح: البحث المحلي يعمل على تحسين حل موجود من خلال استكشاف الحلول المجاورة له باستخدام عمليات مثل التبديل، ويقبل الحل الجديد إذا كان أفضل من الحالي، ويتوقف عند الوصول إلى أمثلية محلية أو استنفاد التكرارات.
تلميح: فكر في كيفية تحسين جدولة موجودة من خلال تبديل مواقع المهام.
سؤال 6: اكتب ملاحظاتك عن نتائج خوارزميات الحل الجشعة مقارنة بخوارزميات حل البحث المحلي في مشكلة تشتمل على ثلاثين مهمة. من وجهة نظرك، لماذا لم تستخدم خوارزمية حل القوة المفرطة في هذه المشكلة المكونة من ثلاثين مهمة؟
- أ) الجشعة أبطأ ولكن أكثر دقة، والبحث المحلي أسرع، والقوة المفرطة ممكنة لـ 30 مهمة.
- ب) الجشعة سريعة ولكن أقل دقة، والبحث المحلي يحسن الدقة بوقت إضافي، والقوة المفرطة غير عملية بسبب التعقيد العالي.
- ج) كلا الخوارزميتين تعطيان نفس النتائج، والقوة المفرطة هي الخيار الأفضل دائماً.
- د) البحث المحلي أسرع من الجشعة، والقوة المفرطة تستخدم عادةً لمشاكل صغيرة مثل 30 مهمة.
الإجابة الصحيحة: خوارزميات الحل الجشعة سريعة ولكن قد تعطي حلولاً دون المستوى الأمثل، بينما خوارزميات البحث المحلي تحسن الحلول الجشعة لتعطي نتائج أفضل ولكنها تستغرق وقتاً أطول. لم تستخدم خوارزمية القوة المفرطة لأن عدد التباديل لـ 30 مهمة هو 30! (حوالي 2.65 × 10^32)، وهو عدد هائل يتطلب وقتاً حاسوبياً غير عملي.
الشرح: الخوارزميات الجشعة تعمل بسرعة O(n log n) ولكن قد لا تكون أمثلية، بينما البحث المحلي يحسن الحل بوقت إضافي. القوة المفرطة غير عملية للمشاكل الكبيرة بسبب التعقيد المضروب (factorial) الذي ينمو بسرعة كبيرة.
تلميح: قارن بين السرعة والدقة للخوارزميات، وفكر في تعقيد القوة المفرطة لعدد كبير من المهام.
🎴 بطاقات تعليمية للمراجعة
عدد البطاقات: 3 بطاقة لهذه الصفحة
اذكر باختصار طريقة عمل البحث المحلي.
الإجابة: البحث المحلي يبدأ من حل أولي، ثم ينتقل بشكل متكرر إلى حلول مجاورة في فضاء البحث، بحثاً عن حل أفضل، حتى يصل إلى حل لا يمكن تحسينه أكثر بالانتقال للحلول المجاورة.
الشرح: البحث المحلي يعمل على استكشاف الحلول المجاورة للحل الحالي، بهدف إيجاد تحسين. يستمر هذا البحث حتى يتم الوصول إلى ما يسمى بـ "الحد الأمثل المحلي"، وهو الحل الذي لا يوجد حل مجاور أفضل منه.
تلميح: فكر في المفهوم الأساسي للانتقال من نقطة إلى نقطة أخرى قريبة منها في محاولة للتحسين.
لماذا لا يُعد استخدام خوارزمية القوة المفرطة (Brute Force) حلاً فعالاً لمشكلة تتضمن ثلاثين مهمة؟
الإجابة: خوارزمية القوة المفرطة تستكشف جميع الحلول الممكنة، مما يجعل عدد العمليات اللازمة لتجربتها ينمو بشكل أسي (factorial). بالنسبة لثلاثين مهمة، فإن العدد يصبح هائلاً وغير قابل للحساب أو التنفيذ في وقت معقول.
الشرح: معدل النمو الأسي أو العاملي للخوارزميات التي تستخدم القوة المفرطة يجعلها غير عملية للمسائل الكبيرة. على سبيل المثال، إذا كانت لدينا n مهمة، فإن عدد التباديل الممكنة يمكن أن يصل إلى n!، وهو رقم كبير جداً لـ n=30.
تلميح: فكر في كيفية زيادة عدد الخيارات مع كل مهمة إضافية عند تجربة كل الاحتمالات الممكنة.
ما هي الملاحظة الرئيسية عند مقارنة نتائج خوارزميات الحل الجشعة (Greedy) مع خوارزميات البحث المحلي (Local Search) لمشكلة معقدة (مثل ثلاثين مهمة)؟
الإجابة: خوارزميات الحل الجشع قد تصل إلى حلول مقبولة بسرعة، لكنها قد لا تكون الأمثل. بينما يمكن لخوارزميات البحث المحلي، رغم أنها قد تكون أبطأ، أن تصل إلى حلول أقرب إلى الأمثل أو حتى الحل الأمثل إذا استُخدمت بشكل صحيح، خاصة إذا بدأت من نقاط جيدة.
الشرح: الخوارزمية الجشعة تتخذ أفضل قرار متاح في كل خطوة دون النظر إلى المستقبل، مما قد يؤدي إلى الوقوع في الحد الأمثل المحلي. البحث المحلي، من ناحية أخرى، يبدأ من حل ويحاول تحسينه تدريجياً، وغالباً ما يحقق نتائج أفضل على المدى الطويل للمشاكل الصعبة.
تلميح: فكر في طبيعة كل خوارزمية: هل تبحث عن أفضل حل في كل خطوة أم تستكشف حول حل قائم؟