خوارزمية البحث A*
- قدّمه
- Peter E. Hart, Nils J. Nilsson, and Bertram Raphael
- السنة
- 1968
- النوع
- algorithm
- العائلة
- Graph Algorithms
هذا النص ترجمة آلية ولم تتم مراجعته بعد. اقرأ النص الأصلي بالإنجليزية
ماذا تفعل؟
خوارزمية البحث A*، التي طورها بيتر إي. هارت، ونيلز ج. نيلسون، وبيرترام رافائيل في عام 1968، هي خوارزمية مثالية لإيجاد المسار تجمع بين فوائد خوارزمية ديكسترا والتوجيه الاستدلالي. إنها تجد أقصر مسار بكفاءة من خلال الموازنة بين المسافة الفعلية من البداية والمسافة المقدرة إلى الهدف.
الفكرة الحدسية وراء الطريقة
تستخدم A* دالة تقييم f(n) = g(n) + h(n)، حيث g(n) هي التكلفة الفعلية من البداية إلى العقدة n، و h(n) هي تقدير استدلالي للتكلفة المتبقية للوصول إلى الهدف. من خلال استكشاف العقد ذات القيمة الأقل لـ f(n)، تضيق الخوارزمية مساحة البحث بكفاءة نحو الهدف مع الحفاظ على المثالية عندما يكون الاستدلال مقبولاً (لا يبالغ في التقدير أبدًا). هذا يجعل A* أسرع بكثير من طرق البحث غير المستنيرة مع بقاء ضمان إيجاد المسار الأمثل.
التاريخ
نشر هارت و نيلسون و رافائيل خوارزمية A* في عام 1968، موضحين أن إضافة معلومات استدلالية إلى خوارزمية ديكسترا يمكن أن تحسن كفاءة البحث بشكل كبير مع الحفاظ على المثالية. أصبحت الخوارزمية أساسية في الذكاء الاصطناعي وبحوث العمليات. تشمل التطورات اللاحقة A* ثنائية الاتجاه، و IDA* (التعميق التكراري)، وتحسينات استدلالية مختلفة. تظل A* الخيار القياسي لإيجاد المسارات في محركات الألعاب الحديثة وأنظمة الروبوتات.
متى تُستخدم
طبق A* عندما تحتاج إلى إيجاد مسارات مثالية في الرسوم البيانية حيث تتوفر دالة استدلال جيدة. إنها فعالة بشكل خاص لإيجاد المسارات في الألعاب والروبوتات وتخطيط المسارات حيث يمكن للبحث المستنير أن يقلل الحسابات بشكل كبير. استخدمها عندما تكون السرعة مهمة ولكن المثالية مطلوبة. في الحالات التي لا تتوفر فيها دالة استدلال موثوقة، استخدم خوارزمية ديكسترا بدلاً من ذلك.
الحدود والاعتبارات
- تعتمد المثالية على قبول دالة الاستدلال
- يتدهور الأداء بشكل كبير مع الاستدلالات السيئة أو غير المقبولة
- يمكن أن يكون استخدام الذاكرة كبيرًا في مساحات البحث الكبيرة (تحتفظ بمجموعات مفتوحة ومغلقة)
- يتطلب معرفة صريحة بالمجال لتصميم دوال استدلال جيدة
لا تغني شروط المصدر عن المراجعة العلمية المستقلة أو التحقق بواسطة محرك تحليل.
نقاط القوة
- إيجاد المسار الأمثل عندما يكون الاستدلال مقبولاً
- أسرع بكثير من خوارزمية ديكسترا أو البحث بالعرض الأول عندما تتوفر استدلالات جيدة
- مرنة: تعمل مع أي دالة استدلال مقبولة
- مناسبة لمشاكل إيجاد المسار لهدف واحد
- تحقق واسع النطاق في العالم الحقيقي في الألعاب والروبوتات وأنظمة الملاحة
التطبيقات
- إيجاد المسارات في ألعاب الفيديو: تنقل الشخصيات غير اللاعبة في الوقت الفعلي في بيئات الألعاب الديناميكية
- تخطيط حركة الروبوت: تخطيط المسار الأمثل للروبوتات المستقلة لتجنب العقبات
- الملاحة بنظام تحديد المواقع العالمي (GPS): حساب المسارات الفعالة مع مراعاة شبكات الطرق وحركة المرور
- حل الألغاز: إيجاد حلول مثالية في المشاكل التوافقية مثل لغز الـ 15
- توجيه الشبكة: تحديد مسارات الحزم الفعالة مع استدلالات جودة الارتباط
- المعلوماتية الحيوية: عمليات البحث عن محاذاة التسلسل والتنبؤ ببنية البروتين
كيف يعمل
كيف يعمل
إنشاء مجموعة مفتوحة تحتوي على عقدة البداية، وتعيين قيمة g الخاصة بها (التكلفة من البداية) إلى الصفر، وحساب قيمة h باستخدام دالة الاستدلال.
اختيار العقدة ذات القيمة الأقل لـ f من المجموعة المفتوحة، وحساب قيم f لجيرانها غير المزارين، وإضافة الجيران الواعدين إلى المجموعة المفتوحة.
مواصلة توسيع العقد حتى يتم الوصول إلى الهدف بأقل قيمة لـ f، مما يضمن المسار الأمثل؛ إعادة بناء المسار عن طريق تتبع مؤشرات الآباء.
الأخطاء الشائعة
- استخدام استدلال غير مقبول يبالغ في تقدير التكاليف، مما يؤدي إلى مسارات غير مثالية
- اختيار استدلال بسيط جدًا أو غير مرتبط بالمشكلة، مما يقلل من كفاءة البحث
- تنفيذ غير فعال للمجموعة المفتوحة (يجب استخدام طابور الأولوية)، مما يتسبب في بطء اختيار العقدة
الأسئلة الشائعة
ما هو الاستدلال المقبول ولماذا هو مهم؟
الاستدلال المقبول لا يبالغ أبدًا في تقدير التكلفة الحقيقية للوصول إلى الهدف. تضمن هذه الخاصية أن A* تجد المسار الأمثل. إذا بالغ الاستدلال في التقدير، فقد تفوت A* مسارات أقصر وتعطي حلولاً غير مثالية.
كيف تصمم استدلالًا جيدًا لمشكلة ما؟
تعتمد الاستدلالات الجيدة على المعرفة بالمجال وهيكل المشكلة. بالنسبة لإيجاد المسارات المستندة إلى الشبكة، تعمل مسافة مانهاتن أو المسافة الإقليدية بشكل جيد. بالنسبة للمشاكل الأكثر تعقيدًا، ضع في اعتبارك تخفيف القيود أو استخدام قواعد بيانات الأنماط لحساب استدلالات مقبولة.
ما الفرق بين خوارزمية A* وخوارزمية ديكسترا؟
كلاهما يجد المسارات المثالية، لكن A* تستخدم استدلالًا لتحديد أولويات الاستكشاف نحو الهدف، مما يجعلها أسرع بكثير عندما يتوفر استدلال جيد. تستكشف ديكسترا بشكل موحد في جميع الاتجاهات وهي أكثر أمانًا عندما تكون الاستدلالات غير موثوقة.
هل يمكن لـ A* ضمان إيجاد أقصر مسار؟
نعم، تضمن A* أقصر مسار عندما يكون الاستدلال مقبولاً (لا يبالغ في تقدير التكلفة الحقيقية أبدًا). مع الاستدلالات غير المقبولة، لا يتم ضمان المثالية.
طرق ذات صلة
المصادر
Hart, P. E., Nilsson, N. J., & Raphael, B. (1968). A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 4(2), 100-107.
افتح مرجع DOIتم النسخ.Russell, S. J., & Norvig, P. (2009). Artificial Intelligence: A Modern Approach (3rd ed.). Pearson.
ردمك: 978-0-13-604259-4تم النسخ.