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

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

Definition

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

Scope

این موضوع شامل فرمول‌بندی یک مسئله به عنوان فضای حالت (حالت‌ها، اقدامات، مدل انتقال، آزمون هدف، هزینه مسیر) و استراتژی‌های جستجوی ناآگاهانه است که آن را بدون راهنمایی خاص دامنه کاوش می‌کنند: جستجوی اول سطح، جستجوی با هزینه یکنواخت، جستجوی اول عمق، جستجوی با عمق محدود، و جستجوی عمق تکراری. این شامل تحلیل این استراتژی‌ها بر اساس کامل بودن، بهینگی، پیچیدگی زمانی، و پیچیدگی فضایی، و تمایز بین جستجوی درختی و جستجوی گرافی با تشخیص حالت‌های تکراری است. راهنمایی اکتشافی در موضوع جداگانه جستجوی اکتشافی و A* مورد بررسی قرار می‌گیرد.

Core questions

• چگونه یک مسئله به عنوان حالت‌ها، اقدامات، مدل انتقال، و آزمون هدف نمایش داده می‌شود؟
• جستجوی اول سطح، اول عمق، با هزینه یکنواخت، و عمق تکراری چگونه در ترتیب‌بندی مرز خود تفاوت دارند؟
• تضمین‌های کامل بودن، بهینگی، زمان، و فضا برای هر استراتژی ناآگاهانه چیست؟
• جستجوی گرافی چگونه از بازکاوی بی‌فایده حالت‌ها که جستجوی درختی اجازه می‌دهد، جلوگیری می‌کند؟

Key concepts

• حالت اولیه و آزمون هدف
• مدل انتقال و جانشین‌ها
• مرز (لیست باز) و مجموعه کاوش‌شده
• جستجوی اول سطح
• جستجوی اول عمق
• جستجوی با هزینه یکنواخت
• عمق تکراری
• جستجوی درختی در مقابل جستجوی گرافی

Key theories

ترتیب‌بندی مرز، استراتژی را تعیین می‌کند

الگوریتم‌های جستجوی ناآگاهانه تنها با ترتیبی که حالت‌ها را از مرز حذف می‌کنند، متمایز می‌شوند: یک صف FIFO جستجوی اول سطح را می‌دهد، یک پشته LIFO جستجوی اول عمق را می‌دهد، و یک صف اولویت‌دار بر اساس هزینه مسیر، جستجوی با هزینه یکنواخت را می‌دهد.

عمق تکراری به عنوان یک بهینه با کارایی فضایی

جستجوی عمق تکراری اول عمق، به طور مکرر جستجوی اول عمق با عمق محدود را با محدودیت‌های افزایشی اجرا می‌کند، و فضای خطی جستجوی اول عمق را با کامل بودن و بهینگی (در هزینه‌های واحد) جستجوی اول سطح ترکیب می‌کند.

Clinical relevance

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

History

جستجوی سیستماتیک فضای حالت از الگوریتم‌های پیمایش گراف دهه ۱۹۵۰، از جمله کارهای مور و دایکسترا در مورد کوتاه‌ترین مسیر، نشأت می‌گیرد و در هوش مصنوعی اولیه به عنوان مدلی برای حل مسئله چارچوب‌بندی شد. تحلیل کورف در سال ۱۹۸۵ در مورد عمق تکراری، بهینگی آن را در میان جستجوهای درختی مجاز با فضای خطی اثبات کرد.

Key figures

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

Seminal works

• nilsson1971
• russell2020

Frequently asked questions

چه زمانی جستجوی اول سطح بهینه است؟

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

چرا به جای جستجوی اول سطح ساده از عمق تکراری استفاده می‌شود؟

جستجوی اول سطح کل مرز را ذخیره می‌کند و ممکن است به حافظه‌ای نمایی در عمق نیاز داشته باشد. عمق تکراری به طور مکرر جستجوی اول عمق را با محدودیت‌های عمق رو به رشد انجام می‌دهد، و تنها از حافظه خطی استفاده می‌کند در حالی که همچنان کامل و بهینه در مسائل با هزینه واحد است، البته با هزینه بازکاوی گره‌های کم‌عمق.