جستجوی فضای حالت

جستجوی فضای حالت (به انگلیسی: State space search) فرآیندی است که در زمینه علوم کامپیوتر از جمله هوش مصنوعی (AI) استفاده می‌شود که در آن پیکربندی‌ها یا حالت‌های متوالی یک نمونه با هدف یافتن یک حالت هدف با ویژگی مطلوب درنظرگرفته می‌شود.

مسائل اغلب به عنوان فضای حالت، مجموعه ای از حالت‌هایی که یک مشکل می‌تواند در آنها باشد، مدل می‌شود. اگر عملیاتی برای تبدیل حالت اول به حالت دوم انجام شود، مجموعه‌ای از حالت‌ها نموداری را تشکیل می‌دهد که در آن دو حالت به‌هم متصل می‌شوند.

جستجوی فضای حالت اغلب با روش‌های جستجوی سنتی علوم رایانه متفاوت است زیرا فضای حالت غیرصریح است: نمودار فضای حالت معمولی برای ایجاد و ذخیره در حافظه بسیار بزرگتر از آن است. در عوض، گره‌ها در حین کاوش تولید می‌شوند و معمولاً پس از آن دور ریخته می‌شوند. یک راه حل برای یک نمونه جستجوی ترکیبیاتی ممکن است شامل خود حالت هدف یا مسیری از حالت اولیه به حالت هدف باشد.

نمونه‌هایی از الگوریتم‌های جستجوی فضای حالت

جستجوی ناآگاهانه

به گفته پول و مک‌ورث، موارد زیر روش‌های جستجوی فضای-حالت ناآگاهانه هستند، به این معنی که آنها هیچ اطلاعات قبلی در مورد مکان هدف ندارند.

• جستجوی عمق-اول سنتی
• جستجوی سطح-اول
• ژرفایش تکراری
• جستجو کمترین-هزینه-اول / جستجوی یکنواخت-هزینه (UCS)

این روش‌ها مکان هدف را به شکل یک تابع اکتشافی می‌گیرند. پول و مک ورث مثال‌های زیر را به عنوان الگوریتم‌های جستجوی آگاهانه ذکر می‌کنند:

• جستجوی عمق-اول آگاهانه/ابتکاری
• جستجوی ابتدا-بهترین پُرآز
• جستجو اِی ستاره

جستارهای وابسته

• فضای حالت
• طرح‌ریزی فضای حالت
• شاخه و کران - روشی برای کارآمدتر کردن جستجوی فضای حالت با هرس زیرمجموعه‌های آن.

منابع

• Stuart J. Russell and Peter Norvig (1995). Artificial Intelligence: A Modern Approach. Prentice Hall.