A* Search
خوارزمية البحث A*
التعريف
خوارزمية بحث عن أقصر مسار تجمع كلفة المسار المقطوع مع تقدير ارشادي لما تبقى.
تختار العقدة التي تقلل \(f(n)=g(n)+h(n)\). إذا كانت الدالة الإرشادية مقبولة (لا تبالغ بالتقدير) فالحل الناتج أمثل. تُستخدم في الألعاب والملاحة والتخطيط.
Definition
A* finds least-cost paths by expanding nodes that minimise cost-so-far plus a heuristic estimate to the goal; with an admissible heuristic it is optimal.
شرح مبسّط للمبتدئين
كملاح يقدّر الطريق المتبقي بالمسافة المباشرة إلى الهدف ليختار المسار الأقصر.
شرح أكاديمي متخصص
يعتمد الأداء على جودة الدالة الإرشادية؛ ويستهلك ذاكرة كبيرة.
أمثلة عملية
- تحديد أقصر طريق على خريطة.
التطبيقات والاستخدامات
- الملاحة والروبوتات.
المزايا
- أمثلية وكفاءة.
القيود والعيوب
- ذاكرة كبيرة.
المعادلات الرياضية
دالة التقييم في A*
f(n)=g(n)+h(n)الكلفة المقطوعة حتى العقدة مضافاً إليها التقدير الإرشادي للكلفة المتبقية.
| الرمز | المعنى |
|---|---|
| \(g(n)\) | كلفة المسار من البداية |
| \(h(n)\) | تقدير الكلفة إلى الهدف |
