البحث في فضاء الحالات

البحث في فضاء الحالات هو الاستكشاف المنهجي لمجموعة الحالات التي يمكن الوصول إليها من حالة أولية عبر الإجراءات المتاحة، بهدف العثور على حالة تحقق اختبار الهدف أو مسار يؤدي إليها.

Definition

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

Scope

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

Core questions

• كيف يتم تمثيل المشكلة كحالات، وإجراءات، ونموذج انتقال، واختبار هدف؟
• كيف يختلف البحث أولاً بالاتساع، والبحث أولاً بالعمق، والبحث بالتكلفة المنتظمة، والبحث بالتعميق التكراري في ترتيب حدودها؟
• ما هي ضمانات الاكتمال، والأمثلية، والوقت، والمساحة لكل استراتيجية غير مُعلَمَة؟
• كيف يتجنب بحث الرسم البياني إعادة الاستكشاف المهدرة للحالات التي يسمح بها بحث الشجرة؟

Key concepts

• الحالة الأولية واختبار الهدف
• نموذج الانتقال والخلفاء
• الحدود (القائمة المفتوحة) والمجموعة المستكشفة
• البحث أولاً بالاتساع
• البحث أولاً بالعمق
• البحث بالتكلفة المنتظمة
• التعميق التكراري
• بحث الشجرة مقابل بحث الرسم البياني

Key theories

ترتيب الحدود يحدد الاستراتيجية

تتميز خوارزميات البحث غير المُعلَمَة فقط بالترتيب الذي تزيل به الحالات من الحدود: قائمة انتظار FIFO تعطي البحث أولاً بالاتساع، ومكدس LIFO يعطي البحث أولاً بالعمق، وقائمة انتظار ذات أولوية بناءً على تكلفة المسار تعطي البحث بالتكلفة المنتظمة.

التعميق التكراري كحل أمثل فعال من حيث المساحة

يقوم البحث بالتعميق التكراري أولاً بالعمق بتشغيل بحث أولاً بالعمق محدود العمق بشكل متكرر مع زيادة الحدود، مما يجمع بين المساحة الخطية للبحث أولاً بالعمق مع اكتمال وأمثلية (على التكاليف الوحدوية) البحث أولاً بالاتساع.

Clinical relevance

يُعد البحث غير المُعلَم في فضاء الحالات الأساس المفاهيمي والتنفيذي لتحديد المسار، وحل الألغاز، وتحليل إمكانية الوصول في التحقق من النماذج، وكالركيزة التي يُبنى عليها البحث الاستدلالي والتنافسي؛ ويساعد فهم تعقيده في تحديد متى يكون البحث الأعمى ممكنًا ومتى تكون الاستدلالات ضرورية.

History

ينحدر البحث المنهجي في فضاء الحالات من خوارزميات اجتياز الرسوم البيانية في الخمسينيات، بما في ذلك عمل مور وديجكسترا حول أقصر مسار، وتم تأطيره كنموذج لحل المشكلات في الذكاء الاصطناعي المبكر. وقد أثبت تحليل كورف عام 1985 للتعميق التكراري أمثليته بين عمليات البحث الشجري المقبولة ذات المساحة الخطية.

Key figures

• Nils J. Nilsson
• Richard E. Korf
• Edward F. Moore
• Edsger W. Dijkstra

Seminal works

• nilsson1971
• russell2020

Frequently asked questions

متى يكون البحث أولاً بالاتساع أمثل؟

يكون البحث أولاً بالاتساع أمثل عندما تكون لكل خطوة نفس التكلفة، لأنه يجد الهدف الأقل عمقًا أولاً. عندما تختلف تكاليف الخطوات، فإن البحث بالتكلفة المنتظمة (الذي يرتب الحدود حسب تكلفة المسار المتراكمة) هو الاستراتيجية غير المُعلَمَة التي تضمن حلاً بأقل تكلفة.

لماذا نستخدم التعميق التكراري بدلاً من البحث أولاً بالاتساع العادي؟

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