📝 أسئلة اختبارية
عدد الأسئلة: 3
سؤال 3: اشرح بإيجاز كيف تعمل خوارزمية البحث بأولوية الأفضل (A* search).
- أ) تستخدم دالة تقييم f(n) = g(n) + h(n) وتختار العقدة ذات أقل قيمة f(n)
- ب) تستخدم البحث العميق أولاً (DFS) مع تحسينات في الذاكرة
- ج) تعتمد على البحث العشوائي مع تحسينات في السرعة
- د) تستخدم خوارزمية جشعة فقط دون مراعاة التكلفة الفعلية
الإجابة الصحيحة: خوارزمية A* search تعمل باستخدام دالة تقييم f(n) = g(n) + h(n)، حيث g(n) هي التكلفة الفعلية من نقطة البداية إلى العقدة n، وh(n) هي دالة الاستدلال (التقديرية) من العقدة n إلى الهدف. تختار الخوارزمية العقدة ذات أقل قيمة f(n) في كل خطوة، مما يجمع بين مزايا البحث بأولوية الاتساع (BFS) والبحث الجشع (Greedy Search).
الشرح: خوارزمية A* search هي خوارزمية بحث مستنيرة تستخدم دالة تقييم تجمع بين التكلفة الفعلية والتكلفة التقديرية للوصول إلى الهدف، مما يجعلها فعالة في إيجاد المسار الأمثل إذا كانت دالة الاستدلال h(n) مقبولة (لا تبالغ في التقدير) ومتسقة.
تلميح: فكر في كيفية حساب التكلفة الإجمالية باستخدام التكلفة الفعلية والتكلفة التقديرية.
سؤال 4: عدل المقطع البرمجي بتغيير الوزن القطري (Diagonal Weight) من 3 إلى 1.5. ماذا تلاحظ؟ هل يتغير المسار الأقصر في حالتي خوارزمية البحث بأولوية الاتساع (BFS) وخوارزمية البحث بأولوية الأفضل (A* search)?
- أ) يتغير المسار في A* فقط لأنها تستخدم الأوزان، بينما BFS لا تتأثر
- ب) يتغير المسار في كلتا الخوارزميتين لأن الأوزان تؤثر على جميع عمليات البحث
- ج) لا يتغير المسار في أي من الخوارزميتين لأن الأوزان ثابتة في التصميم
- د) يتغير المسار في BFS فقط لأنها حساسة للأوزان الجديدة
الإجابة الصحيحة: عند تغيير الوزن القطري من 3 إلى 1.5، يصبح الانتقال القطري أرخص، مما قد يؤدي إلى تغيير المسار الأقصر في خوارزمية A* search إذا كان ذلك يحسن التكلفة الإجمالية، بينما في خوارزمية BFS (غير موزونة) لا يتغير المسار الأقصر لأن BFS تبحث عن أقصر مسار من حيث عدد الخطوات وليس التكلفة الموزونة.
الشرح: خوارزمية BFS تبحث عن المسار الأقصر من حيث عدد الخطوات (غير موزون)، لذا لا تتأثر بتغيير الأوزان. خوارزمية A* search تأخذ في الاعتبار الأوزان (التكاليف)، لذا تغيير الوزن القطري قد يغير المسار الأمثل إذا أصبح الانتقال القطري أكثر كفاءة.
تلميح: تذكر أن BFS تتعامل مع جميع الخطوات بنفس التكلفة، بينما A* تستخدم أوزانًا.
سؤال 5: عدل المقطع البرمجي بتبديل إحداثيات خلية البداية مع إحداثيات الخلية المستهدفة. ماذا تلاحظ؟ هل المسار هو نفسه كما كان سابقًا للحالات الموزونة من خوارزميتي البحث بأولوية الاتساع (BFS) والبحث بأولوية الأفضل (A* search)?
- أ) في BFS، المسار قد يكون معكوسًا ولكن بنفس الطول؛ في A*، قد يتغير إذا كانت الدالة غير متماثلة
- ب) المسار يتغير تمامًا في كلتا الخوارزميتين بسبب تبديل الإحداثيات
- ج) المسار يظل كما هو في كلتا الخوارزميتين لأن البحث لا يعتمد على الاتجاه
- د) يتغير المسار في BFS فقط لأنها حساسة للاتجاه
الإجابة الصحيحة: عند تبديل إحداثيات البداية والهدف، قد يتغير المسار في خوارزمية A* search إذا كانت دالة الاستدلال h(n) غير متماثلة أو إذا كانت الأوزان غير متناظرة، بينما في خوارزمية BFS (غير موزونة) قد يظل المسار هو نفسه من حيث عدد الخطوات إذا كان الرسم البياني غير موجه، ولكن قد يتغير الاتجاه.
الشرح: في BFS غير الموزونة، إذا كان الرسم البياني غير موجه، فإن المسار من A إلى B هو عكس المسار من B إلى A بنفس عدد الخطوات. في A* search، يعتمد على دالة الاستدلال والأوزان؛ إذا كانت متناظرة، قد يكون المسار مشابهًا، وإلا فقد يتغير.
تلميح: فكر في تماثل دالة الاستدلال والأوزان في الخوارزميات.
🎴 بطاقات تعليمية للمراجعة
عدد البطاقات: 3 بطاقة لهذه الصفحة
اشرح بإيجاز آلية عمل خوارزمية البحث بأولوية الأفضل (A* search).
الإجابة: تعتمد خوارزمية البحث بأولوية الأفضل (A*) على تقييم كل عقدة مرشحة بناءً على مجموع دالتين: دالة التكلفة الفعلية من نقطة البداية إلى العقدة الحالية (g(n))، ودالة تقديرية للتكلفة المتبقية من العقدة الحالية إلى الهدف (h(n)). تختار الخوارزمية العقدة ذات أقل قيمة لمجموع هاتين الدالتين (f(n) = g(n) + h(n)) لاستكشافها تالياً، مما يجعلها تبحث بكفاءة نحو الهدف.
الشرح: تجمع A* بين تتبع التكلفة الفعلية (مثل BFS) والتقدير المستقبلي (مثل Greedy Best-First Search) لتوجيه البحث بشكل فعال نحو الحل.
تلميح: فكر في كيفية قياس الخوارزمية لمدى 'جودة' كل خطوة تقوم بها.
عند تغيير الوزن القطري (Diagonal Weight) في خوارزمية البحث بأولوية الأفضل (A*) من 3 إلى 1.5، مع الاحتفاظ بالوزن الأفقي/الرأسي عند 1، ماذا يحدث عادةً للمسار الأقصر مقارنةً بـ BFS؟
الإجابة: عند تقليل الوزن القطري، تصبح الحركة القطرية أقل تكلفة نسبياً. في خوارزمية A*، هذا قد يؤدي إلى تفضيل المسارات القطرية أكثر، مما قد يؤثر على شكل المسار الأقصر مقارنةً بما لو كانت الحركة القطرية مكلفة جداً. قد يصبح المسار الأقصر في A* أكثر 'انحرافاً' نحو القطرية إذا كان ذلك يقلل التكلفة الإجمالية المقدرة.
الشرح: الوزن القطري الأقل يجعل الحركة المائلة (القطرية) أكثر جاذبية للخوارزمية، حيث أنها الآن لا تتطلب 'عقوبة' كبيرة. هذا قد يؤدي إلى مسار أقصر في A* يبدو مختلفًا عن ذلك الذي قد تجده BFS التي غالباً ما تبحث عن أقصر مسار من حيث عدد الخطوات الأفقية والرأسية فقط (ما لم يتم تعديلها).
تلميح: كيف يؤثر تقليل تكلفة الحركة القطرية على الخيارات التي تفضلها الخوارزمية؟
ماذا تلاحظ عند تبديل إحداثيات خلية البداية مع الخلية المستهدفة في المقطع البرمجي؟ وهل المسار هو نفسه لـ BFS و A*؟
الإجابة: عند تبديل إحداثيات البداية والهدف، سيتم عكس المسار. بمعنى أن المسار الذي تبدأ منه A* أو BFS لاستكشاف الطريق من النقطة الأصلية إلى نقطة الهدف الجديدة سيصبح هو نفسه المسار الذي ستجد فيه A* أو BFS الطريق من النقطة الأصلية الجديدة (التي كانت الهدف سابقًا) إلى نقطة الهدف الجديدة (التي كانت البداية سابقًا). ومع ذلك، قد لا يكون المسار 'مرسوماً' بنفس الترتيب أو بنفس الخطوات المحددة بنفس الشكل، ولكنه سيحتل نفس المجموعة من الخلايا أو يتبع نفس المنطق الأساسي. في الغالب، ستجد الخوارزميتان المسار العكسي.
الشرح: بما أن معظم خوارزميات البحث عن المسارات (بما في ذلك BFS و A* في سياقات شبكية بسيطة) تبحث عن أقصر مسار في شبكة لا توجه فيها الحركة، فإن إيجاد المسار من A إلى B يكافئ إيجاد المسار من B إلى A، فقط بترتيب عكسي. التغيير في الأوزان (إذا كانت موجودة) قد يؤثر على كيفية تفضيل A* للمسارات القطرية، ولكن في النهاية، نفس المسار المنطقي سيتواجد.
تلميح: فكر في العلاقة بين المسار من النقطة أ إلى ب، والمسار من النقطة ب إلى أ.