الدرس الرابع (٣)

يقوم الدرس على مقارنة أداء خوارزميات البحث المستنيرة مثل البحث بأولوية الأفضل والخوارزميات غير المستنيرة مثل البحث بأولوية الاتساع في حل مشكلات المتاهات الكبيرة. يوضح الدرس أن الخوارزميات المستنيرة أكثر كفاءة وأقل تعقيداً حسابياً لأنها تفحص عدداً أقل من الخلايا بفضل استخدام دوال الاستدلال مثل مسافة مانهاتن التي تُحسب بقانون القيمة المطلقة لفروق الإحداثيات. كمثال، إذا أردت حساب مسافة مانهاتن بين النقطة A بإحداثيات $(x_1, y_1)$ والنقطة B بإحداثيات $(x_2, y_2)$، فإن القانون هو $\text{Manhattan}(A, B) = |x_1 - x_2| + |y_1 - y_2|$، وهو ما يساعد الخوارزمية في العثور على المسار الأقصر بشكل أسرع.

الفكرة الأساسية

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

الشرح

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

من أهم أدوات الاستدلال المستخدمة في المتاهات مسافة مانهاتن، وهي تعبر عن مجموع الفروق المطلقة بين إحداثيات نقطتين معطاة في المستوى الشبكي. نرمز للنقطة الأولى بالرمز $A$ وإحداثياتها $(x_1, y_1)$، والنقطة الثانية بالرمز $B$ وإحداثياتها $(x_2, y_2)$. نحسب المسافة بينهما رياضياً بالمعادلة:

$\text{Manhattan}(A, B) = |x_1 - x_2| + |y_1 - y_2|$

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

مثال محلول خطوة بخطوة

لنفترض أن لدينا نقطة بداية $A$ عند الإحداثي $(1, 1)$ ونقطة هدف $B$ عند الإحداثي $(4, 5)$ في شبكة متاهة، ونريد حساب مسافة مانهاتن بينهما.

الخطوة الأولى: نحدد إحداثيات النقطة الأولى والثانية بدقة: $x_1 = 1$ $y_1 = 1$ $x_2 = 4$ $y_2 = 5$

الخطوة الثانية: نطبق قانون مسافة مانهاتن: $\text{Manhattan}(A, B) = |x_1 - x_2| + |y_1 - y_2|$

الخطوة الثالثة: نعوض بالقيم الرقمية داخل القانون: $\text{Manhattan}(A, B) = |1 - 4| + |1 - 5|$

الخطوة الرابعة: نحسب القيم المطلقة: $|1 - 4| = |-3| = 3$ $|1 - 5| = |-4| = 4$

الخطوة الخامسة: نجمع الناتجين للحصول على المسافة النهائية: $3 + 4 = 7$ إذن مسافة مانهاتن بين النقطتين هي $7$ خطوات.

أخطاء شائعة

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

سؤالان للتدريب مع الإجابة

السؤال الأول: ما الفرق الأساسي بين خوارزميات البحث المستنيرة وغير المستنيرة من حيث كفاءة فحص الخلايا في المتاهات الواسعة؟ الإجابة: الخوارزميات المستنيرة تفحص عدداً أقل بكثير من الخلايا لأنها تستخدم دوال استدلال ذكية توجهها نحو الهدف، بينما الخوارزميات غير المستنيرة تكون أكثر تعقيداً وتبحث بشكل أبطأ لأنها تفحص عدد أكبر من الخلايا.

السؤال الثاني: احسب مسافة مانهاتن بين النقطة الأولى بإحداثيات $(2, 3)$ والنقطة الثانية بإحداثيات $(6, 6)$. الإجابة: نطبق المعادلة $\text{Manhattan} = |2 - 6| + |3 - 6|$. نحسب القيمة المطلقة الأولى $|-4| = 4$ والثانية $|-3| = 3$. نجمع الناتجين $4 + 3 = 7$ إذن المسافة تساوي $7$.