فضاء الحالة (علوم الحاسوب)

الموسوعة الحرة
عالم الفراغ، مشكلة أقصر مسار مع فضاء حالة محدود

في علم الحاسوب ، تُعرَّف فضاءات الحالة بأنها فضاءات منفصلة تمثل مجموعة جميع التكوينات الممكنة لنظام ما. [ 1 ] وهي تجريد مفيد للاستدلال حول سلوك نظام معين، وتُستخدم على نطاق واسع في مجالات الذكاء الاصطناعي ونظرية الألعاب .

على سبيل المثال، تتميز مسألة لعبة " عالم المكنسة الكهربائية" بمساحة حالة منفصلة ومحدودة، حيث توجد مجموعة محدودة من التكوينات التي يمكن أن تتخذها المكنسة الكهربائية والأوساخ. أما نظام "العداد"، حيث تمثل الحالات الأعداد الطبيعية بدءًا من 1 وتزداد بمرور الوقت [ 2 ]، فيمتلك مساحة حالة منفصلة غير محدودة. في حين أن الوضع الزاوي للبندول غير المخمد [ 3 ] هو مساحة حالة متصلة (وبالتالي غير محدودة).

تعريف

تُعدّ فضاءات الحالة مفيدة في علوم الحاسوب كنموذج بسيط للآلات. ويمكن تعريف فضاء الحالة رسميًا على أنه مجموعة مرتبة [ N , A , S , G ] حيث:   

  • N هي مجموعة من الحالات
  • A عبارة عن مجموعة من الأقواس التي تربط الولايات
  • S هي مجموعة جزئية غير فارغة من N تحتوي على حالات البداية
  • G هي مجموعة جزئية غير فارغة من N تحتوي على حالات الهدف.

ملكيات

أبجدهـوزح
8
ملكة بيضاء f8
الملكة البيضاء د7
الملكة البيضاء جي 6
كوين أبيض A5
الملكة البيضاء h4
الملكة البيضاء b3
ملكة بيضاء من الفئة E2
الملكة البيضاء من الفئة الأولى
8
77
66
55
44
33
22
11
أبجدهـوزح
حالة صالحة في فضاء حالات لغز الملكات الثماني

تتمتع مساحة الحالة ببعض الخصائص المشتركة:

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

يمكن أن تكون فضاءات الحالة إما لانهائية أو محدودة، ومنفصلة أو متصلة.

مقاس

حجم فضاء الحالة لنظام معين هو عدد التكوينات الممكنة لهذا الفضاء. [ 3 ]

محدود

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

(648)=4،426،165،368{\displaystyle {\binom {64}{8}}=4,426,165,368}

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

لا نهائي

يمكن وصف جميع فضاءات الحالة المتصلة بدالة متصلة مقابلة ، وبالتالي فهي لانهائية. [ 3 ] يمكن أن يكون لفضاءات الحالة المنفصلة أيضًا حجم لانهائي ( قابل للعد )، مثل فضاء حالة نظام "العداد" المعتمد على الزمن، [ 2 ] على غرار النظام في نظرية الطوابير الذي يحدد عدد العملاء في طابور، والذي سيكون له فضاء حالة {0، 1، 2، 3، ...}.

استكشاف

استكشاف فضاء الحالة هو عملية حصر الحالات الممكنة بحثًا عن حالة الهدف. على سبيل المثال، يحتوي فضاء حالة لعبة باك مان على حالة هدف عندما يتم تناول جميع حبيبات الطعام، ويتم استكشافه بتحريك باك مان على اللوحة. [ 5 ]

ابحث عن الولايات

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

طُرق

تُعدّ خوارزميات البحث القياسية فعّالة في استكشاف فضاءات الحالة المنفصلة. وتُظهر الخوارزميات التالية كلاً من الاكتمال والأمثلية في البحث في فضاء الحالة: [ 5 ] [ 6 ]

لا تمتد هذه الأساليب بشكل طبيعي لاستكشاف فضاءات الحالة المتصلة. إن استكشاف فضاء حالة متصل بحثًا عن حالة هدف معينة يُعادل تحسين دالة متصلة عشوائية ، وهو أمر غير ممكن دائمًا؛ انظر التحسين الرياضي .

انظر أيضاً

مراجع

  1. ↑ نيكامب، دوان. "تعريف فضاء الحالة" . رؤى رياضية . تم الاسترجاع في 17 نوفمبر 2019 .
  2. 1 2 بابيرنيك، نورمان. "الحالات اللانهائية وانتقالات الحالة اللانهائية" . جامعة كارنيجي ميلون . تم الاطلاع عليه بتاريخ 12 نوفمبر 2019 .
  3. 1 2 3 نيكامب، دوان. "فكرة النظام الديناميكي" . رؤى رياضية . تم الاسترجاع في 12 نوفمبر 2019 .
  4. ↑ تشانغ، ويكسونغ (1999). البحث في فضاء الحالة: الخوارزميات، والتعقيد، والتوسعات، والتطبيقات . سبرينغر. ISBN 978-0-387-98832-0.
  5. 1 2 3 أبيل، بيتر. "المحاضرة 2: البحث غير المُوجَّه" . جامعة كاليفورنيا، بيركلي، CS188 مقدمة في الذكاء الاصطناعي . تم الاطلاع عليه بتاريخ 30 أكتوبر 2019 .
  6. ↑ أبيل، بيتر. "المحاضرة 3: البحث المُستنير" . جامعة كاليفورنيا، بيركلي، CS188 مقدمة في الذكاء الاصطناعي . تم الاطلاع عليه بتاريخ 12 نوفمبر 2019 .