البحث الاستدلالي و A*

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

Definition

البحث الاستدلالي هو بحث مستنير يرتب الحدود باستخدام دالة تقييم تجمع بين التكلفة المعروفة من البداية وتقدير استدلالي للتكلفة المتبقية؛ تستخدم A* الدالة f(n) = g(n) + h(n) وتكون مثالية عندما تكون h مقبولة.

Scope

يغطي هذا الموضوع استراتيجيات البحث المستنير (الاستدلالي)، التي تتمحور حول البحث الأفضل أولاً وخوارزمية A*، بما في ذلك تصميم وخصائص الدوال الاستدلالية (المقبولية، الاتساق/الرتابة)، وضمانات الأمثلية والكفاءة التي تمنحها هذه الخصائص، والمتغيرات المحدودة بالذاكرة مثل A* بالتعميق التكراري (IDA*). ويتناول كيفية بناء الاستدلالات (المشكلات المخففة، قواعد بيانات الأنماط) وكيف توازن بين الدقة والحساب. ينتمي تعلم الاستدلالات من البيانات إلى المجال الفرعي للتعلم الآلي.

Core questions

• ما الذي يجعل الاستدلال مقبولاً، ولماذا تضمن المقبولية أمثلية A*؟
• كيف يعزز الاتساق (الرتابة) الضمانات ويمنع إعادة توسيع العقدة؟
• كيف يتم تصميم الاستدلالات الجيدة، على سبيل المثال من الإصدارات المخففة للمشكلة؟
• كيف تحافظ المتغيرات المحدودة بالذاكرة مثل IDA* على الأمثلية بمساحة محدودة؟

Key concepts

• دالة التقييم f = g + h
• استدلال مقبول
• استدلال متسق (رتيب)
• بحث أفضل أولاً جشع
• بحث A*
• A* بالتعميق التكراري (IDA*)
• هيمنة الاستدلال
• مشكلة مخففة وقواعد بيانات الأنماط

Key theories

أمثلية A* تحت الاستدلالات المقبولة

عندما لا يبالغ الاستدلال h أبدًا في تقدير التكلفة الحقيقية المتبقية، توسع A* العقد بزيادة f = g + h ويضمن إرجاع مسار بأقل تكلفة؛ ومن بين الخوارزميات التي تستخدم نفس المعلومات الاستدلالية، تكون A* هي الأكثر كفاءة بشكل أمثل.

تصميم الاستدلال عبر التخفيف

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

البحث الاستدلالي المحدود بالذاكرة

يقوم A* بالتعميق التكراري بإجراء عمليات بحث متتالية بالعمق أولاً مقيدة بحد عتبة تكلفة f متزايد، مما يحقق أمثلية شبيهة بـ A* مع ذاكرة خطية في عمق الحل.

Clinical relevance

يدعم البحث الاستدلالي إيجاد المسارات في الخرائط والألعاب، وتخطيط الحركة في الروبوتات، ومحركات البحث داخل المخططين الآليين وحلالي الألغاز؛ يحدد الفن العملي لتصميم الاستدلالات بشكل مباشر ما إذا كانت المشكلات الكبيرة قابلة للحل في وقت مقبول.

History

تم تقديم خوارزمية A* بواسطة هارت ونيلسون ورافائيل (1968)، مما أعطى البحث الاستدلالي أساسًا رسميًا للأمثلية. قدمت دراسة بيرل عام 1984 بعنوان 'الاستدلالات' المعالجة النظرية النهائية، وتناولت IDA* لكورف عام 1985 تكلفة ذاكرة A*. لا تزال هذه النتائج مادة أساسية في تعليم الذكاء الاصطناعي.

Key figures

• Peter E. Hart
• Nils J. Nilsson
• Bertram Raphael
• Judea Pearl
• Richard E. Korf

Seminal works

• hart1968
• pearl1984
• korf1985

Frequently asked questions

ما هو الاستدلال المقبول؟

الاستدلال مقبول إذا لم يبالغ أبدًا في تقدير التكلفة الحقيقية للوصول إلى الهدف من أي حالة. المقبولية هي الشرط الذي بموجبه تضمن A* إيجاد حل أمثل (أقل تكلفة).

ما الفرق بين البحث الأفضل أولاً الجشع و A*؟

البحث الأفضل أولاً الجشع يوسع الحالة التي تبدو الأقرب إلى الهدف وفقًا للاستدلال وحده (h)، وهو سريع ولكنه قد يكون بعيدًا عن الأمثلية. تضيف A* التكلفة الفعلية المتكبدة حتى الآن (g)، وتتوسع بواسطة f = g + h، مما يحافظ على الأمثلية عندما يكون الاستدلال مقبولاً.