البحث وحل المشكلات
البحث وحل المشكلات هو فرع من فروع الذكاء الاصطناعي يهتم بصياغة المهام كاستكشاف لمساحة من الحالات أو التكوينات، وإيجاد تسلسلات من الإجراءات أو التعيينات أو التحركات التي تصل إلى الهدف.
Definition
يمثل حل المشكلات القائم على البحث مهمة كحالة أولية، ومجموعة من الإجراءات التي تحول الحالات، واختبار للهدف، وتكلفة للمسار، ويحلها عن طريق الاستكشاف المنهجي للحالات القابلة للوصول حتى يتم العثور على حالة هدف (أو مسار بأقل تكلفة إليها).
Scope
يغطي هذا المجال صياغة المشكلات كمساحات للحالات والخوارزميات التي تستكشفها: البحث غير الموجه (الأعمى) مثل البحث بالعمق أولاً والبحث بالعرض أولاً، والبحث الموجه (الاستدلالي) مثل A* والبحث الجشع الأفضل أولاً، والبحث التنافسي للألعاب ثنائية اللاعبين، وإرضاء القيود. ويتناول كيفية نمذجة المشكلات كحالات وإجراءات واختبارات للهدف، وكيفية تحليل الاكتمال والأمثلية والوقت والمساحة. ويستبعد تعلم استدلالات البحث أو وظائف التقييم من البيانات، وهو ما ينتمي إلى المجال الفرعي المنفصل للتعلم الآلي.
Sub-topics
Core questions
- كيف تُصاغ مهمة من العالم الحقيقي كمساحة حالات ذات حالات وإجراءات واختبار للهدف؟
- متى تكون خوارزمية البحث كاملة (مضمونة لإيجاد حل إذا كان موجودًا) ومثلى (مضمونة لإيجاد حل بأقل تكلفة)؟
- كيف توجه الدالة الاستدلالية البحث نحو الهدف مع الحفاظ على الأمثلية؟
- كيف يمكن التحكم في الانفجار التوافقي لمساحة الحالات عن طريق التقليم أو الترتيب الموجه؟
- كيف يتغير البحث عندما يختار خصم بعض التحركات؟
Key concepts
- مساحة الحالات
- شجرة البحث ورسم بياني البحث
- البحث غير الموجه (الأعمى)
- الدالة الاستدلالية
- المقبولية والاتساق
- بحث A*
- عامل التفرع وعمق البحث
- الاكتمال والأمثلية
- إرضاء القيود
Key theories
- الاستدلالات المقبولة وأمثلية A*
- إذا لم تبالغ الدالة الاستدلالية أبدًا في تقدير التكلفة الحقيقية للوصول إلى الهدف (كانت مقبولة)، فإن بحث A* يوسع العقد بترتيب الأفضل أولاً لـ f = g + h ويضمن إرجاع حل أمثل؛ ويضمن الاتساق أيضًا عدم إعادة توسيع أي عقدة.
- المفاضلة بين البحث غير الموجه والبحث الموجه
- تختلف الاستراتيجيات العمياء (البحث بالعرض أولاً، التكلفة الموحدة، البحث بالعمق أولاً، التعميق التكراري) فقط في ترتيب العقد وتقدم ضمانات دون معرفة المجال، بينما يمكن لتقديرات الاستدلال للتكلفة المتبقية أن تقلل بشكل كبير من المساحة المستكشفة مع خطر فقدان الأمثلية إذا كانت الدالة الاستدلالية غير مقبولة.
- صياغة المشكلة كبحث في مساحة الحالات
- تصبح مجموعة واسعة من المهام قابلة للمعالجة بمجرد صياغتها كبحث عبر حالات متصلة بالإجراءات، مما يجعل اختيار تمثيل الحالة والعوامل قرار تصميم مركزي يحدد عامل التفرع وعمق الحل.
Clinical relevance
يشكل البحث أساسًا لمجموعة واسعة من الأنظمة العملية: تخطيط المسارات والملاحة (A* على شبكات الطرق)، ومحركات الألغاز والألعاب، والتكوين والجدولة الآلية، وتخطيط حركة الروبوتات، وكعمود فقري للتخطيط الآلي وحلول القيود المستخدمة في اللوجستيات وبحوث العمليات.
History
كان البحث محوريًا في الذكاء الاصطناعي منذ أيامه الأولى، حيث صاغ Newell وSimon في نظام حل المشكلات العام (أواخر الخمسينيات) الذكاء كبحث عبر مساحات المشكلات. وقد أعطت خوارزمية A* (Hart, Nilsson, Raphael, 1968) للبحث الاستدلالي أساسًا صارمًا للأمثلية، وقام Pearl في دراسته عام 1984 بتبسيط نظرية البحث الاستدلالي. ولا يزال الإطار يمثل عدسة تنظيمية قياسية في كتب الذكاء الاصطناعي.
Key figures
- Nils J. Nilsson
- Judea Pearl
- Peter E. Hart
- Bertram Raphael
- Allen Newell
- Herbert A. Simon
Related topics
Seminal works
- hart1968
- pearl1984
- russell2020
Frequently asked questions
- ما الفرق بين البحث غير الموجه والبحث الموجه؟
- البحث غير الموجه (الأعمى)، مثل البحث بالعرض أولاً أو البحث بالعمق أولاً، لا يستخدم أي معلومات حول مدى قرب الحالة من الهدف ويستكشف بناءً على بنية مساحة الحالات فقط. أما البحث الموجه (الاستدلالي) فيستخدم تقديرًا للتكلفة المتبقية للوصول إلى الهدف لتحديد أولويات الحالات التي يجب توسيعها، مما قد يكون أكثر كفاءة بكثير.
- لماذا تُستخدم خوارزمية A* على نطاق واسع؟
- تجمع A* بين التكلفة الفعلية من البداية (g) وتقدير استدلالي للوصول إلى الهدف (h)، وعندما تكون الدالة الاستدلالية مقبولة، فإنها تضمن إيجاد حل أمثل بينما تستكشف عادةً عددًا أقل بكثير من الحالات مقارنة بالبحث غير الموجه. هذا التوازن بين الأمثلية والكفاءة يجعلها خيارًا افتراضيًا لتحديد المسارات.