هل النجم جشع؟

2024 مؤلف: Lynn Donovan | [email protected]. آخر تعديل: 2023-12-15 23:43

أ * (أ نجمة ) A * هو مزيج من Dijkstra و جشع . يستخدم المسافة من عقدة الجذر بالإضافة إلى المسافة الاستدلالية إلى الهدف. تنتهي الخوارزمية عندما نجد عقدة الهدف.

أيضًا ، هل تم إكمال البحث الأول عن الجشع؟

في تلخيص، جشع BFS ليس كذلك مكتمل ، ليس أفضل ، لديه تعقيد زمني لـ O (bm) وتعقيد الفضاء الذي يمكن أن يكون متعدد الحدود. * هو مكتمل , أفضل ، ولها تعقيد زمني وفضائي لـ O (bm). لذلك ، بشكل عام ، يستخدم A * ذاكرة أكثر من جشع BFS. A * يصبح غير عملي عندما يكون ملف بحث مساحة ضخمة.

بجانب ما سبق ، هل * مقبول؟ إذا كانت الوظيفة الكشف عن مجريات الأمور مقبول ، مما يعني أنه لا يبالغ أبدًا في تقدير التكلفة الفعلية للوصول إلى الهدف ، ويضمن A * إرجاع المسار الأقل تكلفة من البداية إلى الهدف. قيمة f للهدف هي تكلفة أقصر مسار ، حيث أن h عند الهدف تساوي صفرًا في مقبول ارشادي.

علاوة على ذلك ، لماذا * أفضل من أفضل بحث أول؟

* يحقق أفضل الأداء باستخدام الاستدلال لتوجيه بحث . أ * يجمع بين مزايا أفضل - البحث الأول والتكلفة الموحدة بحث : تأكد من العثور على المسار الأمثل مع زيادة كفاءة الخوارزمية باستخدام الاستدلال.

هل اكتملت الخوارزمية A *؟

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