جستجوی اکتشافی و A*

جستجوی اکتشافی از تخمین خاص مسئله‌ای از هزینه باقیمانده تا رسیدن به هدف استفاده می‌کند تا راهنمایی کند که کدام حالت‌ها را ابتدا کاوش کند؛ A* الگوریتم کانونی آن است که حالت‌ها را به ترتیب مجموع هزینه تاکنون و هزینه تخمینی باقیمانده گسترش می‌دهد.

Definition

جستجوی اکتشافی، جستجوی آگاهانه‌ای است که مرز را با استفاده از یک تابع ارزیابی که هزینه شناخته شده از ابتدا را با تخمین اکتشافی هزینه باقیمانده ترکیب می‌کند، مرتب می‌کند؛ A* از f(n) = g(n) + h(n) استفاده می‌کند و زمانی که h پذیرفتنی باشد، بهینه است.

Scope

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

Core questions

• چه چیزی یک اکتشافی را پذیرفتنی می‌کند و چرا پذیرفتنی بودن، بهینگی A* را تضمین می‌کند؟
• چگونه سازگاری (یکنواختی) تضمین‌ها را تقویت می‌کند و از گسترش مجدد گره جلوگیری می‌کند؟
• چگونه اکتشافی‌های خوب طراحی می‌شوند، برای مثال از نسخه‌های ساده‌شده مسئله؟
• چگونه انواع محدود به حافظه مانند IDA* بهینگی را با فضای محدود حفظ می‌کنند؟

Key concepts

• تابع ارزیابی f = g + h
• اکتشافی پذیرفتنی
• اکتشافی سازگار (یکنواخت)
• جستجوی بهترین-اول حریصانه
• جستجوی A*
• A* با تعمیق تکراری (IDA*)
• غلبه اکتشافی
• مسئله ساده‌شده و پایگاه‌های داده الگو

Key theories

بهینگی A* تحت اکتشافی‌های پذیرفتنی

هنگامی که اکتشافی h هرگز هزینه واقعی باقیمانده را بیش از حد تخمین نمی‌زند، A* گره‌ها را با افزایش f = g + h گسترش می‌دهد و تضمین می‌شود که یک مسیر با کمترین هزینه را بازگرداند؛ در میان الگوریتم‌هایی که از اطلاعات اکتشافی یکسان استفاده می‌کنند، A* به طور بهینه کارآمد است.

طراحی اکتشافی از طریق ساده‌سازی

اکتشافی‌های پذیرفتنی را می‌توان به طور سیستماتیک با حل یک نسخه ساده‌شده از مسئله (نسخه‌ای با محدودیت‌های کمتر بر روی اقدامات) استخراج کرد، زیرا هزینه دقیق یک مسئله آسان‌تر، یک کران پایین برای مسئله اصلی است؛ اکتشافی‌های غالب (آگاهانه‌تر) گره‌های کمتری را گسترش می‌دهند.

جستجوی اکتشافی محدود به حافظه

A* با تعمیق تکراری، جستجوهای عمق-اول متوالی را انجام می‌دهد که توسط یک آستانه هزینه f افزایشی محدود می‌شوند و بهینگی مشابه A* را با حافظه خطی در عمق راه‌حل به دست می‌آورد.

Clinical relevance

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

History

الگوریتم A* توسط هارت، نیلسون و رافائل (1968) معرفی شد و مبنای رسمی بهینگی را برای جستجوی اکتشافی فراهم کرد. تک‌نگاری پرل در سال 1984 با عنوان «اکتشافی‌ها» (Heuristics) درمان نظری قطعی را ارائه داد، و IDA* کورف در سال 1985 به هزینه حافظه A* پرداخت. این نتایج همچنان مطالب اصلی در آموزش هوش مصنوعی هستند.

Key figures

• Peter E. Hart
• Nils J. Nilsson
• Bertram Raphael
• Judea Pearl
• Richard E. Korf

Seminal works

• hart1968
• pearl1984
• korf1985

Frequently asked questions

اکتشافی پذیرفتنی چیست؟

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

تفاوت بین جستجوی بهترین-اول حریصانه و A* چیست؟

جستجوی بهترین-اول حریصانه حالتی را گسترش می‌دهد که به نظر می‌رسد تنها بر اساس اکتشافی (h) به هدف نزدیک‌تر است، که سریع است اما می‌تواند از بهینه بودن فاصله زیادی داشته باشد. A* هزینه واقعی متحمل شده تاکنون (g) را اضافه می‌کند و با f = g + h گسترش می‌یابد، که بهینگی را زمانی که اکتشافی پذیرفتنی باشد، حفظ می‌کند.