الدرس الرابع (٢)
انظر إلى الشيفرة البرمجية أعلى الصفحة. الدالة هنا تتيح للمستخدم تعيين وزن مخصص للحركات الأفقية والرأسية، ووزن آخر مختلف للحركات القطرية. لاحظ كيف يتم تمرير هذه الأوزان في دالة البحث بأولوية الاتساع الموزون لتحديد التكاليف بدقة أكبر بناءً على نوع الحركة. في الأسفل، ترى نتيجة التطبيق العملي: مسار قصير محدد بإحداثيات الخلايا، وطول هذا المسار، وعدد الخلايا التي تمت زيارتها أثناء البحث. هذه الطريقة تمنحنا تحكماً كاملاً في حساب التكلفة الفعلية للانتقال من خلية إلى أخرى حسب المسار المختار.
تقوم خوارزمية البحث بأولوية الأفضل على حل مشكلة المتاهات بشكل اذكى من خوارزمية البحث بأولوية الاتساع، لانها تستخدم دالة استدلالية لتقدير المسافة المتبقية حتى الخلية المستهدفة وتقليل الخلايا المفحوصة. تفحص خوارزمية البحث بأولوية الأفضل كل خلية مجاورة، وتعتمد على دالة مثل الاستدلال الثابت لتحديد المسافة، مما يمكنها من العثور على المسار الاقصر في المتاهات الموزونة حيث تفشل خوارزمية البحث بأولوية الاتساع. على سبيل المثال، في متاهة بحجم خمسة عشر في خمسة عشر، عثرت خوارزمية البحث بأولوية الأفضل على مسار طوله خمس وعشرون وحدة في الاصدار الموزون، بينما فشلت خوارزمية البحث بأولوية الاتساع واعطت مسارا بطول ثلاثين وحدة.
الفكرة الأساسية
تقوم خوارزمية البحث بأولوية الأفضل على توجيه عملية البحث نحو الهدف بذكاء باستخدام دالة استدلالية، بدلا من فحص كل الخلايا بطريقة عمياء كما تسوي خوارزمية البحث بأولوية الاتساع.
الشرح
تتفحص خوارزمية البحث بأولوية الأفضل خلية واحدة في كل مرة ببحث عن كل خلية مجاورة يمكن الوصول إليها. تعتمد الخوارزمية على دالة استدلالية لحساب المسافة المحتملة بين الخلية الحالية والخلية المستهدفة. لضمان عدم المبالغة في التقدير، يجب ألا تكون المسافة المقدرة أكبر من المسافة الحقيقية إلى الهدف. تستخدم دالة مثل الاستدلال الثابت لإرجاع قيمة ثابتة قدرها واحد لكل حركة، مما يضمن تقديرا بسيطا لا يتجاوز المسافة الحقيقية أبدا. تستخدم دالة get_best_candidate لتحديد المرشح الأفضل بدون الحاجة إلى فحص كل المرشحين بصورة متكررة. في الحالة الموزونة، إذا تم تخصيص أوزان مختلفة للحركات الأفقية والراسية والقطرية، فإن خوارزمية البحث بأولوية الأفضل تتفوق على خوارزمية البحث بأولوية الاتساع التي تتجاهل الأوزان وتعطي تكلفة غير دقيقة.
مثال محلول خطوة بخطوة
في متاهة بحجم خمسة عشر في خمسة عشر تحتوي على حواجز، نريد إيجاد مسار من خلية البداية (14,0) إلى الخلية المستهدفة (5,10) في الإصدار الموزون حيث وزن الحركة الأفقية والراسية يساوي واحد ووزن الحركة القطرية يساوي ثلاثة. الخطوة الأولى: تشغيل خوارزمية البحث بأولوية الاتساع لإيجاد مسار، فتجد مسارا بطول ثلاثين وحدة بعد فحص عدد كبير من الخلايا. الخطوة الثانية: تشغيل خوارزمية البحث بأولوية الأفضل باستخدام دالة الاستدلال الثابت. الخطوة الثالثة: تقييم الخلايا المرشحة بناء على التكلفة الفعلية مضافا إليها القيمة الاستدلالية. الخطوة الرابعة: تجد خوارزمية البحث بأولوية الأفضل مسارا بطول خمس وعشرون وحدة فقط.
أخطاء شائعة
الاعتقاد بأن خوارزمية البحث بأولوية الاتساع تجد دائما المسار الأقصر في المتاهات الموزونة، بينما الحقيقة أنها تجد مسارا بعدد خلايا أقل لكن بتكلفة إجمالية أعلى لأنها لا تأخذ الأوزان بعين الاعتبار. استخدام دالة استدلالية تبالغ في تقدير المسافة بحيث تصبح أكبر من المسافة الحقيقية إلى الهدف.
سؤالان للتدريب مع الإجابة
السؤال الأول: ما الفرق الأساسي بين خوارزمية البحث بأولوية الاتساع وخوارزمية البحث بأولوية الأفضل في المتاهات الموزونة؟ الإجابة: خوارزمية البحث بأولوية الاتساع تطبق بحثا بسيطة بالعرض وتتجاهل الأوزان، مما يمنح حلا بتكلفة أعلى، بينما خوارزمية البحث بأولوية الأفضل تستخدم دالة استدلالية لتعديل سلوكها وفقا للأوزان المحددة وايجاد الحل الأمثل. السؤال الثاني: لماذا تعتبر دالة الاستدلال الثابت آمنة في خوارزمية البحث بأولوية الأفضل؟ الإجابة: لأنها تعطي دوما مسافة تقديرية قدرها وحدة واحدة، فلا تقدم أبدا تقديرا أعلى من المسافة الحقيقية.