الصياغة الصحيحة لخوارزمية A*

Question

أنا ألقي نظرة على تعريفات خوارزمية اكتشاف المسار A*، ويبدو أنه تم تعريفها بشكل مختلف إلى حد ما في أماكن مختلفة.

يكمن الاختلاف في الإجراء الذي يتم تنفيذه عند المرور عبر خلفاء العقدة، واكتشاف أن العقدة اللاحقة موجودة في القائمة المغلقة.

• نهج واحد (اقترحه ويكيبيديا, ، و هذا المقال) يقول:إذا كان الخلف مدرجًا في القائمة المغلقة، فما عليك سوى تجاهله
• نهج آخر (المقترح هنا و هنا, مثلا) يقول:إذا كان الخلف ضمن القائمة المغلقة، فافحص تكلفته.إذا كانت أعلى من الدرجة المحسوبة حاليًا، قم بإزالة العنصر من القائمة المغلقة لفحصها في المستقبل.

أنا في حيرة من أمري - ما هي الطريقة الصحيحة؟حدسيًا، الأول يبدو أكثر منطقية بالنسبة لي، لكني أتساءل عن الفرق في التعريف.هل أحد التعريفات خاطئ، أم أنها متماثلة إلى حد ما؟

Answer 1

يكون النهج الأول هو الأمثل فقط إذا كان المسار الأمثل لأي حالة متكررة هو دائمًا أول مسار يجب اتباعه.تنطبق هذه الخاصية إذا كانت الوظيفة الإرشادية لها خاصية تناسق (أيضا يسمى أحادية).تكون الوظيفة الإرشادية متسقة إذا كانت لكل عقدة n وكل خليفة n' ل n, ، التكلفة التقديرية للوصول إلى الهدف من n ليست أكبر من تكلفة خطوة الوصول إليها n' من n بالإضافة إلى التكلفة المقدرة للوصول إلى الهدف من n.

النهج الثاني هو الأمثل إذا كانت الوظيفة الإرشادية مقبولة فقط، أي أنها لا تبالغ أبدًا في تقدير تكلفة الوصول إلى الهدف.

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

وبالتالي، على الرغم من أن النهج الثاني أكثر عمومية لأنه يعمل مع مجموعة فرعية أكبر بدقة من الوظائف الإرشادية، فإن النهج الأول عادة ما يكون كافيا في الممارسة العملية.

مرجع:القسم الفرعي بحث:تقليل التكلفة الإجمالية للحل المقدرة في قسم 4.1 استراتيجيات البحث المستنيرة (الإرشادية). من الكتاب الذكاء الاصطناعي:نهج حديث.