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

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

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

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

الشرح

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

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

انظر إلى متاهة شبكية بحجم $3 \times 3$ حيث خلية البداية هي $(2, 0)$ وخلية الهدف هي $(1, 2)$. تستدعي دالة حل المتاهة خلية البداية، وتفحص الخلايا المجاورة المتاحة لها. تنتقل الخوارزمية إلى الخلية $(1, 0)$، ثم تفحص جيرانها ومنها $(0, 0)$، لتستمر العملية في توسيع الخلايا طبقة تلو الأخرى. يتم حفظ العقدة الأصلية لكل خطوة في قاموس parent، وبمجرد الوصول إلى خلية الهدف $(1, 2)$، تُستدعى دالة إعادة بناء المسار لتتتبع العقد عكسياً من الهدف إلى البداية، فينتج المسار الأقصر المكون من الخلايا: $(2, 0)$ ثم $(1, 0)$ ثم $(0, 1)$ ثم $(1, 2)$، وبمسافة كلية تساوي ثلاث خطوات بعد فحص عشر خلايا إجمالاً.

أخطاء شائعة

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

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

السؤال الأول: ما الفرق الأساسي بين خوارزميات البحث المستمرة وغير المستمرة؟ الإجابة: خوارزميات البحث غير المستمرة تعتمد على مساحة البحث وقواعد محددة مسبقاً دون معلومات إضافية عن الهدف، بينما تستخدم خوارزميات البحث المستمرة دالة استدلالية لتقدير المسافة وتوجيه عملية البحث نحو الهدف.

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