تخطيط الفضاء الحكومي

📅 آخر تحديث: ٣٠ يوليو ٢٠٢٦
✍️ نُشر في: ٣٠ يوليو ٢٠٢٦
الموسوعة الحرة

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

تعريف

أبسط خوارزميات التخطيط الكلاسيكية هي خوارزميات البحث في فضاء الحالة. وهي خوارزميات بحث يكون فيها فضاء البحث مجموعة فرعية من فضاء الحالة: كل عقدة تُمثل حالة من حالات العالم، وكل قوس يُمثل انتقال حالة، والخطة الحالية تُمثل المسار الحالي في فضاء البحث. يُعد البحث الأمامي والبحث الخلفي مثالين رئيسيين على تخطيط فضاء الحالة.

في الخوارزميات التالية، نعني بـ"غير الحتمية" أن خوارزمية البحث المختارة في الرسم البياني لاختيار الفرع التالي اختيارية. يمكن استخدام البحث الشامل (مثل BFS و DFS و IDS وغيرها)، أو استخدام الطرق الاستدلالية (مثل A* و IDA* وغيرها). يعتمد هذا الاختيار عمومًا على طبيعة المشكلة.

البحث الأمامي هو خوارزمية تبحث للأمام من الحالة الأولية للعالم لمحاولة إيجاد حالة تحقق صيغة الهدف.

نقول إن إجراءً ما ينطبق في حالة ما إذا كانت الشروط المسبقة لهذا الإجراء صحيحة في تلك الحالة .

حيث O هي مجموعة الإجراءات، و s هي الحالة الأولية، و g هي حالة الهدف:

Forward-search(O, s 0 , g) s = s 0 P = الخطة الفارغة حلقة إذا كانت s تحقق g، فأرجع P قابل للتطبيق = {أ | أ هي حالة أساسية لمؤثر في O، و أ قابلة للتطبيق في s} إذا كان ذلك ممكناً = ∅، فأرجع فشلاً اختر إجراءً (أ) من بين الإجراءات المتاحة بطريقة غير حتمية s = γ(s, a) P = Pa

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

نقول إن إجراءً ما ذو صلة إذا كانت تأثيراته الإضافية (القيم الحرفية للحالة التي أصبحت صحيحة) موجودة في G ، ولم تكن أي من تأثيراته الحذفية (القيم الحرفية للحالة التي أصبحت خاطئة) موجودة في G.

حيث O هي مجموعة الإجراءات، و s هي الحالة الأولية، و g هي حالة الهدف:

البحث العكسي (O، s 0 ، g) s = s 0 P = الخطة الفارغة حلقة إذا كانت s تحقق g، فأرجع P ذات صلة = {أ | أ هي حالة أساسية لمؤثر في O ذات صلة بـ g} إذا كانت القيمة ذات صلة = ∅، فأرجع فشلاً. اختر إجراءً (أ) بشكل غير حتمي من بين الإجراءات ذات الصلة P = aP s = γ −1 (s, a)

انظر أيضاً

مراجع